Aulas Teóricas - BAC004 - Técnicas de Programação

Transcrição

Ministério da Educação
UNIVERSIDADE FEDERAL DE ITAJUBÁ
CAMPUS ITABIRA
BAC 004 – Informática (Teórica)
Notas de Aula
2010
Sumário
1 Introdução..........................................................................................................................................3
1.1 Considerações Iniciais...............................................................................................................3
1.2 Histórico....................................................................................................................................3
1.3 Estrutura de um Computador Digital.........................................................................................7
1.4 Algoritmo...................................................................................................................................8
1.5 Algoritmos Estruturados..........................................................................................................11
1.6 Linguagens de Programação....................................................................................................12
2 Fundamentos dos Algoritmos Estruturados.....................................................................................14
2.1 Considerações Iniciais.............................................................................................................14
2.2 Constantes................................................................................................................................14
2.3 Variáveis...................................................................................................................................15
2.4 Expressões Aritméticas............................................................................................................16
2.5 Expressões Lógicas..................................................................................................................18
2.6 Expressões Literais..................................................................................................................21
2.7 Comando de Atribuição...........................................................................................................22
2.8 Comandos de Entrada e Saída.................................................................................................22
3 Fundamentos dos Algoritmos Estruturados.....................................................................................24
3.1 Estrutura Seqüencial ...............................................................................................................24
3.2 Estrutura Condicional .............................................................................................................24
3.3 Estruturas de Repetição...........................................................................................................25
3.3.1 Comando Enquanto..........................................................................................................26
3.3.2 Comando Repita...............................................................................................................26
3.3.3 Comando For....................................................................................................................27
4 Estruturas Básicas de Dados............................................................................................................29
4.1 Variáveis Compostas Homogêneas..........................................................................................29
4.2 Variáveis Compostas Heterogêneas.........................................................................................32
5 Modularização e Funções................................................................................................................34
5.1 Introdução................................................................................................................................34
5.2 Ferramentas para modularização.............................................................................................35
5.2.1 Sub-rotinas.......................................................................................................................35
5.2.2 Funções............................................................................................................................36
5.3 Recursividade...........................................................................................................................36
6 Bibliografia......................................................................................................................................39
BAC 004 – Informática Teórica – Notas de Aula
3
1 Introdução
“Quando a complexidade aumenta, as afirmações precisas perdem significado e as
significativas perdem precisão”. Lotfi Zadeh
1.1 Considerações Iniciais
A tarefa de processamento de dados consiste em tomar certa informação,
processá-la e obter o resultado desejado (Figura 1).
Dados
Processamento
Resultado
Figura 1 - Processamento de dados
Desde que o homem começou a processar dados, ele tentou construir máquinas
para ajudá-lo em seu trabalho. O computador eletrônico é o resultado dessas tentativas
que vêm sendo realizadas através dos séculos.
1.2 Histórico
Década de 1940
1943 Alan Turing estava envolvido no desenvolvimento de uma máquina para
decifrar o código das mensagens nazistas, conhecido como Enigma.
1944 Foi construído o primeiro computador eletromecânico, batizado de Mark I.
Utilizado pela marinha americana. O Mark I usava os mesmos princípios da
Máquina Analítica, criada por Babbage cem anos antes.
1946 O ENIAC (Eletronic Numerical Integrator and Calculator) é considerado o
primeiro computador digital e eletrônico. Desenvolvido pelos engenheiros J.
Presper Eckert e John W. Mauchly, na Universidade da Pensilvânia.
Foi criado para cálculo balístico e, posteriormente, utilizado no projeto da bomba de
hidrogênio. Ficou em operação no período de 1946 a 1955.
Possuía 17 mil válvulas, 10 mil capacitores, 70 mil resistores e pesava 30
toneladas. Quando em operação, consumia cerca de 140 quilowatts e era capaz de
realizar 5 mil adições por segundo.
4
Para trabalhar com o ENIAC era necessário conhecer profundamente o
funcionamento do hardware, pois a programação era feita em painéis, através de 6
mil conectores, utilizando linguagem de máquina. Esta tarefa facilmente poderia
levar alguns dias. Corretamente programado, um cálculo que levasse vinte e quatro
horas manualmente era resolvido em menos de trinta segundos.
O professor John von Neumann, consultor do projeto do ENIAC, imaginou uma
máquina de propósito geral onde tanto instruções quanto dados fossem
armazenados em uma mesma memória, tornando o processo de programação
muito mais rápido e flexível (“Arquitetura de von Neumann”).
1949 EDSAC (Eletronic Delay Storage Automatic Calculator) foi o primeiro
computador a implementar o conceito de “programa armazenado”. Outros
computadores foram construídos nessa mesma época com base no mesmo
princípio. Nesta fase, os computadores ainda não possuíam dispositivos com
função de interface com os usuários e o conceito de sistema operacional.
Década de 1950
O uso do transistor e da memória magnética contribuiu para o enorme avanço dos
computadores da época (2ª geração).
O transistor permitiu o aumento da velocidade e da confiabilidade no
processamento, e as memórias magnéticas permitiram o acesso mais rápido aos
dados, maior capacidade de armazenamento e computadores menores.
Apesar do invento do transistor datar do final da década de 1940 (Bell Telephone
Laboratories, 1948), os primeiros computadores transistorizados foram lançados
comercialmente apenas no final da década de 1950. Surgiram as primeiras
empresas da indústria de computadores: Raytheon, RCA, Burroughs e a IBM, o
que levou à criação dos primeiros computadores para utilização em aplicações
comerciais.
1951 UNIVAC (Universal Automatic Computer) foi o primeiro computador bemsucedido fabricado para fins comerciais (censo dos Estados Unidos).
O Massachusetts Institute of Technology (MIT) colocou em operação o que é
considerado o primeiro computador voltado para o processamento em tempo real,
o Whirlwind I.
Ele introduziu a tecnologia de memória magnética. Os programas ou jobs
passaram a ser perfurados em cartões, que, submetidos a uma leitora, eram
gravados em uma fita de entrada. A fita, então, era lida pelo computador, que
executava um programa de cada vez, gravando o resultado do processamento em
uma fita de saída. Ao término de todos os programas, a fita de saída era lida e
impressa. A esse tipo de processamento, onde um conjunto de programas era
submetido ao computador, deu-se o nome de processamento batch.
5
1953 Primeiro sistema operacional, chamado monitor, desenvolvido para o
computador IBM 701
Surgimento das primeiras linguagens de programação de alto nível, como
FORTRAN, ALGOL e COBOL, os programas deixaram de ter relação direta com o
hardware dos computadores, o que facilitou e agilizou enormemente o
desenvolvimento e a manutenção de programas.
Década de 1960
Domínio da tecnologia física do estado sólido permitiu a integração de vários
transistores em uma única embalagem com aproximadamente as mesmas
dimensões de um único transistor. Surgiram, então, os circuitos integrados,
responsáveis pelo aparecimento dos computadores da 3ª geração.
1963 Burroughs lança o computador B-5000 com o sistema operacional Master
Control Program (MCP), que oferecia multiprogramação, memória virtual com
segmentação, multiprocessamento assimétrico, além de ser o primeiro sistema a
ser desenvolvido em uma linguagem de alto nível.
1964 IBM lança o System/360, que causou uma revolução na indústria de
informática, pois introduziu o conceito de máquinas de porte diferente, porém com
uma mesma arquitetura, permitindo a total compatibilidade entre os diferentes
modelos.
1965 A Digital Equipment Corp. (DEC) lançou o PDP-8, representando a primeira
linha de computadores de pequeno porte e baixo cuto.
1969 Ken Thompson, que trabalhou no projeto do sistema operacional MULTICS
(Multiplexed Information and Computing Service), utilizou um PDP-7 para fazer sua
própria versão de um sistema que viria a ser conhecido como UNIX.
Década de 1970
A integração em larga escala (Large Scale Integration – LSI) e a integração em
muito larga escala (Very Large Scale Integration – VLSI), levaram adiante o projeto
de miniaturização e barateamento dos equipamentos.
1971 A Intel Corp. produz seu primeiro microprocessador, o Intel 4004, e três anos
depois o 8080, utilizado no primeiro microcomputador, o Altair. Posteriormente a
Zilog lançaria um processador concorrente ao da Intel, o Z80.
1975 Dennis Ritchie desenvolve a Linguagem C e, juntamente com Ken Thompson,
portam o sistema UNIX para um PDP-11, concebido inicialmente em Assembly.
1976 Steve Jobs e Steve Wozniak produzem o Apple II de 8 bits, tornando-se um
sucesso imediato. Neste ano as empresas Apple e Microsoft são fundadas. O
sistema operacional dominante nos primeiros microcomputadores foi o CP/M
6
(Control Program Monitor) da Digital Research. O Cray-1 é lançado contendo
200.000 circuitos integrados e realizando 100 milhões de operações de ponto
flutuante por segundo (100 MFLOPS). As redes distribuídas difundiram-se,
surgiram vários protocolos de rede, inclusive o NCP (precedessor do TCP/IP).
Surgem as primeiras redes locais.
Década de 1980
1981 A IBM entra no mercado de microcomputadores com o IBM PC (Personal
Computer). O primeiro PC utilizava o processador Intel 8088 de 16 bits e o sistema
operacional DOS (Disk Operating System) da Microsoft, muito semelhante ao
CP/M.
1982 Fundada a Sun Microsystems, que passa a atuar fortemente no setor,
lançando as primeiras estações RISC com o sistema operacional SunOS e,
posteriormente, Sun Solaris.
A Universidade de Berkeley na Califórnia desenvolveu sua própria versão do
sistema UNIX (Berkeley Software Distribution – BSD) e introduziu inúmeros
melhoramentos, merecendo destaque o protocolo de rede TCP/IP (Transmission
Control Protocol / Internet Protocol).
Com a evolução dos microprocessadores, principalmente da família Intel, surgem
os primeiros sistemas operacionais comerciais que oferecem interface gráfica,
como o Microsoft Windows e o OS/2.
O software de rede passa a estar fortemente relacionado com o sistema
operacional e surgem os sistemas operacionais de rede, com destaque para o
Novell Netware e o Microsoft LAN Manager.
Década de 1990
Grandes avanços de hardware, software e telecomunicações foram obtidos nesta
década, conseqüência da evolução das aplicações que necessitavam cada vez
mais de capacidade de processamento e armazenamento de dados, como em
sistemas especialistas, sistemas multimídia, banco de dados distribuídos,
inteligência artificial e redes neurais.
A evolução da microeletrônica permitiu o desenvolvimento de processadores e
memórias cada vez mais velozes e baratos, além de dispositivos de E/S menores,
mais rápidos e com maior capacidade de armazenamento.
Os componentes baseados em tecnologia VLSI evoluem rapidamente para o ULSI
(Ultra Large Scale Integration).
Com o surgimento e a evolução da Internet, o protocolo TCP/IP passou a ser um
padrão de mercado, obrigando os fabricantes a oferecer suporte a este protocolo.
Um fato importante nesta década foi o amadurecimento e popularização do
7
software aberto (open software). Com a Internet, inúmeros produtos foram
desenvolvidos e disponibilizados para uso gratuito, como sistemas operacionais
(Linux e FreeBSD), banco de dados (MySQL), servidores Web (Apache),
servidores de correio (Sendmail), dentre outros.
Década de 2000
Novas arquiteturas paralelas, baseadas em organizações de multiprocessadores
não-convencionais, já se encontram em desenvolvimento em diversas
universidades e centros de pesquisa.
Novas formas de interação usuário-computador. O conceito de processamento
distribuído será mais explorado nos sistemas operacionais. Evolução das redes
sem fio (wireless).
1.3 Estrutura de um Computador Digital
O esquema da estrutura de um computador digital é dado pela figura 2:
Figura 2 - Estrutura de um computador digital
Unidade de Entrada
Traduz informação de uma grande variedade de dispositivos em um código que a
unidade central de processamento é capaz de entender.
8
Memória
Armazena os dados e os programas que “manipulam” estes dados.
Unidade Lógica e Aritmética
Nesta unidade são feitos todos os cálculos aritméticos e qualquer manipulação de
dados, sejam eles numéricos ou não.
Unidade de Controle
É a unidade responsável pelo fluxo dos dados. Ela obtém dados armazenados na
memória e interpreta-os. Controla a transferência de dados da memória para a
unidade lógica e aritmética, da entrada para a memória e da memória para a saída.
Unidade de Saída
Os dados processados são convertidos, por esta unidade, de impulsos elétricos em
palavras ou números que podem ser “escritos” em impressoras ou “mostrados” em
vídeos ou numa séria de outros dispositivos.
1.4 Algoritmo
Conceituação
Para estabelecer o conceito de algoritmo, que é da maior importância em Ciência
da Computação, será antes fixado o conceito de ação. Ação é um acontecimento que, a
partir de um estado inicial, após um período de tempo finito, produz um estado final
previsível e bem definido.
Adota-se a seguinte definição de algoritmo:
“Algoritmo é a descrição de um conjunto de comandos que, obedecidos, resultam
numa sucessão finita de ações”.
Geralmente, um algoritmo se destina a resolver um problema: fixa um padrão de
comportamento a ser seguido, uma norma de execução a ser trilhada, para se atingir,
como resultado final, a solução de um problema.
Exemplo:
Descrever um algoritmo que mostre todos os números da série de Fibonacci
menores que um valor dado n.
Algoritmo
Escreva os termos de Fibonacci inferiores a n
Fim_Algoritmo.
9
Refinamentos
Um algoritmo é considerado completo se os seus comandos forem do
entendimento do seu destinatário. Num algoritmo, um comando que não for do
entendimento do destinatário terá de ser desdobrado em novos comandos, que
constituirão um refinamento do comando inicial.
Se um algoritmo é formado não apenas por um comando, mas por vários, isto
significa que na sua execução não se consideram apenas o estado inicial e o final de
uma ação dele resultante, mas que se consideram também estados intermediários que
delimitam as ações decorrentes de cada comando.
Exemplo:
O algoritmo dos termos de Fibonacci poderia ser refinado em:
Refinamento Escreva os termos de Fibonacci inferiores a n
inicio
Receba o valor de n
Processe os 2 primeiros termos
Processe os termos restantes
fim
Um algoritmo e os seus refinamentos são formados por comandos, que
determinam as ações a serem executadas pelo seu destinatário e por estruturas de
controle que determinam a ordem em que os comandos devem ser executados, se
devem ser executados ou não e quando devem ser repetidos. No exemplo anterior vigora
a estrutura de controle mais simples:estrutura seqüencial, segundo a qual os comandos
devem ser executados um após o outro, na mesma ordem em que aparecem escritos.
Se um comando de um refinamento for um tanto vago, ele poderá, por sua vez, ser
desdobrado em novos comandos, produzindo-se o refinamento de um refinamento, e
assim sucessivamente.
Exemplo:
O comando “Processe os 2 primeiros termos” pode ser desdobrado em:
Refinamento Processe os 2 primeiros termos
inicio
Atribua o valor 1 ao primeiro termo
se ele for menor do que n
então escreva-o
Atribua o valor 1 ao segundo termo
então escreva-o
fim
10
Neste refinamento, aparece uma segunda estrutura de controle: a estrutura condicional:
se condição
então comandos
O comando “escreva-o” só será executado se a condição “ele for menor do que n”
for verdadeira. O comando “escreva-o” não será executado se a condição for falsa, isto é,
se ele for maior ou igual a n. Vê-se, portanto, que um algoritmo, através de estruturas
condicionais, pode provocar ou não a realização de uma ação.
Uma terceira estrutura de controle, a estrutura de repetição, será necessária ao
se desdobrar o comando “processe os termos restantes”.
Exemplo:
Refinamento de “Processe os termos restantes”:
Refinamento Processe os termos restantes
inicio
repita
Calcule novo termo somando os 2 anteriores
Escreva novo termo
até novo termo for maior ou igual a n
fim
Na estrutura de repetição, os comandos e as estruturas de controle abrangidos
devem ser executados repetidamente até que se verifique uma condição (no caso, o novo
termo a ser maior ou igual a n) para que se interrompa a repetição.
Após esses refinamentos sucessivos, o algoritmo pode ser considerado
completo, a menos que o destinatário não saiba fazer a adição de dois termos ou não seja
capaz de entender diretamente algum comando.
Exemplo:
Algoritmo completo para escrita dos termos de Fibonacci inferiores a n:
Algoritmo
Receba o valor de n
{Processamento dos 2 primeiros termos}
Atribua o valor 1 ao primeiro termo
então escreva-o
Atribua o valor 1 ao segundo termo
então escreva-o
11
{Processamento dos termos restantes}
repita
Calcule novo termo somando os 2 anteriores
Escreva novo termo
até novo termo for maior ou igual a n
Fim_Algoritmo.
1.5 Algoritmos Estruturados
Com a evolução, os problemas levados aos computadores são cada vez de maior
porte e maior complexidade. Os algoritmos para resolvê-los ainda devem ser
desenvolvidos pelo ser humano, mas podem ultrapassar os limites de sua compreensão.
Por esta razão, nas últimas décadas surgiram técnicas que permitem sistematizar e
ajudar o desenvolvimento de algoritmos para a resolução de grandes e complexos
problemas nos computadores: são as técnicas de desenvolvimento estruturado de
algoritmos.
Os objetivos destas técnicas são:
• Facilitar o desenvolvimento dos algoritmos;
• Facilitar o seu entendimento;
• Antecipar a comprovação da sua correção;
• Permitir que o seu desenvolvimento possa ser empreendido
simultaneamente por uma equipe de pessoas.
Para atingir estes objetivos, o desenvolvimento estruturado preconiza que:
• Os algoritmos sejam desenvolvidos por refinamentos sucessivos partindo de uma
descrição geral e, gradativa e sucessivamente, atacando as minúcias e particularidades.
Este desenvolvimento também se denomina “construção hierárquica de algoritmos” e
“desenvolvimento top/down”.
• Os sucessivos refinamentos são módulos, que delimitam poucas funções e são os mais
independentes possíveis, isto é, conservam poucos vínculos com outros módulos.
• Nos módulos deve ser usado um número limitado de diferentes comandos e de
diferentes estruturas de controle.
O refinamento sucessivo dos algoritmos permite uma abordagem mais segura e
objetiva do problema. A integração dos módulos é mais perfeita, porque cada módulo é
atacado quando já se estudou claramente o ambiente em que ele deve atuar.
12
A divisão em módulos funcionais permite contornar a limitação humana para
compreender a complexidade. Cada módulo pode ser desenvolvido ou analisado de forma
quase independente, dados os poucos vínculos que deve manter com os outros módulos
do algoritmo.
1.6 Linguagens de Programação
Para armazenar um algoritmo na memória de um computador e para que ele
possa, em seguida, comandar as operações a serem executadas, é necessário que ele
seja programado, isto é, que seja transcrito para uma linguagem que o computador
possa “enteder”, direta ou indiretamente.
Os computadores só podem executar diretamente os algoritmos expressos em
linguagem de máquina, que é um conjunto de instruções capazes de ativar diretamente
os dispositivos eletrônicos do computador. A linguagem de máquina tem vários
inconvenientes para os humanos. É diferente para cada tipo de computador, pois depende
de sua arquitetura. Além disto, é extremamente rudimentar e exige que, mesmo as
operações mais simples ainda sejam refinadas, para expressá-las em termos de registros,
acumuladores e outros dispositivos da máquina. Além disso, a linguagem de máquina é
expressa em forma numérica (binária ou hexadecimal), que a torna pouco expressiva para
os seres humanos.
Nos primeiros computadores, a linguagem de máquina era a única opção para
fazer a programação.
Logo surgiu a idéia de se escreverem programas em Linguagem simbólica, mais
conhecida por Linguagem Assembly ou Linguagem montadora. Na Linguagem
Assembly as instruções não são expressas apenas por números, mas também por letras
e símbolos mais significativos para os humanos. O posicionamento dos dados e
instruções na memória é também feito de forma simbólica.
Um programa em Assembly, para controlar o computador, deve primeiro ser
transformado em linguagem de máquina. Como cada comando da linguagem Assembly
corresponde a um comando em linguagem de máquina, esta transformação pode ser feita
facilmente pelo próprio computador, através de um programa chamado montador ou
Assembler.
O sucesso da linguagem Assembly animou os primeiros pesquisadores a criar
linguagens em que a programação era feita através de uma notação matemática e de
algumas palavras da língua inglesa, deixando ao próprio computador a tarefa de traduzir
este programa para a linguagem de máquina, através de um programa chamado
compilador. A primeira destas linguagens, que teve ampla aceitação, surgiu em 1957 e é
ainda hoje utilizada. Trata-se da linguagem FORTRAN, nome formado com partes das
palavras “Formula Translation”.
Além da grande facilidade, uma imensa vantagem de se escrever os programas em
linguagens de alto nível, como passaram a ser chamadas a linguagem FORTRAN e
outras que se seguiram, é a sua quase total independência da máquina a ser usada. O
13
programador não precisa se deter em particularidades do computador que irá usar. Um
programa escrito em linguagem de alto nível, geralmente com poucas alterações, é aceito
por qualquer computador.
A escolha da linguagem de programação para se usar em um computador
depende, antes de tudo, da existência de um programa compilador (que traduza o
algoritmo escrito na linguagem escolhida para a linguagem de máquina) ou de um
programa interpretador (que interprete cada comando do programa e execute uma série
de instruções que a ele correspondem).
Existindo compiladores ou interpretadores para diversas linguagens, a escolha
pode ser pela linguagem preferida ou mais familiar para o programador, por aquela melhor
implementada no computador, por aquela mais adequada para o tipo de aplicação que se
deseja fazer etc. Mas, para se resolver um problema num computador, mais importante
que a escolha da linguagem de programação é o desenvolvimento de um algoritmo
adequado.
O algoritmo deve ser desenvolvido objetivando sobretudo a clareza, permitindo que
os erros cometidos sejam detectados o quanto antes, evitando excessivas revisões e
visando facilitar futuras modificações. Para se conseguir isto de uma forma natural e
eficiente, deve-se adotar técnicas de desenvolvimento estruturado dos algoritmos. Depois
disto, a programação consistirá quase que só numa transcrição do algoritmo obtido.
14
2 Fundamentos dos Algoritmos Estruturados
“Não há nada de errado com aqueles que não gostam de política,
simplesmente serão governados por aqueles que gostam.”
Platão
2.1 Considerações Iniciais
Uma vez conhecida a definição de algoritmos, será introduzido um conjunto
particular de regras e convenções para o seu desenvolvimento. Deve-se dedicar atenção
especial a este conteúdo pois ele contém os fundamentos necessários para compreensão
dos demais.
As normas utilizadas neste curso não são únicas e seguem a estrutura definida na
referência (FARRER, H. et. Alli., 1999).
2.2 Constantes
Uma constante é um determinado valor fixo que não se modifica ao longo do
tempo, durante a execução de um programa. Uma constante pode ser um número, um
valor lógico ou uma seqüência de caracteres. Conforme o seu tipo, a constante é
classificada como sendo numérica, lógica ou literal.
Constante Numérica
A representação de uma constante numérica nos algoritmos é feita no sistema
decimal, podendo ser um número com ou sem parte fracionária. Exemplos:
• 15;
• 23,5;
• -10.
Constante Lógica
É um valor lógico, isto é, que só pode ser falso ou verdadeiro, usado em proposições
lógicas. Só existem duas constantes deste tipo, sendo representadas pelas palavras falso
e verdadeiro.
15
Constante Literal
Uma constante deste tipo pode ser qualquer seqüência de caracteres (letras,
dígitos ou símbolos especiais) que forme um literal com algum significado para o
problema em estudo. As constantes literais devem aparecer no algoritmo entre aspas
para que não sejam confundidas com outro item qualquer.
Exemplos:
• “Introdução a Computação”
• “12345”
• “XYZ”
• “08/03/2005”
• “FALSO”
2.3 Variáveis
Na matemática, uma variável é a representação simbólica dos elementos de um
certo conjunto.
Nos algoritmos, uma variável corresponde a uma posição de memória, cujo
conteúdo pode variar ao longo do tempo durante a execução de um programa.
Embora uma variável possa assumir diferentes valores, ela só pode armazenar um
valor a cada instante.
Toda variável é identificada por um nome ou identificador. Assim, por exemplo,
num algoritmo para o cálculo das raízes de uma equação do 2º grau (ax2 + bx + c = 0), os
identificadores A, B e C podem representar as posições de memória que armazenam os
coeficientes da equação, fazendo, neste caso, o papel das variáveis na matemática.
Formação dos Identificadores
Um identificador é formado por um ou mais caracteres, sendo que o primeiro
caractere deve, obrigatoriamente, ser uma letra e os caracteres seguintes, letras ou
dígitos, não sendo permitido o uso de símbolos especiais.
Exemplos:
•A
• Aluno
• XYZ123
• CADE
• ZI235
16
É recomendável que os nomes das variáveis sejam os mais significativos
possíveis, isto é, que reflitam, da melhor maneira, a natureza dos valores que nelas estão
sendo armazenados. Isto ajuda muito no entendimento do algoritmo.
Por exemplo: se a variável vai armazenar o nome de um empregado, por que não
escolher o identificador NomeDoEmpregado para representá-la, ao invés de NE ?
Declaração de variáveis
As variáveis só podem armazenar valores de um mesmo tipo, de maneira que
também são classificadas como sendo numéricas, lógicas ou literais.
Para indicar o tipo de uma ou mais variáveis é usada a declaração de variáveis.
Uma vez declarada a variável, qualquer referência que se faça ao seu identificador
implica a referência ao conteúdo do local da memória representado pelo mesmo.
Formato:
declare lista-de-identificadores nome-do-tipo
Onde:
declare
É uma palavra-chave do algoritmo
lista-de-identificadores
São os nomes escolhidos para as variáveis, que
devem estar separados por vírgulas
nome-do-tipo
É uma das três palavras-chaves, numérico, lógico
ou literal que indicam o tipo associado às variáveis.
Exemplos:
• declare NomeDoFuncionario, CPF literal;
• declare Salario, HoraExtra numérico;
• declare PossuiDependentes lógico;
2.4 Expressões Aritméticas
Denomina-se expressão aritmética aquela cujos operadores são aritméticos e cujos
operandos são constantes e/ou variáveis do tipo numérico.
17
O conjunto de operações básicas adotado é o que se conhece da Matemática, a
saber:
• Adição
• Subtração
• Multiplicação
• Divisão
• Potenciação
• Radiciação
Exemplos:
•X+Y
• X – 10
• 2 * Nota
• TOTAL / N
• SOMA ** 2
A notação utilizada para expressões aritméticas nos algoritmos é, basicamente, a
mesma da Matemática, a menos das seguintes restrições:
1. Não é permitido omitir o operador de multiplicação, o que é comum nas
expressões matemáticas. Isto evita confusão quanto aos nomes de variáveis, pois numa
expressão da forma AB+C, como saber se AB é o nome de uma variável ou a
multiplicação entre os conteúdos de duas variáveis, cujos termos são A e B? Assim, será
utilizado o asterisco (*) para representar o operador da multiplicação.
2. Nas expressões aritméticas, as operações guardam entre si uma relação de
prioridade, tal como na matemática:
PRIORIDADE
OPERAÇÃO
1ª
potenciação, radiciação
2ª
multiplicação, divisão
3ª
adição, subtração
Para se obter uma seqüência de cálculo diferente, vários níveis de parênteses
podem ser usados para quebrar as prioridades definidas. Não é permitido o uso de
colchetes e chaves, uma vez que estes símbolos são utilizados nos algoritmos para
outras finalidades.
18
Funções
Além das operações básicas, algumas funções muito comuns na Matemática
podem ser usadas nas expressões aritméticas. A tabela a seguir apresenta algumas das
principais funções e o resultado fornecido por cada uma delas.
Função
LOG (EA)
LN (EA)
EXP (EA)
ABS (EA)
TRUNCA (EA)
ARREDONDA (EA)
QUOCIENTE (EAx,EAy)
RESTO ( EAx,EAy)
(EA)2
RAIZ(EA)
SENO(EA)
COSSENO (EA) OU COS(EA)
ARCTAN (EA)
Resultado
Logaritmo na base 10 de EA
Logaritmo Neperiano de EA
Exponencial de EA
Valor Absoluto de EA
Parte inteira de EA
Arredondamento de EA
Quociente inteiro da divisão de EAx por EAy
Resto da divisão de EAx por EAy
O quadrado de EA
A raiz quadrada de EA
Seno de EA (EA dado em radiandos)
Cosseno de EA ( EA dado em radiandos)
Arco Tangente de EA (radiandos)
Resultado
Real
Real
Real
Real/Inteiro
Inteiro
Inteiro
Inteiro
Inteiro
Real/Inteiro
Real
Real
Real
Real
2.5 Expressões Lógicas
É comum nos algoritmos surgirem situações em que a execução de uma ação está
sujeita a uma certa condição. Esta condição é representada no texto do algoritmo por
meio de uma expressão lógica.
Denomina-se expressão lógica a expressão cujos operadores são lógicos e cujos
operandos são relações, constantes e/ou variáveis do tipo lógico.
Relações
Uma expressão relacional, ou simplesmente relação, é uma comparação realizada
entre dois valores do mesmo tipo básico. Estes valores são representados na relação
através de constantes, variáveis ou expressões aritméticas (para o caso de valores
numéricos). Os operadores relacionais, que indicam a comparação a ser realizada entre
os termos da relação, são conhecidos da Matemática, a saber:
Símbolo
=
≠
>
<
>=
<=
Relação
igual a
diferente de
maior que
menor que
maior ou igual a
menor ou igual a
O resultado obtido de uma relação é sempre um valor lógico.
19
Operadores Lógicos
A Álgebra das Proposições define três conectivos usados na formação de novas
proposições a partir de outras já conhecidas. Estes conectivos são os operadores nas
expressões lógicas, a saber:
OPERADOR
E
OU
NÃO
ALGORITMO
e
ou
não
SÍMBOLO
∧
∨
¬
TIPO DE OPERADOR
CONJUNÇÃO
DISJUNÇÃO
NEGAÇÃO
Neste contexto considera-se uma proposição como sendo uma variável lógica, uma
relação ou uma expressão lógica composta.
Conjunção: p ∧ q
Duas proposições quaisquer podem ser combinadas pela palavra “e” para formar
uma proposição composta, chamada de conjunção das proposições originais. A conjunção
de duas proposições p e q é representada simbolicamente por
p∧q
p e q são chamados fatores da expressão.
Exemplo:
• Seja p “Está chovendo” e seja q “O Sol está brilhando”. Assim, p ∧ q corresponde
à proposição “Está chovendo e o Sol está brilhando”.
O verdadeiro valor da proposição p ∧ q satisfaz a seguinte propriedade:
V1: Se p é verdadeiro e se q é verdadeiro, então p ∧ q será verdadeiro; caso
contrário p ∧ q será falso.
Um meio conveniente de estabelecer V1 consiste em organizar a seguinte tabelaverdade:
p
V
V
F
F
q
V
F
V
F
p∧q
V
F
F
F
20
Disjunção: p ∨ q
Duas proposições quaisquer podem ser combinadas pela palavra “ou” para formar
uma proposição composta, chamada de disjunção das proposições originais. A disjunção
de duas proposições p e q é representada simbolicamente por
p∨q
Exemplo:
• Seja p “Pedro estudou inglês na universidade” e seja q “Pedro morou nos Estados
Unidos”. Assim, p ∨ q corresponde à proposição “Pedro estudou inglês na universidade ou
morou nos Estados Unidos”.
O valor verdade da proposição p ∨ q satisfaz a seguinte propriedade:
V2: Se p é verdadeiro ou se q é verdadeiro, ou ambos são verdadeiros, então p ∨ q
será verdadeiro; caso contrário p ∨ q será falso.
V2 também pode ser escrito na forma de uma tabela-verdade:
p
V
V
F
F
q
V
F
V
F
p∨q
V
V
V
F
Negação: ~ p ou ¬ p
Dada uma proposição p qualquer, uma outra proposição, chamada negação de p,
pode ser formada escrevendo-se “É falso que …” antes de p ou, se possível, inserindo em
p a palavra “não”. Simbolicamente, a negação de p é designada por
~ p ou ¬ p
Exemplo:
• Seja p “Paris está na França” então ~ p pode ser escrita como: “É falso que Paris
esteja na França” ou “Paris não está na França”. O valor verdade da proposição ~ p
satisfaz a seguinte propriedade:
V3: Se p é verdadeiro, então ~ p é falso, caso contrário ~ p é verdadeiro.
V3 também pode ser escrito na forma de uma tabela-verdade:
p
V
F
21
¬p
F
V
Se p for a sentença “Pedro é alto e magro”, então a sentença ~ p será “É falso que
Pedro seja alto e magro”, que pode ser reformulada como “Pedro não é alto ou não é
magro”. Isso não é a mesma proposição que “Pedro é baixo e gordo”.
Tautologia e Contradição
Seja uma proposição A formada pela conexão das proposições p,q,..., etc. Se A é
sempre verdadeira independente dos valores das proposições p,q,..., etc. serem
verdadeiros ou falsos, diz-se que A é uma TAUTOLOGIA. Se A é sempre falsa
independente dos valores de p,q,..., etc. serem verdadeiros ou falsos, diz-se que A é uma
CONTRADIÇÃO.
Qual das proposições abaixo é uma tautologia e qual é uma contradição?
a) p ^ ~p
b) p v ~p
Prioridade
Como é possível ter mais de um operador lógico na mesma expressão uma ordem é
preciso ser imposta. A relação de prioridade guarda a seguinte ordem:
Prioridade
1ª
2ª
3ª
4ª
5ª
Operador
Aritmético
Relacional
Não
E
OU
2.6 Expressões Literais
Uma expressão literal é aquela formada por operadores literais e operandos que
são constantes e/ou variáveis do tipo literal.
Supondo que A e B sejam duas variáveis literais e que o símbolo “|” é um
operador de concatenação de literais, a expressão A | B fornece como resultado um
único literal formado pelo conteúdo de A seguido do conteúdo de B.
22
2.7 Comando de Atribuição
Comando é a descrição de uma ação a ser executada em um dado momento. O
comando de atribuição permite que se forneça um valor a uma certa variável, onde a
natureza deste valor tem de ser compatível com o tipo da variável na qual está sendo
armazenado.
Formato:
Identificador ← expressão
Onde:
Identificador
←
expressão
É o nome da variável à qual está sendo atribuído o
valor;
É o símbolo de atribuição
Pode ser uma expressão aritmética, expressão lógica
ou expressão literal de cuja avaliação é obtido o valor a
ser atribuído à variável.
Exemplos:
•K ←1
• COR ← “azul“
• Media ← (N1 + N2) / 2
• Sim ← (X = 0) e (Y ≠ 2)
Nos comandos em que o valor é representado por uma expressão aritmética ou
lógica, estas devem ser avaliadas em primeiro lugar para que, então, o resultado obtido
seja armazenado na variável.
2.8 Comandos de Entrada e Saída
As unidades de entrada e saída são dispositivos que possibilitam a comunicação
entre o usuário e o computador. Como determinar o momento da entrada dos dados para
o programa e a saída dos resultados obtidos para o usuário? Os comandos de entrada e
saída são as ferramentas para esta finalidade.
23
Formato de um comando de entrada:
leia lista-de-identificadores
Onde:
leia
É uma palavra-chave;
São os nomes das variáveis, separados por vírgula,
nas quais serão armazenados os valores
provenientes do meio de entrada.
Exemplo:
Supondo que NOTA e NUM sejam variáveis do tipo numérico, o comando:
leia NOTA, NUM
Indica que dois valores numéricos serão lidos de uma unidade de entrada, quando
este comando for executado. Analogamente, um comando de saída tem a forma geral:
Formato de um comando de saída:
escreva lista-de-identificadores e/ou constantes
Onde:
escreva
É uma palavra-chave
São os nomes das variáveis mostrados ao usuário
através de um meio de saída.
Exemplo:
O comando:
escreva A, X, 35
Indica que a constante 35 e mais os conteúdos das posições de memória,
representados pelos identificadores A e X, serão exibidos em uma unidade de saída.
24
3 Fundamentos dos Algoritmos Estruturados
Continuação
"Não tenhamos pressa. Mas não percamos tempo."
"O único progresso verdadeiro é o progresso moral. O resto é
simplesmente ter mais ou menos bens."
"O que as vitórias têm de mau é que não são definitivas. O que as
derrotas têm de bom é que também não são definitivas."
José Saramago
3.1 Estrutura Seqüencial
Num algoritmo aparecem em primeiro lugar as declarações seguidas por
comandos que, se não houver indicação em contrário, deverão ser executados numa
seqüência linear, seguindo-se o texto em que estão escritos, de cima para baixo.
Exemplo
Algoritmo
declare A, B, C numérico
leia A, B
C ← (A + B)
escreva A, B, C
Fim_Algoritmo.
Neste exemplo, após serem definidos os tipos das variáveis A, B, C, os valores de
A e B serão lidos, o valor de C calculado e os valores contidos em A, B e C serão escritos.
3.2 Estrutura Condicional
A estrutura condicional permite a escolha do grupo de ações e estruturas a ser
executado quando determinadas condições são ou não satisfeitas. A estrutura condicional
pode ser apresentada através de uma estrutura simples ou de uma estrutura composta.
Formato de uma Estrutura Condicional Simples
se condição
então seqüência de comandos
25
Exemplo
Algoritmo
declare A, B, C numérico
leia A, B, C
se A + B < C
então escreva “MENSAGEM”
Fim_Algoritmo.
Formato de uma Estrutura Condicional Composta
se condição
então seqüência 1 de comandos
senão seqüência 2 de comandos
Neste caso, a seqüência 1 de comandos só será executada se a condição for
verdadeira e a seqüência 2 de comandos só será executada se a condição for falsa.
Exemplo
Algoritmo
declare A, B, C, D numérico
leia A, B
se A = B
então inicio
C ← 1,5
D ← 2,5
fim
senão inicio
C ← -1,5
D ← -2,5
fim
escreva C, D
Fim_Algoritmo.
3.3 Estruturas de Repetição
A estrutura de repetição permite que uma seqüência de comandos seja executada
repetidamente até que uma determinada condição de interrupção seja satisfeita. A
condição de interrupção que deve ser satisfeita é representada por uma expressão lógica.
26
3.3.1 Comando Enquanto
Enquanto o valor da condição for verdadeiro, as ações dos comandos são
executadas. Quando for falso, o comando é abandonado. Se já da primeira vez o
resultado é falso, os comandos não são executados nenhuma vez.
Formato do comando Enquanto
enquanto condição faça
início
comandos
fim
Exemplo
{Objetivo: ler, testar e escrever dez números.}
Algoritmo
declare X,Y, L numérico
L←0
enquanto L <= 10 faça
início
leia X,Y
se X > Y
então escreva X
senão escreva Y
L←L+1
fim
Fim_Algoritmo.
3.3.2 Comando Repita
O funcionamento deste comando é o seguinte: os comandos são executados pelo
menos uma vez. Quando a condição é encontrada, ela é testada. Se for verdadeira o
comando seguinte será executado. Se for falsa, os comandos voltam a ser executados.
Em outras palavras os comandos são executados até que a condição se torne verdadeira.
Formato do comando Repita
repita
comandos
até condição
27
Exemplo
{Objetivo: ler, testar e escrever dez números.}
Algoritmo
L←0
repita
leia X,Y
se X > Y
então escreva X
senão escreva Y
L←L+1
até L > 10
Fim_Algoritmo.
3.3.3 Comando For
O comando para é, na verdade, o comando enquanto utilizando uma variável de
controle, escrito numa notação compactada. Neste caso existirá sempre uma inicialização
da variável de controle, um teste para verificar se a variável atingiu o limite e um
acréscimo na variável de controle.
Formato do comando Repita
para var de val_num_1 até val_num_2 [ passo val_num_3] faça
início
comandos
fim
Onde:
var - Variável de controle tipo numérico (contador);
val. num. 1 - Valor numérico que representa o estado inicial do contador;
val. num. 2 - Valor numérico que representa o estado final do contador;
val. num. 3 - Valor numérico que representa o incremento do contador.
Exemplo
{Objetivo: ler, testar e escrever dez números, utilizando a estrutura PARA.}
Algoritmo
para L de 1 até 10 passo 1 faça
início
leia X,Y
se X > Y
então escreva X
senão escreva Y
fim
Fim_Algoritmo.
28
29
4 Estruturas Básicas de Dados
"Enquanto os sábios pensam sem certeza, os idiotas atacam de
surpresa."
"Se não houver frutos, valeu a beleza das flores; se não houver flores,
valeu a sombra das folhas; se não houver folhas, valeu a intenção da
semente."
Henfil
4.1 Variáveis Compostas Homogêneas
Variáveis compostas homogêneas correspondem a posições de memória,
identificadas por um mesmo nome, individualizadas por índices e cujo conteúdo é de
mesmo tipo.
O conjunto de 10 notas dos alunos de uma disciplina pode constituir uma variável
composta. A este conjunto associa-se o identificador NOTA que passará a identificar não
uma única posição de memória, mas 10.
A referência ao conteúdo do n-ésimo elemento do conjunto será indicada pela
notação NOTA[n], onde n é um número inteiro ou uma variável numérica contendo um
valor inteiro.
Variáveis Compostas Unidimensionais
Conjuntos de dados referenciados por um mesmo nome e que necessitam de
somente um índice para que seus elementos sejam endereçados são ditos compostos
unidimensionais.
Exemplos:
São unidimensionais as variáveis NOTA, IDADE e NOME mostradas a seguir:
72
NOTA
40 50
65
20
IDADE
21 22
19
M
NOME
A R
I
A
30
Declaração
A declaração de variáveis compostas unidimensionais é feita através da seguinte
declaração:
Formato
declare identificador [tamanho] nome_do_tipo
Onde:
declare
identificador
É o nome escolhido para a variável
tamanho
É a quantidade de elementos
nome-do-tipo
É uma das três palavras-chaves, numérico, lógico ou literal
que indicam o tipo associado às variáveis.
Exemplos
• declare Nota[10] numérico
• declare Nome[20] literal
Exemplo de Algoritmo
Preencher uma variável do tipo numérico contendo 6 posições com o valor 2:
Algoritmo
declare N[6], contador numérico
contador ← 1
enquanto contador <= 6 faça
início
N[contador] ← 2
contador ← contador + 1
fim
Fim_Algoritmo.
31
Variáveis Compostas Multidimensionais
Conjuntos de dados referenciados por um mesmo nome e que necessitam de mais
de um índice para ter seus elementos individualizados são ditos multidimensionais.
Exemplo
É bidimensional a variável Matriz mostrada a seguir:
Matriz
72 40 50 65
40 34 98 23
39 45 22 11
Nas variáveis bidimensionais, o primeiro índice representa a linha, o segundo, a
coluna.
Matriz[2,3] referencia o elemento que está na segunda linha e terceira coluna, cujo
conteúdo é 98.
Declaração
A criação de estruturas de dados na forma
multidimensionais é feita através da seguinte declaração:
de
variáveis
compostas
Formato
declare identificador[dimensão1, dimensão2, …, dimensãoN] nome_do_tipo
Onde:
declare
Identificador
É o nome da variável
dimensão1, …
São os limites dos intervalos de variação dos índices da
variável, onde cada par de limites está associado a um
índice
nome-do-tipo
É uma das três palavras-chaves, numérico, lógico ou
literal que indicam o tipo associado às variáveis.
32
Exemplos
• declare Matriz[10, 10] numérico;
• declare Semana[7, 20] literal;
Exemplo de Algoritmo
Ler duas matrizes A e B de ordem 10x10 e apresentar o resultado da operação
A+ B:
Algoritmo
declare A[10,10],B[10,10] numérico
i, j numérico
para i de 1 até 10 passo 1 faça
para j de 1 até 10 passo 1 faça
inicio
leia A[i, j]
leia B[i, j]
fim
para i de 1 até 10 passo 1 faça
para j de 1 até 10 passo 1 faça
escreva A[i, j] + B[i, j]
Fim_Algoritmo.
4.2 Variáveis Compostas Heterogêneas
Variáveis compostas heterogêneas são conjuntos de dados logicamente
relacionados, mas de tipos diferentes (numérico, literal, lógico). São também conhecidos
como registros ou estruturas.
Os registros correspondem a conjuntos de posições de memória conhecidos por
um mesmo nome e individualizados por identificadores associados a cada conjunto de
posições.
Na variável composta homogênea, a individualização de um elemento é feita
através de índices, já no registro cada componente é individualizado pela explicitação de
seu identificador.
Declaração
Criam-se estruturas de dados agrupados na forma de registros através da seguinte
declaração:
Formato:
declare identificadores registro (componentes)
Onde:
declare
identificadores
São os nomes das variáveis que estão sendo associadas aos
registros
registro
Palavra chave
Componentes
São declarações e/ou identificadores de variáveis compostas,
separados por vírgula
Exemplo:
Declarar o registro cadastro que tem a seguinte forma:
CADASTRO
Nome
Rua
Sexo
Número
Nascimento
CEP
CPF
declare CADASTRO registro (Nome, Rua, Sexo literal,
Numero, CEP numérico,
Nascimento literal,
CPF, RG numérico)
Exemplo:
Cadastrando uma conta bancária.
Algoritmo
declare conta[1:15] registro (num, saldo numerico, nome literal)
i numerico
escreva “Digite o número da conta, o nome e o saldo”
para i de 1 até 15 faça
inicio
leia conta [ i ].num, conta [ i ].nome, conta [ i ].saldo
{demais comandos}
fim
Fim_Algoritmo.
RG
33
34
5 Modularização e Funções
"Quem vai, vai. Quem não vai, não vai.”
Simplício
"O homem é a pressão que ele faz.”
Alessandro Bestial
5.1 Introdução
No final da década de 60 o mundo viveu a “crise do software”. Os custos das
atividades de programação se elevavam a cada ano e em contrapartida os custos de
hardware caiam devido ao avanço da tecnologia. Por não existir uma metodologia os
programas eram cheios de erros e com alto custo de desenvolvimento e manutenção.
A programação estruturada é hoje o resultado de uma série de estudos e
propostas de disciplinas e metodologias para o desenvolvimento de software. Conceitos
associados como técnica de refinamentos sucessivos e modularização de programas
integram o ferramental para a elaboração de programas visando, principalmente, a
confiabilidade, legibilidade, manutenibilidade e flexibilidade.
Pode-se reunir as idéias da programação estruturada em três grupos:
•
•
•
Desenvolvimento de algoritmos por fases ou refinamentos sucessivos;
Uso de um número muito limitado de estruturas de controle;
Transformação de certos refinamentos sucessivos em módulos.
Um módulo é um grupo de comandos, constituindo um trecho de algoritmo, com
uma função bem definida e o mais independente possível em relação ao resto do
algoritmo.
Todo módulo é constituído por uma seqüência de comandos que operam sobre um
conjunto de objetos, que podem ser globais ou locais.
Objetos globais são entidades que podem ser usadas em módulos internos a
outro módulo do algoritmo onde foram declaradas.
Objetos locais são entidades que só podem ser usadas no módulo do algoritmo
onde foram declaradas.
A comunicação entre módulos deverá ser feita através de vínculos, utilizando-se
objetos globais ou transferência de parâmetros.
35
A divisão do algoritmo em módulos traz os seguintes benefícios:
•
•
•
Manutenção simples (módulos independentes);
Elaboração e testes em separado;
Reutilização do módulo em outros programas.
5.2 Ferramentas para modularização
Como ferramentas de modularização podemos destacar as sub-rotinas e as
funções.
Os módulos de programação servem basicamente a três objetivos:
•
•
•
Repetição de código;
Dividir e estruturar melhor um algoritmo;
Aumentar a legibilidade de um algoritmo.
Sub-rotinas e funções são módulos hierarquicamente subordinados a um algoritmo,
comumente chamado de módulo principal. Da mesma forma, uma sub-rotina ou uma
função pode conter outras sub-rotinas e funções aninhadas.
A sub-rotina e a função são criadas através das suas declarações em um algoritmo.
Para serem executadas, necessitam de ativação provocada por um comando de
chamada.
5.2.1 Sub-rotinas
Sintaxe
Subrotina NOME (lista_de_parâmetros_formais)
declarações dos objetos locais à sub-rotina;
comandos da sub-rotina;
Fim_sub_rotina NOME
A chamada de uma sub-rotina é feita com uma referência a seu nome e a indicação
dos parâmetros atuais no local do algoritmo onde a sub-rotina deve ser ativada, ou seja,
onde a sua execução deve ser iniciada. A forma geral para a ativação de uma sub-rotina é
a seguinte:
NOME (lista_de_parâmetros_atuais)
36
5.2.2 Funções
Sintaxe
Função tipo NOME (lista_de_parâmetros_formais)
declarações dos objetos locais à função;
comandos da função;
retorne valor
Fim_função NOME
A chamada de uma função é feita com uma referência a seu nome e a indicação
dos parâmetros atuais no local do algoritmo onde a função deve ser ativada. Pode-se
chamar uma função de várias formas:
valor ← NOME (lista_de_parâmetros_atuais)
escreva NOME (lista_de_parâmetros_atuais)
As funções, embora bastante semelhantes às sub-rotinas, têm a característica
especial de retornar ao algoritmo que as chamou um valor associado ao seu nome.
5.3 Recursividade
Uma rotina é chamada recursiva quando na sua implementação existe uma
chamada da própria rotina. Esta chamada recebe o nome de chamada recursiva. A
recursividade é utilizada para simplificar lógica de programação. Quase sempre substitui
uma repetição, e como tal deve ter uma condição que determine a interrupção da
repetição (recursão). No entanto, a solução recursiva de um problema qualquer é quase
sempre menos eficiente (em tempo de computação) do que a versão iterativa
correspondente.
Podemos dividir uma rotina recursiva em duas partes básicas:
•
A condição de parada da recursividade
•
Chamada(s) recursiva(s)
Em termos de programação, uma rotina recursiva pode ser de forma direta ou
indireta. Em geral, uma rotina recursiva (direta) R pode ser expressa como uma
composição formada por um conjunto de comandos C (que não contém chamadas a R) e
uma chamada (recursiva) à rotina R:
37
R = [C, R]
Pode-se ter também uma forma indireta de recursão, na qual as rotinas são
conectadas através de uma cadeia de chamadas sucessivas que acaba retornando a
primeira que foi chamada:
R1 = [C1, R2]
R2 = [C2 , R3]
R3 = [C3, R4]
...
Rn = [Cn, R1]
Assim, diz-se que uma rotina R é indiretamente recursiva se ela contém uma
chamada a outra rotina S, que por sua vez contém uma chamada direta ou indireta a R.
Note que a recursão nem sempre é explícita e, às vezes, pode ser difícil percebê-la
através de ma simples leitura da rotina.
Todo algoritmo deve ser executado em tempo finito. Para garantir que uma
chamada recursiva não criará um “looping” é necessário que ela esteja condicionada a
uma expressão lógica que, em algum instante, se tornará falsa e terminará a recursão.
Assim, uma rotina recursiva é melhor representada por R = [C, T→R], onde T→R indica
que a rotina R somente será chamada se o teste T for satisfeito.
A técnica básica para garantir o término da execução de um algoritmo recursivo
consiste em:
•
exprimir T em termos de uma função f(x), tal que f(x) ≤ 0 implica uma condição de
parada;
•
mostrar que f(x) decresce a cada passo de repetição, isto é, que temos a forma
R(x) = [C,(f(x)>0)→ R(x-1)], onde x decresce a cada chamada.
Na prática, ao definir uma rotina recursiva, dividimos o problema da seguinte
maneira:
Solução trivial: dada por definição; isto é, não necessita da recursão para ser
obtida. Esta parte do problema é resolvida pelo conjunto de comandos C.
Solução geral: parte do problema que em essência é igual ao problema original,
sendo porém menor. A solução, neste caso, pode ser obtida por uma chamada recursiva
R(x-1)
Exemplo: Cálculo de Fatorial. Esta operação matemática é definida de forma
recursiva:
Solução trivial
0! = 1 {dada por definição}
Solução geral
n! = (n-1)! * n para n > 0
{requer reaplicação da rotina para (n-1)!}
Então:
4! = 3! * 4 = 2! * 3 * 4 = 1! * 2 * 3 * 4 = 0! * 1 * 2 * 3 * 4 = 1 * 1 * 2 * 3 * 4 = 24
Algoritmo Exemplo – Cálculo do Fatorial:
Algoritmo
declare numero numerico
função numerico fatorial (valor numerico)
escreva “digite um número para calcular o fatorial”
leia numero
escreva “O fatorial é “, fatorial (numero)
Fim_Algoritmo.
função numerico fatorial (numero numerico)
se numero = 0
então retorne 1
senão retorne numero * fatorial (numero – 1)
fim função fatorial
38
39
6 Bibliografia
FARRER, H. et. alli. Algoritmos Estruturados. 3a. edição. Rio de Janeiro. LTC – Livros
Técnicos e Científicos Editora S/A, 1999.
GUIMARÃES, A. M. e LAGES, N. A. C. Algoritmos e Estrutura de Dados. 1a. edição. Rio
de Janeiro. LTC – Livros Técnicos e Científicos Editora S/A, 1985.
MACHADO, F. B. e MAIA, L. P. Arquitetura de Sistemas Operacionais. 3a. edição. Rio de
Janeiro. LTC – Livros Técnicos e Científicos Editora S/A, 2002.
Observação: Material elaborado pelos professores Fabiana Costa Guedes e Sandro Carvalho
Izidoro, com base nas notas de aula do professor Edmilson Marmo Moreira (ECO - UNIFEI Itajubá)

Aulas Teóricas - BAC004 - Técnicas de Programação

Transcrição

Documentos relacionados

Maior substring em comum

Em uma pizzaria, cada tulipa de chopp custa R$ 0,80 e uma pizza

Contadores, somadores e acumuladores

Conceitos Iniciais sobre Algoritmos e

Teoria dos Grafos Aula 14

Lista 4

Ficha prática - Departamento de Engenharia Electrotécnica

Diagramas Nassi Schneiderman

Minimum Spanning Tree Algoritmos de Prim e Kruskal Algoritmo de

AZTEC AC1000 Automatic