Algoritmos

Universidade Federal Semi-Árido Departamento de Engenharia Ambiental Programação Aplicada a Engenharia

Algoritmos e Estruturas de Dados Algoritmos Estruturados Prof. José Patrocínio da Silva [email protected]

CONCEITOS BÁSICOS Algoritmos

ALGORITMOS – São formas de resolução de um problema, através da especificação passo-a-passo de como resolvê-lo.

A noção de algoritmo é básica em Computação.

Programação de Computadores

CONCEITOS BÁSICOS Resolução de Problemas por Computador Dar uma solução para um problema computacional significa elaborar um ALGORITMO em PSEUDOCÓDIGO (linguagem intermediária entre a linguagem natural e a linguagem de programação) e implementá-lo numa linguagem de programação, gerando um PROGRAMA.

Programação de Computadores

Resolução de Problemas por Computador Algoritmos ■Segundo

Knuth, um algoritmo é uma seqüência de passos bem definida que resolve determinado problema, através da transformação de dados iniciais na resposta desejada, tendo cinco importantes características: • Deve ser finito (finitness); • Os passos devem ser bem definidos, sem ambiguidades (definiteness); • Deve ser eficaz (effectiveness); • Deve possuir uma entrada (input); • Deve produzir uma saída ou resultado (output). Programação de Computadores

Resolução de Problemas por Computador Algoritmos ■Resumindo,

um algoritmo A resolve um problema P se, ao receber qualquer instância I de P, sempre produzir uma solução S para I. – A – algoritmo. – I – entrada (instância). – S – saída (resultado).

I

S

■Para

qualquer entrada I, o algoritmo deve ser executável em tempo finito e, além disso, gerar uma solução correta de P. Programação de Computadores

Resolução de Problemas por Computador Algoritmos ESTRUTURA GERAL DE UM ALGORITMO

» Algoritmo (Nome-do-Algoritmo); » Declaração de constantes, tipos e variáveis; » Início – Seqüências de Comandos; » Fim.

Programação de Computadores

Resolução de Problemas por Computador Algoritmos

ESTRUTURA GERAL DE UM ALGORITMO

» Algoritmo (Nome-do-Algoritmo); » Declaração de constantes, tipos e variáveis; » Início – Atribuições – Comandos de E/S – Estruturas de controle – Seleção – Repetição » Fim.

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Constantes Informação que não sofre variação no decorrer do tempo. Ex: 5, “Não Fume”, 2548, -0,62, “R$10,00”, Falso.

Variáveis Informação que tem a possibilidade de ser alterada em algum instante no decorrer do tempo. Ex: Cotação do dólar, peso de uma pessoa, salário.

Programação de Computadores

Resolução de Problemas por Computador Algoritmos

Declaração de Variáveis e Constantes – Alocar espaço de memória do tamanho do tipo-de-dado e dar um nome a este espaço; – Ao longo do programa, usa-se o nome dado ao invés do valor.

CONST n=50; VAR a, b, c, soma : TIPO;

Programação de Computadores

Exemplo de Um Programa em C #include <stdio.h> #include<stdlib.h> /* Soma dois números*/ main() { float a; /* primeiro número*/ float b; /* segundo numero */ float soma; /* resultado */ printf(" digite o valor de a e de b: \n"); scanf("%f %f",&a,&b); /* Ler a entrada de dados*/ soma = a+b; printf("o valor da soma e: %f \n",soma); system("PAUSE"); return(0); } Programação de Computadores

Resolução de Problemas por Computador Algoritmos Declaração de Variáveis e Constantes – Quando definir variáveis ? » Quando um elemento da lógica para a resolução do problema sofrer alterações de valor ao longo desta resolução.

– Quando definir constantes ? » Quando uma valor fixo for utilizado várias vezes na lógica para a resolução do problema. Programação de Computadores

Resolução de Problemas por Computador Algoritmos

Tipos de Dados Primitivos INTEIRO REAL LÓGICO CARACTERE STRING

Definidos pelo programador DISCIPLINA FILA PILHA

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Expressões Aritméticas – Aquelas cujos operadores são aritméticos e cujos operandos são constantes e/ou variáveis do tipo numérico (inteiro e/ou real).

Operadores Aritméticos – + Adição – - Subtração

* Multiplicação ** Potenciação

– mod ou %

resto da divisão.

/ Divisão // Radiciação

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Funções Matemáticas – – – – –

sen (x) cos(x) tg(x) abs (x) int (x)

- seno de x - cosseno de x - tangente de x - valor absoluto (módulo) de x - parte inteira de um número real

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Prioridades

parênteses mais internos funções matemáticas ** // * / +

-

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Expressões Relacionais – Comparação entre dois valores de um mesmo tipo primitivo. Estes valores podem ser constantes, variáveis ou expressões aritméticas. – O resultado obtido de uma relação é sempre um valor lógico. Operadores Relacionais = igual a > maior que < menor que

<> >= <=

diferente de maior igual a menor igual a Programação de Computadores

Resolução de Problemas por Computador Algoritmos Expressões Lógicas – Aquelas cujos operadores são lógicos e/ou relacionais e cujos operandos são relações e/ou variáveis e/ou constantes do tipo lógico.

Operadores Lógicos e ou xou não -

Conjunção Disjunção (não-exclusiva) Disjunção (exclusiva) negação Programação de Computadores

Resolução de Problemas por Computador Algoritmos Prioridades entre todos os Operadores parênteses mais internos funções aritméticas operadores aritméticos operadores relacionais operadores lógicos

Programação de Computadores

Resolução de Problemas por Computador Algoritmos

ESTRUTURA GERAL DE UM ALGORITMO

» Algoritmo (Nome-do-Algoritmo); » Declaração de constantes, tipos e variáveis; » Início – Atribuições – Comandos de E/S – Estruturas de controle – Seleção – Repetição » Fim.

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Atribuição

Fornece um valor a uma variável. Ex:

a ← 1; sexo ← “FEMININO”; salário ← 128,00;

Programação de Computadores

Resolução de Problemas por Computador Algoritmos

ESTRUTURA GERAL DE UM ALGORITMO

» Algoritmo (Nome-do-Algoritmo); » Declaração de constantes, tipos e variáveis; » Início – Atribuições – Comandos de E/S – Estruturas de controle – Seleção – Repetição » Fim.

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Comandos de Entrada e Saída

Exemplos do comando de entrada leia: leia (x); leia (a, nota, faltas); Exemplos do comando de saída escreva: escreva (x); escreva (a, nota, faltas); escreva (‘Bom Dia ‘, nome); escreva (‘Você pesa ‘, x * 2, ‘quilos.’);

Programação de Computadores

Resolução de Problemas por Computador Algoritmos

ESTRUTURA GERAL DE UM ALGORITMO

» Algoritmo (Nome-do-Algoritmo); » Declaração de constantes, tipos e variáveis; » Início – Atribuições – Comandos de E/S – Estruturas de controle – Seleção – Repetição » Fim.

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Estruturas de Controle de Fluxo – Seqüência – Seleção » » » »

simples composta encadeada múltipla escolha

– Repetição » Teste condicional no início • Número de repetições conhecido • Número de repetições desconhecido

» Teste condicional no fim

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Estruturas de Controle de Fluxo

– Seqüência » início » ; » ; » … » ; » fim Programação de Computadores

Resolução de Problemas por Computador Algoritmos Estruturas de Controle de Fluxo

– Seleção simples início … se então ; ; … ; fim se … fim

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Estruturas de Controle de Fluxo

– Seleção composta

início se então ; ; … ; senão ; ; … ; fim se fim

BLOCO VERDADE

BLOCO FALSO

Programação de Computadores

Resolução de Problemas por Computador Algoritmos

– Seleção composta início

se então se então ; … ; fim se senão se então

;

senão

… ;

se então ; … ; senão

;

fim

fim se

fim se

fim se ;

Programação de Computadores

Resolução de Problemas por Computador Algoritmos – Seleção de múltipla escolha início

fim

… escolha (x) caso VALOR1 : ; caso VALOR2 : ; caso VALOR3 : ; fim escolha … Programação de Computadores

Resolução de Problemas por Computador Algoritmos – Seleção de múltipla escolha início

fim

… se <x = VALOR1> então ; senão se <x = VALOR2> então ; senão se <x = VALOR3> então ; fim se fim se fim se … Programação de Computadores

Resolução de Problemas por Computador Algoritmos – Repetição Usada em trechos do algoritmo em que há a necessidade de se realizar um bloco de comando um número determinado de vezes.

Programação de Computadores

Resolução de Problemas por Computador Algoritmos Repetição com teste no início (ENQUANTO-FAÇA) Permite executar diversas vezes um trecho do algoritmo, porém, sempre verificando antes de cada execução se é “permitido” executar algum trecho. enquanto () faça ; ; … ; fim enquanto – Quando o resultado da for falso, o comando é abandonado. – Se já da primeira vez o resultado for falso, os comandos não são executados nem uma vez. Programação de Computadores

Resolução de Problemas por Computador Algoritmos

Repetição com teste no FINAL (REPITA-ATÉ) repita ; ; … ; até () – O bloco de comandos é executado pelo menos uma vez, independente da validade da . Isto ocorre porque a inspeção da é feita após a execução do bloco. Programação de Computadores

Resolução de Problemas por Computador Algoritmos Repetição com variável de controle (PARA) – para (V = vi; V <= vf; passo p) faça – ; – ; – … onde: – ; • V é a variável de controle; • vi é o valor inicial de V; – fim para

• vf é o valor final de V, ou seja, o valor até o qual ela pode chegar e; • p é o valor do incremento dado a V. Programação de Computadores

Resolução de Problemas por Computador Algoritmos Comparação entre as estruturas de Repetição • •

Toda estrutura ENQUANTO pode ser convertida para REPITA e vice-eversa; Toda estrutura PARA pode ser convertida em ENQUANTO, mas nem toda estrutura ENQUANTO pode ser convertida em PARA.

Estrutura Condição de existência Enquanto início Repita fim Para implícita início

Qtde de execuções Cond. ? mínimo 1 (vf - vi) div p

condição verdadeira condição falsa vi ≤ vf Programação de Computadores

ALGUNS PROBLEMAS

Programação de Computadores

PROBLEMA DE ACHAR O MENOR

Encontrar o menor dentre um conjunto de números.

Programação de Computadores

PROBLEMA DE ACHAR O MENOR ALGORITMO EncontraMenor; VAR n, qtde-num, num, menor: INTEIRO; INICIO LER (n); LER (num); menor ← num; qtde-num ← 1; ENQUANTO (qtde-num < n) LER (num); SE num < menor menor ← num; FIM-SE; qtde-num ← qtde-num +1; FIM-ENQUANTO; ESCREVER (menor); Programação de Computadores FIM.

PROBLEMA DE ACHAR O MENOR EM C ■ ■ ■ ■ ■

#include <stdio.h> #include<stdlib.h> /* Acha o menor número de uma lista*/ main() { int num, n[num]; int cont, menor; /* declarações */ printf("\n digite o numero de elementos da sequencia: "); scanf("%d",&num); for (cont=0;cont
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

}

Programação de Computadores

PROBLEMA DE ACHAR O MENOR E O MAIOR

Encontrar o menor e o maior dentre um conjunto de números.

Programação de Computadores

PROBLEMA DE ACHAR O MENOR E O MAIOR

ALGORITMO EncontraMenorMaior; VAR n, qtde-num, num, menor, maior: INTEIRO; INICIO LER (n); LER (num); menor ← num; maior ← num; qtde-num ← 1; ENQUANTO (qtde-num < n) LER (num); SE num < menor menor ← num; SENAO SE num > maior maior ← num; FIM-SE; qtde-num ← qtde-num +1; FIM-ENQUANTO; Programação de Computadores ESCREVER (menor, maior); FIM.

PROBLEMA DE ACHAR O MENOR E MAIOR EM C #include <stdio.h> #include<stdlib.h> /* Acha o menor e o maior número de uma lista*/ main() { int num, n[num]; int cont, menor, maior; /* declarações */ printf("\n digite o numero de elementos da sequencia: "); scanf("%d",&num); for (cont=0;contmaior){ maior=n[cont]; } cont++; } printf("O menor e: %d \n",menor); printf("O maior e: %d \n",maior); system("PAUSE"); return(0); }

Programação de Computadores

Descrição de Algoritmos ■

A descrição de um algoritmo de forma clara e fácil de ser seguida ajuda no seu desenvolvimento, depuração (correção de erros) e a subsequente transformação do mesmo num programa.

■

1- Descrição Narrativa: Especificação verbal dos passos em linguagem natural. Desvantagens: a linguagem natural é imprecisa e freqüentemente pouco confiável como um veículo de transferir informação. Sua utilização pode ser adotada, entretanto, para a apresentação de comentários sobre o algoritmo (ou parte dele), esclarecendo ou realçando pontos específicos.

■

Programação de Computadores

Descrição Narrativa Descrição Narrativa: Linguagem Natural : Os algoritmos são expressos diretamente em linguagem natural. Pseudolinguagem: Emprega uma linguagem intermediária entre a linguagem natural e uma linguagem de programação.

Programação de Computadores

Descrição por Fluxograma ■

2 - Fluxograma Uso de ilustrações gráficas para transmitir informações (Ex. Gerais: mapas, diagramas explicativo para montagem de aparelhos, etc.).

■ ■

Um fluxograma mostra, de forma gráfica, a lógica de um algoritmo, enfatizando passos individuais e o fluxo de execução.

■

Desvantagens: utilização questionável de fluxogramas detalhados, pois obscurecem a estrutura do programa.

Programação de Computadores

Simbologia utilizada em fluxogramas

Programação de Computadores

Fluxogramas A notação por fluxograma auxilia a explicar a seqüência de instruções em algoritmos e programas.

Estrutura de Controle Seqüencial

Estrutura de Controle Condicional Programação de Computadores

Fluxogramas

Estrutura de Controle Repetitiva

OBS.: Na notação por fluxograma um retângulo representa um passo ou módulo do algoritmo, uma seta indica o próximo comando a ser executado, um losango indica uma condição que interfere no fluxo do algoritmo ou programa. Esta forma de representação de algoritmos emprega várias formas geométricas para descrever cada uma das possíveis ações durante a execução do algoritmo. Programação de Computadores

Exemplo

Programação de Computadores

Pseudolinguagem É uma notação que se assemelha a uma linguagem de programação, mas também possibilita ao programador concentrar-se no problema a ser modelado sem “se prender” a uma linguagem programação específica. Esta forma de representação tem a vantagem de fazer com que o algoritmo seja escrito de uma forma que está próxima de uma linguagem de programação.

Programação de Computadores

Exemplos ALGORITMO maiorque; VAR x, y, m, n: REAL; LER (x); LER (y); x ← m; y ← n; SE x > y ESCRVER(‘O maior é x’, x); SENÃO ESCRVER(‘O maior é y’, y); FIM-SE FIM

início x recebe m y recebe n

x é maior que y?

não

y é maior

sim

x é maior

Programação de Computadores

Exemplos ALGORITMO Azarao; CONST n = 100; VAR num, cont: INTEIRO; INICIO num ← 13; cont ← 1; ENQUANTO cont < 100 ESCREVA (num); num ← num +13; cont ← cont +1; FIM-ENQUANTO; FIM.

início recebe num Receber cont n ←100

cont < =100 ?

escreva num

num ← num +13 cont ← cont +1 FIM

Programação de Computadores

PROBLEMA DO AZARÃO

Fazer um programa que escreva os 100 primeiros múltiplos de 13.

Programação de Computadores

Datas importantes ■ ■ ■ ■ ■

Primeira avaliação (teórica) - 10 de Setembro 2007; Segunda Avaliação (Teórica + Prática) – 08 Outubro de 2007; Terceira Avaliação (Teórica + Prática) – 26 Novembro de 2007; Quarta Avaliação (Teórica + Prática) – 03 Dezembro de 2007.

de de de de

A prova de reposição será feita 72 horas após a aplicação da terceira avaliação. Programação de Computadores

PROBLEMA DO AZARÃO ALGORITMO Azarao; CONST n = 100; VAR num, cont: INTEIRO; INICIO num ← 13; cont ← 1; ENQUANTO cont < 100 ESCREVA (num); num ← num +13; cont ← cont +1; FIM-ENQUANTO; FIM. Programação de Computadores

PROBLEMA DO AZARÃO EM C #include <stdio.h> #include<stdlib.h> /* Achar o 100 primeiros múltplos de 13*/ main() { int num,n,cont; /*declarações*/ n=100; cont=1; num=13; while(cont
PROBLEMA DO AZARÃO ALGORITMO Azarao; CONST n = 100; VAR num, cont: INTEIRO; INICIO num ← 13; cont ← 1; REPITA ESCREVA (num); num ← num +13; cont ← cont +1; ATE cont > 100; FIM.

Programação de Computadores

PROBLEMA DO VÍCIO

Calcule e mostre a despesa diária, semanal e mensal de uma pessoa com cigarros, dados o número de cigarros que ela fuma por dia e o preço do maço de cigarros que ela fuma.

Programação de Computadores

PROBLEMA DO VÍCIO ALGORITMO Vicio; VAR num-c-dia : INTEIRO; preco-m, preco-c, despesa-d, despesa-s, despesa-m: REAL; INICIO ESCREVA (‘Quantos cigarros vc fuma por dia?’); LER (num-c-dia); ESCREVA (‘Quanto custa o maco de cigarros que vc fuma?’); LER (preco-m); preco-c ← preco-m/20; despesa-d ← preco-c * num-c-dia; despesa-s ← despesa-d * 7; despesa-m ← despesa-d * 30; ESCREVA (‘Sua despesa com cigarros diária, semanal e mensal eh: ‘ despesa-d, despesa-s, despesa-m); FIM. Programação de Computadores

PROBLEMA DO VÍCIO EM C #include <stdio.h> #include<stdlib.h> /* Acha o menor e o maior número de uma lista*/ main() { float precom,precoc,despd,desps,despm; /*declarações reais*/ int numcdia; /* declarações inteiras*/ printf("\n digite o numero de cigaros que voce fuma por dia: "); scanf("%d",&numcdia);/*ler numero de cigarros por dia*/ printf("\n digite o preco do maco de cigarros que voce fuma: "); scanf("%f",&precom); /*ler o preco do maço*/ precoc=precom/20.0; /*calcula preço unitário do cigarro*/ despd=precoc*numcdia;/*Calcula despesa diária*/ desps=despd*7.0; /*calcula despesa semanal*/ despm=despd*30.0; /*calcula despesa mensal*/ printf("sua despesa diaria e: %f \n",despd); printf("sua despesa semanal e: %f \n",desps); printf("sua despesa mensal e: %f \n",despm); system("PAUSE"); return(0); }

Programação de Computadores

PROBLEMA DA CORRIDA DE AUTOMÓVEL

Em uma corrida de automóveis com n voltas, foram anotados os tempos, em ordem, de um piloto em cada volta. Fazer um programa que dê o melhor e o pior tempo e em que volta aconteceram.

Programação de Computadores

PROBLEMA DA CORRIDA DE AUTOMÓVEL

ALGORITMO CorridaAutomovel; VAR num-voltas, cont-voltas, melhor-volta, pior-volta : INTEIRO; tempo-volta, melhor-tempo, pior-tempo: REAL; INICIO ESCREVA (‘Entre com o numero total de voltas da corrida:’); LER (num-voltas); ESCREVA (‘Entre com o valor do primeiro tempo anotado:’); LER (tempo-volta); melhor-tempo ← tempo-volta; pior-tempo ← tempo-volta; melhor-volta ← pior-volta ← 1; PARA cont-volta ← 2 a n ESCREVA (‘Entre com o valor do tempo da próxima volta:’); LER (tempo-volta); SE tempo-volta > pior-tempo pior-tempo tempo-volta; pior-volta cont-volta; Programação de Computadores SENAO SE tempo-volta < melhor-tempo melhor-tempo tempo-volta; melhor-volta cont-volta;

PROBLEMA DA CORRIDA DE AUTOMÓVEL

ALGORITMO CorridaAutomovel; VAR num-voltas, cont-voltas, melhor-volta, pior-volta : INTEIRO; tempo-volta, melhor-tempo, pior-tempo: REAL; INICIO ESCREVA (‘Entre com o numero total de voltas da corrida:’); LER (num-voltas); ESCREVA (‘Entre com o valor do primeiro tempo anotado:’); LER (tempo-volta); melhor-tempo ← tempo-volta; pior-tempo ← tempo-volta; melhor-volta ← pior-volta ← 1; PARA cont-volta ← 2 a n ESCREVA (‘Entre com o valor do tempo da próxima volta:’); LER (tempo-volta); SE tempo-volta > pior-tempo pior-tempo tempo-volta; pior-volta cont-volta; SENAO SE tempo-volta < melhor-tempo melhor-tempo tempo-volta; melhor-voltaProgramação cont-volta;de Computadores FIM-SE;

PROBLEMA DA CORRIDA DE AUTOMÓVEL ALGORITMO CorridaAutomovel; VAR num-voltas, cont-voltas, melhor-volta, pior-volta : INTEIRO; tempo-volta, melhor-tempo, pior-tempo: REAL; INICIO ... ESCREVA (‘Melhor volta = ‘, melhor-volta, ‘ com tempo = ‘,melhor-tempo); ESCREVA (‘Pior volta = ‘, pior-volta, ‘ com tempo = ‘,pior-tempo); FIM.

Programação de Computadores

PROBLEMA DO FATORIAL DE UM NÚMERO

Calcule o fatorial de 5. E para um n qualquer ?

Programação de Computadores

PROBLEMA DO FATORIAL DE UM NÚMERO ENUNCIADO DO PROBLEMA: Calcular o fatorial de 5. PARÂMETROS: n RESTRIÇÕES: n ∈ Z+ SOLUÇÃO: result = n.(n-1).(n-2). ... .2.1 INSTÂNCIA: n=5 SOLUÇÃO_DA_INSTÂNCIA: result=5.4.3.2.1=120

Programação de Computadores

PROBLEMA DO FATORIAL DE UM NÚMERO ALGORITMO Fatorial; VAR fat, i : INTEIROS; INICIO fat = 1; PARA i := 2 a n FAÇA fat := fat * i; END; MOSTRE fat; FIM. Programação de Computadores

PROBLEMA SOBRE A SÉRIE DE FIBONACCI

Calcule o n-ésimo termos da série de Fibonacci.

Programação de Computadores

PROBLEMA SOBRE A SÉRIE DE FIBONACCI ENUNCIADO DO PROBLEMA: Mostrar o n-ésimo termo da Série de Fibonacci. PARÂMETROS: n RESTRIÇÕES: n ∈ Z+ SOLUÇÃO: result = n-ésimo termo INSTÂNCIA: n=5 SOLUÇÃO_DA_INSTÂNCIA: result=3

Programação de Computadores

PROBLEMA SOBRE A SÉRIE DE FIBONACCI ALGORITMO Fibonacci; VAR i, fib,fib1,fib2,n : INTEIRO; INICIO SE n = 1 RETURN 0; SENAO SE n = 2 RETURN 1; fib1 := 1; fib2 := 0; PARA i := 3 a N FAÇA fib := fib1 + fib2; fib2 := fib1; fib1 := fib; FIM-PARA; MOSTRE fib;

FIM. Programação de Computadores

PROBLEMA SOBRE A SÉRIE DE FIBONACCI ALGORITMO Fibonacci-v2; VAR i, fib,fib1,fib2,n : INTEIRO; INICIO SE n <= 2 RETURN n; fib1 := 1; fib2 := 0; PARA i := 3 a N FAÇA fib := fib1 + fib2; fib2 := fib1; fib1 := fib; FIM-PARA; MOSTRE fib;

FIM. Programação de Computadores

PROBLEMA DOS APROVADOS

Dado um conjunto de n notas de alunos, contar o número de alunos que foram aprovados. Considera-se aprovado o aluno que obteve nota igual ou maior que 5.0.

Programação de Computadores

Solução

Programação de Computadores

PROBLEMA DA AVALIAÇÃO

Fornecer a média aritmética simples das n notas de um aluno, indicando também sua situação final (média>=9 excelente, média>=7 bom, média>=5 regular, média<5 insuficiente).

Programação de Computadores

PROBLEMA IV

Como medir exatamente 2 litros utilizando apenas mangueira, um balde de 4 litros e outro de 3 litros?

Programação de Computadores

PROBLEMA IV

ENUNCIADO DO PROBLEMA: Como medir exatamente 2 litros utilizando apenas mangueira, um balde de 4 litros e outro de 3 litros. PARÂMETROS: vasilhames A e B. RESTRIÇÕES: capacidades máximas A=4l, B=3l: 0≤A ≤ 4 e 0 ≤ B ≤ 3 SOLUÇÃO: (A=2) ou (B=2) INSTÂNCIA: A=0 e B=0 SOLUÇÃO_DA_INSTÂNCIA: (A=2) ou (B=2) Programação de Computadores

PROBLEMA IV ALGORITMO Medir2Litros; CONST LimA=4; LimB=3; VAR A, B : INTEIROS; INICIO LIMPAR A e B; ENCHER B; DESPEJAR_B_EM_A; ENCHER B; DESPEJAR_B_EM_A; MOSTRAR B; FIM. Programação de Computadores

PROBLEMA IV ENCHER B ENQUANTO (NÃO_CHEIO(B)) FAÇA B = B+1; FIM-ENQUANTO;

DESPEJAR_B_EM_A ENQUANTO (NÃO_CHEIO(A)) OU (NÃO_VAZIO(B)) FAÇA B = B - 1; A = A + 1; FIM-ENQUANTO; Programação de Computadores

PROBLEMA IV ENCHER B ENQUANTO (B < LimB) FAÇA B = B+1; FIM-ENQUANTO;

DESPEJAR_B_EM_A ENQUANTO (A < LimA) E (B > 0) FAÇA B = B - 1; A = A + 1; FIM-ENQUANTO; Programação de Computadores

PROBLEMA IV

LIMPAR A e B A = 0; B = 0; MOSTRAR B ESCREVER (B);

Programação de Computadores

PROBLEMA IV ALGORITMO Medir2Litros; CONST LimA=4; LimB=3; VAR A, B : INTEIROS; INICIO LIMPAR A e B; ENCHER B (B); DESPEJAR_B_EM_A (B,A); ENCHER_B(B); DESPEJAR_B_EM_A (B,A); MOSTRAR B; FIM. Programação de Computadores

Histórico – Linguagem de programação estruturada – 1º linguagem de programação de alto nível e foi proposta em 1956 – Surgiu visando a resolução de problemas da área científica, com o uso de computadores – O nome é a composição de: FORmula TRANslation – Sua versão mais recente é o FORTRAN 90.

Programação de Computadores

Conceitos da Linguagem ■

■

■

Basicamente há duas formas de se escrever um programa em FORTRAN: – com formulário fixo (‘fixed form’) ou – com formulário livre (‘free form’). O segundo (free form) disponível apenas para a programação em FORTRAN 90. Novos compiladores aceitam os formatos e os comando anteriores.

Programação de Computadores

Conceitos da Linguagem Formatação ■

Formatação no Formulário Fixo

1.

Coluna 1, C ou * indicam comentário – comentários são ignorados pelo compilador

2.

Os números dos comandos podem ser quaisquer(int >= 0) constituindo em 1 a 5 dígitos, colocados no campo das colunas 1 a 5.

1.

Para indicar continuação de um comando utiliza-se um caracter qquer diferente de espaço ( b) e zeros na coluna 6; podendo haver no MAX. 19 linhas de contunuação.

2.

As colunas 73 a 80 são utilizadas pelo compilador, portanto não se deve escrever nestas colunas. Programação de Computadores

Conceitos da Linguagem Formatação ■

FORTRAN 90 – Formato Livre – O programa pode ser escrito em qualquer posição – as linhas de continuação são indicadas pelo símbolo ‘&’ no fim da sentença – e a próxima linha abaixo que não seja um comentário será tomada como continuação – Deixe sempre um espaço entre os comandos e o símbolo de continuação – É permitida a inserção de comentários após o ‘& – Os rótulos devem ser os primeiros caracteres da linha, e podem estar em qualquer coluna. Programação de Computadores

Conceitos Básicos Comentários ■ ■ ■

■

Não são interpretados pelo compilador Um bom programa tem muitos comentários O comando ‘! ’ indica que o que vem após ele é comentário, ele pode vir em qualquer posição, inclusive após os comandos. Alguns compiladores aceitam qualquer caractere diferente de números para iniciar a linha de comentário

Programação de Computadores

Conceitos Básicos Constantes ■

■

Constante é uma quantidade fixa, invariável; um valor que não muda no decorrer dos cálculos relativos ao programa. Classes: – Numéricas – tratam números – Lógicas – tratam valores lógicos (verdadeiro x falso) – Cadeia de Caracteres – tratam seq. de caracteres

Programação de Computadores

Conceitos Básicos Variáveis e Nomes de Blocos ■

■

■ ■

Variável é uma entidade que armazena constantes e é conhecida no programa por um nome. É um nome representando uma área de memória, que pode conter de 1 a 6 caracteres alfanuméricos, começando necessariamente por uma letra. Caracteres adicionais são permitidos, mas ignorados. Recomendações para nomes de variáveis!

Programação de Computadores

Conceitos Básicos Tipos de Variáveis ■

■

Inteiras (INTEGER) – Podem assumir os seguintes valores: INTEGER*1

–128 a 127

INTEGER*2

–32,768 a 32,767

INTEGER*4

–2,147,483,648 a 2,147,483,647

INTEGER*4 pode ser representado somente por: INTEGER Programação de Computadores

Conceitos Básicos Tipos de Variáveis ■

■

■

Reais (REAL) – Precisão simples, 6 casas decimais (padrão): – REAL*4 ou REAL `3.402823E+38 – Precisão dupla, 15 casas decimais (padrão): REAL*8 ou DOBLE PRECISION`1.797693134862316D+308 A parte exponencial deve ser separada por um ‘d’ ou ’D’ no lugar do ‘e’ ou ‘E’ para real do tipo *8. Programação de Computadores

Conceitos Básicos Tipos de Variáveis ■

Complexas (COMPLEX) – Precisão simples, 6 casas decimais: » COMPLEX*8 ou COMPLEX – Precisão dupla, 15 casas decimais: » COMPLEX*16

■

Os valores que um complexo pode assumir são os mesmos que os reais. Programação de Computadores

Conceitos Básicos Tipos de Variáveis ■

Alfanuméricas (CHARACTER) – CHARACTER NOME*w

■

Onde w representa o número máximo de caracteres que a variável pode conter dentro do programa.

Programação de Computadores

Conceitos Básicos Tipos de Variáveis ■ ■

■

■

Lógicas (LOGICAL) LOGICAL NOME Podem assumir os valores – .TRUE. (VERDADEIRO) ou – .FALSE. (FALSO) Ou somente T e F ou ainda 1 e 0 ou diferente de zero e 0.

Programação de Computadores

Operadores Atribuição – Identificador = Expressão ■

■

Exemplos: – ano = 1999 – nome = ‘Joao’ – Temp = 25.4 Em Fortran 90, pode ser utilizado ; – ano = 1999; nome = ‘Joao’;Temp = 25.4

Programação de Computadores

Operadores Literais ■

Uma função útil para variáveis literais é a concatenação (junção de palavras)

■

Exemplo: – A = ‘tele’ – B = ‘visao’ – C = A//B

Programação de Computadores

Operadores Aritméticos ■

Executam operações aritméticas comuns FORTRAN

+

* / **

Matemática Tradicional

Significado

+ -

soma Subtração Multiplicação Divisão

ap

Potenciação

Programação de Computadores

Operadores Relacionais ■

Comparam variáveis, constantes ou expressões e retornam – ‘.TRUE.’, .TRUE. ‘T’ ou ‘1’ se a comparação for verdadeira, – ‘.FALSE.’, .FALSE. ‘F’ ou ‘0’ se a comparação for falsa. FORTRAN

F90

Matemática Tradicional

Significado

.LT.

<

<

MENOR QUE

.LE.

<=

<

MENOR OU IGUAL QUE

.EQ.

==

=

IGUAL A

NE.

/=

GT.

>

>

MAIOR QUE

.GE.

>=

≥

MAIOR OU IGUAL QUE

. .

DIFERENTE DE

=

Programação de Computadores

Operadores Lógicos ■

São usados quando são necessárias mais de uma condição relacional ou quando é preciso inverter seu resultado. FORTRAN

Significado

.AND.

Junção – verdadeiro se os dois operadores forem verdadeiros Disjunção – verdadeiro se um dos dois operadores forem verdadeiro Negação – verdadeiro se o operador for falso

.OR. .NOT. .NEQV. ou .XOR. .EQV.

Desigualdade Lógica – verdadeiro se somente um dos operadores for verdadeiro Igualdade Lógica – verdadeiro se os dois operadores forem falsos ou verdadeiros Programação de Computadores

Prioridades em FORTRAN Operador

Prioridade

**

1ª

*

2ª

/

2ª

+

3ª

-

3ª

.EQ.

4ª

.NE.

4ª

.GT.

4ª

.GE.

4ª

.LT.

4ª

.LE.

4ª

.NOT.

5ª

.AND.

6ª

.OR.

7ª

O uso de parênteses pode ser feito para trocar a ordem de prioridade.

Programação de Computadores