Capítulo VI – Variáveis Indexadas

Capítulo VI – Variáveis Capítulo VI – Variáveis IndexadasIndexadas

6.1 – A necessidade de variáveis indexadas6.1 – A necessidade de variáveis indexadas

6.2 – Vetores e matrizes6.2 – Vetores e matrizes

6.3 – Aplicações com vetores numéricos6.3 – Aplicações com vetores numéricos

6.4 – Aplicações com matrizes numéricas6.4 – Aplicações com matrizes numéricas

6.5 – Cadeias de caracteres6.5 – Cadeias de caracteres

6.6 – Aplicações com vetores de cadeias de 6.6 – Aplicações com vetores de cadeias de caracterescaracteres

6.3 – Aplicações com 6.3 – Aplicações com Vetores NuméricosVetores Numéricos

6.3.1 – Ordenação dos valores de um 6.3.1 – Ordenação dos valores de um vetorvetor

Colocar em Colocar em ordem crescente ou decrescenteordem crescente ou decrescente os os valoresvalores dentro dos dentro dos elementoselementos de um vetor de um vetor

16 45 72 5 8 67 95 74 70 800 1 2 3 4 5 6 7 8 9

VVetor desordenado

5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

VVetor ordenado crescentemente

São inúmeros os São inúmeros os métodosmétodos para a para a ordenaçãoordenação de vetores apresentados na literaturade vetores apresentados na literatura

Alguns deles são bem Alguns deles são bem simplessimples, porém , porém ineficientesineficientes para vetores muito para vetores muito longoslongos

Outros, para vetores Outros, para vetores longoslongos, são mais , são mais eficienteseficientes, porém mais , porém mais complexoscomplexos

Nesta seção será apresentado o conhecido Nesta seção será apresentado o conhecido método método Bubble-SortBubble-Sort (método da bolha)(método da bolha), que , que é dos mais simplesé dos mais simples

Esse nome é dado porque tem-se a impressão Esse nome é dado porque tem-se a impressão de que os elementos de que os elementos borbulhamborbulham até chegar à até chegar à sua sua posição definitivaposição definitiva

O método O método Bubble-SortBubble-Sort consiste em: consiste em:

■ Percorrer o vetorPercorrer o vetor várias vezes várias vezes

■ Durante cada percurso, efetuar Durante cada percurso, efetuar trocatroca de posição de posição de de elementos adjacenteselementos adjacentes, caso o elemento da , caso o elemento da esquerdaesquerda seja seja maiormaior que o da que o da direitadireita

■ Em cada percurso, um elemento atinge sua Em cada percurso, um elemento atinge sua posição definitivaposição definitiva

■ Se, durante um dos percursos, Se, durante um dos percursos, não houver não houver trocastrocas, considera-se que o vetor está , considera-se que o vetor está ordenadoordenado

Exemplo: Exemplo: seja o seguinte vetor e o método em seja o seguinte vetor e o método em seu inícioseu início

16 45 72 5 8 67 95 74 70 800 1 2 3 4 5 6 7 8 9

p

(cursor para percorrer o vetor várias vezes)

(limitante de i a cada percurso)

i

trocou(semáforo

que acende quando há troca)

V

Não trocarNão trocar

16 45 72 5 8 67 95 74 70 800 1 2 3 4 5 6 7 8 9

p

i

trocou

V


16 45 72 5 8 67 95 74 70 800 1 2 3 4 5 6 7 8 9

p

i

trocou

V

TrocarTrocar

16 45 72 5 8 67 95 74 70 800 1 2 3 4 5 6 7 8 9

p

i

trocou

V

TrocarTrocar

16 45 5 72 8 67 95 74 70 800 1 2 3 4 5 6 7 8 9

p

i

trocou

V

TrocarTrocar

16 45 5 8 72 67 95 74 70 800 1 2 3 4 5 6 7 8 9

p

i

trocou

V


16 45 5 8 67 72 95 74 70 800 1 2 3 4 5 6 7 8 9

p

i

trocou

V

TrocarTrocar

16 45 5 8 67 72 95 74 70 800 1 2 3 4 5 6 7 8 9

p

i

trocou

V

TrocarTrocar

16 45 5 8 67 72 74 95 70 800 1 2 3 4 5 6 7 8 9

p

i

trocou

V

TrocarTrocar

16 45 5 8 67 72 74 70 95 800 1 2 3 4 5 6 7 8 9

p

i

trocou

V

95 em sua posição definitiva 95 em sua posição definitiva

trocou acesa: começar novo percursotrocou acesa: começar novo percurso

retroceder pretroceder p

16 45 5 8 67 72 74 70 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

A variável cursora ‘i’ não precisa chegar até V[8]

Basta chegar até V[7]


16 45 5 8 67 72 74 70 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i

TrocarTrocar

16 45 5 8 67 72 74 70 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i

TrocarTrocar

16 5 45 8 67 72 74 70 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


16 5 8 45 67 72 74 70 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


16 5 8 45 67 72 74 70 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


16 5 8 45 67 72 74 70 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i

TrocarTrocar

16 5 8 45 67 72 74 70 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


16 5 8 45 67 72 70 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i

80 em sua posição definitiva80 em sua posição definitiva

trocou acesa: iniciar novo percursotrocou acesa: iniciar novo percurso


16 5 8 45 67 72 70 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

TrocarTrocar

16 5 8 45 67 72 70 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i

TrocarTrocar

5 16 8 45 67 72 70 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


5 8 16 45 67 72 70 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


5 8 16 45 67 72 70 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


5 8 16 45 67 72 70 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i

TrocarTrocar

5 8 16 45 67 72 70 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


trocou acesa: novo percursotrocou acesa: novo percurso


5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V


5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

p

trocou

V

i


trocou apagada: vetor ordenadotrocou apagada: vetor ordenado

5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

trocou

Vp

5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

V

Se, em todos os percursos, a lâmpada acender, o processo termina quando p chegar a -1

p

■ O teste da O teste da necessidade de trocanecessidade de troca entre dois entre dois elementos elementos adjacentesadjacentes pode ser feito pelo pode ser feito pelo seguinte trecho:seguinte trecho:

if (V[i] > V[i+1]) {if (V[i] > V[i+1]) {

aux = V[i]; V[i] = V[i+1];aux = V[i]; V[i] = V[i+1];

V[i+1] = aux; trocou = true;V[i+1] = aux; trocou = true;

}}

Um Um percurso genéricopercurso genérico da variável da variável ii pode ser pode ser expresso por:expresso por:

for (trocou = false, i = 0; i <= p; i++)for (trocou = false, i = 0; i <= p; i++)

Testar e Trocar (i, i+1);Testar e Trocar (i, i+1);

Seja este trecho abreviado para

Testar e Trocar (i, i+1);

‘aux’ é uma variável auxiliar para realização de troca de conteúdo entre variáveis

Seja este trecho abreviado para

Percorrer até (p);

■ for (trocou = false, i = 0; i <= p; i++)for (trocou = false, i = 0; i <= p; i++)

Testar e Trocar (i, i+1);Testar e Trocar (i, i+1);

Sendo Sendo nn, o número de elementos do vetor, os , o número de elementos do vetor, os diversos percursos necessários para a diversos percursos necessários para a ordenação podem ser realizados porordenação podem ser realizados por

for (trocou = true, p = n-2; p >= 0 && trocou == for (trocou = true, p = n-2; p >= 0 && trocou == true; p--)true; p--)

Percorrer até (p);Percorrer até (p);

A seguir o programa do A seguir o programa do Bubble-SortBubble-Sort completo completo

Percorrer até (p);

#include <stdio.h>#include <stdio.h>

#include <stdlib.h>#include <stdlib.h>

/*/* Criacao do tipo logic e suas constantesCriacao do tipo logic e suas constantes */*/

typedef char logic; const logic false = 0, true = 1;typedef char logic; const logic false = 0, true = 1;

/*/* Criacao do tipo vetorCriacao do tipo vetor */*/

typedef int vetor[50];typedef int vetor[50];

/*/* Cabecalho e declarações locaisCabecalho e declarações locais */*/

int main () {int main () {

int n, i, p, aux; logic trocou; vetor V;int n, i, p, aux; logic trocou; vetor V;

/*/* Leitura do vetor a ser ordenadoLeitura do vetor a ser ordenado */*/

printf ("Ordenacao de numeros pelo Bubble-Sort\printf ("Ordenacao de numeros pelo Bubble-Sort\n\n");n\n");

printf ("\tNumero de elementos: "); scanf printf ("\tNumero de elementos: "); scanf ("%d",&n);("%d",&n);

printf ("\n\tElementos: ");printf ("\n\tElementos: ");

for (i = 0; i < n; i++)for (i = 0; i < n; i++)

scanf ("%d", &V[i]);scanf ("%d", &V[i]);

/*/* Escrita do vetor desordenadoEscrita do vetor desordenado */*/

printf ("\n\nVetor desordenado:\n\n");printf ("\n\nVetor desordenado:\n\n");

for (i = 0; i < n; i++) for (i = 0; i < n; i++)

printf ("%4d", V[i]);printf ("%4d", V[i]);

/*/* Aplicação do metodo bubble-sortAplicação do metodo bubble-sort */*/

for (trocou = true, p = n-2; p >= 0 && trocou == for (trocou = true, p = n-2; p >= 0 && trocou == true; p--) true; p--)

for (trocou = false, i = 0; i <= p; i++)for (trocou = false, i = 0; i <= p; i++)

if (V[i] > V[i+1]) {if (V[i] > V[i+1]) {

aux = V[i]; V[i] = V[i+1];aux = V[i]; V[i] = V[i+1];

V[i+1] = aux; trocou = true;V[i+1] = aux; trocou = true;

}}

/*/* Escrita do vetor ordenadoEscrita do vetor ordenado */*/

printf ("\n\nVetor ordenado:\n\n");printf ("\n\nVetor ordenado:\n\n");

for (i = 0; i < n; i++) for (i = 0; i < n; i++)

printf ("%4d", V[i]);printf ("%4d", V[i]);

/*/* Fechamento da telaFechamento da tela */*/

printf ("\n\n"); system ("pause");printf ("\n\n"); system ("pause");

return 0;return 0;

}}Ordenacao de numeros pelo Bubble-Sort

Numero de elementos: 10

Elementos: 16 45 72 5 8 67 95 74 70 80

Vetor desordenado:

16 45 72 5 8 67 95 74 70 80

Vetor ordenado:

5 8 16 45 67 70 72 74 80 95

Digite algo para encerrar:

Resultado de uma execução

6.3.2 – Procura de valores em um vetor6.3.2 – Procura de valores em um vetor

Outro problema muito conhecido: Outro problema muito conhecido: procurarprocurar um um dado dado valorvalor entre os elementos de um entre os elementos de um vetorvetor

Quando o vetor Quando o vetor não está ordenadonão está ordenado, deve-se , deve-se percorrê-lopercorrê-lo sequencialmente sequencialmente, comparando os , comparando os valores de seus elementos com o valores de seus elementos com o valor valor procuradoprocurado

A procura A procura terminatermina quando o valor for quando o valor for encontradoencontrado, ou quando se chegar ao , ou quando se chegar ao final do final do vetorvetor

Esse tipo de procura é denominado Esse tipo de procura é denominado procura procura sequencialsequencial

Exemplo: Exemplo: seja o seguinte vetor desordenado:seja o seguinte vetor desordenado:

Seja a procura do valor Seja a procura do valor 6767::

Percorre-se o vetor com um cursor Percorre-se o vetor com um cursor ii, de , de V[0]V[0] em dianteem diante

Quando Quando i = 5i = 5, , V[i] = V[5] = 67V[i] = V[5] = 67 Então o valor procurado foi encontrado na Então o valor procurado foi encontrado na

posição 5 posição 5 do vetor do vetor VV

16 45 72 5 8 67 95 74 70 800 1 2 3 4 5 6 7 8 9

V 10n

iNúmero de elementos do vetor


Percorre-se o vetor com um cursor Percorre-se o vetor com um cursor ii, de , de V[0]V[0] em dianteem diante

Para Para 0 ≤ i ≤ n-1 (n = 10)0 ≤ i ≤ n-1 (n = 10), , V[i] ≠ 50V[i] ≠ 50 Então o valor procurado não foi encontrado Então o valor procurado não foi encontrado

no vetor no vetor VV

16 45 72 5 8 67 95 74 70 800 1 2 3 4 5 6 7 8 9

V 10n

i

Trecho de programa que realiza a procura Trecho de programa que realiza a procura sequencial:sequencial:

printf ("Numero procurado: "); scanf ("%d", &num);printf ("Numero procurado: "); scanf ("%d", &num);

i = 0; i = 0;

while (i < n && V[i] != num)while (i < n && V[i] != num)

i++;i++;

if (i < n)if (i < n)

printf ("\n\t%d estah na posicao %d do vetor\n\printf ("\n\t%d estah na posicao %d do vetor\n\n", num, i);n", num, i);

elseelse

printf ("\n\t%d nao estah no vetor\n\n",num);printf ("\n\t%d nao estah no vetor\n\n",num);

16 45 72 5 8 67 95 74 70 800 1 2 3 4 5 6 7 8 9

V 10n

i 67num

Caso ‘n’ seja muito grande e ‘num’ não esteja em ‘V’, o tempo de procura é longo

É proporcional a ‘n’

Quando o Quando o vetorvetor estiver estiver ordenadoordenado::


Percorre-se o vetor com um cursor Percorre-se o vetor com um cursor ii, de , de V[0]V[0] em diante, enquanto em diante, enquanto V[i] < 67V[i] < 67

Quando Quando i = 4i = 4, , V[i] = V[4] = 67V[i] = V[4] = 67 Então o valor procurado foi encontrado na Então o valor procurado foi encontrado na

posição 4 posição 4 do vetor do vetor VV

10n

i

5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9


Percorre-se o vetor com um cursor Percorre-se o vetor com um cursor ii, de , de V[0]V[0] em diante, enquanto em diante, enquanto V[i] < 50V[i] < 50

Quando Quando i = 4i = 4, , V[i] = V[4] > 50V[i] = V[4] > 50 Então o valor procurado não foi encontrado Então o valor procurado não foi encontrado

no vetor no vetor VV

10n

i

5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

Trecho de programa que realiza a procura Trecho de programa que realiza a procura sequencial:sequencial:

printf ("Numero procurado: "); scanf ("%d", &num);printf ("Numero procurado: "); scanf ("%d", &num);

i = 0; i = 0;

while (i < n && V[i] < num) while (i < n && V[i] < num)

i++;i++;

if (i < n && V[i] == num)if (i < n && V[i] == num)

printf ("\n\t%d estah na posicao %d do vetor\n\printf ("\n\t%d estah na posicao %d do vetor\n\n", num, i);n", num, i);

elseelse

printf ("\n\t%d nao estah no vetor\n\n",num);printf ("\n\t%d nao estah no vetor\n\n",num);

5 8 16 45 67 70 72 74 80 950 1 2 3 4 5 6 7 8 9

V 10n

i 67num

Caso n seja muito grande e num > V[n-1], o problema é o mesmo do vetor desordenado

No pior caso, o tempo é proporcional a ‘n’, como para o vetor desordenado

(T(n) é O(n) – é da ordem de n)

Procura binária: Procura binária: importante método de importante método de procura, para procura, para vetores ordenadosvetores ordenados

O O tempotempo de procura, no caso do valor de procura, no caso do valor não não estar no vetorestar no vetor é proporcional a é proporcional a loglog22nn, o que, , o que, para para vetores longosvetores longos, é muito significativo , é muito significativo (T(n) é O(log(T(n) é O(log22n))n))

O método consiste em comparar o O método consiste em comparar o valor valor procuradoprocurado com o do elemento da com o do elemento da posição posição médiamédia do vetor do vetor

Se forem Se forem iguaisiguais, o valor terá sido , o valor terá sido encontradoencontrado

Caso contrárioCaso contrário, ele estará ou à , ele estará ou à esquerdaesquerda ou ou à à direitadireita do do elemento médioelemento médio

O campo de procura fica reduzido pela metade; repete-se o procedimento acima, até encontrar ou até anular esse campo

Exemplo: Exemplo: seja o seguinte vetor ordenado:seja o seguinte vetor ordenado:

Seja a procura do valor Seja a procura do valor 1515

-5

0

-1

1

4

2

7

3

10

4

14

5

15

6

17

7

21

8

23

9

24

10

30

11

32

12

38

13

45

14

50

15

53

16

V

Posição média:

med = (0 + 16)/2 = 8

med

15 < V[8]

Posição média:

med = (0 + 7)/2 = 3

med

15 > V[3]

Posição média:

med = (4 + 7)/2 = 5

med

15 > V[5]

Posição média:

med = (6 + 7)/2 = 6

med

15 = V[6]

Achou 15 na posição 6

Seja a procura do valor Seja a procura do valor 4141

-5

0

-1

1

4

2

7

3

10

4

14

5

15

6

17

7

21

8

23

9

24

10

30

11

32

12

38

13

45

14

50

15

53

16

V

Posição média:

med = (0 + 16)/2 = 8

med

41 > V[8]

Posição média:

med = (9 + 16)/2 = 12

med

41 > V[12]

Posição média:

med = (13 + 16)/2 = 14

med

41 < V[14]

Posição média:

med = (13 + 13)/2 = 13

med

41 > V[13]

Campo de procura vazio;Não achou 41

Para os valores Para os valores 1515 e e 4141, o , o número de número de comparaçõescomparações foi foi 44

Numa procura Numa procura sequencialsequencial, para o , para o 1515 e o e o 4141, , seriam necessárias seriam necessárias 77 e e 15 comparações15 comparações, , respectivamenterespectivamente

Para Para vetores muito longosvetores muito longos, essa diferença, no , essa diferença, no pior caso, seria muito grande pior caso, seria muito grande (n (n e e loglog22n)n)

-5

0

-1

1

4

2

7

3

10

4

14

5

15

6

17

7

21

8

23

9

24

10

30

11

32

12

38

13

45

14

50

15

53

16

V

med

-5

0

-1

1

4

2

7

3

10

4

14

5

15

6

17

7

21

8

23

9

24

10

30

11

32

12

38

13

45

14

50

15

53

16

V

medinf (limite inferior do campo de procura)

sup(limite

superior do campo de procura)achou = false; inf = 0; sup = n - 1;

do {med = (inf + sup) / 2;if (num == V[med]) achou =

true;else if (num < V[med]) sup =

med - 1;else inf = med + 1;

} while (!achou && inf <= sup);

Trecho de programa para efetuar uma procura binária

achou: variável que guarda a resposta da procura

Quando inf > sup, o campo de procura é vazio

A seguir, um programa completo

Passos seguidos pelo programa da Procura Passos seguidos pelo programa da Procura binária:binária:

Leitura dos dados sobre o vetor;Leitura dos dados sobre o vetor;

Verificação da condição de ordenação para o Verificação da condição de ordenação para o vetor;vetor;

Se no mínimo um de seus elementos estiver fora Se no mínimo um de seus elementos estiver fora de ordem {de ordem {

Emitir mensagem notificando o fato;Emitir mensagem notificando o fato;

Encerrar a execução;Encerrar a execução;

}}

Senão Senão

iniciar uma seção de procuras, que deve iniciar uma seção de procuras, que deve ser encerrada ser encerrada mediante sinalização do mediante sinalização do operador; operador;

/*/* Diretivas de preprocessamanto e declaracoesDiretivas de preprocessamanto e declaracoes */*/



#include <conio2.h>#include <conio2.h>

typedef char logic;typedef char logic;

const logic false = 0, true = 1;const logic false = 0, true = 1;

typedef int vetor[50];typedef int vetor[50];

int main () {int main () {

int n, i, inf, sup, med, num;int n, i, inf, sup, med, num;

vetor V;vetor V;

logic achou, erro;logic achou, erro;

char c;char c;

/*/* Leitura dos elementos do vetorLeitura dos elementos do vetor */*/

printf ("PROCURA BINARIA EM VETORES\n\n");printf ("PROCURA BINARIA EM VETORES\n\n");

printf ("Numero de elementos do vetor: "); scanf printf ("Numero de elementos do vetor: "); scanf ("%d",&n);("%d",&n);

printf ("\nElementos: ");printf ("\nElementos: ");

for (i = 0; i < n; i++) scanf ("%d", &V[i]);for (i = 0; i < n; i++) scanf ("%d", &V[i]);

/*/* Verificacao da ordenacao do vetorVerificacao da ordenacao do vetor */*/

for (i = 0, erro = false; i < n-1 && erro == false; for (i = 0, erro = false; i < n-1 && erro == false; i++)i++)

if (V[i] > V[i+1]) erro = true;if (V[i] > V[i+1]) erro = true;

if (erro == true)if (erro == true)

printf ("\n\tRelacao desordenada: nao printf ("\n\tRelacao desordenada: nao havera procuras\n");havera procuras\n");

/*/* Secao de procurasSecao de procuras */*/

else {else {

clrscr ();clrscr ();

printf ("Secao de Procuras:\n\n");printf ("Secao de Procuras:\n\n");

printf ("Procurar numero (s/n)?: ");printf ("Procurar numero (s/n)?: ");

do scanf ("%c", &c);do scanf ("%c", &c);

while (c != 's' && c != 'n' && c != 'S' && c != while (c != 's' && c != 'n' && c != 'S' && c != 'N');'N');

while (c == 's' || c == 'S') {while (c == 's' || c == 'S') {

printf ("\n\n\tNumero: "); scanf ("%d", printf ("\n\n\tNumero: "); scanf ("%d", &num);&num);

/*/* Procura de um numero no vetorProcura de um numero no vetor*/*/

achou = false; inf = 0; sup = n - 1;achou = false; inf = 0; sup = n - 1;

do {do {

med = (inf + sup) / 2;med = (inf + sup) / 2;

if (num == V[med]) achou = true;if (num == V[med]) achou = true;

else if (num < V[med]) sup = med else if (num < V[med]) sup = med - 1;- 1;

else inf = med + 1;else inf = med + 1;

} while (!achou && inf <= sup);} while (!achou && inf <= sup);

/*/* Emissao do resultado da procura e final do Emissao do resultado da procura e final do programaprograma */*/

if (achou)if (achou)

printf ("\n\t%d estah na posicao %d da relacao\n\n", printf ("\n\t%d estah na posicao %d da relacao\n\n", num, med);num, med);

elseelse

printf ("\n\t%d nao estah na relacao\n\n",num);printf ("\n\t%d nao estah na relacao\n\n",num);

printf ("Procurar outro numero (s/n)?: ");printf ("Procurar outro numero (s/n)?: ");

do scanf ("%c", &c);do scanf ("%c", &c);

while (c != 's' && c != 'n' && c != 'S' && c !while (c != 's' && c != 'n' && c != 'S' && c != 'N');= 'N');

}}

}}

/*/* Fechamento da telaFechamento da tela */*/

printf ("\n\n"); system ("pause"); getch ();printf ("\n\n"); system ("pause"); getch ();

}}

7.3.3 – Manipulação de polinômios7.3.3 – Manipulação de polinômios

Seja Seja P(x)P(x) um polinômio em um polinômio em xx dado pela dado pela fórmulafórmula

P(x) = AP(x) = A00 + A + A11x + Ax + A22xx22 + A + A33xx33 + … + A + … + An-1n-1xxn-1n-1 + + AAnnxxnn

Há Há várias formasvárias formas de se de se armazenararmazenar na na memória um memória um polinômiopolinômio com este com este

Uma das formas mais Uma das formas mais simplessimples é guardar seus é guardar seus coeficientescoeficientes num num vetorvetor e seu e seu graugrau numa numa variávelvariável escalar inteira escalar inteira

P(x) = AP(x) = A00 + A + A11x + Ax + A22xx22 + A + A33xx33 + … + A + … + An-1n-1xxn-1n-1 + + AAnnxxnn

A seguir, o A seguir, o desenvolvimentodesenvolvimento de um programa de um programa para ler os dados sobre para ler os dados sobre 2 polinômios2 polinômios e fazer a e fazer a somasoma e a e a multiplicaçãomultiplicação entre eles entre eles

No próximo slide, um No próximo slide, um exemplo da telaexemplo da tela por ele por ele produzidaproduzida

n

A0

0

A1

1

A2

2

A3

3

An-

1n-1

An

n

P

TRABALHO COM POLINOMIOSTRABALHO COM POLINOMIOS

Grau do Polinomio P1: Grau do Polinomio P1: 33

Coeficientes de P1 (0 a 3):Coeficientes de P1 (0 a 3):

3 5 -2 43 5 -2 4

Grau do Polinomio P2: Grau do Polinomio P2: 33

Coeficientes de P2 (0 a 3):Coeficientes de P2 (0 a 3):

4 -3 0 -44 -3 0 -4

Polinomio P1: Grau 3Polinomio P1: Grau 3

+ (3) + (5)*X + (-2)*X^2 + (4)*X^3+ (3) + (5)*X + (-2)*X^2 + (4)*X^3

Polinomio P2: Grau 3Polinomio P2: Grau 3

+ (4) + (-3)*X + (-4)*X^3+ (4) + (-3)*X + (-4)*X^3

Polinomio Soma PS: Grau 2Polinomio Soma PS: Grau 2

+ (7) + (2)*X + (-2)*X^2+ (7) + (2)*X + (-2)*X^2

Polinomio Produto PM: Grau 6Polinomio Produto PM: Grau 6

+ (12) + (11)*X + (-23)*X^2 + (10)*X^3 + (-32)*X^4 + (8)*X^5 + (-16)*X^6+ (12) + (11)*X + (-23)*X^2 + (10)*X^3 + (-32)*X^4 + (8)*X^5 + (-16)*X^6

Digite algo para encerrar:Digite algo para encerrar:

Polinômios de entrada:

P1(x) = 3 + 5x - 2x2 + 4x3

P2(x) = 4 - 3x - 4x3

P(x) = AP(x) = A00 + A + A11x + Ax + A22xx22 + A + A33xx33 + … + A + … + An-1n-1xxn-1n-1 + A + Annxxnn

Esse Esse desenvolvimentodesenvolvimento se orientará pelos seguintes se orientará pelos seguintes passospassos::

Leitura e correçãoLeitura e correção dos dados dos dois polinômios dos dados dos dois polinômios

EscritaEscrita dos dois polinômios dos dois polinômios

SomaSoma dos dois polinômios, com dos dois polinômios, com correçãocorreção do grau, do grau, e escrita do e escrita do resultadoresultado

MultiplicaçãoMultiplicação dos dois polinômios e escrita do dos dois polinômios e escrita do resultadoresultado

n

A0

0

A1

1

A2

2

A3

3

An-

1n-1

An

n

P

P(x) = AP(x) = A00 + A + A11x + Ax + A22xx22 + A + A33xx33 + … + A + … + An-1n-1xxn-1n-1 + A + Annxxnn

Necessidade de correção do grau:Necessidade de correção do grau:

Possibilidade do operador digitar o valor Possibilidade do operador digitar o valor zerozero para para os os coeficientescoeficientes dos termos de dos termos de graus mais graus mais elevadoselevados

Numa Numa soma soma de polinômios de mesmo grau, os de polinômios de mesmo grau, os coeficientescoeficientes dos termos de dos termos de graus mais elevadosgraus mais elevados dos dois polinômios poderão ter o dos dois polinômios poderão ter o mesmo valormesmo valor absoluto com absoluto com sinais opostossinais opostos

Exemplo: P1(x) = 3 + 5x - 2xExemplo: P1(x) = 3 + 5x - 2x2 2 + 4x + 4x33 P2(x) = 4 + 2x P2(x) = 4 + 2x22 - 4x- 4x33

n

A0

0

A1

1

A2

2

A3

3

An-

1n-1

An

n

P

Declarações:Declarações:

typedef float polin[100];typedef float polin[100];

polin P1 = {0}, P2 = {0}, PS = {0}, PM = polin P1 = {0}, P2 = {0}, PS = {0}, PM = {0}, Paux;{0}, Paux;

int n1, n2, ns, nm, naux, i, j;int n1, n2, ns, nm, naux, i, j;

n1, n2, ns, nm: grausn1, n2, ns, nm: graus do do 1º1º e e 2º2º polinômios e polinômios e dos polinômios dos polinômios somasoma e e multiplicaçãomultiplicação

P1P1, , P2P2, , PS PS e e PMPM são inicializados com são inicializados com zerozero nas nas declarações, para facilitar a programação da declarações, para facilitar a programação da somasoma e da e da multiplicaçãomultiplicação

n

A0

0

A1

1

A2

2

A3

3

An-

1n-1

An

n

P

Leitura de um polinômio:Leitura de um polinômio:

Consiste na leitura de um valor para Consiste na leitura de um valor para nn e de e de valores para valores para n+1n+1 elementoselementos do vetor do vetor PP

Leituras similares já foram vistasLeituras similares já foram vistas

n

A0

0

A1

1

A2

2

A3

3

An-

1n-1

An

n

P

Correção do grau de um polinômio lido:Correção do grau de um polinômio lido:

Supondo que o valor lido para Supondo que o valor lido para nn seja seja 7 7 e que os e que os 88 valores para os elementos de valores para os elementos de P P sejam sejam 66,, -3 -3,, 44,, -5 -5,, 12 12,, 0 0,, 0 0 e e 0 0,, tem-se:tem-se:

Na realidade, o grau de Na realidade, o grau de P P não é não é 77

7n

6

0

-3

1

4

2

-5

3

12

4

0

5

P0

6 98

0

7 99

Correção do grau de um polinômio lido:Correção do grau de um polinômio lido:

Percorre-se o vetor com um cursor Percorre-se o vetor com um cursor ii, de , de P[n] = P[n] = P[7]P[7] para a esquerda, enquanto para a esquerda, enquanto P[i] = 0P[i] = 0

Quando Quando i = 4i = 4, , P[i] = P[4] = 12 ≠ 0P[i] = P[4] = 12 ≠ 0

Então grau do polinômio éEntão grau do polinômio é 4 4

7n

6

0

-3

1

4

2

-5

3

12

4

0

5

P0

6 98

0

7 99

i

4n

Programação:

for (i = n; P[i] == 0.0 && i != 0; i--);n = i;

Se inclusive P[0] = 0.0, zero é o grau de P

Escrita de um polinômio:Escrita de um polinômio:

printf ("\nPolinomio P: Grau %d\n\n\t", n);printf ("\nPolinomio P: Grau %d\n\n\t", n);

for (i = 0; i <= n; i++)for (i = 0; i <= n; i++)

if (P[i] != 0.0 || n == 0) {if (P[i] != 0.0 || n == 0) {

printf (" + (%g)", P[i]);printf (" + (%g)", P[i]);

if (i != 0) {if (i != 0) {

printf ("*X");printf ("*X");

if (i > 1) printf ("^%d", i);if (i > 1) printf ("^%d", i);

}}

}}

n

A0

0

A1

1

A2

2

A3

3

An-

1n-1

An

n

P

Só escreve um termo se o coeficiente não for zero ou se for único termo de um polinômio de grau zeroSó escreve a incógnita X se o grau do termo não for zero

Só escreve o grau do termo se for maior que 1

Exemplos:

+ (3) + (5)*X + (-2)*X^2 + (4)*X^3

+ (4) + (-3)*X + (-4)*X^3

Soma de 2 polinômios P1 e P2:Soma de 2 polinômios P1 e P2:

Exemplo 1:Exemplo 1:

2n1

3

0

5

1

-2

2

0

3

0

4

0

5

P10

6

0

7

0

99

P1(x) = 3 + 5x - 2x2

P2(x) = 4 - 3x + 6x2 + 4x3 - 5x4

PS(x) = 7 + 2x + 4x2 + 4x3 - 5x4

+

4n2

4

0

-3

1

6

2

4

3

-5

4

0

5

P20

6

0

7

0

99

4ns

7

0

2

1

4

2

4

3

-5

4

0

5

PS0

6

0

7

0

99

ns = maior (n1, n2)

Inicialmente P1 = P2 = PS = {0}


Exemplo 2:Exemplo 2:

4n1

3

0

5

1

-2

2

-4

3

5

4

0

5

P10

6

0

7

0

99

P1(x) = 3 + 5x - 2x2 - 4x3 + 5x4

P2(x) = 4 - 3x + 6x2 + 4x3 - 5x4

PS(x) = 7 + 2x + 4x2 + 0x3 + 0x4

= 7 + 2x + 4x2

+

4n2

4

0

-3

1

6

2

4

3

-5

4

0

5

P20

6

0

7

0

99

2ns

7

0

2

1

4

2

0

3

0

4

0

5

PS0

6

0

7

0

99

Inicialmente, ns = maior (n1, n2)

Depois faz-se a correção do grau


4n1

3

0

5

1

-2

2

-4

3

5

4

0

5

P10

6

0

7

0

99

4n2

4

0

-3

1

6

2

4

3

-5

4

0

5

P20

6

0

7

0

99

2ns

7

0

2

1

4

2

0

3

0

4

0

5

PS0

6

0

7

0

99

ns = (n1 > n2) ? n1 : n2;for (i = 0; i <= ns; i++)

PS[i] = P1[i] + P2[i];for (i = ns; PS[i] == 0.0 && i != 0; i--);ns = i;

Programação

Multiplicação de 2 polinômios P1 e P2:Multiplicação de 2 polinômios P1 e P2:

Exemplo:Exemplo:

P1(x) = 3 + 5x - 2x2 + 4x3

P2(x) = 4 - 3x - 4x3

PM(x) =

4 * (3 + 5x - 2x2 + 4x3) +(-3x) * (3 + 5x - 2x2 + 4x3) +(-4x3) * (3 + 5x - 2x2 + 4x3)

*

PM(x) =

12 + 20x - 8x2 + 16x3 + - 9x - 15x2 + 6x3 - 12x4 + - 12x3 - 20x4 + 8x5 - 16x6

PM(x) = 12 + 11x - 23x2 + 10x3 - 32x4 + 8x5 - 16x6

Esquema de programação:

PM(x) = 0;for (j = 0; j <= n2; j++) if (P2[j] != 0) { Paux(x) = P1(x) * P2[j]; PM(x) += Paux(x); }

‘Paux’ guarda a multiplicação de P1 por um termo de P2




nm = n1 + n2;for (j = 0; j <= n2; j++)

if (P2[j] != 0.0) { for (i = 0; i < 100; i++) Paux[i] = 0;

for (i = 0; i <= n1; i++)Paux[i+j] = P1[i] *

P2[j];naux = n1 + j;for (i = 0; i <= naux; i++)

PM[i] = Paux[i] + PM[i];

}

Programação

‘j’ é o grau do termo de P2 que multiplica P1

O grau de Paux é a soma do grau de P1 com o grau do termo de P2 que multiplica P1




nm = n1 + n2;for (j = 0; j <= n2; j++)

if (P2[j] != 0.0) { for (i = 0; i < 100; i++) Paux[i] = 0;

for (i = 0; i <= n1; i++)Paux[i+j] = P1[i] *

P2[j];naux = n1 + j;for (i = 0; i <= naux; i++)

PM[i] = Paux[i] + PM[i];

}

Programação

Dentro do ‘if’

for (i = 0; i < 100; i++) Paux[i] = 0;

pode ser substituído por

polin Paux = {0.0};

Conceito de bloco, a ser visto no capítulo de Subprogramação

A seguir, o programa completo dos polinômios

/* Declaracoes, inicializacoes e escrita de titulo/* Declaracoes, inicializacoes e escrita de titulo*/*/



typedef float polin[100];typedef float polin[100];

int main ( ) {int main ( ) {

polin P1 = {0}, P2 = {0}, PS = {0}, PM = {0};polin P1 = {0}, P2 = {0}, PS = {0}, PM = {0};

int n1, n2, ns, nm, naux, i, j;int n1, n2, ns, nm, naux, i, j;

printf ("TRABALHO COM POLINOMIOS\n\n");printf ("TRABALHO COM POLINOMIOS\n\n");

/* Leitura do primeiro polinomio e correcao de seu grau /* Leitura do primeiro polinomio e correcao de seu grau */*/

printf ("Grau do Polinomio P1: "); scanf ("%d", &n1);printf ("Grau do Polinomio P1: "); scanf ("%d", &n1);

printf ("Coeficientes de P1 (0 a %d):\n\t", n1);printf ("Coeficientes de P1 (0 a %d):\n\t", n1);

for (i = 0; i <= n1; i++)for (i = 0; i <= n1; i++)

scanf ("%f", &P1[i]);scanf ("%f", &P1[i]);

for (i = n1; P1[i] == 0.0 && i != 0; i--);for (i = n1; P1[i] == 0.0 && i != 0; i--);

n1 = i;n1 = i;

/* Leitura do segundo polinomio e correcao de seu grau /* Leitura do segundo polinomio e correcao de seu grau */*/

printf ("\nGrau do Polinomio P2: "); scanf ("%d", &n2);printf ("\nGrau do Polinomio P2: "); scanf ("%d", &n2);

printf ("Coeficientes de P2 (0 a %d):\n\t", n2);printf ("Coeficientes de P2 (0 a %d):\n\t", n2);

for (i = 0; i <= n2; i++)for (i = 0; i <= n2; i++)

scanf ("%f", &P2[i]);scanf ("%f", &P2[i]);

for (i = n2; P2[i] == 0.0 && i != 0; i--);for (i = n2; P2[i] == 0.0 && i != 0; i--);

n2 = i;n2 = i;

/* Escrita dos polinomios lidos /* Escrita dos polinomios lidos */*/

printf ("\nPolinomio P1: Grau %d\n\n\t", n1);printf ("\nPolinomio P1: Grau %d\n\n\t", n1);

for (i = 0; i <= n1; i++)for (i = 0; i <= n1; i++)

if (P1[i] != 0.0 || n1 == 0) {if (P1[i] != 0.0 || n1 == 0) {

printf (" + (%g)", P1[i]);printf (" + (%g)", P1[i]);

if (i != 0) {if (i != 0) {

printf ("*X"); if (i > 1) printf ("^%d", i);printf ("*X"); if (i > 1) printf ("^%d", i);

}}

}}

printf ("\n\nPolinomio P2: Grau %d\n\n\t", n2);printf ("\n\nPolinomio P2: Grau %d\n\n\t", n2);

for (i = 0; i <= n2; i++)for (i = 0; i <= n2; i++)

if (P2[i] != 0.0 || n2 == 0) {if (P2[i] != 0.0 || n2 == 0) {

printf (" + (%g)", P2[i]);printf (" + (%g)", P2[i]);

if (i != 0) {if (i != 0) {

printf ("*X"); if (i > 1) printf ("^%d", i);printf ("*X"); if (i > 1) printf ("^%d", i);

}}

}}

/* Soma dos polinomios e escrita do resultado /* Soma dos polinomios e escrita do resultado */*/

ns = (n1 > n2) ? n1 : n2;ns = (n1 > n2) ? n1 : n2;

for (i = 0; i <= ns; i++)for (i = 0; i <= ns; i++)

PS[i] = P1[i] + P2[i];PS[i] = P1[i] + P2[i];

for (i = ns; PS[i] == 0.0 && i != 0; i--);for (i = ns; PS[i] == 0.0 && i != 0; i--);

ns = i;ns = i;

printf ("\n\nPolinomio Soma PS: Grau %d\n\n", ns);printf ("\n\nPolinomio Soma PS: Grau %d\n\n", ns);

for (i = 0; i <= ns; i++)for (i = 0; i <= ns; i++)

if (PS[i] != 0.0 || ns == 0) {if (PS[i] != 0.0 || ns == 0) {

printf (" + (%g)", PS[i]);printf (" + (%g)", PS[i]);

if (i != 0) {if (i != 0) {

printf ("*X"); if (i > 1) printf ("^printf ("*X"); if (i > 1) printf ("^%d", i);%d", i);

}}

}}

/* Multiplicacao dos polinomios e escrita do resultado /* Multiplicacao dos polinomios e escrita do resultado */*/

nm = n1 + n2;nm = n1 + n2;

for (j = 0; j <= n2; j++)for (j = 0; j <= n2; j++)

if (P2[j] != 0.0) {if (P2[j] != 0.0) {

polin Paux = {0.0};polin Paux = {0.0};

for (i = 0; i <= n1; i++) Paux[i+j] = P1[i] * P2[j];for (i = 0; i <= n1; i++) Paux[i+j] = P1[i] * P2[j];

naux = n1 + j;naux = n1 + j;

for (i = 0; i <= naux; i++) PM[i] = Paux[i] + for (i = 0; i <= naux; i++) PM[i] = Paux[i] + PM[i];PM[i];

}}

printf ("\n\nPolinomio Produto PM: Grau %d\n\n", nm);printf ("\n\nPolinomio Produto PM: Grau %d\n\n", nm);

for (i = 0; i <= nm; i++)for (i = 0; i <= nm; i++)

if (PM[i] != 0.0 || nm == 0) {if (PM[i] != 0.0 || nm == 0) {

printf (" + (%g)", PM[i]);printf (" + (%g)", PM[i]);

if (i != 0) { printf ("*X"); if (i > 1) printf ("^%d", if (i != 0) { printf ("*X"); if (i > 1) printf ("^%d", i); }i); }

}}

printf ("\n\n"); system ("pause"); return 0;printf ("\n\n"); system ("pause"); return 0;

}}

Observações:Observações:

Neste programa, há 2 trechos muito semelhantes Neste programa, há 2 trechos muito semelhantes para para lerler os dados de os dados de P1P1 e e P2P2 e 4 para e 4 para escreverescrever P1P1, , P2P2, , PSPS e e PMPM

Conforme o mesmo capítulo sobre Conforme o mesmo capítulo sobre Subprogramação, pode-se fazer um só Subprogramação, pode-se fazer um só subprogramasubprograma para para lerler e outro para e outro para escreverescrever o o conteúdo de um conteúdo de um polinômio genéricopolinômio genérico

Pode-se então Pode-se então chamá-loschamá-los respectivamente respectivamente duasduas e e quatro vezesquatro vezes na função na função mainmain, uma para cada , uma para cada polinômio polinômio

Isso deixa a função Isso deixa a função mainmain bem mais bem mais sintéticasintética

Além disso, pode-se fazer um Além disso, pode-se fazer um subprogramasubprograma para para somarsomar e outro para e outro para multiplicarmultiplicar 2 polinômios 2 polinômios

Exercícios 6.3:Exercícios 6.3:

1.1.Escrever um programa para: Escrever um programa para:

a)a)Ler um número inteiro e armazená-lo na Ler um número inteiro e armazená-lo na variável variável nn

b)b)Ler dois vetores Ler dois vetores A A e e BB de números reais com de números reais com nn elementos cada elementos cada

c)c)Formar e escrever dois outros vetores Formar e escrever dois outros vetores CC e e DD de de n n números reais tais que, para números reais tais que, para 0 0 i i n-1 n-1::

C[i] = max (A[i], B[i]) e D[i] = média (A[i], C[i] = max (A[i], B[i]) e D[i] = média (A[i], B[i])B[i])

2.2. Escrever um programa para ler um vetor Escrever um programa para ler um vetor desordenado de números inteiros, eliminar todas desordenado de números inteiros, eliminar todas as suas duplicatas e escrevê-lo sem elementos as suas duplicatas e escrevê-lo sem elementos repetidosrepetidos

3.3. Em Estatística, utiliza-se uma série de medidas Em Estatística, utiliza-se uma série de medidas para a análise de um conjunto de dados. Dado para a análise de um conjunto de dados. Dado um conjunto de valores um conjunto de valores XXii (0 ≤ i ≤ n-1) (0 ≤ i ≤ n-1) são são definidas, entre outras grandezas:definidas, entre outras grandezas:

Escrever um programa em C para ler e imprimir Escrever um programa em C para ler e imprimir os os elementos do vetor elementos do vetor XX, calcular e imprimir , calcular e imprimir

Média aritmética

Média quadrática

Desvio padrão

X, RMQ e S

¯

4.4. O MMC (mínimo múltiplo comum) entre vários O MMC (mínimo múltiplo comum) entre vários números pode ser calculado conforme o seguinte números pode ser calculado conforme o seguinte esquema usando como exemplo os números 48, esquema usando como exemplo os números 48, 36, 63, 7536, 63, 75

Escrever um programa em C para ler um vetor Escrever um programa em C para ler um vetor de números inteiros positivos e achar e escrever de números inteiros positivos e achar e escrever o MMC entre eles, usando o esquema acima; o o MMC entre eles, usando o esquema acima; o programa deve mostrar o andamento do cálculo, programa deve mostrar o andamento do cálculo, ou seja, deve exibir o esquema acima ou seja, deve exibir o esquema acima

Documents

Capítulo VI – Variáveis Indexadas