Lista_3_gabarito

Prévia do material em texto

Lista 3 – Ordenação e Pesquisa 
 
1) Crie um vetor não ordenado de inteiros com elementos distintos e em seguida, imprima 
seus dados. Use, adequadamente, um método de busca. 
Solução : 
#include <iostream> 
using namespace std; 
#define TAMANHO 5 //define uma constante TAMANHO que vale 5 
 
//Protótipos 
void imprimir(int v[], int n); 
void inserirSemRepeticao(int v[], int valor, int &n); 
int buscaSequencial(int v[], int valor, int n); 
 
//Prog. principal 
int main() 
{ 
 int v[TAMANHO], 
 valor, //valor a ser inserido em v 
 n, //quantidade de elementos existentes no vetor v 
 posicao; //armazena o inteiro retornado pela função buscaSequencial 
 
 cout << "CRIANDO UM VETOR COM ATE NO MAXIMO " << TAMANHO 
 << " ELEMENTOS." << endl; 
 
 n = 0; //inicializa a quantidade de elementos em v 
 for (int i = 1; i <= TAMANHO; i++) 
 { 
 cout << "Digite um valor : "; 
 cin >> valor; 
 posicao = buscaSequencial(v,valor,n); //chama a função buscaSequencial 
 
 if (posicao >= 0) // se achou o valor no vetor 
 cout << "\nERRO : Valor ja existente. Fracasso na insercao. " << endl << endl; 
 else //se não achou o valor no vetor 
 inserirSemRepeticao(v,valor,n); //insere um valor em v, sem seguir qualquer ordem 
 } //fim do for 
 
 cout << "\n\nImprimindo os dados do vetor v : "; 
 imprimir(v,n); //chama a função imprimir 
 
 cout << endl; 
 system("pause"); 
 
} //fim do programa principal 
 
//Definições das funções 
 
void imprimir(int v[], int n) 
{ 
 for (int i = 0; i < n; i++) 
 cout << " " << v[i]; 
} 
 
int buscaSequencial(int v[], int valor, int n) 
{ 
 for (int i = 0; i < n; i++) 
 if (v[i] == valor) //testa se o valor está em v 
 return i; //retorna o índice do valor em v e sai da função 
 //Note que dentro do for só existe o if e dentro do if só existe o return i; 
 return -1; //sai da função retornando um valor impossível para índice. 
} 
 
//Obs.: A função inserirSemRepetir não verifica se há espaço no vetor e nem verifica 
// se o elemento já existe no vetor. Note que tais testes são realizados na função main. 
// Como não há ordem alguma dos dados, podemos adicionar o valor passado 
// no final do vetor. 
 void inserirSemRepeticao(int v[], int valor, int &n) 
{ 
 v[n] = valor; // insere no final, visto que não ordem. 
 n++; // ajusta a quantidade de elementos em v 
} 
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 
2) Crie um vetor não ordenado de inteiros, ordene-o pelo bubblesort e depois ofereça um menu, 
várias vezes, com as seguintes opções : 
 
1- Pesquisa binária 
2- Apresentar os dados da lista 
3- Terminar o programa. 
 
Crie uma função para a opção 1 e outra para a opção 2. 
 
Solução : 
 
#include <iostream> 
 
using namespace std; 
 
#define TAM 10 
 
//Note : As definições das funções foram escritas antes da main. Por esta razão, 
// os protótipos não serão necessários. 
 
//Definições das funções 
 
int inserirSemOrdem(int v[], int valor, int &n, int tamanho) { 
 if (tamanho == n) 
 { 
 cout << "ERRO: Lista cheia."; 
 return 0; //sinaliza lista cheia 
 } 
 else 
 { 
 v[n] = valor; //ADICIONA NO FIM DO VETOR 
 n++; //ajusta a quantidade de elementos no vetor 
 return 1; //sinaliza sucesso na inserção 
 } 
} 
 
 
int buscaBinaria(int v[], int valor, int n) 
{ 
 int ini = 0, // inicializa o início do intervalo para a busca 
 fim = n -1, // inicializa o fim da intervalo 
 meio; // armazenará o índice do meio do intervalo 
 
 while (ini <= fim) 
 { 
 meio = (ini + fim)/2; // determina o meio do intervalo 
 if (v[meio] == valor) //testa se o valor está no meio do vetor 
 return meio; // achou o valor na área de índice meio - sai da função e retorna esta posição 
 if (valor < v[meio]) //testa se o valor vem antes do meio do vetor 
 fim = meio -1; //redefine o fim, caso o valor possa estar antes do meio 
 else 
 ini = meio+1; //redefine o ini, caso o valor possa estar depois do meio 
 } 
 return -1; // não achou o valor no vetor 
} 
 
void imprimir(int v[], int n) 
{ 
 for (int i = 0; i < n; i++) 
 cout << " " << v[i]; 
} 
 
void ordenarBolha(int v[], int n) // n é o no. de elementos em v 
{ 
 int i , // índice 
 fim = n - 1, 
 aux; //auxiliar para troca 
 bool trocou = true; // é verdade que trocou - artifício para entrar no loop 
 
 
 while (trocou) 
 { 
 trocou = false; // sinaliza que é falso que trocou, pois nem começou a testar 
 for (i = 0; i < fim; i++) 
 { 
 if (v[i] > v[i+1]) 
 { 
 // as próximas 3 linhas promovem a troca de v[i] com v[i+1] 
 // usando uma variável auxiliar de nome aux 
 aux = v[i]; 
 v[i] = v[i+1]; 
 v[i+1] = aux; 
 // sinaliza que é verdadeiro que trocou 
 trocou = true; 
 } // fim if 
 } // fim for 
 fim--; // decrementa o fim 
 } // fim while 
} // fim da função 
 
 
 
 
 
 
//////////////// Programa principal ///////////////////////////////////////// 
int main() 
{ 
 int v[TAM], //declara um vetor com capacidade para TAM elementos inteiros 
 n = 0, //inicializa a quantidade de elementos no vetor v 
 valor, // valor para inserção 
 inseriu, // indica se houve inserção ou não 
 opcao, //opção do menu 
 posicao; //variavel que armazenará o retorno da busca 
 
 char resposta; 
 
 cout << "\t\tCRIANDO UM VETOR DE ELEMENTOS INTEIROS QUAISQUER " << endl; 
 while (true) { 
 cout << "\nValor para insercao (sem ordem) ? "; 
 cin >> valor; 
 inseriu = inserirSemOrdem(v,valor,n,TAM); 
 if (inseriu == 0) //indica lista cheia 
 break; //sai do while se a lista estiver cheia 
 getchar(); //limpa o buffer de entrada 
 cout << "Digite P para PARAR ou qualquer tecla para CONTINUAR => "; 
 cin >> resposta; 
 if (resposta == 'P' || resposta == 'p') 
 break; 
 } 
 cout << "\n\nOrdenando pelo bubblesort ... " << endl; 
 ordenarBolha(v,n); //chama a função que implementa o método bubblesort 
 
 do { 
 cout<< “\n######################################### " << endl << endl; 
 cout << "\t\t\tMENU " << endl; 
 cout << "1 - Pesquisa binaria \n2 - Apresentar os dados da lista \n3 - Terminar o programa. " 
 << endl; 
 cout << "\nOPCAO => "; 
 cin >> opcao; 
 switch (opcao) { 
 case 1 : cout << "Digite um valor para busca : "; 
 cin >> valor; 
 posicao = buscaBinaria(v,valor,n);if (posicao < 0) 
 cout << "\nERRO : " << valor << " nao encontrado. " << endl; 
 else 
 cout << "\nEncontrado o valor " << valor << " na posicao " << posicao << endl; 
 
 break; // sai do switch 
 
 case 2: cout << "\nDados da lista ordenada : " << endl; 
 imprimir(v,n); 
 break; 
 
 case 3 : cout << "\nFIM DO PROGRAMA." << endl; 
 break; 
 
 default : cout << "ERRO : Opcao invalida. " << endl; 
 
 } 
 } while (opcao != 3); 
 
 
 cout << endl << endl; 
 system("pause"); 
 
}// FIM DA MAIN 
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 
 
3) Use seu programa anterior e ofereça um menu com as seguintes opções : 
 1 – Ordenação por troca (Bubblesort) 
 2- Ordenação por seleção 
 3- Ordenação por inserção 
 Dessa forma, o usuário poderá escolher a ordenação antes de ir para o 2º. menu já programado 
no exercício 2. 
 
Solução : 
 
#include <iostream> 
 
using namespace std; 
 
#define TAM 10 
 
//protótipos 
 
int inserirSemOrdem(int [], int , int &, int ); 
int buscaBinaria(int [], int , int); 
void imprimir(int [], int ); 
void imprimir(int [], int); 
void bubblesort(int [], int ); 
void ordenaSelecao(int [], int ); 
void ordenaInsercao(int [], int ); 
 
 
//////////////// Programa principal ///////////////////////////////////////// 
 
int main() 
{ 
 int v[TAM], //declara um vetor com capacidade para TAM elementos inteiros 
 n = 0, //inicializa a quantidade de dados em v 
 valor, // valor para inserção 
 sinal, // sinaliza que houve insercao ou que houve ordenacao, conforme trecho do programa 
 opcao, //opção do menu 
 posicao; //variavel que armazenará o retorno da busca 
 
 char resposta; //indica se continuará inserindo ou não 
 
 cout << "\tCRIANDO UM VETOR DE ELEMENTOS INTEIROS QUAISQUER " << endl; 
 
 
 
 while (true) 
 { 
 
 cout << "\nValor para insercao (sem ordem) ? "; 
 cin >> valor; 
 sinal = inserirSemOrdem(v,valor,n,TAM); 
 if (sinal == 0) //indica lista cheia 
 break; //sai do while se a lista estiver cheia 
 getchar(); //limpa o buffer de entrada 
 cout << "Digite P para PARAR ou qualquer tecla para CONTINUAR => "; 
 cin >> resposta; 
 if (resposta == 'P' || resposta == 'p') 
 break; //sai do while 
 } 
 
 
 cout << "\n##################################################### " << endl << endl; 
 cout << "\t\t\tMENU 1 : ESCOLHENDO UMA ORDENACAO" << endl; 
 cout << "1 - BUBBLESORT \n2 - ORDENACAO POR INSERCAO " 
 << " \n3 - ORDENACAO POR SELECAO." << endl; 
 cout << "\nOPCAO => "; 
 cin >> opcao; 
 
 sinal = 0; //sinaliza que nao houve ordenação 
 switch (opcao) 
 { 
 case 1 : cout << "Ordenando por trocas ... metodo bubblesort " << endl; 
 bubblesort(v,n); 
 sinal = 1; //sinaliza que houve ordenação 
 break; 
 
 
 case 2 : cout << "Ordenacao por insercao " << endl; 
 ordenaInsercao(v,n); 
 sinal = 1; //sinaliza que houve ordenação 
 break; 
 
 case 3 : cout << "Ordenacao por selecao " << endl; 
 ordenaSelecao(v,n); 
 sinal = 1; //sinaliza que houve ordenação 
 break; 
 
 default : cout << "AVISO : NENHUMA ORDENACAO SELECIONADA. " << endl; 
 } //fim do switch 
 
 do { 
 cout << "\n############################################ " << endl << endl; 
 cout << "\t\t\tMENU 2 : ESCOLHENDO OPCOES VARIADAS" << endl; 
 cout << "1 - Pesquisa binaria \n2 - Apresentar os dados da lista \n3 - Terminar o programa. " 
 << endl; 
 cout << "\nOPCAO => "; 
 cin >> opcao; 
 
 
 
 
 
 
 switch (opcao) 
 { 
 case 1 : if (sinal == 0) 
 cout << "ERRO : Nao sera possivel realizar a busca binaria " 
 << " em vetor nao ordenado. " << endl; 
 else //houve ordenação 
 { 
 cout << "Digite um valor para busca : "; 
 cin >> valor; 
 posicao = buscaBinaria(v,valor,n); 
 
 if (posicao < 0) 
 cout << "\nERRO : " << valor << " nao encontrado. " << endl; 
 else 
 cout << "\nEncontrado o valor " << valor << " na posicao " << posicao << endl; 
 } 
 break; // sai do switch 
 
 case 2: cout << "\nDados da lista : " << endl; 
 imprimir(v,n); 
 break; 
 
 case 3 : cout << "\nFIM DO PROGRAMA." << endl << endl; 
 break; 
 
 default : cout << "ERRO : Opcao invalida. " << endl; 
 
 } 
 } while (opcao != 3); 
 
 cout << endl << endl; 
 system("pause"); 
 
}// FIM DA MAIN 
 
 
 
//Definições das funções 
 
int inserirSemOrdem(int v[], int valor, int &n, int tamanho) 
{ 
 if (tamanho == n) 
 { 
 cout << "ERRO: Lista cheia."; 
 return 0; //sinaliza lista cheia – fracasso na inserção 
 } 
 else 
 { 
 v[n] = valor; //ADICIONA NO FIM DO VETOR 
 n++; //ajusta a quantidade de elementos no vetor 
 return 1; //sinaliza lista não cheia 
 } 
} 
 
 
 
 
 
int buscaBinaria(int v[], int valor, int n) 
{ 
 int ini = 0, // inicializa o início do intervalo para a busca 
 fim = n -1, // inicializa o fim da intervalo 
 meio; // armazenará o índice do meio do intervalo 
 
 while (ini <= fim) 
 { 
 meio = (ini + fim)/2; // determina o meio do intervalo 
 if (v[meio] == valor) //testa se o valor está no meio do vetor 
 return meio; // achou o valor na área de índice meio - sai da função e retorna esta posição 
 if (valor < v[meio]) //testa se o valor vem antes do meio do vetor 
 fim = meio -1; //redefine o fim, caso o valor possa estar antes do meio 
 else 
 ini = meio+1; //redefine o ini, caso o valor possa estar depois do meio 
 } 
 return -1; // não achou o valor no vetor -retorna valor que não pode ser índice 
} 
 
 
void imprimir(int v[], int n) 
{ 
 for (int i = 0; i < n; i++) 
 cout << " " << v[i]; 
} 
 
 
//métodos de ordenação 
 
void bubblesort(int v[], int n) // n é o no. de elementos em v 
{ 
 int i ,// índice 
 fim = n - 1, 
 aux; //auxiliar para troca 
 bool trocou = true; // é verdade que trocou - artifício para entrar no loop 
 
 
 while (trocou) 
 { 
 trocou = false; // sinaliza que é falso que trocou, pois nem começou a testar 
 for (i = 0; i < fim; i++) 
 { 
 if (v[i] > v[i+1]) 
 { 
 // as próximas 3 linhas promovem a troca de v[i] com v[i+1] 
 // usando uma variável auxiliar de nome aux 
 
 aux = v[i]; 
 v[i] = v[i+1]; 
 v[i+1] = aux; 
 // sinaliza que é verdadeiro que trocou 
 trocou = true; 
 } // fim if 
 } // fim for 
 fim--; // decrementa o fim 
 } // fim while 
} // fim da função 
 
void ordenaSelecao(int v[], int n) { 
 int i, j, menor, aux; 
 
 for (j = 0; j < n-1; j++) 
 { 
 menor = j; 
 for (i = j+1; i < n; i++) 
 if (v[i] < v[menor]) 
 menor = i; 
 // trecho que faz a troca usando uma variável auxiliar aux - ESTÁ FORA DO 2º. FOR 
 aux = v[j]; 
 v[j] = v[menor]; 
 v[menor] = aux; 
 } 
} 
 
 
void ordenaInsercao(int v[], int n) // n é o número de elementos em v 
{ 
 int i, j, aux; 
 
 for (j = 1; j < n; j++) 
 for (i=j; i > 0 && v[i-1]> v[i]; i--) 
 { 
 //As 3 próximas linhas promovem a troca do elemento v[i] com v[i-1] 
 aux = v[i-1]; 
 v[i-1] = v[i]; 
 v[i] = aux; 
 } 
}