Ir ao conteúdo
  • Cadastre-se

Estou com dúvidas em relação a a busca sequecial, binária e ordenação no c++


Visitante

Posts recomendados

Olá, estou com algumas dúvidas em alguns exercícios dessa prova ae:

https://uploaddeimagens.com.br/imagens/2-jpg--1500

https://uploaddeimagens.com.br/imagens/3-jpg--986

 

Nessa letra b da primeira questão, pelo q eu vi dessa menina fazendo, eu entendi q as comparações eram feitas em cada if ou else contando sempre os dois!!!! E só deu esse resultado quando eu coloquei aqueles conts no código da função q está na letra c!!!! Tente ver o meu raciocínio na letra b. Na letra d eu coloquei uma justificativa n muito confiável rsrsrsrsrsrs e mudei a função para receber um vetor d chars, alguém poderia analisar pra ver se ta certo rsrsrs!!! E no número dois letra a eu fiz um jeito parecido com o da menina também, eu acho q está certo, mas eu n sei..... E na letra b eu tentei fazer essa função, mas n entendi direito a questão e consequentemente eu n consegui fazer e a letra c eu coloquei algumas teorias lá, só n sei se estar certo riririiririri No número 3 eu coloquei umas teorias lá também, alguém poderia me ajudar a complementar e ver se tem algo d errado?

 

1)

a)      Essa função faz uma busca binária.

 

B)      a[10]={'b','d','g','i','i','o','o','r','r','r'};    //Esta é a ordenação do nome rodrigorib !

 

esq=0;                                                                                                                              

dir=9;

 

i=(esq+dir)/2

x<a

x>a

 

i=(0+9)/2=4.5                                                                                                                                

 

‘d’ < a[4] -> true  --> 1 comparação                                                                             esq=0                                                 

‘d’ > a[4] -> false --> 1 comparação                                                                             dir=4-1=3

 

i=(0+3)/2=1.5

 

‘d’ < a[1] -> false --> 1 comparação

‘d’ > a[1] -> false --> 1 comparação

 

1+1+1+1=4

 

Letra encontrada! Foram feitas 4 comparações.

 

c)       int processa(char a[], int n, char x){

  int esq=0;

           int dir = n-1;

           int i;

           int cont=0;

        while (esq<=dir){

        i = (dir+esq)/2;

        cont++;

        if(x<a){

            dir=i-1;

            cont++;

        }

        else if (x>a){

            esq=i+1;

            cont++;

        }

        else{

            cont++;

            return cont;

        }

    }

    return -1;

}

d)      int processa2(char a[], int n, char x){

    int cont=0;

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

        cont++;

        if (x==a){

        return cont;

        }

    }

    return -1;

}

 

 

 

a==x -> false

1.    

 

a==x ->true

 

Foram feitas 2 comparações! No caso da função processa2, que consiste no método da busca sequencial, ela fez menos comparações que a função de busca binária que é a processa, então nesse caso ela foi mais eficaz, porém a busca binária é mais eficiente em vetores maiores, fazendo bem menos comparações.

 

2)

a) 0 1 2 3 4 5  6   <-- Índices do vetor

    R O D R I G O //Trocando o elemento da posição 0 pela posição 2

    D O R R I G O // Trocando os elementos da posição 1 pela posição 5

    D G R R I O O // Trocando os elementos da posição 2 pela posição 4

    D G I R R O O // Trocando os elementos da posição 3 pela posição 5

    D G I O R R O // Trocando os elementos da posição 4 pela posição 6

    D G I O O R R //Vetor ordenado!

B) void troca(char &a, char & B){

    char aux;

    aux=a;

    a=b;

    b=aux;

}

 

int min(char a[], int esq, int dir){

    int i;

    while (esq<=dir){

        i=(esq+dir)/2;

    if(a[esq]>a){

        esq=i+1

    }

    else if(a[dir]<a){

        dir=i-1

    }

    else{

        return i;

    }

    }

    return -1;

}

 

void selecao(char a[], int n){

    int menor;

    for(int i=0;i<n-1;i++){

        menor=i;

        for(int j=i+1;j<n;j++){

            if(a[j]<a[menor]){

                menor=j;

            }

        }

    troca(a[menor],a);

    }

}

c) A ordenação por inserção é melhor que o método da seleção nos casos onde existem elementos repetidos em um dado vetor que se quer ordenar, sendo também que ele é um método adaptável. Porém, se o vetor estiver em ordem decrescente, o método de seleção seria o mais apropriado.

 

3)

a) No caso médio, o método de ordenação quicksort tem boa eficiência, quando o elemento denominado “pivô” ou índice médio, que é a soma dos índices externos do vetor dividido por 2, for também o elemento que estará na sua posição de origem depois que todo o vetor for ordenado, ou seja, n log(n).

 

B) Um método de ordenação estável é um método onde não à trocas nas ordens relativas dos elementos, ou seja, se tiver elementos repetidos em um vetor, as suas respectivas ordens serão mantidas. O quicksort não é um método estável, pois as trocas na fase de partição não consideram as ordens relativas dos elementos.

Link para o comentário
Compartilhar em outros sites

Não estou querendo q corrija a prova da menina, é porque eu vou cursar a matéria de progamação de computadores II no próximo semestre e talvez eu puxe com o professor q deu essa prova, por isso q eu tentei resolver e estou querendo tirar dúvidas para ter menos dor d cabeça no futuro! rsrsrs


Ahhhh.... eu n consegui entrar nesse link!

Link para o comentário
Compartilhar em outros sites

Visitante
Este tópico está impedido de receber novas respostas.

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...