Baixe o app para aproveitar ainda mais
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
Compartilhar