Baixe Algoritmo e Estrutura de Dados e outras Notas de estudo em PDF para Algoritmos, somente na Docsity! UNIVERSIDADE FERNANDO PESSOA PROGRAMAÇÃO I INTRODUÇÃO À ALGORITMIA E ESTRUTURAS DE DADOS José Vasconcelos Luís Paulo Reis Engenharia do Ambiente Engenharia Civil Engenharia Informática Engenharia da Qualidade 1º ANO Março 2002 Programação I Universidade Fernando Pessoa 2 Índice 1. ALGORITMOS E A RESOLUÇÃO DE PROBLEMAS ......................................... 3 1.1. RESOLUÇÃO DE PROBLEMAS ................................................................................... 3 1.2. APROXIMAÇÃO DESCENDENTE (TOP-DOWN APPROACH) ........................................... 4 1.3. NOÇÃO FORMAL DE ALGORITMO.............................................................................. 6 1.4. CARACTERÍSTICAS DE UM ALGORITMO ................................................................... 6 2. ESTRUTURAS DE DADOS........................................................................................ 7 2.1. ESTRUTURAS DE DADOS PRIMITIVAS........................................................................ 8 2.1.1. Tipo de dados booleano.................................................................................. 8 2.1.2. Tipo de dados numérico ................................................................................. 8 2.1.3. Tipo de dados alfanumérico ........................................................................... 9 2.1.4. Representação dos dados ............................................................................... 9 2.2. ESTRUTURAS DE DADOS NÃO PRIMITIVAS .............................................................. 12 2.2.1. Vectores ........................................................................................................ 12 2.2.2. Matrizes .............................................................................................................. 13 3. NOTAÇÃO ALGORÍTMICA....................................................................................... 14 3.1. PSEUDOCÓDIGO ..................................................................................................... 14 3.1.1. Instrução de atribuição ................................................................................ 15 3.1.2. Leitura e escrita de dados ............................................................................ 16 3.1.3. Estrutura condicional ................................................................................... 17 3.1.4. Instruções de repetição................................................................................. 18 3.1.5. Operações e Expressões Aritméticas............................................................ 21 3.1.6. Operadores e operações relacionais............................................................ 21 3.1.7. Operadores e operações lógicas .................................................................. 22 3.2. ALGORITMOS PROPOSTOS ...................................................................................... 23 3.3. DIAGRAMAS DE FLUXO (FLUXOGRAMAS).............................................................. 30 3.3.1. Notação gráfica ............................................................................................ 30 3.3.2. Fluxogramas vs. Estruturas de controlo ...................................................... 30 3.3.3. Algoritmo em pseudocódigo / Fluxograma .................................................. 33 4. PROVA E TESTE DE ALGORITMOS................................................................... 34 Programação I Universidade Fernando Pessoa 5 • Por exemplo, para os passos 2.2, 2.3, 3.2 e 3.3 poderiam também derivadas descrições mais precisas e detalhadas, do tipo: Repita ... até ... • Aumento do detalhe do algoritmo pode continuar quase indefinidamente. • Grau de detalhe depende das necessidades do agente que vai executar o algoritmo. Exemplo 2: Encontrar o número de telefone que corresponde a um dado nome numa lista telefónica. Algoritmo Lista-Telefónica Passo Descrição 1 Encontre a página da lista que contém o último apelido do nome 2 Encontre na página determinada no passo 1, o nome procurado Aumentando o detalhe, obtemos instruções elementares não ambíguas: 1.1 Coloque o marcador D (dedo) ao acaso na lista 1.2 Abra a lista 1.3 Último apelido está contido numa das páginas (esquerda ou direita)? Se sim, siga para o passo 2 1.4 Último apelido precede a página esquerda? Se sim, coloque o marcador atrás da página esquerda; se não, coloque o marcador à frente da página direita. 1.5 Vá para 1.2 (retome a sequência de instruções no passo 1.2) Eliminando formulações mal definidas (ex.: coloque o marcador atrás): 1.1.1 Torne A igual ao apelido do nome a seleccionar (atribuição à variável A) 1.1.2 Escolha uma posição n ao acaso no intervalo [1,N] (n representa o número de páginas útil da lista) 1.1.3 Torne D igual a n (atribua à variável D o valor n) 1.2 Abra a lista no local seleccionado pelo marcador D 1.3 A está contido numa das páginas (esquerda ou direita)? Se sim, siga para o passo 2. 1.4 A precede o primeiro apelido da página esquerda? Se sim, faça n igual a (n+1)/2 (actualização do valor de n); se não, faça n igual a (N+n)/2. 1.5 Vá para 1.2 (retome a sequência de instruções no passo 1.2) Programação I Universidade Fernando Pessoa 6 1.3. Noção formal de algoritmo Um algoritmo é um processo discreto (sequência de acções indivisíveis) e determinístico (para cada passo da sequência e para cada conjunto válido de dados, corresponde uma e uma só acção) que termina quaisquer que sejam os dados iniciais (pertencentes a conjuntos pré-definidos). Um algoritmo é constituído por um conjunto de expressões simbólicas que representam acções (escolher, atribuir, etc.), testes de condições (estruturas condicionais) e estruturas de controlo (ciclos e saltos na estrutura sequencial do algoritmo) de modo a especificar o problema e respectiva solução. 1.4. Características de um Algoritmo Entradas Quantidades inicialmente especificadas (por exemplo, através de instruções de leitura). Saídas Uma ou mais saídas (habitualmente por instruções de escrita) Finitude A execução deve terminar sempre num número finito de passos. Precisão Todos os passos do algoritmo devem ter um significado preciso não ambíguo, especificando exactamente o que deve ser feito. Para evitar a ambiguidade das linguagens humanas (linguagens naturais), linguagens especiais (denominadas linguagens de programação) foram criadas para exprimir algoritmos. Eficácia Os passos devem conduzir à resolução do problema proposto. Devem ainda ser executáveis numa quantidade finita de tempo e com uma quantidade finita de esforço. Eficiência Em muitos casos colocam-se questões de eficiência a um algoritmo. Programação I Universidade Fernando Pessoa 7 2. Estruturas de Dados A resolução de problemas através de algoritmos requer a representação de entidades e objectos reais em itens de dados. As diferentes formas nas quais os itens de dados são logicamente relacionados definem diferentes estruturas de dados (figura 2). Esta secção apresenta um conjunto de estruturas de dados classificadas como primitivas e não primitivas. Estruturas de dados primitivas são directamente manipuladas em linguagem máquina (binária), enquanto que estruturas de dados não primitivas (ou complexas) representam estruturas de informação em conjuntos (formados por estruturas de dados primitivas) logicamente relacionados. Figura 2: Estruturas de Dados A representação de uma particular estrutura de dados na memória do computador é designado por estrutura de armazenamento. É fundamental saber distinguir estes dois conceitos: estrutura de dados vs. estrutura de armazenamento. Existem diferentes configurações de armazenamento correspondentes a uma particular estrutura de dados. A preocupação desta disciplina centra-se na forma como representamos entidades e objectos reais através de estruturas de dados e não na forma como os armazenamos fisicamente na memória (primária ou secundária) do computador. Primitivas Não Primitivas (Complexas) { Boolenas (lógicas) Numéricas Caracteres alfanuméricos Ponteiros { InteirosReais { Comprimento fixo (variáveis indexadas) Comprimento variável (Listas – adjacência física) Ficheiros (memória secundária) { VectorMatriz {Lineares Não lineares { Bidimensional...Multi-indexado Estruturas de Dados {Pilhas Filas Listas {ÁrvoresGrafos {SequenciaisSequenciais indexados Directos Programação I Universidade Fernando Pessoa 10 Informação Contextual Conteúdo informativo (significado) de um dado, depende do contexto. Por exemplo, o dado 0100 0001, pode representar: 65 Numa operação utilizando binário 41 Numa operação utilizando BCD (“Binary Coded Decimal”) A Símbolo (letra) ASCII MOV A,B Instrução do microprocessador INTEL 8080 O contexto pode depender do uso no problema particular, da posição numa sequência de dados ou da posição física no sistema de computação. Tipo de dados vs. Variáveis vs. Constantes A compreensão dos conceitos anteriores é de fundamental importância para a eficiente construção de algoritmos. Os seguintes exemplos descrevem a diferença entre estes conceitos e o relacionamento lógico entre eles. Exemplo 3 X ← 47 Esta expressão algorítmica simples significa que à variável X foi atribuído o valor (ou constante) 47. Esta operação de atribuição tem por pressuposto (em termos algorítmicos) o facto que X é uma variável do tipo inteiro. Exemplo 4 CAR ← ‘G’ Esta expressão algorítmica simples significa que à variável CAR foi atribuído o valor (ou constante) ‘G’. Esta operação de atribuição tem por pressuposto (em termos algorítmicos) o facto que CAR é uma variável do tipo alfanumérico. Por convenção os valores alfanuméricas são apresentadas entre plicas (ex.: CAR1 ← ‘7’ ou CAR2 ← ‘J’). Programação I Universidade Fernando Pessoa 11 Nomes de variáveis Uma variável é uma entidade que representa um determinado valor e o seu nome é escolhido de forma a reflectir o valor que representa (ex.: a variável MAX pode representar o valor máximo de um conjunto de valores numéricos). Por convenção, um nome de uma variável não deve conter espaços, não deve iniciar por números e não deve conter determinados caracteres especiais, tais como * , = ? , / * ; : . , } [ ] {, etc. O nome de uma variável deve iniciar sempre por uma letra, seguido de um conjunto de caracteres incluindo letras, números e alguns caracteres especiais, como é o caso do caracter ‘_’ que pode ser utilizado para separar palavras que constituem o nome da variável (ex.: NUM_ALUNO). As próximas variáveis são consideradas válidas: NUM N_ALUNO NOMEALUNO NOME_ALUNO X1 Y2 As próximas variáveis são consideradas inválidas: 7NUM Y-Z T/4 U*VAR DUAS-PAL DUAS PALAVRAS Programação I Universidade Fernando Pessoa 12 2.2. Estruturas de dados não primitivas As estruturas de dados não primitivas são definidas através de conjuntos de estruturas de dados primitivas. Conforme a figura 2, existem estruturas de comprimento fixo e de comprimento variável a nível da memória principal (ou primária) do computador, e existem estruturas de dados na forma de ficheiros de dados que são manipuladas na memória secundária (ou permanente) do computador. No contexto desta disciplina de introdução à programação, serão estudadas as estruturas de dados de comprimento fixo (vectores e matrizes) e alguns exemplos de ficheiros de dados e suas aplicações. 2.2.1. Vectores Elementos de um vector (array) são representados através de conjuntos de variáveis de um determinado tipo de dados. Um vector contem um nome ao qual está associado um tipo de dados em função dos dados a manipular pelo vector, um índice do tipo inteiro, e uma dimensão do tipo inteiro. Um vector é apresentado através de um nome e de um índice entre parêntesis rectos. A figura seguinte ilustra a representação e a manipulação dos elementos de um vector. Figura 3: Representação e manipulação de vectores O vector VNUM [I] representado na figura anterior é um vector do tipo numérico (inteiro) com uma dimensão de 8 (variável N) elementos. O acesso a elementos (valores) do vector são efectuados através da utilização de um índice (no exemplo anterior representado na variável I). Por exemplo, o valor associado à posição 6 do vector VNUM é igual a 90. I 34 121 7 78 0 90 3 15 VNUM [ ] I = 1 .. 8 N = 8 VNUM [2] = 121 VNUM [7] = 3 VNUM [12] - indefinido 1 2 3 4 5 6 7 8 I <- 5 VNUM [I] = 0 I <- 1 VNUM [I] = 32 Programação I Universidade Fernando Pessoa 15 Exemplo 5 Algoritmo FACTORIAL. Este algoritmo calcula o factorial de um número inteiro. 1. [Leitura do número] Read (N) 2. [Caso particular de N = Ø ou N = 1] If N=0 Or N=1 Then FACT ← 1 3. [Outros números] Else FACT ← N NUM ← N – 1 Do For I = NUM To 1 Step –1 FACT ← FACT * I 4. [Impressão do resultado (N!)] Print (‘O Factorial de ‘,N,’ é igual a ‘,FACT) 5. [Termina] Exit 3.1.1. Instrução de atribuição A instrução de atribuição é representada através do símbolo ← que é colocado à direita da variável que recebe o valor da atribuição (ex.: FACT ← 1). Ter atenção a diferença entre o sinal de atribuição ← e o símbolo = que é utilizado como operador relacional. Numa instrução de atribuição pode constar variáveis, constantes, operadores e outras funções matemáticas como indica o próximo exemplo. Exemplo 6 VAR ← 12 / 7 FACT ← FACT * NUM N ← MOD (NUM1,NUM2) Programação I Universidade Fernando Pessoa 16 3.1.2. Leitura e escrita de dados Perante a notação algorítmica é possível obter (ou ler) valores de variáveis, assim como escrever (ou imprimir) os valores dessas variáveis através de instruções de leitura (entrada de dados) e instruções de escrita (saída de dados). Leitura de dados Sintaxe: Read (<nome da variavel>) Exemplo 7 Read (N_ALUNO) Exemplo 8 Read (N_ALUNO) Do For I = 1 to N_ALUNO Read (NOME_ALUNO [ I ]) Saída de dados Sintaxe: Write (<nome da variável>) ou Write (<‘texto’>) ou Write (<nome da variável>, ‘texto’ ) ou Write (‘texto’, <nome da variável 1>, ‘texto’ <nome da variável 2>, ‘texto’, ...) Exemplo 9 Write (N_ALUNO) Write (‘só texto ...’) Write (‘O número de alunos é igual a ‘, N_ALUNO) Write (‘O número ’,N_ALUNO,‘ refere-se ao n.º de alunos da disciplina de programação’) Exemplo 10 Read (N) Do For I = 1 to N Write (NOME_ALUNO [ I ]) Programação I Universidade Fernando Pessoa 17 3.1.3. Estrutura condicional If Statement – If ... Then … Else (Se … Então … Senão) Esta declaração representa um teste de condição lógica (se ... então ... senão) na qual é executado um conjunto de instruções consoante a condição especificada for verdadeira ou falsa. A declaração If pode ter uma das seguintes formas: 1. If Condition Then ___________ ___________ … 2. If Condition Then ___________ ___________ … Else ___________ ___________ … A seguir à clausula Then um conjunto de instruções é executado no caso da condição ser verdadeira. Caso contrário (Else – Senão), será executado o conjunto de instruções a seguir à clausula Else. Exemplo 11 If N > 10 Then X ← (X + 15) / 2 Print (X) Exemplo 12 If N > 10 Then X ← (X + 15) / 2 Print (X) Else X ← X * 5 Print (X) Programação I Universidade Fernando Pessoa 20 Do For (Fazer para …) A instrução Do For é utilizada quando é necessário repetir um conjunto de passos um determinado número de vezes. Sintaxe: Do For INDEX = N1 to N2 Step P ___________ ___________ … INDEX indica o índice que é incrementado em cada ciclo de processamento. N1 e N2 referem dois números inteiros representativos do intervalo inferior e superior da sequência de números a executar. A clausula Step determina o incremento na sequência numérica. Por defeito, o Step tem valor 1. Exemplo 16 X ←10 Do For I = 1 to 70 X ← X + 5 Print (X) Exemplo 17 Read (Y) Do For J = 10 to 100 Step 10 Y ← Y + 25 Print (Y) Programação I Universidade Fernando Pessoa 21 Exemplo 18 X ← 0 Do For I = 150 to 5 Step –5 Read (A[ I ]) X ← X + A[ I ] Write (X) 3.1.5. Operações e Expressões Aritméticas A notação algorítmica inclui operações e funções matemáticas que permitem efectuar variados cálculos aritméticos. Dois tipos de valores numéricos são considerados: reais e inteiros. As regras de precedência têm por base as regras padrão das expressões matemáticas. Deste modo, temos por ordem decrescente, os parêntesis - ( ) - a exponenciação (↑), a multiplicação (*), a divisão (/), a adição (+) e finalmente a subtracção (-). Determinadas funções matemáticas podem ser utilizadas na definição de expressões computacionais, tais como: mod(M,N) – função que retorna o resto da divisão de M por N. int(NUM) – função que retorna o parte inteira de um número real. sqr(NUM) – função que retorna a raiz quadrada de um número inteiro ou real. Exemplo 19 X ← (A+B) ↑3 – (A-A/3)*B N ← mod(20,6) RNUM ← sqr(NUM) 3.1.6. Operadores e operações relacionais Os operadores matemáticos relacionais (=, <, >, ≤, ≥, ≠) têm um conjunto de símbolos correspondentes a nível computacional. A nível computacional temos respectivamente os seguintes operadores relacionais: =, <, >, <=, >=, e <>. As expressões lógicas representam relações entre valores do mesmo tipo de dados. Programação I Universidade Fernando Pessoa 22 O resultado da avaliação de uma expressão lógica pode ter um de dois valores possiveis: verdadeiro (true) ou falso (false). Exemplo 20 A ← 20 ( a variável A tem atribuído o valor numérico 20) 1. A <= 10 / 3 + 5 2. A <> A + 10 A relação 1 tem valor falso e a relação 2 tem valor verdadeiro. 3.1.7. Operadores e operações lógicas A notação algorítmica também inclui os seguintes operadores lógicos: Operador Notação Negação not Conjunção and Disjunção or Os operadores lógicos são utilizados em conjunto com os operadores relacionais e aritméticos. Deste modo, é considerada a seguinte ordem de precedência entre operadores. Precedência Operador 1 Parêntesis 2 Aritmético 3 Relacional 4 Lógico Considere o seguinte exemplo assumindo que a variável NUM tem o valor 1. 1. (NUM < 2) and (NUM < 0) 2. (NUM < 2) or (NUM < 0) 3. not(NUM < 2) As expressões 1,2,3 têm valores falso, verdadeiro, e falso respectivamente. A próxima secção propõe um conjunto de algoritmos e respectiva resolução. Programação I Universidade Fernando Pessoa 25 Algoritmo DIAGONAL PRINCIPAL Este algoritmo efectua a leitura de uma matriz quadrada com N linhas e colunas. A matriz é constituída por números inteiros. Determinar os seguintes valores: a) O somatório da diagonal principal da matriz. b) O valor minimo da diagonal principal. c) O valor máximo da diagonal principal. 1. [Leitura da matriz quadrada] Read (N) Do For I = 1 to N Do For J = 1 to N Read (M[I,J]) 2. [Inicializações] SOMA ← Ø MIN ← M[1,1] MAX ← M[1,1] 3. [Tratar os elementos da primeira diagonal da matriz] Do For I = 1 to N [determina o somatório] SOMA ← SOMA + M[I,I] [determina o valor minimo] If M[I,I] < MIN Then MIN ← M[I,I] [determina o valor maximo] If M[I,I] > MAX Then MAX ← M[I,I] 3. [Imprimir os resultados] Write(‘O somatório dos elementos da primeira diagonal da matriz é igual a ‘,SOMA) Write(‘O menor elemento da primeira diagonal da matriz é igual a ‘,MIN) Write(‘O maior elemento da primeira diagonal da matriz é igual a ‘,MAX) 4. [Termina] Exit Programação I Universidade Fernando Pessoa 26 Pesquisa e ordenação de vectores a) Ordenação por selecção Algoritmo ORDENAÇÃO VECTOR Dado um vector K com N elementos, este algoritmo ordena o vector por ordem crescente. 1. [Selecção sucessiva dos valores até ao índice N-1] Do For PASS = 1 To N - 1 MIN ← PASS 2. [Obter o índice do valor mínimo] Do For I = PASS + 1 To N If K[I] < K[MIN] Then MIN ← I 3. [Trocar os valores] If MIN <> PASS Then TEMP ← K[PASS] K[PASS] ← K[MIN] K[MIN] ← TEMP 4. [Termina] Exit A próxima figura ilustra a forma como um determinado vector é ordenado através da selecção e troca sucessiva de valores. Considere o seguinte vector K[ ] de números inteiros e as respectivas passagens até obter a ordenação dos seus elementos. Figura 5: Ordenação dos elementos de um vector por selecção 5 3 7 2 1K[ ] 1 2 3 4 5 1 3 7 2 5 1 2 7 3 5 1 2 3 7 5 1 2 3 5 7 1º Passagem 2º Passagem 3º Passagem 4º Passagem (vector ordenado) Programação I Universidade Fernando Pessoa 27 b) Pesquisa linear Os próximos três algoritmos representam três versões para a resolução do mesmo problema: pesquisar a existência de um dado elemento num determinado vector. Pesquisa linear de elementos de um vector (versão 1.0) Algoritmo PESQUISA_LINEAR_V1.0 Dado um vector K com N elementos (N ≥ 1), este algoritmo permite verificar a existência de um dado elemento (valor) representado pela variável X. 1. [Iniciar a ‘bandeira’] FLAG ← Ø 2. [Pesquisar sucessivamente cada elemento do vector] Do For I = 1 to N If K[I] = X Then Write (‘O valor ’,X, ‘ foi encontrado na posição ’,I) FLAG ← 1 3. [Verificar o sucesso da pesquisa] If FLAG = Ø Then Write(‘O valor’ ,X,’ não foi encontrado) 4. [Termina] Exit NOTA: esta versão é pouco eficiente, na medida em que é necessário efectuar N testes até encontrar um determinado elemento do vector. Os próximos algoritmos (versão 1.1. e 1.2.) apresentam uma forma mais eficiente de resolver este problema. Programação I Universidade Fernando Pessoa 30 3.3. Diagramas de Fluxo (Fluxogramas) Um diagrama de fluxo representa de uma forma gráfica as instruções e respectivas operações incluídas em determinado algoritmo. O objectivo principal de um diagrama de fluxo (ou fluxograma) é facilitar a compreensão e desenvolvimento de algoritmos para a resolução de problemas através da utilização e composição de símbolos gráficos. 3.3.1. Notação gráfica De modo a construir um fluxograma é necessário conhecer a notação gráfica a utilizar e respectivo significado. A próxima tabela apresenta os símbolos (e respectivo significado) utilizados na construção de fluxogramas. Símbolo Significado Inicio / fim do algoritmo Leitura e escrita (entrada e saída) de dados Instruções de atribuição Estrutura condicional 3.3.2. Fluxogramas vs. Estruturas de controlo As estruturas de controlo (condicional e ciclos) apresentadas anteriormente podem ser representadas graficamente conforme os seguintes diagramas. Programação I Universidade Fernando Pessoa 31 ESTRUTURA If ... Then ... Else C A IF C THEN A ELSE B C A IF C THEN A B False True TrueFalse Figura 6: Representação em fluxograma da estrutura If ... Then ... Else ESTRUTURA Do While C WHILE C DO A A True False Figura 7: Representação em fluxograma da estrutura de controlo Do While Programação I Universidade Fernando Pessoa 32 ESTRUTURA Repeat Until C A REPEAT A UNTIL C True False Figura 8: Representação em fluxograma da estrutura de controlo Repeat Until ESTRUTURA For ... To Figura 9: Representação em fluxograma da estrutura de controlo Do For True False For I = X To Y Step P I ← X I >= Y (P<0) I <= Y A I ← I + P