3

Olá, estou com dificuldades em resolver o meu exercício e gostaria de uma ajuda. Pensei em fazer com max heap, mas não deu certo.

Eis o enunciado:

“Problema da ordenação indireta”.) Escreva um algoritmo que recebe um número inteiro n e um vetor constante de números inteiros A[1..n] e devolve um vetor B[1..n] de índices do vetor A de tal forma que A[B[1]] ≤ A[B[2]] ≤ . . . ≤ A[B[n]]. Os valores armazenados em um vetor constante não podem ser alterados. Se A é um vetor constante e A[1] = 5, então A[1] = 5 para sempre.

Ex.: Suponha uma entrada A = [3, 6, 1, 8]. O seu algoritmo deve devolver B = [3, 1, 2, 4], pois, A[B[1]] = A[3] = 1 ≤ A[B[2]] = A[1] = 3 ≤ A[B[3]] = A[2] = 6 ≤ A[B[4]] = A[4] = 8.

Eis o que já tentei:

#include <stdio.h>
#include <stdlib.h>

void ordena(int v1[], int v2[], int v3[]);
void imprime(int v[]);

int main()
{
   int v1[4];
   int v2[4];
   int v3[4];
   /*
   printf("Digite 4 valores)");
   scanf("%d", v[0]);
   scanf("%d", v[1]);
   scanf("%d", v[2]);
   scanf("%d", v[3]);
  */
   v1[0] = 3;
   v1[1] = 6;
   v1[2] = 1;
   v1[3] = 8;

   v2[0] = 3;
   v2[1] = 1;
   v2[2] = 2;
   v2[3] = 4;


   ordena(v1, v2, v3);

   imprime(v3);


   return 0;
}

void ordena(int v1[], int v2[] , int v3[]){
    int aux, i, j;
    int k;
    k=0;
        for(i=0;i<4;i++){
                for(j=0;j<4;j++){
                    if(v1[v2[i]] > v1[j]){
                        v3[k] = v1[v2[i]];
                        k++;
                    }

                }
        }

}
void imprime(int v[])
{
   int i;
   for(i = 0; i < 4; i++)
   {
      printf("\nElemento %d.... %d\n", i, v[i]);
   }
}

1 Resposta 1

4

O truque é criar uma cópia do array original (já que este não pode ser alterado). O vetor B é inicializado com [1, 2, 3, 4]. Cada vez que você troca dois elementos de lugar na cópia de A, você efetua a troca com as mesmas posições em B. Quando a cópia de A estiver ordenada, o vetor B estará pronto.

Eis o código resultante:

#include <stdio.h>

void ordena(int tamanho, const int *a, int *b) {
    int *copia = (int *) malloc(tamanho * sizeof(int));
    int i;
    for (i = 0; i < tamanho; i++) {
        copia[i] = a[i];
        b[i] = i + 1;
    }

    int achou_inversao;
    do {
        achou_inversao = 0;
        for (i = 0; i < tamanho - 1; i++) {
            if (copia[i] > copia[i + 1]) {
                int aux = copia[i];
                copia[i] = copia[i + 1];
                copia[i + 1] = aux;
                aux = b[i];
                b[i] = b[i + 1];
                b[i + 1] = aux;
                achou_inversao = 1;
            }
        }
    } while (achou_inversao);
    free(copia);
}

int main(void) {
    int a[] = {3, 6, 1, 8};
    int b[] = {0, 0, 0, 0};
    ordena(4, a, b);
    printf("%d %d %d %d", b[0], b[1], b[2], b[3]);
    return 0;
}

Eis a saída:

3 1 2 4

Veja funcionando no IDE one.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .