Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO
GRANDE DO NORTEGRANDE DO NORTE
Algoritmos e Técnicas de ProgramaçãoProgramação
ÉDocente: Éberton da Silva Marinhoe-mail: [email protected]@ifrn.edu.br
Curso de Tecnologia em Sistemas para Internet
03/09/2013
SUMÁRIOFunçõesBiblioteca padrão do C++Recursividade
2222
FUNÇÕES
FUNÇÕESTrecho de código com uma finalidade específica, bem determinadaP d t dif t d d d d li d Pode ter diferentes nomes dependendo da linguagem de programação: sub-rotinas, procedimentosVantagensVantagens
Reutilização de códigoEconomia de espaçoEconomia de espaçoEconomia de tempoMelhor isolamento do códigogDeixa o código mais organizado e fácil de manipular
44
FUNÇÕESUma função é um trecho de código que pode ser chamada de qualquer parte de um programaE t t d f ãEstrutura de uma funçãotipo_de_retorno nomeFunção ( lista_de_Parâmetros ){
//corpo da função//corpo da função
return expressão
}
tipo_retorno: tipo de retorno devolvido pela função ou a palavra void para indicar que nenhum valor é devolvidonomeFunção: identifica a funçãonomeFunção: identifica a funçãolista_de_Parâmetros: lista de parâmetros, separados por vírgula, que a função poderá utilizar
ã V l d l id l f ã d h l 5expressão: Valor devolvido pela função, quando houver valor a retornar
5
FUNÇÕES
66
FUNÇÕESNome de uma função
Começa com uma letra ou um sublinhado (_) e pode conter letras números ou outros sublinhadosconter letras, números ou outros sublinhadosLembrem-se que C++ é sensível ao caso
77
FUNÇÕESChamada a uma função
A chamada a uma função de um programa é feita primeiramente a partir da função mainprimeiramente a partir da função main.
88
FUNÇÕESProtótipos das funções
C++ requer que uma função seja declarada ou definida antes de seu uso O modelo de uma função é definida antes de seu uso. O modelo de uma função é chamada de protótipoUm protótipo de função possui o mesmo cabeçalho da implementação, porém terminando com ‘;’Em um protótipo de função o nome dos parâmetros pode ser omitido deixando apenas os tipos dos pode ser omitido, deixando apenas os tipos dos parâmetros.
Exemploint max( int, int);
99
PARÂMETROS DE UMA FUNÇÃOPassagem de parâmetros por valor
A função recebe uma cópia dos valores dos de quem chama a funçãochama a funçãoSe o valor de um parâmetro variável local é mudado, a mudança afeta apenas a função e não tem efeito fora dela
1010
PARÂMETROS DE UMA FUNÇÃO
1111
PARÂMETROS DE UMA FUNÇÃOUtiliza-se a passagem de parâmetro por referência quando se deseja que uma função modifique o valor do parâmetro passado e devolva modifique o valor do parâmetro passado e devolva este valor para a função de chamadaUm parâmetro passado por referência tem o Um parâmetro passado por referência tem o símbolo ‘&’ precedido do nome da variável
1212
PARÂMETROS DE UMA FUNÇÃO
1313
EXERCÍCIOFaça um programa um caixa eletrônico que dado um valor x a ser sacado pelo usuário, o programa informe quantas notas de cada valor abaixo serão emitidasquantas notas de cada valor abaixo serão emitidas
Notas de 1:Notas de 1:Notas de 5:N t d 20Notas de 20:Notas de 100:
Para cada uma das notas, faca uma função que receba um valor e retorne a quantidade de notas que devem 14um valor e retorne a quantidade de notas que devem ser emitidas
14
EXERCÍCIO RESOLVIDO#include <iostream> void intercambio1(int pri, int
void intercambio1(int, int);
void intercambio2(int&, int&);
seg){
int aux;
aux = pri;
i
int main(){
int a, b;
pri = seg;
seg = aux;
}
a= 10; b = 20;
intercambio1(a, b);
std::cout << "chamada a
void intercambio2(int& pri, int& seg){
int aux;std::cout << "chamada a intercambio1 a=" << a << " e b=" << b << endl;
aux = pri;
pri = seg;
seg = aux;
intercambio2(a, b);
std::cout << "chamada a intercambio2 a=" << a << " e
}
15intercambio2 a a e b=" << b << endl;
return 0;
}
15
ESCOPOE é d l iá l é i í lEscopo é a zona de um programa na qual uma variável é visível.Tipos de escopo
Escopo de programaEscopo de programaEscopo de arquivo-fonteEscopo de funçãop çEscopo de bloco
int i; // Escopo de programa
static int j; // Escopo de arquivo
func(int k){ // Escopo de programa, k escopo de blocofunc(int k){ // Escopo de programa, k escopo de bloco
int m; // Escopo de bloco
... // Escopo de função16
}16
ESCOPO DE PROGRAMAVariáveis deste tipo podem ser referenciadas por qualquer função no programa completo; também chamadas de variáveis globaischamadas de variáveis globais
int g h; // Variáveis globaisint g, h; // Variáveis globais
main(){
// ...
}
1717
ESCOPO DE ARQUIVOVariável declarada fora de qualquer função, cujo modelo contém a palavra reservada static, tem escopo de arquivo fonte Tais variáveis podem ser escopo de arquivo-fonte. Tais variáveis podem ser referenciadas em qualquer ponto do arquivo onde a mesma foi declarada.
static int i;
void func(){
...
}}
1818
ESCOPO DE FUNÇÃOUma variável declarada dentro de uma função pode ser acessada apenas dentro dela.
func(int k){ // k tem Escopo de função
int m; // Escopo de funçãoint m; // Escopo de função
... // Escopo de função
}
1919
ESCOPO DE BLOCOVariável declarada dentro de um bloco
void funcdemo(){
for(int i = 0; i<10; i++){
std::cout << “i” << “\n”;
}
// Aqui a variável i não é visível
}}
2020
VARIÁVEIS LOCAISAlém de um escopo restrito, elas só ficam na memória enquanto a execução do programa estiver no escopo da variávelestiver no escopo da variável
Economia de memóriaSegurança, pois apenas uma parte do código pode Segurança, pois apenas uma parte do código pode manipular a variável localMelhor organização do código
2121
CONCEITO E USO DE CONCEITO E USO DE FUNÇÕES DE BIBLIOTECA
BIBLIOTECA C++C++ vem com uma biblioteca de funções para suporte a algumas operações que são mais realizadas pelos usuáriosrealizadas pelos usuáriosAs funções que desempenham papéis semelhantes são organizados em grupo através semelhantes são organizados em grupo através de bibliotecas (arquivo com a declaração das funções – arquivo de cabeçalho)
2323
BIBLIOTECA C++Bibli i dBibliotecas mais usadas
E/S padrãoMatemáticaRotinas-padrãoVisualizar janela de textoDe conversãoDe diagnósticoDe manipulação de memóriaControle de processoClassificaçãoDiretóriosData e horaDe interfaceDiversasBusca 24Manipulação de cadeiasgráficos
24
FUNÇÕES DE CARACTERE (CCTYPE)
2525
FUNÇÕES NUMÉRICAS (CMATH, Ç ( ,CSTDLIB)
Funções Matemáticas
2626
FUNÇÕES NUMÉRICAS (CMATH, Ç ( ,CSTDLIB)
Funções Trigonométricas
2727
FUNÇÕES NUMÉRICAS (CMATH, Ç ( ,CSTDLIB)o Funções Logarítmicas e Exponenciais
2828
EXERCÍCIOS COM BIB. MATEMÁTICA
C i l i ifi li 1. Crie um programa calc_cientifica para realizar as operações listadas abaixo. Inicialmente deve ser apresentado ao usuário uma interface com as opções que ele pode escolher. Depois o programa deve ler o(s) valor(es) correspondentes a opção escolhida e apresentar o resultado ao usuário
• Exemplo• ExemploDigite uma das opções entre colchetes[P] : pow(x, y)[ ] p ( , y)[S] : sqrt(x)[E] : exp(x)[L] : log(x)Opção: _
2929
NÚMERO ALEATÓRIOS E PSEUDO-ALEATÓRIOS
E b lh ú l ó i i Em computação não trabalhamos com números aleatórios pois não há como gerar um número realmente aleatórioEm computação, geramos números pseudo-aleatórios com base em Em computação, geramos números pseudo aleatórios com base em fórmulas que fazem parecer a série de números gerados aleatório.Características de uma boa fórmula
não repetição: a sequncia não pode estar em ciclo e nem se repetir;boa distribuição numérica: se a fórmula está gerando boa distribuição numérica: se a fórmula está gerando números aleatórios entre 0 e 9, o número de zeros, uns, dois, etc. que ela gera devem ser aproximadamente iguais depois de um longo período de tempo;um longo período de tempo;ausência de previsões: você não tem como prever qual será o próximo número, a não ser que conheça a fórmula e
30a origem (o valor inicial). 30
FUNÇÕES NUMÉRICAS - NÚMEROS ÇALEATÓRIOS
Principais funções: rand, random, randomize e srand. Tais funções estão na biblioteca cstdlib
d() t ú d l tó i t 0 rand(): retorna um número pseudo-aleatório entre 0 e um valor máximo definido em C++randomize(): inicializa o gerador de números pseudo-() g paleatórios com base no tempo (semente), logo a biblioteca ctime deve ser incluída no programa
d( t ) i i i li d d ú srand(semente): inicializa o gerador de números pseudo-aleatórios com uma semente. random(número): gera um número aleatório dentro ( ) gde um intervalo especificadoSe utilizarmos as funções rand ou random sem usar
d d i t 31srand ou randomize, sempre teremos a mesma sequência de números aleatórios
31
EXEMPLOS
#i l d i#include <iostream>
#include <cstdlib>
#include <ctime>
int main(){
srand(100);
std::cout << “Número aleatório menor que 10 ”
<< rand() % 10;<< rand() % 10;
return 0;
}
3232
EXERCÍCIOSCrie um programa que gere 15 números aleatórios entre 1 e 100 utilizando as funções dadas anteriormentedadas anteriormente.
Crie um programa que gere 10 000 números Crie um programa que gere 10.000 números aleatórios entre 1 e 10 e guarde em variáveis quantas vezes cada um apareceu. Exiba estes quantas vezes cada um apareceu. Exiba estes números. Qual a conclusão que podemos chegar sobre a função aleatória de tais números?
3333
RECURSIVIDADE
RECURSIVIDADE
DefiniçãoFunção que chama a si mesma diretamente (na mesma função) ou indiretamente (através de outra(s) mesma função) ou indiretamente (através de outra(s) função(ões)).
ExemplospAnalisadores sintáticos recursivosEstratégia dividir para conquistarProgramação dinâmicaFatorial
3535
RECURSIVIDADE
Fatorialn! = n * (n-1) * (n-2) * ... * 2 * 1
! n! = n * (n-1)!n * (n-1) * (n-2)!( ) ( )n * (n-1) * (n-2) * ... * 2!n * (n-1) * (n-2) * ... * 2 * 1!
Critério de paradaQuando n for igual a 1Quando n for igual a 1
3636
RECURSIVIDADE
Fatorial de um número usando a recursividade
3737
RECURSIVIDADE
Para cada chamada de uma função, recursiva ou não, os parâmetros e as variáveis locais são empilhados na pilha de execuçãoempilhados na pilha de execução.
3838
RECURSIVIDADE
Toda função que puder ser produzida por um computador pode ser escrita como função recursiva sem o uso de iteração; reciprocamente recursiva sem o uso de iteração; reciprocamente, qualquer função recursiva pode ser descrita através de iterações sucessivas.çAlgumas linguagens desenvolvidas para programação lógica e programação funcional permitem recursões como única estrutura de repetição, tais como o map e Scheme.
3939
RECURSÃO VERSUS ITERAÇÃO
N l d f t i l i l t ã No exemplo do fatorial, a implementação iterativa tende a ser ligeiramente mais rápida na prática do que a implementação recursiva, uma p á ca o q e a p e e ação ec s va, a vez que uma implementação recursiva precisa registrar o estado atual do processamento de maneira que ela possa continuar de onde parou maneira que ela possa continuar de onde parou após a conclusão de cada nova execução subordinada do procedimento recursivo. Esta ação consome tempo e memória. Existem outros tipos de problemas cujas soluções são inerentemente recursivas já que elas são inerentemente recursivas, já que elas precisam manter registros de estados anteriores.
Percurso de uma árvore; 40;Algoritmos de divisão e conquista,
40
RECURSIVIDADEVantagensVantagens
Os algoritmos recursivos normalmente são mais compactos, mais legíveis e mais fáceis de serem compreendidos. Algoritmos para resolver problemas de natureza recursiva são fáceis de serem implementados em linguagens de
ã d l í lprogramação de alto nível.Desvantagens
Por usarem intensivamente a pilha, o que requer alocações e desalocações de memória os algoritmos recursivos tendem a ser mais lentos que os memória, os algoritmos recursivos tendem a ser mais lentos que os equivalentes iterativos, porém pode valer a pena sacrificar a eficiência em benefício da clareza. Algoritmos recursivos são mais difíceis de serem depurados durante a fase de desenvolvimento.
A li õAplicaçõesNem sempre a natureza recursiva do problema garante que um algoritmo recursivo seja a melhor opção para resolvê-lo. O algoritmo recursivo para obter a seqüência de Fibonacci é um ótimo exemplo disso.Algoritmos recursivos são aplicados em diversas situações como em: i) problemas envolvendo manipulações de árvores; ii) analisadores léxicos recursivos de compiladores; e iii) problemas que envolvem tentativa e erro ("Backtracking"). 41( g ) 41
EXERCÍCIO
Crie uma função recursiva que dado um número, a função deva imprimir recursivamente os antecessores do número até que chegue a 0antecessores do número até que chegue a 0.
4242
EXERCÍCIOSLista de exercícios
4343
DÚVIDAS
e-mail:[email protected]@ifrn.edu.br
Endereço eletrônico da disciplina: http://docente.ifrn.edu.br/ebertonmarinho
44444444