Exercício Matriz

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Exercício Matriz
*
*
Exercício 1
Faça um programa em C++ que inicialize os arrays a e b com os valores abaixo e depois imprima esses valores como uma tabela.
a
b
*
*
#include <iostream>
include <iomanip>
using namespace std;
int main(){
	const int linha=3, coluna =4;
	int a[linha][coluna]= { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} }; 
	int b[3][4]={ {1, 2}, {5}, {9} };
	cout<<“\nMatriz A: “<<endl;
	for (int i=0; i<linha;i++){
		for(int j=0; j<coluna;j++)
			cout<<setw(5)<<a[i][j];
		cout<<endl; }
	 cout<<“\nMatriz B: “<<endl;
	for (int i=0; i<linha;i++){
		for(int j=0; j<coluna;j++)
			cout<<setw(5)<<b[i][j];
		cout<<endl; }
	return 0;
}
*
*
Exercício 2
Implemente uma função pesquisaLinear que receba um array unidimensional e um valor-chave como argumentos, faça uma pesquisa linear no array para encontrar o valor-chave e retorne sua posição no array ou retorne –1 se o valor não for encontrado. 
*
*
Resposta 2
int pesquisaLinear (int a[], int tam, int chave){
 int posicao=-1;
 for (int i=0; i<tam;i++)
 if (a[i]==chave){
 posicao=i;
 break;
 }
 return posicao;
}
*
*
int main(){
 int tamArray, valor, achou;
 cout<<"\nDigite o tamanho do array: ";
 cin>>tamArray;
 int array[tamArray];
 
 cout <<"\nDigite os valores do array:"<<endl;
 for (int i=0; i<tamArray; i++)
 cin>>array[i];
 cout <<"\nDigite o valor a ser procurado: ";
 cin>> valor; 
 achou= pesquisaLinear(array, tamArray, valor);
 if (achou!=-1)
 cout<<"\nO valor foi encontrado na posicao "<<achou<<endl;
 else
 cout <<"\nValor nao encontrado."<<endl;
 
 return 0;
}
*
*
Exercício 3
No programa do exercício anterior implemente uma função bublleSort para ordenar os elementos do array dado. Inicialmente, implemente o algoritmo original, executando n-1 passagens, comparando n-1 pares de elementos em cada passagem. Em seguida, reduza o número de comparações a cada passagem, considerando que após a primeira passagem, o último elemento já estará ordenado; após a segunda passagem, os dois últimos elementos já estarão ordenados; após a terceira passagem, os três últimos, e assim sucessivamente. 
*
*
Bubble sort
58 10 25 32 37 45
10 58 25 32 37 45
10 58 25 32 37 45
10 25 58 32 37 45
10 25 58 32 37 45
10 25 32 58 37 45
10 25 32 58 37 45
10 25 32 58 37 45
10 25 32 37 58 45
10 25 32 37 45 58
58 10 25 32 37 45
*
*
Bubble sort
void bubbleSort (int a[],int tam){
 int aux;
 
 for (int pass=0; pass<tam-1; pass++)
 for (int i=0; i<tam-1); i++)
 if (a[i]>a[i+1]){
 aux=a[i];
 a[i]=a[i+1];
 a[i+1]=aux;
 }
}
*
*
Bubble sort v2
void bubbleSort(int a[],int tam){
 int aux;
 
 for (int pass=0; pass<tam-1; pass++)
 for (int i=0; i<tam-(pass+1); i++)
 if (a[i]>a[i+1]){
 aux=a[i];
 a[i]=a[i+1];
 a[i+1]=aux;
 }
}
*
*
int main(){
 int tamArray, valor, achou;
 cout<<"\nDigite o tamanho do array: ";
 cin>>tamArray;
 int array[tamArray];
 
 cout <<"\nDigite os valores do array:"<<endl;
 for (int i=0; i<tamArray; i++)
 cin>>array[i];
 imprimeArray(array, tamArray);
 
 bubbleSort(array, tamArray);
 cout<<"\nArray ordenado."<<endl;
 imprimeArray(array, tamArray);
 
 system("pause");
 return 0;
}
*
*
Exercício 4
Refaça o exercício nº 1 implementando uma pesquisa binária no lugar da linear, utilizando o array ordenado pela função bublleSort, isto é, no programa, leia a chave, crie o array, ordene-o (com bubbleSort) e busque a chave (com pesquisaBinaria).
*
*
Pesquisa binária
Quando o array no qual será feita a pesquisa está ordenado, é possível reduzir significativamente o tempo da pesquisa utilizando-se da pesquisa binária. 
Essa técnica consiste em dividir o array ao meio consecutivas vezes, desprezando-se a metade que não contém a chave. O processo se repete até que a chave seja encontrada ou até que se comprove que a chave não está no array. 
*
*
Pesquisa binária
Pesquisa a chave = 61 no array a abaixo
*
*
*
*
int pesquisaBinaria (int a[], int tam, int chave){
 int posicao=-1;
 int indice1 =-1, indice2= tam;
 int ind = (indice1+indice2)/2;
 while (indice2-indice1!=1){
 if (a[ind]==chave){
 posicao=ind;
 break;
 }
 else 
 if(chave > a[ind])
 indice1=ind;
 else 
 indice2=ind;
 ind = (indice1+indice2)/2;
 }
 return posicao;
}