Lista2-ED1-2014-1

Prévia do material em texto

Estruturas de Dados I
Lista de Exercícios 2
Prof. Leandro M. Zatesko
Prof. Marcelo Cezar Pinto
1
o. semestre de 2014
Exercício 1. Faça um programa que lê duas frações e imprime a soma delas, na
forma de uma fração irredutível. Assuma que, numa fração, o numerador é separado
do denominador por uma barra (/). Por exemplo, se seu programa ler
11/18 17/24
deverá imprimir
95/72
Exercício 2. Faça um programa que lê um inteiro positivo N e uma sequência de N
inteiros x1, . . . ,xn e calcula mdc(x1, . . . ,xn). Lembre que mdc(a,b,c) = mdc(mdc(a,b), c).
Exercício 3. Resolva o Problema #1022 — TDA Racional — do URI Online Judge.
Exercício 4. Faça um programa que, dado um número n > 2, imprime todos os ele-
mentos do conjunto Π(n), ou seja, todos os números primos que são menores que n.
Por exemplo, se seu programa receber 20, deverá imprimir:
2
3
5
7
11
13
17
19
Exercício 5. Dizemos que dois números primos são gêmeos se a diferença entre eles
é 2. Exemplos de pares de primos gêmeos são (3,5), (5,7), (11,13), (17,19), (29,31)
etc. Assim como sabemos que existem infinitos números primos (isso foi mostrado
por Euclides), acredita-se fortemente que existem infinitos números primos gêmeos,
embora ninguém ainda tenha conseguido provar essa conjectura. Faça um programa
que, dado um número n > 2, imprima todos os pares de primos gêmeos menores que
n. Por exemplo, se seu programa receber 45, deverá imprimir:
3 5
5 7
11 13
17 19
29 31
41 43
Exercício 6. Um número na base 62 utiliza, nesta ordem, os dígitos
0, . . . ,9, a, . . . , z,A, . . . ,Z.
Assim, temos, por exemplo, que:
〈10〉10 = 〈a〉62;
〈35〉10 = 〈z〉62;
〈36〉10 = 〈A〉62;
〈61〉10 = 〈Z〉62;
〈62〉10 = 〈10〉62.
Faça um programa que converta um número na base 62 para a base decimal. Por
exemplo, ao receber como entrada
V1daL0ka
seu programa deverá imprimir
200800901482282
Exercício 7. Seguindo a ordem dos dígitos apresentada no Exercício 6, quais seriam
os dígitos utilizados na base 23? Faça um programa que converta um número na base
62 para a base 23. Faça um outro programa também que converta da base 23 para a
base 62.
Exercício 8. Resolva o Problema #1307 — Tudo o que Você Precisa é Amor — do URI
Online Judge.
Exercício 9. Resolva o Problema #1264 — Um Problema Fácil! — do URI Online
Judge. Aqui vão algumas dicas:
1. Cuidado com o texto! Ele tenta confundir você! No enunciado do problema ele
usa R para o valor e N para a base, e depois, nas especificações da entrada, usa
N para o valor.
2. Cuidado com o texto de novo! Ele não usa a ordem usual 0, . . . ,9, a, . . . , z,A, . . . ,Z ,
mas a ordem 0, . . . ,9,A, . . . ,Z,a, . . . , z.
3. Leia o valor de cada caso de teste não como um int, mas como uma string.
4. Após ler a string, converta-a para um vetor V de int’s, cada posição do vetor
correspondendo ao valor do respectivo caracter, desconsiderando a ocorrência
do sinal -. Por exemplo, a string -abc0123ABC deve ser convertida para o vetor
2
V 36 37 38 0 1 2 3 10 11 12
5. Identifique qual é o maior valor do vetor V . A base por onde você deve começar
deve ser este valor mais um. No exemplo, a base por onde você deve começar
deve ser 39. Tome cuidado também para não começar com uma base menor que
2 (Se o vetor tiver só zero, o maior valor mais um vai ser 1. Neste caso, você deve
tomar 2 como base, não 1).
6. Para calcular o resto da divisão do valor do caso de teste codificado na base base
por base−1, calcule o resto da divisão de V [0] por (base−1) e, para cada posição
j > 0 do vetor V , multiplique o resto que você já tem acumulado por base, some
V [j] e calcule novamente o resto deste resultado por base − 1. Isso funciona! E
não é por mágica, é por causa de uma disciplina da Teoria dos Números que a
gente chama de Aritmética Modular. Em código:
resto = V[0] % (base - 1);
for (j = 1; j < tamanho_de_V; j++) {
resto = (resto * base + V[j]) % (base - 1);
}
7. Se, após calcular o resto, esse resto não for zero, incremente a base e tente nova-
mente. Se nenhuma base entre 2 e 62 servir, imprima a frase
such number is impossible!
8. Continue lendo os casos de teste até encontrar EOF.
3