- TP1.1
- (receitas)Indica,justificando, quais dos seguintes métodos são algoritmos. Propõe alterações para tornar em algoritmos os que o não são ou corrigir os que não resolvem o problema proposto.
- (a)
- (Tirado das instruções de um shampoo) 1i
- i.
- Molhe bem a cabeça
- ii.
- Coloque uma porção do shampoo na sua mão
- iii.
- Lave a cabeça com o shampoo
- iv.
- Espere um minuto
- v.
- Retire o shampoo da cabeça com água em abundância
- vi.
- Repita o processo (ou seja, volte ao passo i)
- (b)
- Método para obter uma sequência aleatória dos primeiros seis inteiros positivos (com a ajuda de um papel, um lápis e um vulgar dado de seis faces): 1i
- i.
- Tome uma folha de papel (em branco)
- ii.
- Lance o dado
- iii.
- Se o valor da face do dado que ficou voltada para cima ainda não estiver na folha de papel, escreva-o (com o lápis)
- iv.
- Se o número de números na folha de papel for inferior a 6, volte para o passo ii, se for igual a 6 leia a lista de números que consta da folha de papel.
- (c)
- Método para determinar os números primos superiores a 2 e inferiores a um inteiro positivo n (crivo de Eratóstenes): 1i
- i.
- começa por construir uma lista com todos números ímpares de 3 até n;
- ii.
- risca todos os múltiplos de 3 maiores que 3
- iii.
- risca todos os múltiplos de 5 maiores que 5;
- iv.
- procede da mesma forma para cada número na lista ainda não riscado; os números que restam são primos.
- (d)
- Método para determinar os factores primos de um inteiro positivo n : 1i
- i.
- Se o n é o número 1 (n == 1) termine
- ii.
- Seja p o número 2 (p = 2)
- iii.
- Se n é divisível por p (n % p == 0), então n passa a ser o quociente de n por p (n = n / p) e insira p na lista de divisores de n (caso p não faça já parte dessa lista). Se n não for divisível por p, então p passa a ser igual ao seu sucessor (p = p + 1)
- iv.
- Volte ao passo i
- TP1.2
- Num conjunto de 6 moedas existe exactamente uma que é mais leve que todas as outras. Dispõe-se duma balança de dois pratos que permite comparar dois conjuntos de moedas, indicando apenas se os seus pesos são iguais ou um é mais pesado que o outro. Pretende-se determinar qual a moeda mais leve utilizando apenas duas pesagens. Podes generalizar o método para n moedas? E se fossem 9 moedas, era possível detectar a moeda deficiente apenas com duas pesagens?
- TP1.3
- Encontra algoritmos para os seguintes problemas:
- (a)
- Dadas duas palavras determinar qual a maior segundo a ordem do dicionário (ordem lexicográfica).
- (b)
- Dada uma prateleira de livros verificar se estes se encontram ordenados pelo seu título de forma crescente (pela ordem lexicográfica).
- (c)
- Ordenar pelos títulos o conjunto de livros de uma prateleira. O algoritmo encontrado na alínea anterior pode ajudar a encontrar pistas para resolver este problema.
- TP1.4
- Considera um tabuleiro de xadrez com 2n colunas e 2n linhas, para n inteiro positivo, e peças em forma de L que ocupem exactamente três posições no tabuleiro.
- (a)
- Se se retirar uma qualquer posição do tabuleiro, será possível cobrir todas as restantes posições com peças em L, sem que elas se sobreponham ou ``saiam'' do tabuleiro?
Sugestão: Começa por seguir o algoritmo seguinte para n = 1 e depois para n = 3. Certifica-te que o algoritmo resolve o problema para qualquer n, e indica qual a resposta. 2ii
- i.
- Se n é 1, o tabuleiro é 2x2 e é fácil verificar que qualquer que seja posição que se retire, é possível cobrir as restantes com uma peça em L. A resposta é sim.
- ii.
- Se n > 1, colocámos uma peça em L no centro do tabuleiro de forma a que a posição central que não fica coberta pertença ao quadrante a que se retirou uma posição. Aplicar o processo a cada um dos quadrantes.
- (b)
- Da resposta ao problema anterior que se pode dizer da divisibilidade por 3 dos números da forma 22n - 1?
- TP1.5
- Dois jogadores escolhem, alternadamente, números distintos de 1 a 9. O primeiro que escolher três números cuja soma perfaça 15, ganha o jogo. Existe uma estratégia de jogo que garanta que nunca se perca? Qual a relação deste jogo com o ``Jogo do Galo''?
- TP1.6
- Descreve um algoritmo que dada uma quantidade em €uros x, encontrar o menor conjunto de moedas de €2, €1, €0,50, €0,20, €0,10, €0,05, €0,02, €0,01. Imaginemos que temos a quantidade de moedas que necessitarmos.
- TP1.8
- Serão Algoritmos? Porquê?
- Construir a lista de todos os inteiros positivos
- Arranjar uma lista de numeros por ordem crescente
- Extrair o 1º elemento de uma lista
- Atirar uma moeda ao ar
- Se sair cara voltar ao passo anterior
- Tirar uma moeda do bolso
- Voltar ao passo anterior