Departamento de Ciência da
Computação - IME - USP
Um caixa de banco tem somente notas de a
e b
reais para fornecer
aos seus clientes. Quando um cliente chega com um cheque no valor de
c
reais, o caixa precisa fazer umas contas para decidir se é
possível descontar o cheque ou não.
Escreva um programa que resolva o problema do caixa de
banco: o programa lê do teclado 3 inteiros positivos
a, b
e c
e imprime
TODAS as combinações possíveis de notas de
a
reais e
notas de b
reais, totalizando c
reais, ou uma
mensagem informando que não é possível descontar o cheque.
Exemplos:
a = 5
, b = 3
e c = 11
seu programa deve imprimir:
1 notas de 5 e 2 notas de 3
a = 3
, b = 5
e c = 30
seu programa deve imprimir:
10 notas de 3 e 0 notas de 5 5 notas de 3 e 3 notas de 5 0 notas de 3 e 6 notas de 5
a = 5
, b = 3
e c = 7
seu programa deve imprimir:
Não é possível descontar o cheque
a = 4
, b = 6
e c = 121
seu programa deve imprimir:
Não é possível descontar o cheque
a = 4
, b = 7
e c = 127
seu programa deve imprimir:
2 notas de 4 e 17 notas de 7 9 notas de 4 e 13 notas de 7 16 notas de 4 e 9 notas de 7 23 notas de 4 e 5 notas de 7 30 notas de 4 e 1 notas de 7
a = 6
, b = 15
e c = 199
seu programa deve imprimir:
Não é possível descontar o cheque
#-------------------------------------------------------------------- # SOLUÇÃO 1: # #-------------------------------------------------------------------- def main(): ''' Programa que lê valores de notas a e b e o valor c de um cheque e imprime todas as maneiras possíveis de se descontar o cheque com notas de a e b. Se não for possível descontar o cheque o programa imprime "Nao é possivel descontar o cheque". ''' a = int(input("Digite o valor de a: ")) b = int(input("Digite o valor de b: ")) c = int(input("Digite o valor do cheque: ")) # indica se é possível descontar o cheque possível = False # número máximo de notas de a max_a = c // a # número máximo de notas de b max_b = c // b # para cada número possível n_a de notas de a for n_a in range(max_a+1): # para cada número possível n_b de notas de b for n_b in range(max_b+1): # verifique se é possível descontar o cheque de valor c # com n_a notas de a e n_b notas de b if n_a*a + n_b*b == c: print("%d notas de %d e %d notas de %d" %(n_a,a,n_b,b)) # print(n_a, "notas de", a, "e", n_b, "notas de", b) possível = True if not possível: # equivalente a possível == False print("Nao é possivel descontar o cheque") main() #-------------------------------------------------------------------- # SOLUÇÃO 2: # #-------------------------------------------------------------------- def main(): ''' Programa que lê valores de notas a e b e o valor c de um cheque e imprime todas as maneiras possíveis de se descontar o cheque com notas de a e b. Se não for possível descontar o cheque o programa imprime "Nao é possivel descontar o cheque". ''' a = int(input("Digite o valor de a: ")) b = int(input("Digite o valor de b: ")) c = int(input("Digite o valor do cheque: ")) # indica se é possível descontar o cheque possível = False # número máximo de notas de a max_a = c // a # número máximo de notas de b max_b = c // b # para cada número possível n_a de notas de a n_a = 0 while n_a <= max_a: # para cada número possível n_b de notas de b n_b = 0 while n_b <= max_b: # verifique se é possível descontar o cheque de valor c # com n_a notas de a e n_b notas de b if n_a*a + n_b*b == c: print("%d notas de %d e %d notas de %d" %(n_a,a,n_b,b)) # print(n_a, "notas de", a, "e", n_b, "notas de", b) possível = True n_b += 1 n_a += 1 if not possível: # equivalente a possível == False print("Nao é possivel descontar o cheque") main() #-------------------------------------------------------------------- # SOLUÇÃO 3: # #-------------------------------------------------------------------- def main(): ''' Programa que lê valores de notas a e b e o valor c de um cheque e imprime todas as maneiras possíveis de se descontar o cheque com notas de a e b. Se não for possível descontar o cheque o programa imprime "Nao é possivel descontar o cheque". ''' a = int(input("Digite o valor de a: ")) b = int(input("Digite o valor de b: ")) c = int(input("Digite o valor do cheque: ")) # indica se é possível descontar o cheque possível = False # para cada número possível n_a de notas de a n_a = 0 while c >= 0: # é possível descontar c nom n_a notas de a? if c % b == 0: n_b = c // b print("%d notas de %d e %d notas de %d" %(n_a,a,n_b,b)) # print(n_a, "notas de", a, "e", n_b, "notas de", b) possível = True c -= a n_a += 1 if not possível: # equivalente a possível == False print("Nao é possivel descontar o cheque") main()
Escreva um programa que leia do teclado um número inteiro n > 0
e uma sequência
de n
números reais e
imprima uma tabela mostrando os números que compõem a sequência e o número de
vezes que cada um deles ocorre na mesma.
Exemplo para a entrada:
8 -1.7 3.0 0.0 1.5 0.0 -1.7 2.3 -1.7a saída deve ser:
-1.7 ocorre 3 vezes 3.0 ocorre 1 vezes 0.0 ocorre 2 vezes 1.5 ocorre 1 vezes 2.3 ocorre 1 vezes
#-------------------------------------------------------------------- # SOLUÇÃO 1: Versão com função auxiliar # #-------------------------------------------------------------------- def main(): ''' Dados n e uma sequência com n números reais, conta e imprime o número de vezes que cada número ocorre na sequência. ''' n = int(input("Digite o tamanho da sequencia: ")) # armazena os números que ocorrem na sequência lista = [] # contador do número de vezes que cada número ocorre na sequência # n_ocorrências[i] == número de vezes que lista[i] ocorre na sequência n_ocorrências = [] for i in range(n): x = float(input("Digite um número: ")) j = insere_novo(x,lista) # é a primeira vez que x ocorre na sequência? if j > len(n_ocorrências)-1: # sim, é a primeira vez n_ocorrências.append(1) else: # não, x já havia ocorrido e x == lista[j] n_ocorrências[j] += 1 print(" Número no. ocorrências") for i in range(len(lista)): print("%10.2f %6d" %(lista[i],n_ocorrências[i])) # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . def insere_novo(x, lista): '''(float, list) -> int Recebe um float 'x' e uma lista 'lista' e retorna o índice da posição em que x ocorre na lista. Caso x não ocorra na lista ele é inserido no final e o índice dessa posição é retornado. ''' # número de elementos na lista n = len(lista) # procure x na lista for i in range(n): if x == lista[i]: return i # insira x na lista lista.append(x) return n main() #-------------------------------------------------------------------- # SOLUÇÃO 2: Versão sem função # #-------------------------------------------------------------------- def main(): ''' Dados n e uma sequência com n números reais, conta e imprime o número de vezes que cada número ocorre na sequência. ''' n = int(input("Digite o tamanho da sequencia: ")) # armazena os números que ocorrem na sequência lista = [] # contador do número de vezes que cada número ocorre na sequência # n_ocorrências[i] == número de vezes que lista[i] ocorre na sequência n_ocorrências = [] for i in range(n): # leia o próximo número da sequência x = float(input("Digite um número: ")) # verifique que x já está na lista achou = False j = 0 m = len(lista) while j < m and not achou: # "not achou" é equivalente a "achou == False" if x == lista[j]: achou = True else: j += 1 if achou: # se achou == True então que x == lista[j] # incremente o número de ocorrências n_ocorrências[j] += 1 else: # é a primeira ocorrência de x na sequência # insira x na lista lista.append(x) # inicialize o contador de ocorrências do novo elemento n_ocorrências.append(1) print(" Número no. ocorrências") for i in range(len(lista)): print("%10.2f %6d" %(lista[i],n_ocorrências[i])) main() #-------------------------------------------------------------------- # SOLUÇÃO 3: Versão que lê a sequência inteira e só depois # calcula o número de ocorrências # #-------------------------------------------------------------------- def main(): ''' Dados n e uma sequência com n números reais, conta e imprime o número de vezes que cada número ocorre na sequência. ''' n = int(input("Digite o tamanho da sequencia: ")) # 1 leia todos os números da sequência sequência = [] # armazenará, iniciamente, toda a sequência de floats for i in range(n): sequência[i] = float(input("Digite o %do. número da sequência" %(i+1)) # 2 conte e imprima o número de ocorrência de cada número na sequência print(" Número no. ocorrências") i = 0 while i < n: n_ocorrências = 1 x = sequência[i] # percorra a sequência a partir da posição de índice i+1 # contando e removendo as ocorrências de x j = i+1 while j < n: if x == sequência[j]: n_ocorrências += 1 # "remova" o elemento sequência[j] sequência[j] = sequência[n-1] # diminua o tamanho da sequência n = n - 1 else: j = j + 1 # imprima x e o número de ocorrências print("%10.2f %6d" %(x, n_ocorrências)) # vamos examinar o próximo elemento i = i + 1 main() #-------------------------------------------------------------------- # SOLUÇÃO 4: Versão lê a sequência inteira de uma vez # #-------------------------------------------------------------------- def main(): ''' Dados n e uma sequência com n números reais, conta e imprime o número de vezes que cada número ocorre na sequência. ''' n = int(input("Digite o tamanho da sequencia: ")) # 1 leia todos os números da sequência sequência_str = input("Digite uma sequência com %d números: " %n) # 2 converta a string para uma lista de strings em que cada # elemento é um string que representa um número float lista_str = sequência_str.split() # linhas a seguir não fazem parte da solução if n != len(lista_str): print("Opsss, tem problema com o número de elementos da sequência") return None # fui # 3 converta cada string da lista para float sequência = [] # armazenará, iniciamente, toda a sequência de floats for num_str in lista_str: num_float = float(num_str) sequência.append(num_float) # 4 conte e imprima o número de ocorrência de cada número na sequência print(" Número no. ocorrências") i = 0 while i < n: n_ocorrências = 1 x = sequência[i] # percorra a sequência a partir da posição de índice i+1 # contando e removendo as ocorrências de x j = i+1 while j < n: if x == sequência[j]: n_ocorrências += 1 # "remova" o elemento sequência[j] sequência[j] = sequência[n-1] # diminua o tamanho da sequência n = n - 1 else: j = j + 1 # imprima x e o número de ocorrências print("%10.2f %6d" %(x, n_ocorrências)) # vamos examinar o próximo elemento i = i + 1 main()
Os elementos aij
de uma matriz de números reais
An×n
representam os custos de transporte da cidade i
$ para a
cidade j
.
Um itinerário que percorre k
cidades é representado por uma lista
C
com k
inteiros.
Nesta questão vamos resolver o problema de calcular custos de
itinerários entre as cidades, para achar o itinerário mais barato.
Por exemplo, para A4×4
,
A | 0 | 1 | 2 | 3 |
0 | 14.8 | 2.9 | 7.5 | 8.9 |
1 | 5.3 | 8.4 | 18.0 | 14.8 |
2 | 2.3 | 21.7 | 3.9 | 8.7 |
3 | 7.3 | 12.1 | 43.7 | 57.8 |
k = 9
cidades, representado
pela lista
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
C | 0 | 3 | 1 | 3 | 3 | 2 | 1 | 0 | 2 |
= a03 + a31 + a13 + a33 + a32 + a21 + a10 + a02
= 8.9 + 12.1 + 14.8 + 57.8 + 43.7 + 21.7 + 5.3 + 7.5
= 171.8
e o itinerário entre k = 1
cidade, representado
pela lista
0 | |
C | 2 |
item (a)
Escreva uma função custo
com cabeçalho:
def custo(A, C):que recebe uma matriz
A
de números reais de dimensão n × n
,
n > 0
,
e uma lista C
com k > 0
números inteiros.
A função deve retornar o custo do itinerário entre as k
cidades.
def custo(A, C): ''' (matriz, list) -> float Recebe uma matriz quadrada A de custos de transporte e uma lista C representado um itinerário e retorna o custo do itinerário. ''' # comprimento do itinerário k = len(C) custo_itinerário = 0 for i in range(k-1): origem = C[i] # cidade origem destino = C[i+1] # cidade destino custo_itinerário += A[origem][destino] return custo_itinerário
item (b)
Escreva um programa que:
A
(matriz de custos),
m
, m > 0
,
m
itinerários; cada itinerário consiste de uma
sequência de k
números inteiros, onde k > 0
, representando as
cidades (ou seja, o programa deve ler do teclado o valor de
k
e uma sequência de k
inteiros),
m
itinerários o seu programa deve
imprimir o seu custo.
O seu programa deve, utilizar a função custo
do
item anterior, mesmo que não a tenha implementado. Além da função custo
você pode utlizar a função com cabeçalho:
def le_matriz(nome_do_arquivo):sem implementá-la. A função
le_matriz
recebe o nome de um
arquivo e retorna uma matriz de números reais.
Por exemplo para
A | 0 | 1 | 2 | 3 |
0 | 14.8 | 2.9 | 7.5 | 8.9 |
1 | 5.3 | 8.4 | 18.0 | 14.8 |
2 | 2.3 | 21.7 | 3.9 | 8.7 |
3 | 7.3 | 12.1 | 43.7 | 57.8 |
m = 3
, itinerário 1 , k = 3 , |
0 | 1 | 2 | tem custo 20.9 (= 2.9 + 18.0 ) | |
itinerário 2 , k = 2 , |
2 | 1 | tem custo 21.7 | ||
itinerário 3 , k = 4 , |
2 | 3 | 0 | 1 | tem custo 25.0 ( =14.8 + 7.3 + 2.9 ) |
A saída do programa deve ser:
O itinerário mais barato tem custo 20.9 e passa pelas cidades: 0 1 2
def main(): ''' Programa para o cálculo de um itinerário de menor custo ''' # 1 leia o nome do arquivo nome_arquivo = input("Digite o nome do arquivo com a matriz de custos: ") # 2 leia a matriz de custos A = leia_matriz(nome_arquivo) # 3 leia o número e itinerários m = int(input("Digite o número de itinerários: ")) # 4 leia o primeiro itinerário e calcule o seu custo # o primeiro é o mais barato até que se prove o contrário itinerário_barato = leia_itinerário() menor_custo = custo(A, itinerário_barato) print("Custo do 1o. itinerário é %f" %(menor_custo)) # 5 leia cada um dos demais itinerário, calcule o seu custo # e mantenha o itinerário mais barato até o momento for i in range(m-1): # leia o itinerário itinerário = leia_itinerário() # calcule e imprima o seu custo custo_itinerário = custo(A, itinerário) print("Custo do %do. itinerário é %f" %(i+2,custo_itinerário)) # verifique se este itinerário é o mais barato até o momento if custo_itinerário < menor_custo: menor_custo = custo_itineráreo itinerário_barato = itinerário # 6 imprima o itinerário mais barato print("O itinerário mais barato tem custo %f e passa pelas cidades:" %(menor_custo)) for cidade in itinerário_barato: print(cidade) #-------------------------------------------------------------------------- def leia_itinerário(): ''' (None) -> list Função que lê um itinerário do teclado e cria uma lista com esse itinerário. A função retorna a lista criada. ''' k = int(input("Digite o número de cidades no itinerário: ")) itinerário = [] for i in range(k): cidade = int(input("Digite a %da. cidade do itinerário: " %(i+1))) itinerário.append(cidade) return itinerário #----------------------------------------------------------------------- main()