O program descrito aqui devera realizar as seguintes funcoes:1 - Calcular o inteiro com valor mais alto em um vetor de inteiros por algoritmos iterativos; 2 - Calcular o inteiro com valor mais alto em um vetor de inteiros por algoritmos recursivos; 3 - Ler um vetor de inteiros e verificar se o vetor é ordenado crescente por algoritmos iterativos; 4 - Leia um vetor de inteiros e verifique se o vetor é ordenado crescente por algoritmos recursivos. Todos os algoritmos devem, após a execução, gravar seus valores de entrada e o número de iterações e salvá-los em um arquivo.
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define clean fflush(stdin)//simplifica a funcao fflush
//OBS: o meu teclado e americano, por isso nao havera acentos ou cedilhas neste documento
//fp = nome do vetor do arquivo, P valor da primeira posicao, R valor da posicao final, q ou m valor da posicao do meio
//p seria o primeiro termo e p o ultimo
//it = contador de iteracoes, it++ conta mais uma iteracao e atualiza o valor de it
//os algoritmos de soma recursa foram baseados no pseudocodigo mostrado na aula
void writeFile(int in,int it, FILE *fp)
{
//faz a gravacao em arquivo
char space[] = " ";//string para espacar
fprintf(fp,"%d",in);//grava em disco o valor de in(input)
fprintf(fp,space);
fprintf(fp,"%d",it);// grava o valor de it - iteracoes em disco
char jumpLine[]= "\n";//strinf para pular uma linha
fprintf(fp,jumpLine);//identa (pula uma linha)
}
int maxrec(FILE *fp, int v[], int p, int r)
{
int it =0, q =(p+r)/2 ;
if (p==r)
{
printf("%d \n",v[p]);
return v[p];
}
else
{
int x1, x2;
printf("entrou 1\n");
x1 = maxrec(fp, v, p, q);it++;
printf("saiu 1\n");
printf("entrou 2\n");
x2 = maxrec(fp, v, q + 1, r);
printf("saiu 2 \n");
if (x1 >= x2)
{
it++;printf("iterou x1>x2\n");
writeFile(p,it,fp);
return x1;
}
else if (x1 < x2)
{
it++;
writeFile(p,it,fp);
printf("iterou\n");
return x2;
}
}
}
int maxRec(FILE *fp,int vetor[],int p, int r)
{
// n seria o tamanho do vetor e o *vetor sera o vetor de inteiros
int n = (r-p)+1;
int h = (p+r)/2; //esse vai ser a etapa de divisao
int max =0,max2 =0, it =0;//ite sao as iteracoes que ocorreram
if(p == r)
{
it++;
writeFile(n,it,fp);//grava os parametros de entrada e saida no arquivos
return vetor[p];//caso o vetor seja de tam = 1, ele retorn o valor do vetor unico
}else
{
printf("halfway there \n");
max = maxRec(fp,vetor, p, h);it++;//faz a chamada recursiva para a primeira metade
printf("primeira recursao feita \n");
max2 = maxRec(fp,vetor, h + 1, r);it++;//faz a chamada recursiva para a segunda metade
printf("segunda recursao feita \n");
writeFile(n,it,fp);//grava os parametros de entrada e saida no arquivos
if(max >= max2)
{
return max;//verifica o maior
} else return max2;//retorna o resultado do teste
}
}
int maxit(FILE *fp,int vector[], int tam)
{
//verifica o valor maximo de forma iterativa
int i=0, max=vector[0], it =0;//inicializa as variaveis
for(i=1; i<tam;i++)
{//loop de verificacao
if(max > vector[i])
{//verifica se o atual valor maximo e menor que o atual do vector
max = vector[i];//caso max > vetorAtual atualiza o valor de max
it++;//incrementa o contador de iteracoes
}
}
writeFile(tam,it,fp);//grava em disco os valores de entrade e saida
return max;//retorna o valor do maximo do vector
}
void randomize(int vetor[], int n)
{
//randomiza o vetor para que o usario nao precise faze-lo
int it =0,i;//inicializa as variaveis
srand( (unsigned) time(NULL));//define o padrao de randomizacao
for(i=0;i<n;i++)
{
vetor[i] = rand()%50;//inicializa o atual valor do vetor
printf("%d ",vetor[i]);it++;//mostra para o usuario o valor de vetor para uso futuro
};printf("\n");
//como isso e so uma automatizacao do vetor o numero de iteracoes nessa funcao sera desprezado
}
int crescRec(FILE *fp,int vetor[], int p, int r)
{
//verifica se esta em ordem crescente atraves da rurcsao
int it =0, m= (r+p)/2, res =0;//inicializa o contador de iteracao e o valor do meio
if(p == r)
{//verifica se o vetor tem tamanho definido igual a 1
it++;
return 1;//se sim retorna 1 para indicar que esta crescente
}else {// caso nao executa esse
int p1 = crescRec(fp,vetor,p,m);it++;//verifica recursivamente se a primeira metade esta crescente
int p2 = crescRec(fp,vetor, p+1,r);it++;//verifica recursivamente se a segunda metade esta crescente
if(p1==p2 && p1 == 1)
{//verifica se ambas a partes estao crescente
// caso esteja retorna verdade
res=1;
};//caso nao mantem res = 0
}writeFile(m*2,it,fp);//grava parametros em arquivo
return res;
}
int crescIte(FILE *fp,int vetor[], int tam)
{
int it =0, i, cres=0,res=0;//inicializa
for(i=0;i<tam;i++)
{
if(vetor[i]>vetor[i+1])
{//verifica se esta crescente ao varrer o vetor
cres++;it++;//caso esteja crescente incrementa cres e o contador de iteracoes
}
}
if(cres == tam)
{//se cres tiver o valor do tamnho sera porque o vetor esta em ordem crescente
res =1;//retorna verdade caso esteja crecente
}writeFile(tam,it,fp);//grava os resultados em discos
return res;//retorna a resposta
}
int locIte(FILE *fp,int vector[],int x,int tam)
{
int temp = 0, pos =0,it=0;//locasisa o valor x no veto de forma recursiva
for(temp;temp< tam;temp++)
{
it++;//conta uma iteracao
if (vector[pos]== x)
{
it++;break;//aumenta o contador de forma iterativa e sai do loop
}
}
writeFile(20,it,fp);//grava valores do n do vetor e de saida
return temp;//retona o valor do local
}
int locRec(FILE *fp,int vector[], int p,int r, int x)
{
int n = (r+p),it=0,q=n/2,pos=0;
if(vector[pos] == x)
{
//verifica se esta na posicao atual de pos no vetor
it++;//conta uma iteracao grava em arquivo e termina a funcao retornando a posicao
writeFile(n,it,fp);
return pos;
}
if (vector[pos] != x)
{
pos++; // caso nao esteja em pos ele incrementa pos
}
if((q-p) == 1 || (q+1 - r)== 1)
{
return -1; // caso termine de varrer a metade e nao ache retorna -1 e sai do loop
}
else{
int x1 = locRec(fp,vector,p,q,x);it++;//divide e verifica para primeira metade do vetor (x1)
int x2 = locRec(fp,vector,q+1,r,x);it++;//divide e verifica para segunda metade do vetor (x2)
if(x1 != (-1) && vector[x1] == x)
{
it++;//verifica se x1 e valido e se for verifica se ele possui o valor desejado
writeFile(n,it,fp);//caso seja grava os valores de entrade o numero de iteracoes
return x1;//retona a posicao
} else if (x2 != (-1) && vector[x2] == x)
{
it++;//verifica se x2 e valido e possui o valor desejado
writeFile(n,it,fp);//caso seja grava os valores de entrade o numero de iteracoes
return x2;//retorna a posicao de x
}
}
}
int mkFile(FILE *fp)
{//cria o arquivo e abre para esqcrita
fp = fopen("C:\\Users\\JESUIS\\Dropbox\\arquivos UFRPE\\eps de algoritmo\\data.txt","w");
char line1[] = "input iterations";// deixa mais bonito com um cabecalho
fputs(line1,fp);//grava o cabecalho
fprintf(fp,"\n");//pula uma linha
if(fp == NULL)
{//verifica se o arquivo foi criado com sucesso
printf("erro");
exit(1);//caso nao ele sai com 1
}
}
int finishFile (FILE *fp)
{//fecha e finilisa o aquivo
fclose(fp);
if(fp == NULL)
{//verifica se ha algum problema com o arquivo
exit(1);
}
}
int ssmRec(FILE *fp,int vector[], int p, int r)
{
int it=0,tam = (p+r); //
if (p==r){ //verifica se o vetor tem tamanho escolhido 1 ou se so tem 1 valor
//e caso som retorna o valor dele como a soma maxima
it =1;
writeFile(tam,it,fp); //grava os resultados de entrada e saida
return vector[p]; //retorna o valor
}else
{
int q = (p+r)/2;it++; // | etapa de divisao do algoritmo
int x1 = ssmRec(fp,vector,p,q);it++; // | divide o vetor em 2 chama a funcao recursivamente pra cada
int x2 = ssmRec(fp,vector,q+1,r);it++; // | metade do algoritmo
int s = vector[q]; //guarda o inteiro que possui o valor do item do meio do vetor
int y1 = s;
for (int j = q-1; j < p; ++j) { //maximo em parts que terminam em q (y1)
s= s +vector[j];it++;
if (s>y1){
y1 =s;it++;
}
}
s = vector[q+1];it++;
int y2 = s;it++;
for (int l = p+2; l < r; ++l)
{//soma maxima que comeca em q+1 (y2
s=s+vector[l];it++;
if (s>y2)
{
y2=s;it++;
}
}
int y =y1+y2;it++; //soma os valores obtidos em y1 e y2
int testMax[3]; // cria um vetor para armazenar os valores
testMax[0]=x1;
testMax[1]=x2;
testMax[2]=y;
int result = maxRec(fp,testMax,2,0);it++;//recicla a funcao maximo recursivo para verificar qual sera o maior falor entre x1 x2 e y
fprintf(fp,"resultado do maxRec obtido pelo ssmRec \n");//lembrete gravado no arquivo visto que a funcao maxRec faz gravacoes
writeFile(tam,it,fp);//grava os resultados obtidos de entrade e saida
return result;//retorna a soma maxima
}
}
int ssmIte(FILE *fp,int vector[], int p,int r)
{//varre o vetor pelo segmento de soma maxima
int x = vector[p], ite =0,n=(p+r);
for (int j = r; j < p; ++j)
{
int s=0;
for (int k = j; k < p; ++k)
{
s=s+vector[k];ite++;//faz a soma
if(s>x)
{//caso o valor de s tenha superado x, x recebe o valor de s e conta uma iteracao
x=s;ite++;
}
}
}
writeFile(n,ite,fp);//realiza a gravacao
return x;//retorna valor
}
int main(void)
{
int n=10; //define o vetor como as 20 instacias pedidas para este ep
int vetor[20]; //cria o vetor
clean;
randomize(vetor, n);//inicializa vetor com valores randomicos
clean;//clean o buffer de entrada
FILE *fp;//cria o ponteiro de file
mkFile(fp);//cria efetivamente o arquivo
int troca =0;//condicao do switch case
//informa para o usuario como utilizar o menu
printf("1 - maxrec \n 2-maxIt\n 3 crescRec \n 4 crecIt \n 5 locIte \n 6 locREc \n 7 seg soma max recur \n 8 seg soma maxima ite \n ");
clean;scanf("%d",&troca);//recupera a funcap que o user deseja utilizar
switch(troca)
{
//declaracao do swtich case
case 0:
{
int p,r;
printf("informe o valor de p e de r com um espaco entre eles \n");
clean;
scanf("%d %d",&p,&r);
int max = maxRec(fp, vetor,p,r);
printf("%d foi o maior \n",max);
break;
}
case 1:
{
int p,r;
printf("informe o valor de p e de r com um espaco entre eles \n");
clean;
scanf("%d %d",&p,&r);
int mx = maxrec(fp, vetor, p, r);//chama a funcao e recupera o resultado
printf("\n o maior foi %d",mx);
break;
}
case 2:
{
int res = maxit(fp,vetor,n);//chama a funcao e recupera o resultado
printf("maximo foi %d",res);
break;
}
case 3:
{
printf("informe o P e o R \n");
int p, r;clean;
scanf("%i %i",&p, &r);
int fim = crescRec(fp,vetor,p,r);//chama a funcao e recupera o resultado
if(fim ==1)
{
printf("esta cescente \n");
}else printf("nao esta crescente \n");
break;
}
case 4:
{
int resp = crescIte(fp,vetor,n);//chama a funcao e recupera o resultado
if(resp == 1)
{
printf("esta crescente \n");
}else printf("nao esta crescente \n");
break;
}
case 5:
{
printf("informe o valor que deseja buscar \n");
int x,res;
clean;
scanf("%d",&x);
res =locIte(fp,vetor,x,20);//chama a funcao e recupera o resultado
printf("o valor %d esta na pos %d",x,res);
break;
}
case 6:
{
printf("informe o P e o R e depois o valor a buscar separados por espaco\n");
int p, r,x;
clean;
scanf("%i %i %d",&p,&r,&x);
int pos = locRec(fp,vetor,p,r,x);//chama a funcao e recupera o resultado
printf(" o x = %d esta localisado na posicao %d",vetor[pos],pos);
break;
}
case 7:
{
printf("informe o P e o R \n");
int p, r;
clean;
scanf("%i %i",&p,&r);
int sum = ssmRec(fp,vetor,p,r);//chama a funcao e recupera o resultado
printf("a soma do vetor maximo foi %d",sum);
break;
}
case 8:
{
printf("informe o P e o R \n");
int p, r;clean;
scanf("%i %i",&p,&r);
int x = ssmIte(fp,vetor,p,r);//chama a funcao e recupera o resultado
printf("o segmento de soma maxima tem valor igual a %d \n");//mostra o resultado pro usuario
break;
}
default:
{
printf("entrada invalida");//mostra uma mensagem de erro caso o user insira algum valor diferente do mostrado no menu
}
}
finishFile(fp);//fecha o arquivo
}