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.7
a 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
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()