Trabalho Matemática discreta

Prévia do material em texto

Trabalho de Matemática Discreta 
O trabalho deve ser feito em equipe de até 5 alunos. Cada equipe deve entregar um 
relatório descrevendo a solução para cada programa acompanhado dos arquivos fontes. 
Data de Entrega: 08/10/2010 
O trabalho valerá 30% da N1 
N1 = (7*AP1 + 3T1)/10 
PROBLEMA 1 
 
Obs: Desenvolva uma solução para este problema utilizando vetor e outra solução sem utilizar vetor 
 
 
 
 
 
 
 
 
PROBLEMA 2 
 
 
Obs: Desenvolva uma solução para este problema e argumente o porquê sua solução está correta. 
 
 
Problema 3 
F91 
McCarthy é um teórico famoso de ciência da computação. No seu trabalho, ele definiu uma 
função recursiva, chamada f91, que recebe como entrada um inteiro N e retorna um inteiro 
positivo definido como a seguir: 
 Se N ≤ 100, então f91 (N) = f91 (f91 (N + 11)); 
 Se N ≥ 101, então f91 (N) = N - 10. 
Escreva um programa que computa a função f91 de McCarthy. 
Entrada 
O arquivo de entrada consiste de uma série de inteiros positivos, cada inteiro é no máximo 
1.000.000. Cada linha possui somente um número. O fim da entrada é alcançada quando o 
número 0 é encontrado. O número 0 não deve ser considerado como parte do conjunto de 
teste. 
Saída 
O programa deve imprimir cada resultado em uma linha, seguindo o formato fornecido no 
exemplo de saída. 
Exemplo 
Entrada: 
500 
91 
0 
 
Saída: 
f91(500) = 490 
f91(91) = 91 
 
Obs: Faça um relatório descrevendo a solução para este problema. 
 
 
 
 
 
 
 
 
Problema 4 
ONZE 
A sua tarefa é, dado um número positivo N, determinar se ele é um múltiplo de onze. 
Entrada 
A entrada é um arquivo onde cada linha contém um número positivo. Uma linha contendo o 
número 0 sinaliza o fim da entrada. Os números dados podem conter até 1000 dígitos. 
Saída 
A saída do programa deve indicar, para cada número da entrada, se ele é um múltiplo de onze 
ou não. 
Exemplo de Entrada 
112233 
30800 
2937 
323455693 
5038297 
112234 
0 
Exemplo de Saída 
112233 is a multiple of 11. 
30800 is a multiple of 11. 
2937 is a multiple of 11. 
323455693 is a multiple of 11. 
5038297 is a multiple of 11. 
112234 is not a multiple of 11. 
 
Obs: Faça um relatório descrevendo a sua solução. 
 
 
 
 
 
 
 
Problema 5 
FEYNMAN 
Richard Phillips Feynman era uma físico americando muito famoso e ganhador do Prêmio Nobel de 
Física. Ele trabalhava em física teórica e também foi pioneiro no campo da computação quântica. Ele 
visitou a América do Sul por dez meses, dando palestras e aproveitando a vida nos trópicos. Ele 
também é conhecido pelos livros "Surely You’re Joking, Mr. Feynman!" e "What Do You Care What 
Other People Think?", que inclui algumas de suas aventuras abaixo do equador. 
Sua paixão da vida inteira era resolver e criar quebra-cabeças, trancas e códigos. Recentemente, um 
fazendeiro idoso da América do Sul, que hospedou o jovem físico em 1949, achou alguns papéis e 
notas que acredita-se terem pertencido a Feynman. Entre anotações sobre mesóns e eletromagnetismo, 
havia um guardanapo onde ele escreveu um simples desafio: "quantos quadrados diferentes existem 
em um quadriculado de N x N quadrados?". 
No mesmo guardanapo havia um desenho, que está reproduzido abaixo, mostrando que para N = 2, a 
resposta é 5. 
 
Entrada 
A entrada contém diversos casos de teste. Cada caso de teste é composto de uma única linha, contendo 
apenas um inteiro N, representando o número de quadrados em cada lado do quadriculado (1 <= N 
<= 100). 
O final da entrada é indicado por uma linha contendo apenas um zero. 
Saída 
Para cada caso de teste na entrada, seu programa deve imprimir uma única linha, contendo o número 
de diferentes quadrados para a entrada correspondente. 
Exemplo de entrada 
2 
1 
8 
0 
Saída para o exemplo de entrada 
5 
1 
204 
 
PROBLEMA 6 
Par ou ímpar 
Existem muitas versões do Par ou Ímpar, um jogo jogado por competidores para decidir questões 
aletórias (Tais como "Quem codificará este problema?"). Em uma das versões, para dois jogadores, o 
jogo inicia com cada jogador dizendo par ou ímpar. Então eles contam até três (algumas pessoas 
dizem "Um, dois, três, VAI!"). No três, ambos jogadores mostram uma das mãos, mostrando um 
número de dedos (de zero a cinco). Se a soma dos dedos resulta em um número par, então a pessoa 
que disse par ganha. Se a soma dos dedos for um número ímpar, então a pessoa que disse ímpar ganha. 
John e Mary jogaram muitas vezes jogos de Par ou Ímpar. Em todos os jogos John escolheu ímpar (e, 
conseqüentemente, Mary escolheu par). Durante os jogos cada jogador escreveu, em pequenos cartões, 
quantos dedos ele/ela mostraram, usando uma carta para cada jogo - Mary usou cartões azuis, John 
usou cartões vermelhos. O objetivo deles era ser capar de re-checar os resultados depois, procurando 
pelos cartões de cada jogo. Entretanto, no fim do dia John derrubou o deque de cartões, e após terem 
separados os cartões por cor, eles agora perderam a ordem. 
Dado o conjunto de números escritos nos cartões vermelhos e azuis, você deve escrever um programa 
para determinar o número mínimo de jogos que Mary certamente ganhou. 
Entrada 
A entrada contém vários casos de teste. A primeira linha de cada caso de teste contém um inteiro N 
representando o numero de jogos jogados (1<=N<=100). A segunda linha de um caso de teste contém 
N inteiros Xi, indicando o numero de dedos mostrados por Mary em cada um dos jogos (0<=Xi =5, 
para 1<=i<=N). A terceira linha de cada caso de teste contém N inteiros Yi, indicando o número de 
dedos mostrados por John em cada um dos jogos (0<=Yi<=5, para 1<=i<=N). O fim da entrada é 
indicado por N=0. 
Saída 
Para cada caso de teste, seu programa deve escrever uma linha, contendo um inteiro, indicando o número 
mínimo de jogos que Mary certamente ganhou. 
Exemplo de entrada 
3 
1 0 4 
3 1 2 
9 
0 2 2 4 2 1 2 0 4 
1 2 3 4 5 0 1 2 3 
0 
Exemplo de saída 
0 
3 
Problema 7 
Problema: COPA 
Uma Copa do Mundo de futebol de botões está sendo realizada com times de todo o mundo. 
A classificação é baseada no número de pontos ganhos pelos times, e a distribuição de pontos 
é feita da forma usual. Ou seja, quando um time ganha um jogo, ele recebe 3 pontos; se o jogo 
termina empatado, ambos os times recebem 1 ponto; e o perdedor não recebe nenhum ponto. 
Dada a classificação atual dos times e o número de times participantes na Copa do Mundo, 
sua tarefa é de determinar quantos jogos terminaram empatados até o momento. 
Entrada 
A entrada contém vários casos de teste. A primeira linha de um caso de teste contém dois 
inteiros T e N, indicando respectivamente o número de times participantes (2 ≤ T ≤ 200) e o 
número de partidas jogadas (0 ≤ N ≤ 10000). Cada uma das T linhas seguintes contém o nome 
de um time (uma cadeia de máximo 10 letras e dígitos), seguido de um espaço em branco, 
seguido do número de pontos que o time obteve até o momento. O final da entrada é indicado 
por T = 0. 
Saída 
Para cada um dos casos de teste seu programa deve imprimir uma única linha contendo um 
número inteiro, representando a quantidade de jogos que terminaram empatados até o 
momento. 
Exemplo de entrada 
3 3 
Brasil 3 
Australia 3 
Croacia 3 
3 3 
Brasil 5 
Japao 1 
Australia 1 
0 0 
Saída para o exemplo de entrada 
0 
2 
 
 
 
 
 
 
Problema 8 
Considere um girassol amarelo com N pétalas. Com esse girassol, Leonardo e Clarissa brincam de 
bem-me-quer e mal-me-quer. Em cada jogada, a pessoa pode escolher entre retiraraté K pétalas 
vizinhas da flor. Leonardo começa jogando e dizendo bem-me-quer. Depois, Clarissa joga dizendo 
mal-me-quer. Como Leonardo gosta de Clarissa, ele deseja retirar a última pétala. Ele vai conseguir? 
Entrada 
A entrada contém diversos casos de teste. Cada caso de teste é composto de uma única linha, contendo 
dois inteiros N e K, N representando o número de pétalas (1 <= N <= 100) e K representando o 
número máximo de pétalas que podem ser retiradas (1< = K< = N ). 
O final da entrada é indicado por uma linha contendo dois zeros. 
Saída 
Para cada um dos casos de teste seu programa deve imprimir uma única linha contendo sim 
caso Leonardo sempre consiga retirar a última e nao caso contrário 
Entrada Saída 
15 2 
16 2 
23 4 
0 0 
nao 
sim 
sim 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Problema 9 
Problema: BIT 
As Ilhas Weblands formam um reino independente nos mares do Pacífico. Como é um reino 
recente, a sociedade é muito influenciada pela informática. A moeda oficial é o Bit; existem 
notas de B$ 50,00, B$10,00, B$5,00 e B$1,00. Você foi contratado(a) para ajudar na 
programação dos caixas automáticos de um grande banco das Ilhas Weblands. 
Tarefa 
Os caixas eletrônicos das Ilhas Weblands operam com todos os tipos de notas disponíveis, 
mantendo um estoque de cédulas para cada valor (B$ 50,00, B$10,00, B$5,00 e B$1,00). Os 
clientes do banco utilizam os caixas eletrônicos para efetuar retiradas de um certo número 
inteiro de Bits. 
Sua tarefa é escrever um programa que, dado o valor de Bits desejado pelo cliente, determine 
o número de cada uma das notas necessário para totalizar esse valor, de modo a minimizar a 
quantidade de cédulas entregues. Por exemplo, se o cliente deseja retirar B$50,00, basta 
entregar uma única nota de cinquenta Bits. Se o cliente deseja retirar B$72,00, é necessário 
entregar uma nota de B$50,00, duas de B$10,00 e duas de B$1,00. 
Entrada 
A entrada é composta de vários conjuntos de teste. Cada conjunto de teste é composto por 
uma única linha, que contém um número inteiro positivo V, que indica o valor solicitado pelo 
cliente. O final da entrada é indicado por V = 0. 
Saída 
Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A 
primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde 
n é numerado a partir de 1. Na segunda linha devem aparecer quatro inteiros I, J, K e L que 
representam o resultado encontrado pelo seu programa: I indica o número de cédulas de 
B$50,00, J indica o número de cédulas de B$10,00, K indica o número de cédulas de B$5,00 e 
L indica o número de cédulas de B$1,00. A terceira linha deve ser deixada em branco. A 
grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente. 
Exemplo 
Entrada: 
1 
72 
0 
 
Saída: 
Teste 1 
0 0 0 1 
 
Teste 2 
1 2 0 2 
Restrições 
0 <= V <= 10000 (V = 0 apenas para indicar o fim da entrada) 
Problema 10 
 
 
 
Problema 11 
Um tripla de Pitágoras é um conjunto de três números naturais,a b c , tal que 
a
2
 + b
2
 = c
2 
Existe exatamente um tripla pitagórica em que a + b + c = 1000. 
Encontre o produto abc. 
Problema 12 
Uma função indutivamente definida 
 
Considere a função f indutivamente definida para todos os inteiros da seguinte forma: 
 
 
Dado um valor inteiro positivo n encontre o valor de f(n). 
 
Entrada 
A entrada consiste de vários casos testes. Cada caso de teste é composto de uma única linha, 
contendo um inteiro N (1 <= N <= 2147483647). 
 O final da entrada é indicado por uma linha contendo -1. 
Saída 
Para cada um dos casos de teste seu programa deve imprimir uma única linha contendo f(n) = 
seguido pelo valor de f(n). 
 
Exemplo de Entrada 
2 
53 
153 
-1 
Exemplo de Saída 
f (2) = 1 
f (53) = 27 
f (153) = 77 
Desenvolva uma solução recursiva para o problema e uma solução não recursiva. Mostre que 
sua solução está correta por indução.