5 - Exercícios sobre Arrays

Prévia do material em texto

Observações de Engenharia de Software 6.1 Definir o tamanho de cada array como uma constante simbólica torna os programas mais flexíveis. 6.2 É possível passar um array por valor usando um truque simples explicado no Capítulo 10. 6.3 O qualificador de tipo const pode ser aplicado a um parâmetro de um array em uma definição de função para evitar que o array original seja modificado no corpo da função. Esse é outro exemplo do princípio do privilégio mínimo. As funções não devem ter a capacidade de modificar um array, a menos que isso seja absolutamente necessário. Exercícios de Revisão 6.1 Complete as lacunas: a) Listas e tabelas de valores são armazenadas em_. b) Os elementos de um array são relacionados entre si pelo fato de que possuem o mesmo ___________ e ______________. c) O número usado para fazer referência a um elemento específico de um array é chamado seu _________ d) Deve ser usado um(a) _______________ para declarar o tamanho de um array porque isso torna os programas mais flexíveis. e) O processo de colocar em ordem os elementos de um array é chamado ________ um array. f) O processo de determinar se um array contém um valor chave específico é chamado _______________ o array g) Um array que usa dois subscritos é chamado array _____________ . 6.2 Diga se cada uma das sentenças a seguir é verdadeira ou falsa. Se a resposta for falsa, explique o motivo a) Um array pode armazenar muitos tipos diferentes de valores. b) Um subscrito de array pode ser um tipo de dado float. c) Se houver menos inicializadores em uma lista do que o número de elementos no array, a lingua gem C inicializa automaticamente os elementos restantes com o último valor da lista de inicializa dores. d) É um erro se uma lista de inicializadores possuir mais inicializadores do que o número de elementos do array. e) Um elemento em particular de um array que for passado a uma função e modificado na função chamada terá seu valor modificado na função que chamou. 6.3 Responda às seguintes perguntas a respeito de um array chamado fracoes. a) Defina uma constante simbólica TAMANHO a ser substituída pelo texto de substituição 10. b) Declare um array com tantos elementos do tipo float quanto o valor de TAMANHO e inicialize os elementos com o valor 0. c) Dê o nome do quarto elemento a partir do início do array. 
d) Chame o elemento 4 do array. e) Atribua o valor 1. 667 ao elemento nove do array. f) Atribua o valor 3.333 ao sétimo elemento do array. g) Imprima os elementos 6 a 9 do array com dois dígitos de precisão à direita do ponto decimal e mostre a saída que é realmente apresentada na tela. h) Imprima todos os elementos do array usando uma estrutura de repetição for. Admita que a variável in teira x foi definida como uma variável de controle para o loop. Mostre a saída do programa. 6.4 Responda às seguintes perguntas a respeito de um array chamado tabela. a) Declare o array como um array inteiro com 3 linhas e 3 colunas. Considere que a constante simbólica TAMANHO foi definida como 3. b) Quantos elementos o array contém? c) Use uma estrutura de repetição for para inicializar cada elemento do array com a soma de seus subscri tos. Presuma que as variáveis inteiras x e y são declaradas como variáveis de controle. d) Imprima os valores de cada elemento do array tabela. Presuma que o array foi inicializado com a de claração, int tabela[TAMANHO][TAMANHO] = {{1, 8}, {2, 4, 6}, {5}}; e as variáveis inteiras x e y são declaradas como variáveis de controle. Mostre a saída. 6.5 Encontre o erro em cada um dos segmentos de programa a seguir e o corrija. a) #define TAMANHO 100; b) TAMANHO = 10; c) Assuma int b[10] = {0}, i; for (i = 0; i <= 10; i++) d) #include <stdio.h>; e) Assuma int a[2][2J = {{1, 2}, {3, 4}}; a[1,1] = 5; 
 Respostas dos Exercícios de Revisão 6.1 a) Arrays. b) Nome, tipo. c) Subscrito, d) Constante simbólica, e) Classificação, f) Pesquisa, g) Bidimensional 6.2 a) Falso. Um array pode armazenar apenas valores do mesmo tipo. b) Falso. Um subscrito de array deve ser um inteiro ou uma expressão inteira. c) Falso. A linguagem C inicializa automaticamente os elementos restantes com zeros. d) Verdadeiro. e) Falso. Os elementos isolados de um array são passados por meio de chamadas por valor. Se o array intei ro for passado a uma função, quaisquer modificações se refletirão no original. 6.3 a) #define TAMANHO 10 b) float fracoes[TAMANHO] = {0}; c) fracoes [3] d) fracoes[4] e) fracoes [9] = 1.667; f) fracoes [6] = 3.333; g) printf ("%.2'f %.2f\n", fracoes[6], fracoes[9]); Saída: 3.33 1.67. h) for (x = 0; X <= TAMANHO - 1; X++) printf("fracoes[%d] = %f\n", x, fracoes[x]); Saída: fracoes[0] = 0.000000 fracoes[1] = 0.000000 fracoes[2] = 0.000000 fracoes[3] = 0.000000 fracoes[4] = 0.000000 fracoes[5] = 0.000000 fracoes[6] = 3.333000 fracoes[7] = 0.000000 fracoes[8] = 0.000000 fracoes[9] = 1.667000 6.4 6.4 a) int tabela [TAMANHO] [TAMANHO] ; b) Nove elementos. c) for (x = 0; X <= TAMANHO - 1; X++) for (y = 0; y <= TAMANHO - 1; y++) tabela[x][y] = x + y; d) for (x = 0; x <= TAMANHO - 1; X+ + ) for (y = 0; y <= TAMANHO - 1; y++) printf("tabela[%d][%d] =%d\n", x, y, tabela[x][y]); Saída: tabela[0][0] = 1 tabela[0][1] = 8 tabela[0][2] = 0 tabela[1][0] = 2 tabela[1][1] = 4 tabela[1][2] = 6 tabela[2][0] = 5 tabela[2][1] = 0 tabela[2][2] = 0 6.5 a) Erro: Ponto-e-vírgula no final da diretiva de pré-processador #define. Correção: Eliminar o ponto-e-vírgula. b) Erro: Atribuir um valor a uma constante simbólica usando uma instrução de atribuição. Correção: Atribuir um valor a uma constante simbólica em uma diretiva de pré-
processador #define sem usar o operador de atribuição, como em #define TAMANHO 10. c) Erro: Fazer referência a um elemento além dos limites do array (b [10]). Correção: Mudar o valor final da variável de controle para 9. d) Erro: Ponto-e-vírgula no final da diretiva de pré-processador #include. Correção: Eliminar o ponto-e-vírgula. e) Erro: Subscritos do array de forma incorreta. Correção: Mudar a instrução para a [1][1] = 5 ; Exercícios 6.6 Preencha as lacunas em cada uma das sentenças a seguir: a) A linguagem C armazena listas de valores em _____________. b) Os elementos de um array estão relacionados entre si pelo fato de que __________. c) Ao se referir a um elemento de array, o número da posição contida entre colchetes é chamado _______________. d) Os nomes dos cinco elementos do array p são ______, ____________, ___________. ____________ e ______________ e) O conteúdo de um elemento determinado do array é chamado _____________ daquele elemento. f) Denominar um array, declarar seu tipo e especificar seu número de elementos é chamado_______________ um array. g) O processo de colocar elementos de um array em ordem descendente ou ascendente é chamado ________________ . h) Em um array bidimensional, o primeiro subscrito (por convenção) identifica a ___________________ de um elemento, e o segundo subscrito (por convenção) identifica a _______________ de um elemento. i) Um array m-por-n contém ____________ linhas, ________ colunas e _____________ elementos. j) O nome do elemento na linha 3 e coluna 5 do array d é ________________ . 6.7 Diga quais das sentenças a seguir são verdadeiras e quais são falsas; explique os motivos pelos quais as sentenças foram consideradas falsas. a) Para se referir a um local ou um elemento em particular dentro de um array, especificamos o nome de array e o valor daquele elemento. b) Uma declaração de array reserva espaço para ele. c) Para indicar que 100 locais devem ser reservados para um array inteiro p, o programador deve escrever a declaração p[100] ; d) Um programa em C que inicializa todos os 15 elementos de um array com zeros deve conter uma instrução for. e) Um programa em C que soma os elementos de um array de dois subscritos deve conter instruções aninhadas. f) A média, a mediana e a moda do seguinte conjunto de valores são 5, 6 e 7 respectivamente:1, 2, 5,6,7,7,7. 6.8 Escreva instruções em C que realizem o seguinte: a) Apresentem na tela o valor do sétimo elemento do array de caracteres f. b) Entrem com um valor no elemento 4 de um array unidimensional de ponto flutuante b. c) Inicializem cada um dos 5 elementos de um array unidimensional inteiro g com o valor 8. 
d) Somem os elementos de um array de ponto flutuante c que possui 100 elementos. e) Copiem o array a para a primeira parte do array b. Considere float a [11], b[34] ; f) Determine e imprima o menor e o maior valor contidos em um array de ponto flutuante w com 99 elementos. 6.9 Considere um array inteiro 2-por-5 t. a) Escreva uma declaração para t. b) Quantas linhas t possui? c) Quantas colunas t possui? d) Quantos elementos t possui? e) Escreva os nomes de todos os elementos da segunda linha de t. f) Escreva os nomes de todos os elementos da terceira coluna de t. g) Escreva uma única instrução em C que defina como zero o elemento da linha 1 e coluna 2 de t. h) Escreva uma série de instruções em C que inicialize como zero cada elemento de t. Não use uma estrutura de repetição. i) Escreva uma estrutura for aninhada que inicialize cada elemento de t como zero. j) Escreva uma instrução em C que entre com os valores dos elementos de t a partir do terminal. k) Escreva uma série de instruções em C que determine e imprima o menor valor do array t. 1) Escreva uma instrução em C que exiba na tela os elementos da primeira linha de t. m) Escreva uma instrução em C que some os elementos da quarta coluna de t. n) Escreva uma série de instruções em C que imprima o array t em um formato organizado de tabela. Liste os subscritos das colunas como cabeçalho ao longo do topo e liste os subscritos das linhas à esquerda de cada linha. 6.10 Use um array unidimensional para resolver o seguinte problema. Uma companhia paga seus vendedores com base em comissões. O vendedor recebe $200 por semana mais 9 por cento de suas vendas brutas daquela semana. Por exemplo, um vendedor que teve vendas brutas de $3000 em uma semana recebe $200 mais 9 por cento de $3000, ou seja, um total de $470. Escreva um programa em C (usando um array de contadores) que determine quantos vendedores receberam salários nos seguintes intervalos de valores (considere que o salário de cada vendedor é trancado para que seja obtido um valor inteiro): 1. $200-$299 2. $300-$399 3. $400-$499 4. $500-$599 5. $600-$699 6. $700-$799 7. S800-S899 8. $900-$999 9. $1000 em diante 6.11 A classificação de bolhas (bubble sort) apresentada na Fig. 6.15 é ineficiente para arrays grandes. Faça as modificações simples a seguir para melhorar o desempenho da classificação de bolhas. a) Depois da primeira passada, garante-se que o maior número está no elemento de maior número do array; depois da segunda passada, os dois maiores números estão em 
"seus lugares", e assim por diante. Em vez, de fazer nove comparações en cada passada, modifique a classificação de bolhas para fazer oito comparações na segunda passada, sete na terceira e assim por diante. b) Os dados do array já podem estar na ordem adequada ou quase ordenados completamente, assim, por que fazer nove passadas se um número menor seria suficiente? Modifique a classificação para verificar se alguma permuta foi feita ao final de cada passada. Se nenhuma permuta foi realizada, os dados já devem estar na ordem adequada e o programa deve ser encerrado. Se foram feitas permutas, pelo menos uma passada é necessária. 6.12 Escreva instruções simples que realizem cada uma das operações seguintes em um array unidimensional: a) Inicialize com zeros os 10 elementos do array inteiro contagem. b) Adicione 1 a cada um dos 15 elementos do array inteiro bonus. c) Leia os 12 valores do array de ponto flutuante temperaturasMensais a partir do teclado. d) Imprima os 5 valores do array inteiro melhoresEscores em um formato de coluna. 6.13 Encontre o(s) erro(s) em cada uma das seguintes instruções: a) Considere: char str[5]; scanf("%s", str); /* Usuário digita hello */ b) Considere: int a[3] ; printf("$d %d %d\n", a[1], a[2], a[3]); c) float f[3] = {1.1, 10.01, 100.001, 1000.0001}; d) Considere: double d[2] [10] ; d[l, 9] = 2.345; 6.14 Modifique o programa da Fig. 6.16 de forma que a função moda seja capaz de manipular um empate no valor da moda. Modifique também a função media de forma que seja encontrada a média dos dois valores do meio de um array com número par de elementos. 6.15 Use um array unidimensional para resolver o seguinte problema. Leia 20 números, todos situados entre 10 e 100, inclusive. À medida que cada número for lido, imprima-o somente se não for duplicata de um número já lido. Experimente o "pior caso", no qual todos os 20 números são diferentes. Use o menor array possível para resolver esse problema. 6.16 Classifique os elementos do array bidimensional 3-por-5 vendas para indicar a ordem na qual eles são definidos como zero pelo seguinte segmento de programa: for (linha = 0; linha <= 2; linha++) for (coluna = 0; coluna <= 4; coluna++) vendas[linha][coluna] = 0; 6.17 6.17 O que faz o seguinte programa? #include <stdio.h> #define TAMANHO 10 int quelssoFaz(int [], int}; main() int total, a[TAMANHO] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; total = quelssoFaz(a, TAMANHO); printf("Soma dos valores dos elementos do array e %d\n", total); return 0; } int quelssoFaz(int b[], int tamanho) { if (tamanho == 1) 
return b[0]; else return b[tamanho - 1] + quelssoFaz(b, tamanho - 1); } 6.18 O que faz o seguinte programa? #include <stdio.h> #define TAMANHO 10 void algumaFuncao(int [], int}; main() int a[TAMANHO] = {32, 27, 64, 18, 95, 14, 90, 70, 60, 37); printf("Os valores no array sao: \n"); algumaFuncao(a, TAMANHO); printf("\n"); return 0; void algumaFuncao(int b[], int tamanho) if (tamanho > 0) { algumaFuncao(&b[1], tamanho - 1); printf("%d ", b[0]); 6.19 Escreva um programa em C que simule a jogada de dois dados. O programa deve usar rand para rolar o primeiro dado e deve usar rand novamente para rolar o segundo dado. A soma dos dois valores deve então ser calculada. Nota: Como cada dado pode mostrar um valor inteiro de 1 a 6, a soma dos dois valores \ de 2 a 12 com 7 sendo a soma mais freqüente e 2 e 12 sendo as somas menos freqüentes. A Fig. 6.23 mostra as 36 combinações possíveis dos dois dados. Seu programa deve rolar os dados 36.000 vezes. Use um array unidimensional para registrar o número de vezes que cada soma possível é obtida. Imprima os resultados em um formato de tabela. Além disso, determine se as somas são razoáveis, i.e., há seis maneiras de obter 7, portanto, aproximadamente um sexto do total de jogadas deve ser 7. 6.20 Escreva um programa que rode 1000 jogos de Craps e responda a cada uma das seguintes perguntas: a) Quantos jogos são vencidos na primeira jogada, segunda jogada,vigésima jogada e depois da vigésima jogada? b) Quantos jogos são perdidos na primeira jogada, segunda jogada,vigésima jogada e depois da vigésima jogada? c) Quais as probabilidades de vencer no jogo de Craps? (Nota: Você deve descobrir que Craps é um jogos de cassino mais honestos. O que você acha que isso significa?) d) Qual a duração média de um jogo de Craps? e) As probabilidades de vencer aumentam com a duração do jogo? 6.21 (Sistema de Reserva Aérea) Uma pequena companhia aérea acabou de comprar um computador para o seu novo sistema automático de reservas. O presidente pediu a você que programasse o novo sistema em C. Você deve escrever um programa para atribuir assentos a cada vôo do único avião da companhia (capacidade: 10 assentos). Seu programa deve exibir o seguinte menu de alternativas: Favor digitar 1 para "fumante" Favor digitar 2 para "naofumante" Se a pessoa digitar 1, seu programa deve fazer a reserva de um assento no setor dos fumantes (assentos 1-5). Se a pessoa digitar 2, seu programa deve reservar um assento no setor de não-fumantes (assentos 6-10). 
 1 2 3 4 5 6 1 2 3 4 5 6 7 2 3 4 5 6 7 83 4 5 6 7 8 9 4 5 6 7 8 9 10 5 6 7 8 9 10 11 6 7 8 9 10 11 12 Fig. 6.23 Os 36 resultados possíveis da jogada de dois dados. Seu programa deve então imprimir um cartão de embarque indicando o número do assento do passageiro e se ele se encontra no setor de fumantes ou de não-fumantes do avião. Use um array unidimensional para representar o esquema dos assentos do avião. Inicialize todos os elementos do array com 0 para indicar que todos os assentos estão livres. A medida que cada assento for reservado, iguale os elementos correspondentes a 1 para indicar que o assento não está mais disponível. Seu programa nunca deve, obviamente, reservar um assento que já tenha sido distribuído. Quando o setor de fumantes estiver lotado, seu programa deve perguntar se a pessoa aceita um lugar no setor de não-fumantes (e vice-versa). Em caso positivo, faça a reserva apropriada do assento. Em caso negativo, imprima a mensagem "Próximo voo sai em 3 horas." 6.22 Use um array bidimensional para resolver o seguinte problema. Uma companhia tem quatro vendedores (1 a 4) que vendem 5 produtos diferentes (1 a 5). Uma vez por dia, cada vendedor elabora um memorando de cada tipo diferente de produto vendido. Cada memorando contém: 1. O número do vendedor 2. O número do produto 3. O valor total em dólares daquele produto vendido naquele dia Dessa forma, cada vendedor elabora de 0 a 5 memorandos de vendas por dia. Admita que as informações de todos os memorandos do último mês estão disponíveis. Escreva um programa que leia todas essas informaçõess das vendas do último mês e faça um resumo do total de vendas por vendedor e por produto. Todos os totais devem ser armazenados no array bidimensional vendas. Depois de processar todas as informações do último mês, imprima os resultados em um formato de tabela com cada coluna representando um vendedor diferente e cada linha representando um produto diferente. Faça a soma dos valores de cada linha para obter as vendas totais de cada produto no último mês; faça a soma dos valores em cada coluna para obter as vendas totais de cada vendedor no último mês. A tabela impressa deve incluir esses totais à direita das linhas somadas e abaixo das colunas somadas. 6.23 (Gráfico da Tartaruga). A linguagem Logo, que é particularmente popular entre os usuários de computadores pessoais, tornou famoso o conceito dos gráficos da tartaruga. Imagine uma tartaruga mecânica que percorra uma sala sob o controle de um programa em C. A tartaruga possui uma caneta em uma de duas posições, para cima ou para baixo. Quando a caneta está para baixo, a tartaruga desenha figuras à medida que se move; quando a caneta está para cima, a tartaruga se move livremente sem desenhar nada. Neste problema, você simulará a operação da tartaruga e criará também um esquema computadorizado de movimento. Use um array plano 50-por-50 inicializado com zeros. Leia comandos de um array que os contém. Controle sempre a posição atual da tartaruga e se a caneta está para 
cima ou para baixo. Admita que a tartaruga sempre começa na posição 0,0 do plano com sua caneta para cima. O conjunto de comandos da tartaruga que seu programa deve processar são os seguintes: Comando Significado 1 Caneta para cima 2 Caneta para baixo 3 Giro para direita 4 Giro para a esquerda 5, 10 Movimento 10 espaços a frente ( ou outro número diferente de 10 6 Imprime o array 50-por-50 9 Fim dos dados (sentinela) Suponha que a tartaruga esteja em algum lugar próximo do centro do plano. O "programa" a seguir desenharia e imprimiria um quadrado 12-por-12: 2 5,12 3 5,12 3 5,12 3 5,12 1 6 9 À medida que a tartaruga se move com a caneta para baixo, defina os elementos apropriados do array plano como 1s. Quando o comando 6 (imprimir) for emitido, onde houver um 1 no array exiba um asterisco ou outro caractere de sua escolha. Sempre que houver um zero, exiba um espaço em branco. Escreva programa em C para implementar os recursos do gráfico da tartaruga descritos aqui. Escreva vários programas de gráficos da tartaruga para desenhar formas interessantes. Adicione outros comandos para aumentar a potencialidade de sua linguagem de gráfico de tartaruga. 6.24 (Passeio do Cavalo) Um dos problemas mais interessantes para os fãs do jogo de xadrez é o problema do Passeio do Cavalo, proposto originalmente pelo matemático Euler. A questão é esta: a peça do jogo de drez chamada cavalo pode se mover ao longo de um tabuleiro vazio e passar uma única vez em cada uma 64 casas? Estudamos aqui esse interessante problema em profundidade. O cavalo faz movimentos em formato de L (percorre duas casas em uma direção e uma no sentido perpendicular às duas primeiras). Dessa forma, de uma casa no meio do tabuleiro, o cavalo pode fazer movimentos diferentes (numerados de 0 a 7), como mostra a Fig. 6.24. a) Desenhe um tabuleiro de xadrez 8-por-8 em uma folha de papel e tente fazer o Passeio do Cavalo a mão, Coloque um 1 no primeira casa para a qual se mover, um 2 na segunda casa, um 3 na terceira etc. Antes de começar os movimentos, imagine até onde você chegará, lembrando-se que um passeio completo consiste em 64 movimentos. Até onde você chegou? Você chegou perto do quanto havia imaginado? 
 0 1 2 3 4 5 6 7 0 1 2 1 2 3 0 3 K 4 4 7 5 5 6 6 7 Fig. 6.24 Os oito movimentos possíveis do cavalo, b) Agora vamos desenvolver um programa que moverá o cavalo pelo tabuleiro de xadrez. O tabuleiro em si é representado pelo array bidimensional 8-por-8 tabuleiro. Cada um dos quadrados (casas) é inicializado com o valor zero. Descrevemos cada um dos oito movimentos possíveis em termos de seus componentes horizontais e verticais. Por exemplo, um movimento do tipo 0. como mostra a Fig. 6.24, consiste em mover dois quadrados horizontalmente para a direita e um quadrado verticalmente para cima. O movimento 2 consiste em mover um quadrado horizontalmente para a esquerda e dois quadrados verticalmente para cima. Os movimentos horizontais para a esquerda e verticais para cima são indicados por números negativos. Os oito movimentos podem ser descritos por arrays bidimensionais, horizontal e vertical, como se segue: horizontal[0] = 2 horizontal[1] = 1 horizontal[2] = -1 horizontal[3] = -2 horizontal[4] = -2 horizontal[5] = -1 horizontal [6] = 1 horizontal[7] = 2 vertical[0] = -1 vertical[1] = -2 vertical[2] = -2 vertical[3] = -1 vertical[4] = 1 vertical[5] = 2 vertical[6] = 2 vertical[7] = 1 As variáveis linhaAtual e colunaAtual indicam a linha e a coluna da posição atual do cavalo. Para fazer um movimento do tipo numMov, em que numMov está entre 0 e 7, seu programa usa as instruções linhaAtual += vertical[numMov]; colunaAtual += horizontal[numMov]; Utilize um contador que varie de 1 a 64. Grave a última contagem em cada casa para a 
qual o cavalo se mover. Lembre-se de testar cada movimento potencial para verificar se cavalo já esteve naquele quadrado. E, obviamente, teste cada movimento potencial para se certificar de que o cavalo não está saindo do tabuleiro. Agora escreva um programa para mover o cavalo pelo tabuleiro de xadrez. Rode o programa. Quantos movimentos o cavalo fez? c) Depois de tentar escrever e rodar o programa do Passeio do Cavalo, provavelmente você adquiriu alguns conceitos valiosos. Usaremos esses conceitos para desenvolver uma heurística (ou estratégia) para mover o cavalo. A heurística não garante o sucesso, mas uma heurística desenvolvida cuidadosamente aumenta as probabilidades de ele ser atingido. Você pode ter observado que os quadrados externos são, de alguma forma, mais problemáticos do que os quadrados próximos ao centro do tabuleiro. Na realidade, os quadrados mais problemáticos, ou inacessíveis, são os quatro cantos. A intuição pode sugerir que você deve tentar mover o cavalo para os quadrados mais problemáticos e deixar livres os quadrados mais fáceis de atingir para que, quando o tabuleiro ficar congestionado próximo ao final do passeio, haja maior probabilidade de sucesso. Podemosdesenvolver uma "heurística de acessibilidade" classificando cada um dos quadrados de acordo com sua acessibilidade e depois sempre mover o cavalo para o quadrado (dentro dos movimentos em forma de L, obviamente) que seja mais inacessível. Colocamos no array bidimensional acessibilidade os números que indicam a partir de quantos quadrados um determinado quadrado pode ser acessado. Portanto, em um tabuleiro vazio, as casas centrais são classificadas com 8s, os quadrados dos cantos são classificados com 2s e os outros quadrados possuem números de acessibilidade 3, 4 e 6, como é mostrado a seguir 2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2 Agora escreva uma versão do programa do Passeio do Cavalo usando a heurística de acessibilidade. Em qualquer tempo, o cavalo deve se mover para o quadrado com menor número de acessibilidade. Em caso de empate, o cavalo pode se mover para qualquer dos quadrados que empataram. Portanto, o passeio pode começar em qualquer um dos quatro cantos. (Nota: A medida que o cavalo se mover no tabuleiro, seu programa deve reduzir os números de acessibilidade quando cada vez mais quadrados forem ocupados. Dessa forma, a qualquer instante durante o passeio o número de acessibilidade de cada quadrado disponível permanecerá igual ao número de quadrados dos quais aquele espaço pode ser alcançado.) Rode essa versão de seu programa. Você conseguiu fazer um passeio completo? Agora modifique o programa para executar 64 passeios, um para cada quadrado do tabuleiro. Quantos passeios completos você coseguiria fazer? d) Escreva uma versão do programa do Passeio do Cavalo na qual, ao encontrar um empate entre dois ou mais quadrados, você faça sua escolha verificando os quadrados que podem ser alcançados a partir dos quadrados "empatados". Seu programa deve fazer o movimento do cavalo para o quadrado para o qual o próximo movimento levar ao quadrado com menor número de acessibilidade. 
 6.25 (Passeio do Cavalo: Métodos de Força Bruta) No Exercício 6.24 desenvolvemos uma solução para o problema do Passeio do Cavalo. O método usado, chamado "heurística de acessibilidade", gera muitas soluções e funciona de uma maneira eficiente. Como os computadores continuam a ser cada vez mais poderosos, poderemos resolver muitos problemas com base apenas no poder computacional e em algoritmos relativamente simples. Vamos chamar esse método de resolução de problemas de "força bruta". a) Use a geração de números aleatórios para permitir ao cavalo percorrer o tabuleiro (em seus movimentos permitidos na forma de L, obviamente) de maneira aleatória. Seu programa deve executar um passeio e imprimir o tabuleiro final. Até onde o cavalo chegou? b) Muito provavelmente, o programa anterior levará a um passeio relativamente curto. Agora modifique seu programa para tentar 1000 passeios. Use um array unidimensional para controlar o número de passeios por extensão alcançada. Quando seu programa terminar de fazer os 1000 passeios, ele deve imprimir essas informações em um formato de tabela. Qual o melhor resultado? c) Muito provavelmente, o programa anterior forneceu alguns passeios "respeitáveis" mas nenhum passeio completo. Agora "retire os limites" e simplesmente deixe seu programa ser executado até que um passeio completo seja produzido. (Cuidado: Essa versão do programa pode rodar durante horas em um computador poderoso.) Mais uma vez. conserve urna tabela do número de passeios para cada extensão alcançada e imprima essa tabela quando o primeiro passeio completo for realizado. Quantos passeios seu programa tentou fazer antes de produzir um passeio completo? Quanto tempo levou? d) Compare a versão de força bruta do Passeio do Cavalo com a versão de heurística de acessibilidade. Qual exigiu um estudo mais cuidadoso do problema? Que algoritmo foi mais difícil de desenvolver? Qual exige mais poder computacional? Poderíamos estar certos (antecipadamente) de obter um passeio completo cea| a heurística de acessibilidade? Poderíamos estar certos (antecipadamente) de obter um passeio completo com o método da força bruta? Analise as vantagens e desvantagens da resolução de problemas em geral por força bruta. 6.26 (Oito Damas) Outro quebra-cabeça para os fãs do jogo de xadrez é o problema das Oito Damas. Resumidamente: é possível colocar oito damas em um tabuleiro vazio de xadrez, de forma que nenhuma dama "ataque" qualquer uma das outras, isto é, de forma que não haja duas damas na mesma linha, na mesma coluna ou ao longo da mesma diagonal? Use o método de raciocínio desenvolvido no Exercício 6.24 para formular uma heurística para resolver o problema das Oito Damas. Execute seu programa. (Dica: É possível ai um valor numérico a cada quadrado do tabuleiro indicando quantos quadrados são "eliminados" se uma for colocada ali. Por exemplo, cada um dos quatro cantos receberia o valor 22, como na Fig. 6.25.) Depois de esses "números de eliminações" serem colocados em todas as 64 casas (quadrados), uma heurística apropriada poderia ser: coloque a próxima dama no quadrado com menor número de eliminações Por que essa estratégia é intuitivamente atraente? 6.27 (Oito Damas: Métodos de Força Bruta) Neste problema, você desenvolverá vários métodos de força bruta para resolver o problema das Oito Damas apresentado no Exercício 6.26. 
 ******** ** * * * * * * * * * * * * Fig. 6.25 Os 22 quadrados (casas) eliminados ao colocar uma dama no canto superior esquerdo do tabuleiro. a) Resolva o problema das Oito Damas usando a técnica de força bruta aleatória desenvolvida no Exercício 6.25. b) Use uma técnica completa, i.e., tente todas as combinações possíveis das oito damas no tabuleiro. c) Por que você acha que o método da força bruta pode não ser apropriado para resolver o problema das Oito Damas? d) Compare e observe as diferenças entre os métodos da força bruta aleatória e da força bruta completa em geral. 6.28 (Eliminação de Valores Duplicados) No Capítulo 12 exploramos a estrutura de dados da árvore de pesquisa binaria de alta velocidade. Um recurso de uma árvore de pesquisa binária é que os valores duplicados são eliminados ao serem feitas inserções na árvore. Isso é chamado eliminação de valores duplicados. Escreva um programa que produza 20 números aleatórios entre 1 e 20. O programa deve armazenar todos os valores não-duplicados em um array. Use o menor array possível para realizar essa tarefa. 6.29 (Passeio do Cavalo: Teste do Passeio Fechado) No Passeio do Cavalo, um passeio completo é aquele em que o cavalo faz 64 movimentos passando por cada casa (quadrado) do tabuleiro apenas uma vez. Um passeio fechado ocorre quando o movimento 64 está a um movimento do local onde o cavalo começou o passeio. Modifique o programa do Passeio do Cavalo escrito no Exercício 6.24 para verificar se um passeio completo obtido é um passeio fechado. 6.30 (A Peneira de Eratóstenes) Um inteiro primo é qualquer inteiro que só pode ser dividido exatamente por si mesmo e por 1. A Peneira de Eratóstenes é um método de encontrar números primos. Ele funciona da seguinte maneira: 1) Crie um array com todos os elementos inicializados com 1 (verdadeiro). Os elementos do array com subscritos primos permanecerão 1. Todos os outros elementos do array serão definidos posteriormente como zero. 2) Começando com o subscrito 2 do array (o subscrito 1 deve ser primo), sempre que for encontrado um elemento do array cujo valor seja 1, faça um loop pelo restante do array e defina como zero todos os elementos cujo subscrito seja múltiplo do subscrito com valor 1. Para o subscrito 2 do array, todos os elementos além do 2 que forem múltiplos de 2 serão definidos como zero (subscritos 4, 6, 8, 10 etc). Para o subscrito 3 do array, todos os elementos além do 3 que forem múltiplos de 3 serão definidos como zero (subscritos 6, 9, 12, 15 etc). Quando esse processo for concluído, os elementos do array que ainda estiverem definidoscomo 1 indicam que o subscrito é um número primo. Esses subscritos 
podem ser impressos. Escreva um programa que use um array de 1000 elementos para determinar e imprimir os números primos entre 1 e 999. Ignore o elemento 0 do array. 6.31 (Classificação de Depósitos) Uma classificação de depósitos começa com um array unidimensional de inteiros positivos a ser classificado e um array bidimensional de inteiros com linhas possuindo subscritos de 0 a 9 e colunas com subscritos de 0 a n - 1, onde n é o número de valores do array a ser classificado. Cada linha do array bidimensional é chamada um depósito (bucket). Escreva uma função bucketClass que utilize um array inteiro e o tamanho do array como argumentos. O algoritmo é o seguinte: 1) Faça um loop pelo array unidimensional e coloque cada um de seus valores em uma linha do array de depósitos, baseado nos dígitos na casa das unidades. Por exemplo, 97 é colocado na linha 7. 3 é colocado na linha 3 e 100 é colocado na linha 0. 2) Faça um loop pelo array de depósitos e copie os valores de volta para o array original. A próxima ordem dos valores acima no array unidimensional será 100, 3 e 97. 3) Repita esse processo para posição subseqüente dos dígitos (dezenas, centenas, milhares etc.) e pare quando o dígito da extremidade esquerda do maior número for processado. Na segunda passada do array, 100 é colocado na linha 0, 3 é colocado na linha 0 (possui apenas um dígito) e 97 é colocado na linha 9. A ordem dos valores no array unidimensional é 100, 3 e 97. Na terceira passada, 100 é colocado na linha 1, 3 é colocado na linha zero e 97 é colocado na linha zero (depois do 3). A classificação de depósito garante a colocação de todos os valores em uma ordem apropriada após o processamento do dígito mais à esquerda do maior número. A classificação de depósito sabe que chegou ao fim quando todos os valores forem copiados na linha zero do array bidimensional. Observe que o array bidimensional de depósitos é dez vezes maior que o tamanho do array inteiro a ser ordenado. Essa técnica de ordenação (classificação) fornece um desempenho melhor do que a classificação de bolhas, mas exige capacidade de armazenamento muito maior. A classificação de bolhas exige apenas um local adicional na memória para o tipo de dados a ser classificado. A classificação de depósitos é um exemplo de troca de espaço por tempo. Ela usa mais memória, mas tem melhor desempenho. Essa versão de classificação de depósitos exige a cópia de todos os dados novamente no array original ao fim de cada passada. Outra possibilidade é criar um segundo array bidimensional de depósitos e mover repetidamente os dados entre os dois arrays de depósitos até que todos os dados estejam copiados na linha zero de um dos arrays. A linha zero conterá então o array ordenado. 
 Exercícios de Recursão 6.32 (Classificação de Seleção) Uma classificação de seleção pesquisa um array à procura de seu menor elemento. Quando o menor elemento for encontrado, ele é permutado com o primeiro elemento do array. O processo é então repetido para o subarray que se inicia com o segundo elemento do array. Cada passada do array resulta na colocação de um elemento em seu local apropriado. Essa classificação exige capacidade de processamento idêntica à da classificação de bolhas para um array de n elementos, devem ser feitas n - 1 passadas, e para cada subarray devem ser feitas n - 1 comparações para encontrar o menor valor. Quando o subarray a ser processado possuir um elemento, o array estará ordenado. Escreva uma função recurisva seleClass para realizar esse algoritmo. 6.33 (Palíndromos) Um palíndromo é uma string que é soletrada da mesma forma da frente para trás ou de trás para a frente. Alguns exemplos de palíndromos são "radar" "orava o avaro" e "socorram marrocos". Escreva uma função recursiva testePalind que retorne 1 se a string armazenada no array for um palíndromo, ou 0 em caso contrário. A função deve ignorar espaços e pontuação na string. 6.34 (Pesquisa Linear) Modifique o programa da Fig. 6.18 para usar uma função recursiva pesqLinear para realizar a pesquisa linear no array. A função deve receber um array inteiro e o tamanho do array como argumentos. Se a chave de busca (pesquisa) for encontrada, retorne o subscrito do array; caso contrário, retorne -1. 6.35 (Pesquisa Binária) Modifique o programa da Fig. 6.19 para usar uma função recursiva pesqBinar para realizar a pesquisa binária no array. A função deve receber um array inteiro e os subscritos inicial e final como argumentos. Se a chave de busca (pesquisa) for encontrada, retorne o subscrito do array; caso contrário, retorne 1. 6.36 (Oito Damas) Modifique o programa Oito Damas criado no Exercício 6.26 para que o problema seja resolvido recursivamente. 6.37 (Imprimir um Array) Escreva uma função recursiva imprimeArray que tome um array e seu tamanho. como argumentos, imprima o array e não retorne nada. A função deve parar o processamento e retornar quando receber um array de tamanho zero. 6.38 (Imprimir uma string de trás para a frente) Escreva uma função recursiva inverteString que tome um array de caracteres como argumento, imprima o array de caracteres na ordem inversa e nada retorne. A função deve parar o processamento e retornar quando um caractere nulo de terminação de string for encontrado. 6.39 (Encontrar o valor mínimo de um array) Escreva uma função recursiva miniRecursivo que tome um array inteiro e o tamanho do array como argumentos e retorne o menor elemento do array. A função deve parar o processamento e retornar quando receber um array de 1 elemento.