Procedimentos e Funções Problema 1: Escreva um procedimento ou função em linguagem C que troca dois valores A e B. Problema 2: Escreva um procedimento

Procedimentos e Funções

Problema 1:

Escreva um procedimento ou função em linguagem C

que troca dois valores A e B.

Problema 2:


que retorna a soma e o produto de dois valores A e B.


Passagem de Parâmetros:

• Passagem por Valor: Quando a função é chamada o parâmetro passado por valor é copiado, ou seja, o valor da variável utilizada como parâmetro não é alterado.

• Passagem por Referência: Quando a função é chamada o endereço do parâmetro passado por referência é atribuído à um ponteiro, ou seja, qualquer alteração no conteúdo apontado será refletida no conteúdo da variável utilizada como parâmetro.


Exemplo :

void FuncaoInutil(int A, int* B){

A = 1;*B = 2;

}

int main(){

int X = 0, Y = 0;FuncaoInutil(X, &Y);printf(“%d %d”, X, Y);return 0;

}


Exercício 1:

Escreva um procedimento ou função em linguagem Cque troca dois valores A e B.

Exercício 2:

Escreva um procedimento ou função em linguagem Cque recebe dois valores A e B, calcula a soma eguarda o resultado em A.

Exercício 3:

Escreva um procedimento ou função em linguagem Cque retorna a soma e o produto de dois valores A e B.


Solução:

void troca(int* A, int* B){

int aux;aux = *A;*A = *B;*B = aux;

}


Solução:

void SomaEmA(int* A, int B){

*A = *A + B;}


Solução:

void SomaProduto(int A, int B, int* soma, int* prod)

{*soma = A + B;*prod = A * B;

}


Exercício :


que recebe um vetor de números inteiros V de

tamanho 100, e um inteiro N, em seguida você deve

imprimir os N primeiros valores do vetor.


Solução:

void ImprimeVetor(int V[100], int N){

int i;for (i = 0; i < N; i++)

printf(“%d ”, V[i]);}


Exercício :


que recebe um vetor de números inteiros V de

tamanho 100, e um inteiro N por referência, em

seguida você deve ler valores inteiros da entrada até

que o usuário digite -1. Ao final todos os valores

diferentes de -1 devem estar armazenados em V e o

total de valores deve estar em N.


Solução:

void LeVetor(int V[100], int* N){

int aux;*N = 0;scanf(“%d”, &aux);while (aux != -1){

V[*N] = aux;(*N)++;scanf(“%d”, &aux);

}}


Exercício :

Escreva uma função em linguagem C que recebe um

vetor de números inteiros V de tamanho 100, um

inteiro N que contém o número de posições

preenchidas de V, e um número inteiro X. A sua

função deve retornar 1 se V contém o valor X e zero

caso contrário.


Algoritmo :

• Percorra todos os valores do Vetor• Compare cada valor com o número procurado• Se um dos valores for igual então retorne 1• Senão continue procurando• Se chegar ao fim da busca retorne zero, porque o

valor não foi encontrado.


Busca Linear:

int BuscaLinear(int V[100], int N, int X){

int i;for (i = 0; i < N; i++){

if( V[i] == X )return 1;

}return 0;

}


Problema :

E se os vetores do exercício anterior estivessem

sempre ordenados? Seria necessário verificar todos os

elementos para determinar se X está em V?


Algoritmo :

• Marque os extremos direito (dir) e esquerdo (esq) do vetor.

• Compare o valor procurado com o valor central (meio)

• Se for igual retorne saia do laço.• Senão, se o valor for maior que o valor de meio,

então esq recebe meio mais 1.• Senão dir recebe meio menos 1.• Atualize o valor do meio.• Repita enquanto esq for menor que dir.• Ao sair do laço se valor for igual a meio retorne 1,

senão retorne 0.


Busca Binária :

X = 3; esq = 0; dir = N – 1; meio = (esq + dir)/2;

1 2 7 15 23 56 57 58 70 72 78

esq meio dir

1 2 7 15 23 56 57 58 70 72 78

esq meio dir

1 2 7 15 23 56 57 58 70 72 78

esq meio dir

1 2 7 15 23 56 57 58 70 72 78

esq meio dir


Busca Binária: esq = 0; dir = N - 1; meio = (esq + dir) / 2; while (esq < dir) { if ( X == V[meio] ) break; else if ( X > V[meio] ) esq = meio + 1; else dir = meio - 1; meio = (esq + dir) / 2; } if ( X == V[meio] ) return 1;

return 0;


Problema :

Não há como garantir que o usuário sempre digitará

um vetor ordenado. E agora? Como devemos fazer

para que seja possível utilizar a busca binária sempre?


Exercício :

Escreva uma função em linguagem C que retorna a

posição no vetor (não é o valor) do menor elemento. A

função recebe como parâmetros um vetor V de 100

elementos e um inteiro N que indica o número de

elementos de V.


Solução:

int MenorElemento(int V[100], int N){ int i, menor = 0;

for(i = 1; i < N; i++) if(V[i] < V[maior]) menor = i; return menor;}


Algoritmo :

• Remova o menor elemento do vetor (V) e insira na primeira posição livre do vetor auxiliar (Ordenado).

• Repita este processo até acabarem os elementos do vetor V.


Ordenação por Seleção (Selection Sort) :

3 20 78 15 56 23 2 1 19 28 6

3 20 78 15 56 23 2 6 19 28

1

N = 11; M = 0;

N = 10; M = 1;

3 20 78 15 56 23 28 6 19

58 2

N = 9; M = 2;


Ordenação por Seleção (Selection Sort) :

void SelectionSort(int V[100], int N, int Ordenado[100]){ int M = 0, i; while(N > 0) { i = MenorElemento(V, N); Ordenado[M] = V[i]; V[i] = V[N - 1]; N--; M++; }}


Problema :

Como ordenar um vetor sem alterar os dados do vetor

original V ?


Algoritmo :

• Percorra o vetor (V)• Para cada elemento (aux) de V, insira uma cópia

de aux na primeira posição livre do vetor auxiliar (Ordenado).

• Se o valor de aux for menor que do elemento anterior, então troque aux com o anterior.

• Senão saia do laço.• Repita as trocas até que aux chegue na primeira

posição.


Ordenação por Inserção (Insertion Sort) :

2 15 1 3 6 23 57

2

2 15 1 3 6 23 57

2 15

M = 0; i = 0;

M = 1; i = 1;

2 15

2 15 1 3 6 23 57

2 15 1

M = 2; i = 2;

2 1 15

1 2 15


Ordenação por Inserção (Insertion Sort) :

2 15 1 3 6 23 57

1 2 15 3

M = 3; i = 3;

1 2 3 15

1 2 3 15

2 15 1 3 6 23 57

1 2 3 15 6

M = 4; i = 4;

1 2 3 6 15

1 2 3 6 15


Solução :void InsertionSort( int V[100], int N, int Ordenado[100]){ int M = 0, i, j, k; for (i = 0; i < N; i++) { Ordenado[M] = V[i]; k = M; for (j = M - 1; j >= 0; j--) if (Ordenado[k] < Ordenado[j] ) Troca(&Ordenado[k--],

&Ordenado[j]); else

break; M++; }}


Problema :

Como ordenar um vetor sem o uso de um vetor auxiliar

(Ordenado) ?


Algoritmo :

• Para cada elemento i do vetor V.• Se o valor de i + 1 for menor que i• Então troque i + 1 com i.• Senão incremente o valor de i.• Repita este processo até i chegue ao fim do vetor.• Repita todo o processo até que todos os

elementos do vetor tenham sido comparados.


Ordenação por Troca (Bubble Sort) :

57 30 8 15 56 23 2

30 57 8 15 56 23 2

i = 0;

i = 1;

30 8 57 15 56 23 2i = 2;

30 8 15 56 23 2 57i = 0;

30 8 15 57 56 23 2i = 3;

30 8 15 56 57 23 2i = 4;

30 8 15 56 23 57 2i = 5;

30 8 15 56 23 2 57i = 6;

8 30 15 56 23 2 57i = 1;


Solução :

void BubbleSort( int V[100], int N){

int j, i; for ( i = 0; i < N - 1; i++ ) { for ( j = 0; j < N - 1; j++ ) if ( V[j] < V[j + 1] ) Troca( &V[j], &V[j + 1] ); }}

Documents

Procedimentos e Funções Problema 1: Escreva um procedimento ou função em linguagem C que troca dois valores A e B. Problema 2: Escreva um procedimento