Responde Aí

Algoritmos estruturados

Ver Todos os Exercícios

Teoria

Introdução

Fala aí, aqui é o Guga do Responde Aí! Tudo bem com você?

A programação está rodeada de nomes de pessoas que resolveram inúmeros problemas computacionais complexos através do desenvolvimento de algoritmos para essas soluções, por exemplo: Algoritmo de Dijkstra, Kruskal, Bellman-Ford etc.

Mas qual é o motivo pelo qual os algoritmos são tão importantes?

Nós precisamos aprendê-los para que possamos nos comunicar com o computador, uma vez que todos os programas têm o objetivo de resolver determinados problemas através do processamento de uma máquina. Um algoritmo nada mais é do que uma estrutura que deve ser seguida durante o desenvolvimento desses programas de forma com que o computador entenda o que deve ser feito em uma linguagem mais próxima da computacional.

Algoritmo

Imagine a seguinte situação:

Você decidiu fazer aquele bolo de chocolate delicioso em uma dessas tardes, mas se esqueceu daquele jeitinho especial de se preparar essa sobremesa. Então, decidiu ir à gaveta velha da sua casa e pegar o livro de receitas da sua família.

Bateu aquela fome, né?

Pode parecer estranho, mas a receita que está nesse livro que você acabou de pegar é um algoritmo. Isso acontece porque uma receita é uma sequência de passos bem definidos, pois nós temos tudo aquilo que devemos fazer na ordem correta, por exemplo:

  • Adicione os ovos, chocolate, farinha de trigo, leite, açúcar e a manteiga no recipiente;
  • Misture tudo até que a massa fique homogênea;
  • ...
  • Retire o bolo do forno.

Seguindo cada um desses passos na ordem em que são apresentados, no final nós teremos como resultado aquele super bolo que queríamos comer.

É por esse motivo que os algoritmos são passos bem definidos, que ao serem executados na ordem certinha em que são apresentados, atingem um determinado objetivo.

Algoritmo ou programa?

A verdade é que um programa é um algoritmo. Isso acontece, pois para desenvolvermos programas nós utilizamos as chamadas linguagens de programação.

Então, imagina a linguagem que você está aprendendo agora (C). Ela nada mais é do que uma ferramenta utilizada para converter um algoritmo que nós escrevemos na linguagem natural, como a receita do bolo de chocolate, para um algoritmo em uma linguagem mais próxima daquela que o computador entende (linguagem de máquina).

É por esse motivo que existem inúmeras linguagens de programação. Uma linguagem de programação mais moderna, como por exemplo Python (nós temos um ótimo conteúdo sobre ela aqui no Responde Aí!), consegue realizar essa conversão mantendo sua linguagem mais próxima do natural e por esse motivo é considerada de alto nível. Por outro lado, as linguagens de programação mais antigas (pensa lá para a década de 50) possuem uma proximidade bem maior com a linguagem de máquina e por esse motivo são consideradas de baixo nível.

Sendo assim, um programa nada mais é do que um algoritmo convertido da linguagem natural para instruções em uma linguagem compreendida pelo computador, utilizando-se para isso das linguagens de programação.

Ficou mais fácil de entender, né?

Características de um algoritmo

Todos os algoritmos seguem uma série de características, são elas:

  • Não deve ter instruções com duplo sentido;
  • Deve possuir entradas e saídas bem definidas;
  • Deve ser finito, para isso não deve entrar em instruções com repetições sem fim;
  • Deve ser genérico e entendido de forma clara por todos;
  • Deve ser independente, podendo ser executado em inúmeras linguagens.

Então, sempre que formos criar um algoritmo utilizando a linguagem natural, basta imaginarmos que estamos criando uma receita!

Ou seja, temos que colocar tudo em passos bem claros para atingir um objetivo.

Convertendo um algoritmo em um programa

Que tal aprendermos na prática como realizar a conversão de um algoritmo na linguagem natural para um algoritmo em uma linguagem computacional?

O algoritmo a seguir descreve os passos para o cálculo da média aritmética de dois valores:

  • Ler o primeiro valor;
  • Ler o segundo valor;
  • Somar o primeiro valor com o segundo;
  • Dividir o resultado da soma por 2;
  • Escrever o resultado.

Para convertermos esse algoritmo, basta seguirmos os seguintes passos:

  1. Analisar o problema: o problema que será resolvido é o cálculo da média aritmética de dois valores;
  2. Identificar restrições: as entradas deverão ser apenas números;
  3. Identificar as entradas: dois números;
  4. Identificar as saídas: a média aritmética das entradas;
  5. Descrever a solução.

Para descrevermos a solução para o cálculo da média aritmética de dois valores utilizaremos passos genéricos (que podem ser transferidos para qualquer linguagem de programação):

  • Ler e armazenar o primeiro valor;
  • Ler e armazenar o segundo valor;
  • Somar o primeiro valor com o segundo e armazenar o resultado;
  • Dividir o resultado da soma por 2 e armazenar o resultado;
  • Imprimir o resultado da divisão do somatório por 2.

Pronto! Acabamos de converter o nosso primeiro algoritmo em um programa. No nosso caso, utilizaríamos a linguagem C para codificar esses passos genéricos.

Por enquanto é só, não vai sair daqui sem fazer os exercícios de fixação, hein!?

Estou de olho!

Algoritmo ou programa?

Características de um algoritmo

Convertendo um algoritmo em um programa

Exercícios Resolvidos

Exercício Resolvido #1

Faça um algoritmo na linguagem natural para ler três números, calcular a soma deles e escrever o resultado.

Passo 1

A primeira coisa que nós devemos fazer é descrever os passos de leitura dos números:

Passo 2

Agora que já conhecemos o valor dos números, podemos realizar a soma deles:

Passo 3

Por fim, basta escrevermos o resultado da soma:

Resposta

Juntando tudo, abaixo temos o algoritmo para calcular a soma de três números e escrever o resultado:

Exercício Resolvido #2

Faça um algoritmo na linguagem natural capaz de ler as dimensões de um retângulo (base e altura), calcular e escrever a sua área.

Passo 1

A primeira coisa que nós devemos fazer é descrever os passos de leitura das dimensões do retângulo:

Passo 2

Com o conhecimento das medidas do retângulo, o próximo passo do algoritmo é efetuar o cálculo da área:

Passo 3

Por fim, devemos escrever o resultado dessa multiplicação:

Resposta

Em seguida temos o algoritmo para calcular a área de um retângulo:

Exercício Resolvido #3

Crie um algoritmo capaz de ler 50 números inteiros e ao final informar quantos desses números estão no intervalo entre 10 (inclusive) e 100 (inclusive).

Passo 1

A primeira coisa que nós devemos fazer é descrever o passo de leitura dos 50 números. Como se trata de mais de um número, podemos utilizar uma estrutura de repetição de passo:

Passo 2

Além disso, devemos verificar a cada leitura se o número está o não no intervalo definido no enunciado. Para isso, podemos descrever um passo de verificação:

Vale lembrar que se o número estiver dentro do intervalo, um informe deve ser realizado. Com base nisso, o passo de verificação deve ser seguido de um passo de informe:

Resposta

Agora que já conseguimos descrever os passos essenciais, abaixo temos o algoritmo para ler 50 números e informar quais deles estão dentro do intervalo entre 10 (inclusive) e 100 (inclusive):

Exercício Resolvido #4

Faça um algoritmo para trocar uma lâmpada e realizar o teste dela.

Passo 1

Em primeiro lugar, nós precisamos reconhecer que uma lâmpada está queimada antes de realizar a troca dela. Por esse motivo, o primeiro passo do algoritmo é:

Passo 2

Com o acionamento do interruptor, a lâmpada pode acender ou não. Porém, a troca de uma lâmpada só ocorre se ela estiver queimada, dessa forma já temos uma condição de troca:

Como a condição acima nos confirma que uma lâmpada será trocada, ela deve ser seguida dos passos que efetivamente trocam a lâmpada:

Passo 3

Com a nova lâmpada instalada, devemos verificar se ela também não está queimada. Para isso, podemos adicionar em nosso algoritmo um passo de repetição que irá trocar de lâmpada enquanto as novas instalações não acenderem:

Resposta

Por fim, o algoritmo completo para a troca de uma lâmpada é:

Exercício Resolvido #5

Elabore um algoritmo que mova três discos de uma Torre de Hanói, que consiste em três hastes (a – b – c), uma das quais serve de suporte para três discos de tamanhos diferentes (1 – 2 – 3), os menores sobre os maiores. Pode-se mover um disco de cada vez para qualquer haste, contanto que nunca seja colocado um disco maior sobre um menor.

O objetivo é transferir os três discos para outra haste.

Passo 1

Em primeiro lugar, nós devemos decidir para que haste iremos transferir os três discos. Nesse exemplo, transferiremos da haste B para a haste A.

Vale lembrar que o menor número de movimentações possíveis para transferir todos os discos de uma determinada haste para outra é dado por:

2 n - 1

Onde n é o número de discos da torre.

Sendo assim, nesse exemplo o menor número possível de movimentos é:

2 3 - 1 = 7

Resposta

A lógica da torre de Hanói é utilizar uma das hastes como auxiliar para que um disco maior nunca fique sobre um menor. Dessa forma, o algoritmo para movimentar os discos da haste B para a haste A é:

Exercício Resolvido #6

Um homem precisa atravessar um rio com um barco que possui capacidade apenas para carregar ele mesmo e mais uma de suas três cargas, que são: um lobo, um bode e um maço de alfafa. O que o homem deve fazer para conseguir atravessar o rio sem perder suas cargas? Escreva um algoritmo utilizando a linguagem natural para mostrar a resposta, ou seja, indicando todas as ações necessárias para efetuar uma travessia segura.

Passo 1

Antes de tudo, devemos reunir algumas características do problema.

Informações:

  • Um barco com 2 lugares;
  • Um homem;
  • Um lobo;
  • Um bode;
  • Um maço de alfafa.

E que se ficarem sozinhos (sem a presença do homem):

  • Lobo devora bode;
  • Bode devora alfafa.

Passo 2

Estando todos em uma margem do rio, a primeira travessia no barco deve ser feita com o homem e o bode, deixando o lobo e o maço de alfafa sozinhos:

Passo 3

Agora, devemos voltar ao lado oposto do rio para buscar um dos remanescentes:

Passo 4

Já no lado oposto, podemos realizar a travessia de volta com o lobo ou o maço de alfafa, nesse caso escolheremos o lobo e deixaremos o maço:

Passo 5

Com o lobo e o bode na outra margem do rio, o homem não pode voltar sem carga para buscar o maço de alfafa, pois o lobo devora o bode:

Passo 6

Já na margem oposta, o mesmo acontece com o bode e o maço de alfafa. Então, o homem deve deixar o bode e atravessar com o maço de alfafa:

Passo 7

Nesse momento, temos em uma margem o Lobo e o maço de alfafa e na outra o bode. Como não há problema em deixar o maço de alfafa e o lobo sozinhos:

Passo 8

Na margem oposta resta apenas o bode, sendo assim:

Resposta

Dessa forma, o algoritmo completo para a realização de travessias seguras é:

Exercício Resolvido #7

Três jesuítas e três canibais precisam atravessar um rio; para tal, dispõem de um barco com capacidade para duas pessoas. Por medida de segurança, não se deve permitir que em alguma margem a quantidade de jesuítas seja inferior à de canibais. Qual a solução para efetuar a travessia com segurança? Elabore um algoritmo mostrando a resposta, indicando as ações que concretizam a solução deste problema.

Passo 1

A primeira coisa que devemos fazer é reunir algumas das características do enunciado.

Informações:

  • Um barco com 2 lugares;
  • Três jesuítas;
  • Três canibais.

Regra de segurança:

  • Uma margem sempre deve possuir um número de jesuítas maior ou igual ao de canibais.

Também é interessante definirmos algumas referências para as margens, nesse exemplo utilizaremos A para a margem inicial e B para a margem oposta do rio.

Passo 2

Estando todos na margem A, a primeira travessia do barco será feita com um jesuíta levando um canibal para a margem B desse mesmo rio:

Com o canibal na margem B, o próximo passo do algoritmo é:

Passo 3

Já na margem A, com três jesuítas e dois canibais presentes, existem as seguinte possibilidades:

  1. A travessia de A para B ser feita por um canibal e um jesuíta, nesse caso a margem B se torna insegura para o jesuíta;
  2. A travessia de A para B ser feita por dois jesuítas, nesse caso a margem A se torna insegura para o jesuíta remanescente.

Dessa forma, a travessia do barco da margem A para a margem B deve ser feita por dois canibais:

Com o canibal na margem B, o próximo passo do algoritmo é:

Passo 4

Já na margem A, com três jesuítas e apenas um canibal presentes, existe a seguintes possibilidade de travessia:

  1. A travessia de A para B ser feita por um canibal e um jesuíta, nesse caso a margem B se torna insegura para o jesuíta.

Sendo assim, a travessia do barco da margem A para a margem B deve ser feita por dois jesuítas:

Com um dos jesuítas na margem B, o seu amigo jesuíta não pode voltar sozinho para a margem A, pois a margem B se tornaria insegura para o jesuíta deixado. Com isso, o próximo passo do algoritmo é:

Passo 5

Na margem A, com dois jesuítas e dois canibais presentes, existem as seguintes possibilidades de travessia:

  1. A travessia de A para B ser feita por um canibal e um jesuíta, nenhuma das margens se torna instantaneamente um insegura (mas confia em mim, os retornos se tornam extremamente complicados devido ao espalhamento entre canibais e jesuítas);
  2. A travessia de A para B ser feita por dois canibais, nesse caso a margem B se tornaria um perigo para o jesuíta presente lá.

Dessa forma, a travessia do barco da margem A para a margem B deve ser feita por dois jesuítas:

Na margem B, com os três jesuítas e um canibal presentes, o algoritmo se torna praticamente solucionado.

Uma vez que os três jesuítas já se encontram na margem B, o canibal presente nessa mesma margem pode ser o realizador das travessias que irão buscar os dois canibais remanescentes na margem A, dessa forma os próximos passos do algoritmo serão:

Pronto, agora todos estão em segurança na margem B do rio!

Resposta

O algoritmo completo para a travessia dos três jesuítas e dos três canibais em segurança é: