Introdução à Programação - Poli - Psub - em Python - 2013

Prévia do material em texto

Departamento de Ciência da Computação - IME - USP
MAC2166 Introdução à Computação
Escola Politécnica - Primeiro Semestre de 2013
Prova Substitutiva
QUESTÃO 1
 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:
Para a = 5, b = 3 e c = 11 seu programa deve imprimir:
 1 notas de 5 e 2 notas de 3 
Para 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 
Para a = 5, b = 3 e c = 7 seu programa deve imprimir:
 Não é possível descontar o cheque 
Para a = 4, b = 6 e c = 121 seu programa deve imprimir:
 Não é possível descontar o cheque 
Para 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 
Para a = 6, b = 15 e c = 199 seu programa deve imprimir:
 Não é possível descontar o cheque 
UMA SOLUÇÃO
#--------------------------------------------------------------------
# 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() 
QUESTÃO 2
 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 
UMA SOLUÇÃO
#--------------------------------------------------------------------
# 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()
QUESTÃO 3
 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.014.8
2 2.3 21.7 3.9 8.7
3 7.3 12.143.757.8
o itinerário entre 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
tem custo
= 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
tem custo zero.
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.
UMA SOLUÇÃO
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:
leia o nome de um arquivo que contém uma matriz de reais A (matriz de custos),
leia um número inteiro m, m > 0,
leia 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),
para cada um dos m itinerários o seu programa deve imprimir o seu custo.
ao final, o programa deve imprimir o custo do itinerário mais barato e a sequência de cidades desse
itinerário.
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.014.8
2 2.3 21.7 3.9 8.7
3 7.3 12.143.757.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 
UMA SOLUÇÃO
def main():
 '''
 Programa para o cálculo de um itinerário de menor custo
 '''
 # 1 leiao 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()
 
 
 
Last modified: Fri Jul 12 19:50:46 BRT 2013
	MAC2166 Introdução à Computação
	Escola Politécnica - Primeiro Semestre de 2013
	Prova Substitutiva
	QUESTÃO 1
	QUESTÃO 2
	QUESTÃO 3