Revisões de pseudo-código

Considere a pseudo-linguagem dada nas aulas com as seguintes regras:

• apenas uma instrução por linha;
• as linhas tem de estar numeradas;
  
• operações aritméticas (+,-,/,X) calculo entre registos;
• operações lógicas (=, !=, <, <=, =>, >)
• JUMP ou GOTO (proximo passo de execução é colocado na linha indicada)
  
• PUT ou := (fazer atribuições a registos);
  
• READ, WRITE (ler do input e imprimir para o output);
• IF .... ELSE ..... (condição de verdadeiro ou falso)
• END (fim do programa)
  

Implemente os seguintes programas usando a linguagem acima referida:

1. Indique se o número lido é zero, positivo ou negativo. Se for positivo imprimir 1 caso contrario 0;
   
2. Calcule os primeiros dez múltiplos de 2
3. Calcule as primeiras dez potências de 2
4. Ler dois números e calcular:
1. o maior;
2. o menor;
3. o resultado da soma dos dois números;
4. o resultado da multiplicação dos dois números;
5. Dado o valor do salário de um trabalhador adicione 2,5% ao salário de um funcionário, caso este seja inferior a 500€ e 1,5% se for superior;
   
6. Leia dois números e apresente-os por ordem crescente;
7. Dado um salário calcule o Salário Bruto, Salário Liquido e Imposto a pagar:
1. salário menor que 1000€, taxa 5%;
2. salário maior ou igual a 1000€ e menor que 5000€, taxa 11%;
3. salário maior ou igual a 5000€, taxa 35%

Bom Trabalho !

Algoritmos - Revisão

EXERCÍCIOS DE REVISÃO

1. Escreva um algoritmo que leia n números inteiros e determine se cada um deles é um número da sequência de Fibonacci ou não.
   
   Definição da sequência de Fibonacci
   
   
2. Imagine que quer fazer uma pesquisa entre os habitantes de uma pequena vila. Escreva um algoritmo que recolha a idade, género (M/F) e salário de todos as pessoas que desejam participar na pesquisa (para encerrar a entrada de dados entre a idade menor ou igual a zero). Após recolher todos os dados indique:
   
3. • A média de salário do grupo
   • Maior e menor idade do grupo
   • A percentagem do total de mulheres com salário até R$ 300,00
   • A quantidade de homens
     
     
4. Faça um algoritmo que escreva todos os números múltiplos de 7 entre 1 e N, sendo N um valor introduzido pelo utilizador. Por exemplos: 7, 14, 21, 28, 35.
   
   
5. Elabore um algoritmo que receba dois números inteiros positivos. Calcule e mostre:
   
   • Caso os números formem um intervalo crescente, a media dos números do intervalo, incluindo os números digitados;
   • Caso os números formem um intervalo decrescente, a quantidade de números pares, incluindo os números digitados;
   • Se os números forem iguais, mostrar uma mensagem.

Visual Studio .Net - Visual Basic Express Edition

Links de Download das versões "Express Edition" do Visual Studio:

http://msdn2.microsoft.com/en-us/express/aa718401.aspx

ou o link directo para o Visual Basic Express Edition:

http://go.microsoft.com/fwlink/?linkid=57033
(gravar em CD)

Algoritmos e resolução de problemas

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 2ⁿ colunas e 2ⁿ 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 2²ⁿ - 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.7

Descreve um algoritmo para aplicar a formula resolvente.

TP1.8

Serão Algoritmos? Porquê?

i)

• Construir a lista de todos os inteiros positivos
• Arranjar uma lista de numeros por ordem crescente
• Extrair o 1º elemento de uma lista

ii)

• Atirar uma moeda ao ar
• Se sair cara voltar ao passo anterior

iii)

• Tirar uma moeda do bolso
• Voltar ao passo anterior

Apontadores Exercícios

1. Escreva a função com o protótipo void mult(int *v1, int *v2, int *v3, int n) que multiplica os vectores v1 e v2 elemento a elemento e coloca o resultado no vector v3. Os vectores têm comprimento n .(Ex (1,2,3)X(4,5,6)=(4,10,18)).
   
   
2. Escreva a função com o protótipo int comp_vec(int *v1, int *v2, int n) que retorna 1 se os vectores v1 e v2 forem iguais e 0 se forem diferentes. Os vectores têm comprimento n.
   
   
3. Escreva a função com o protótipo int is_ident(int *mat, int n) onde mat é uma matriz nxn. A função deverá retornar 1 se mat for a matriz identidade e 0 caso contrário. (Definição de Matriz Identidade)
   
   
4. Escreva a função com o protótipo void comuns(int a[], int m, int b[], int n) onde a[] e b[] contêm respectivamente m e n elementos distintos ordenados por ordem crescente e sem repetição. A função deve imprimir por ordem crescente os elementos comuns aos 2 vectores. Por exemplo, para os vectores [1,3,4,7,8] e [2,3,4,6,8,9] deverá ser impresso 3 4 8.
   
   
5. Escreva a função com o protótipo void sort_vec(int *vec, int n) que ordena os elementos do vector vec de n elementos por ordem crescente. Note que o vector pode conter elementos repetidos.
   
   
6. Considere 2 vectores globais de strings char *proibidos[] e char *gratis[] que representam respectivamente os prefixos de números de telefone de utilização proibida e grátis. Ambas estas lista usam o valor NULL para indicar o fim da lista. Um exemplo:
   char *proibidos[] = {"23","2677",NULL};
   char *gratis[] = {"0800","11",NULL};
   Implemente uma função com o protótipo int classifica_numero(char *tel) que retorna respectivamente 1,0 ou -1 conforme respectivamente o número de telefone tel é proibido (algum proibidos[i] é prefixo dele), grátis (algum gratis[i] é prefixo dele) ou nem grátis nem proibido. Para o exemplo dado, temos que classifica_numero("234455666") retorna 1.
   Recorde que dadas duas palavras p e s, diz-se que p é prefixo de s, se e só se, existir uma palavra y (que pode ser vazia) tal que s = py.
   A função int classifica_numero(char *tel) deverá utilzar uma função auxiliar com o protótipo int prefixo(char *p, char *s) que retorna 1 se p é prefixo de s e 0 caso contrário.

Apontadores (Revisões)

http://paginas.fe.up.pt/~apm/C_tut/Cap_8.htm

Apontadores e funções

Quando se passam argumentos para funções em C, estes são passados por valor (excepto os arrays, como veremos); ou seja, é criada uma cópia do argumento no stack do processador e é essa cópia que chega à função; quando a função termina essa cópia desaparece. No entanto há situações em que a passagem de argumentos por valor não é muito conveniente; por exemplo, quando queremos que modificações feitas aos argumentos no interior das funções cheguem a quem as chamou, ou quando necessitamos de passar argumentos de tamanho muito elevado (estruturas com muitos membros). Certas linguagens permitem então a passagem de parâmetros de outra forma - passagem por referência - em que a informação que chega à função é apenas o endereço do local na memória onde se encontra o valor do argumento (p. exemplo, argumentos declarados como var no Pascal). No entanto o C não permite esse mecanismo sendo necessário o uso explícito de apontadores para o implementar. (Nota: o C++ contém já esse mecanismo).

Por exemplo, se quiséssemos escrever uma função para trocar o conteúdo de duas variáveis, a forma habitual não funcionaria:

void swap(int a, int b)
{
int t;

t = a; a = b; b = t;
}

com a chamada

swap(i, j);

Para funcionar teríamos de recorrer a apontadores e ao operador

&

de obtenção do endereço de uma variável:

void swap(int *a, int *b)
{
int t;

t = *a; *a = *b; *b = t;
}

com a chamada

swap(&i, &j);

É possível também retornar apontadores como resultado de uma função, usado geralmente quando se pretende retornar informação que ocupe um grande espaço, como as estruturas:

typedef struct { float x, y, z; } coord;

coord *coor_fn(void);

void main(void)
{
coord p1;

...
p1 = *coord_fn();
...
}

coord *coor_fn(void)
{
coord p;

p = ... ;
return &p;
}

Aqui retorna-se um apontador cujo conteúdo é imediatamente de-referenciado para uma variável do tipo correspondente. Deve fazer-se esta transferência de imediato uma vez que a variável p é local à função e desaparece quando a função retorna, podendo a memória que lhe corresponde ser reutilizada.

Array's em C (2)

1. Dada uma matriz a[n][m] determinar a matriz que resulta de:
1. Trocar o menor elemento de cada linha i pelo elemento maior;
2. Deslocar a primeira coluna para a segunda, a segunda para a terceira, ... , a n-ésima para a primeira;
3. ordenar a matriz considerando o seguinte critério: a linha i é maior do que a linha j se na coluna de menor índice em que os elementos diferem, o elemento da linha i é maior do que o da linha j.
2. Dadas duas matrizes de inteiros a[n][m] e b[m][k] calcular a matriz c[n][k] correspondente ao produto matricial de a por b.
3. Dada uma matriz quadrada de inteiros a[n][n]
1. calcular a sua transposta.
2. substituir cada componente de a[][] não pertencente aos limites (4 cantos: superior, inferior, esquerdo e direito) pela média aritmética dos seus 8 vizinhos.
4. Dada uma matriz com 1000 linhas e 7 colunas representando 1000 sorteios do totoloto (para valores inteiros de 1 a 52) calcular:
1. Para cada sorteio o número de pares de números consecutivos;
2. Os 3 números que ocorrem mais vezes;
3. A maior sequência de números consecutivos.
5. Simulação do jogo do galo. O jogo do galo joga-se num tabuleiro de 3x3 e dois jogadores. Cada jogador coloca alternadamente um 1 ou um 2 numa das quadriculas e ganha o que colocar 3 peças em linha (horizontal, vertical ou diagonal principal). O tabuleiro é representado por uma variável indexada a[2][2] que contém as jogadas feitas, supondo-se que se o jogador i jogou numa certa posição então o conteúdo dessa posição é i, para i=1,2. Se uma posição ainda não foi jogada o conteúdo de a nessa posição é 0. Nenhum jogador pode jogar numa posição já preenchida e o jogo termina empatado se todas as posições estão ocupadas e nenhum jogador ganhou. Em cada jogada deve ser imprimido o tabuleiro, isto é, a. No início o programa deve pedir o nome de cada um dos jogadores e imprimir o nome do jogador que ganhar.
6. Simulação do jogo 5 em linha.

Objectivo do Jogo

Dois jogadores preenchem alternadamente as posições dum tabuleiro N×N, N>4. Um joga com peças 0 e o outro joga com peças 1. Ganha o jogo, o primeiro jogador que conseguir colocar 5 peças consecutivas na mesma direcção: numa linha, coluna ou diagonal (faz 5 em linha). O jogo termina - empatado - se já não houverem posições para preencher com peças. Supõe-se que inicialmente todas as posições do tabuleiro contêm o símbolo X.

Regras do Jogo

Os dois jogadores jogam alternadamente. Em cada jogada, um jogador selecciona uma posição da matriz indicando apenas a coluna c (de 1 a N) em que pretende jogar. Se a coluna c estiver toda preenchida, e, ainda restarem posições livres noutra coluna, terá de escolher uma dessas colunas livres. A posição em que ficará a sua peça será a corresponde à linha de maior numeração ainda livre, nessa coluna. Isto é, para uma dada coluna c, a primeira posição a ser preenchida é a (c,N), a segunda a (c,N-1), a terceira a (c,N-2), ... No fim de cada jogada, o computador terá de avaliar se o jogador ganhou o jogo. Para isso, basta verificar se com a peça que jogou conseguiu fazer 5 em linha. Note que não é necessário percorrer todas as posições do tabuleiro, mas apenas as posições que estão na mesma linha, coluna ou diagonais da última peça jogada.

O programa a desenvolver deve, em cada jogada:
• mostrar o tabuleiro
• indicar qual o jogador que deve jogar
• pedir ao jogador que seleccione uma coluna
• verificar se o jogador fez 5 em linha
• verificar se o jogo terminou e indicar o vencedor
• permitir a continuação do jogo

Estruturas em C (2)

(Manipulação duma base de dados de livros) Suponha que para cada livro existe informação sobre os seguintes campos:

Título

80 caracteres

Autor1

20 caracteres (Nome Próprio)

Autor2

20 caracteres (Apelido)

Ano de Edição

inteiro sem sinal

Tema

40 caracteres

1. Defina uma estrutura em C para guardar a informação anterior e defina uma variável indexada que contenha 100 elementos dessa estrutura.
2. Escreva funções que permitam:
   1. Introduzir um novo livro (pelo terminal);
   2. Leitura dos dados de um ficheiro, supondo que no ficheiro cada campo é guardado numa linha; para optimizar as pesquisas pode guardar a informação ordenada (lexicograficamente) pelo campo Autor2;
   3. Retirar a informação de um livro da base de dados;
   4. Guardar a informação da base de dados num ficheiro;
   5. Procurar um livro por: Título ou Autor2;
   6. Produzir os seguintes relatórios:
      1. listagem de todos os livros
      2. listagem de todos os livros de um autor;
      3. listagem de todos os livros de um tema;
      4. listagem de todos os livros editados num mesmo ano;
      Para cada um dos relatórios, deve ser pedido ao utilizador para seleccionar quais os campos que pretende que sejam listados.
3. Escreva um interface que após lida a base de dados, usando a função definida em , permita ao utilizador selecionar uma das tarefas:

   1. Introduzir novo livro
   2. Procurar por autor
   3. Procurar por titulo
   4. Retirar um livro;
   5. Relatórios
   6. Terminar
   

   Se for selecionada a tarefa 5. o utilizador ainda deverá escolher qual dos relatórios e qual a informação a imprimir.
   

Funções em C (1)

Crie programas e funções em linguagem C para resolver os seguintes problemas:

1. Dado um valor e a taxa do iva, crie uma função que devolva o preço a pagar (preço com iva incluido)
2. Dado um valor e a taxa de desconto, crie uma função que devolva o preço final a pagar
3. Crie uma função que processe os salários dos trabalhadores independentes atendendo às seguintes condições:
1. a função recebe o valor hora (em euros) a pagar e o tempo (horas)
   
2. ao valor bruto tem de ser acrescido iva de 21%
3. ao valor bruto tem de ser deduzido a taxa de IRS em 20%
4. Deverá ser apresentado ao utilizador, o valor bruto, o valor a pagar do iva, o valor deduzido para o IRS e o valor liquido que o trabalhador recebe.
   

Estruturas em C (1)

Gestão de Cursos ...

---

Crie uma base de dados em C, através de estruturas de forma a guardar os seguintes dados:

5
Programacao Imperativa
1
Calculo Infinitesimal I
1
Programacao Estruturada
1
Probabilidades e Estatistica
2
Modelos de Computacao
2

6
Joao Diogo Silva
2001018001
1
2
Mariana Pinto Matias
2001018003
4
1
4
2
3
Anabela Moreira
2004018014
3
1
3
2
Sonia Silva
1999018015
1
1
Manuel Pereira
2001019005
2
3
2
Carlos Santos
2004019007
3
1
2
3

No exemplo anterior Programacao Imperativa é a disciplina 1 e Programacao Estruturada
a disciplina 3. Note também que Programacao Imperativa será a primeira disciplina a ocorrer na estrutura
de dados Disc, enquanto Programacao Estruturada será a terceira.

Os quatro primeiros dígitos dos códigos dos alunos representam o ano, os três seguintes o código do curso e os três últimos identificam o
aluno. O primeiro número que está a seguir ao código do aluno indica o número de disciplinas em que está inscrito.
Os números seguintes identificam essas disciplinas.

Dada uma base de dados contendo informação sobre alunos e disciplinas de cursos duma faculdade, pretende-se consultá-la para:

• obter o número de alunos inscritos a cada disciplina

  Output: o título da tabela é Numero de alunos inscritos. A seguir tem uma linha de intervalo e depois a informação pedida para cada disciplina, obedecendo ao formato nome_disciplina : total_inscritos

• obter as disciplinas que têm mais alunos dum dado curso inscritos

  Output: o título é Disciplinas com mais alunos do curso codigo_curso , segue-se linha de intervalo, e depois os nomes das disciplinas.
  A linha final contem o número de disciplinas nas condições indicadas e o número de alunos inscritos em cada uma delas, seguindo o formato,
  Total = número_disciplinas Maximo = numero_de_alunos.

• imprimir, por ordem alfabética, a lista de alunos dum dado curso que entraram num dado ano.

  Output: o título é Alunos do curso código_do_curso que entraram em ano. São indicados depois todos os alunos nas condições pretendidas, código_do_aluno nome_do_aluno, e finalmente, o número total desses alunos (Total = número_alunos). Existirá uma linha de intervalo a seguir ao título e antes da linha final.
  NB: O programa não deverá alterar a base de dados, nem copiar integralmente o seu conteúdo para outra estrutura de dados auxiliar.

• para uma dada disciplina (identificada pelo seu nome), determinar os cursos que têm o maior número de alunos inscritos nessa disciplina ou um número que não difira desse mais do que k unidades, para k dado.
  NB: Para contar quantos alunos de cada curso estão inscritos à disciplina dada, o programa só deverá percorrer a estrutura Alunos uma única vez. Nessa passagem, deve identificar os cursos existentes.
  

Deverao ser criadas 2 estruturas que agreguem a informação que se pretende, uma chamada aluno e outra disciplina