MAC2166 - Introdução à Computação

30/06/2014 - Aula 22

Linguagem C - Problema 17

Escreva uma função de busca, que recebe um inteiro x, um inteiro n e um vetor v de inteiros com n elementos ordenados crescentemente. A função deve devolver um índice m tal que v[m] == x ou devolve -1 se tal m não existe.


Solução

In []: 
int busca_binaria(int x, int n, int v[MAX]){
    int e = 0, d = n-1, m;

    while (e <= d) {
        m = (e+d) / 2;
        if (x == v[m])
            return m;
        if (x < v[m])
            d = m-1;
        else
            e = m+1;
    }
    return -1;
}

Linguagem C - Problema 18

Escreva uma função de ordenação que receba como parâmetro um inteiro n e um vetor v de inteiros com n elementos e ordene (em ordem crescente) os elementos em v.


Solução 1 (Ordenação por Inserção)

In []: 
void ordenacao_insercao(int n, int v[MAX]){
    int i, j, x;

    for (i = 1; i < n; i++) {
        x = v[i];
        for (j = i-1; j >=0 && v[j] > x; j--)
            v[j+1] = v[j];
        v[j+1] = x;
    }
}

Solução 2 (Ordenação por Seleção)

In []: 
void ordenacao_selecao(int n, int v[MAX]){
    int i, j, x, min;

    for (i = 0; i < n; i++){
        min = i;
        for (j = i+1; j < n; j++)
            if (v[j] < v[min])
                min = j;
        x = v[i];
        v[i] = v[min];
        v[min] = x;
    }
}

Solução 3 (BubbleSort)

In []: 
void bubblesort(int n, int v[MAX]){
    int i, j, trocou = FALSE, x;

    trocou = TRUE;
    for (i = n -1; i >= 0 && trocou; i--) {
        trocou = FALSE;
        for (j = 0; j < i; j++)
            if (v[j] > v[j+1]) {
                x = v[j];
                v[j] = v[j+1];
                v[j+1] = x;
                trocou = TRUE;
            }
    }
}

Programa para testar as funções dos problemas 17 e 18:

In []: 
#include <stdio.h>
#define MAX 100
#define TRUE 1
#define FALSE 0

int busca_binaria(int x, int n, int v[MAX]);
void ordenacao_insercao(int n, int v[MAX]);
void ordenacao_selecao(int n, int v[MAX]);
void bubblesort(int n, int v[MAX]);

int main(){
    int n, v[MAX], i, x;

    /* Le uma sequencia de numeros */
    printf("Digite o numero de elementos da sequencia: ");
    scanf("%d", &n);
    printf("Digite os %d numeros: \n", n);

    for (i=0; i < n; i++)
        scanf("%d", &v[i]);

    /* Ordena os numeros usando uma das funcoes de ordenacao */
    ordenacao_insercao(n,v);
    /* ordenacao_selecao(n,v); */
    /* bubblesort(n,v);        */

    printf("\nA sequencia ordenada fica: \n");
    for (i=0; i < n; i++)
        printf("%d  ", v[i]);
    printf("\n\n");

   /* Busca um numero na sequencia */
   printf("Digite o numero a ser buscado: ");
    scanf("%d", &x);

    i = busca_binaria(x,n,v);
    if (i == -1)
        printf("O numero nao esta na sequencia!");
    else
        printf("O numero esta na posicao %d da sequencia ordenada.", i);

    return 0;
}

Tópicos vistos na Aula 22

Referências e outros materiais para estudo

Página do Prof. Paulo Feofiloff: