argcv

codes and stuff

Archive for junho 2012

Ordenação por seleção

leave a comment »

O programa a seguir implementa o conhecido algoritmo de ordenação por seleção. O algoritmo não apresenta nada de novo (a não ser talvez a ordem de varredura), mas é interessantíssimo escrevê-lo do zero, atentando para cada detalhe lógico.

Além disso, o programa apresenta uma função que determina se um dado vetor v[] está ordenado em ordem crescente.


/* Escrito por Renato R. Leme, em 14/06/2012 */
/* e-mail: rntreisleme@gmail.com             */
/* site: https://argcv.wordpress.com          */

#include <stdio.h>

int crescente (int n, int v[]);
void ordena (int n, int v[]);

void main () {
    int v[8] = {51, 50, 3, 23, 2, 89, 90, 13};
    int i;

    printf ("Antes:    ");
    for (i = 0; i < 8; i++) printf ("%d ", v[i]);
    ordena (8, v);
    printf ("\nDepois:   ");
    for (i = 0; i < 8; i++) printf ("%d ", v[i]);
    printf ("\n");

    if (crescente (8, v)) printf ("\n--> É crescente.\n\n");
    else printf ("\n--> Não é crescente.\n\n");
}

// A função abaixo recebe n > 0 e v[0...n-1]. Retorna
// 1 caso v[] seja crescente e 0 caso contrário.

int crescente (int n, int v[]) {
    int i;
    for (i = 1; i < n && v[i] >= v[i-1]; i++);
    return (i == n) ? 1 : 0;
}

// A função ordena() recebe n > 0 e v[0...n-1].
// Reorganiza o vetor de modo crescente.

void ordena (int n, int v[]) {
    int i, j, min, x;
    for (i = 0; i < n; ++i) {
        min = n-1;
        for (j = n-2; j >= i; --j) if (v[j] < v[min]) min = j;
        x = v[i]; v[i] = v[min]; v[min] = x;
    }
}

Até mais!

Written by rntreis

junho 15, 2012 at 12:06 am

Publicado em C, programação

Algoritmo de inserção animado com dança romena

leave a comment »

Ótimo vídeo criado na Sapientia University que ilustra o algoritmo de inserção.

 

😀

Written by rntreis

junho 7, 2012 at 7:21 pm

Publicado em dicas, programação

Manipulação de Lista Encadeada

leave a comment »

Estou deixando à disposição um algoritmo que implementa uma “ficha de usuário” como pretexto para utilizar uma lista encadeada.

Possui cinco funções básicas de manipulação, sendo que todas, com exceção da primeira, são recursivas. A primeira adiciona uma célula na lista, a segunda busca por uma célula, a terceira remove, a quarta imprime todas as células e a quinta remove da memória a lista inteira e é executada na saída do programa.

/* Escrito por Renato R. Leme, em 06/06/2012 */
/* e-mail: rntreisleme@gmail.com             */
/* site: https://argcv.wordpress.com          */

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

typedef struct ficha {
    char nome[100];
    int idade;
    int ID;
    struct ficha *prox;
} ficha;

void adiciona (ficha *ini);
void imprima (ficha *ini);
int busca (char *ch, ficha *ini);
int buscaeRemove (char *ch, ficha *ini);
void libera (ficha *ini);

void main () {
    int menu;
    ficha *ini;
    ini = malloc (sizeof (ficha));
    ini->prox = NULL;

    while (menu != 0) {
        printf ("\nO que deseja fazer?\n\n--> 1 - Cadastrar usuário\n");
        printf ("--> 2 - Buscar cadastro\n--> 3 - Remover cadastro\n");
        printf ("--> 4 - Ver cadastros\n--> 0 - Sair\n--> ");
        scanf ("%d", &menu);
        switch (menu) {
            case 0: break;
            case 1: {
                adiciona (ini);
                break;
            }
            case 2: {
                __fpurge (stdin);
                char ch[100];
                printf ("\nDigite o nome completo de quem deseja buscar: ");
                gets (ch);
                if (busca (ch, ini)) printf ("---> O usuário encontra-se cadastrado!\n\n");
                else printf ("---> Registro não econtrado!\n\n");
                break;
            }
            case 3: {
                __fpurge (stdin);
                char ch[100];
                printf ("\nDigite o nome completo do cadastrado que deseja remover: ");
                gets (ch);
                if (buscaeRemove (ch, ini)) printf ("---> Removido com sucesso!\n\n");
                else printf ("---> Registro não econtrado!\n\n");
                break;
            }
            case 4: {
                imprima (ini);
                break;
            }
        }
        __fpurge (stdin);
    }
    printf ("\n");
    libera (ini);
}

// A função abaixo recebe uma lista ini e adiciona
// uma nova célula no seu início.

void adiciona (ficha *ini) {
    ficha *nova;
    if (!(nova = malloc (sizeof (ficha)))) {
        printf ("Falha na alocação de memória!\n\n");
        return;
    }
    __fpurge (stdin);
    printf ("\nDigite o nome: ");
    gets (nova->nome);
    __fpurge (stdin);
    printf ("Digite a idade: ");
    scanf ("%d", &nova->idade);
    __fpurge (stdin);
    printf ("Digite o ID: ");
    scanf ("%d", &nova->ID);
    __fpurge (stdin);
    printf ("\n");

    nova->prox = ini->prox;
    ini->prox = nova;
}

// A função que se segue recebe uma ficha ini e
// imprime os dados de ini->prox.

void imprima (ficha *ini) {
    if (ini->prox == NULL) return;
    printf ("\nNome: %s", (ini->prox)->nome);
    printf ("\nIdade: %d", (ini->prox)->idade);
    printf ("\nID: %d", (ini->prox)->ID);
    printf ("\n");
    imprima (ini->prox);
}

// A função abaixo busca por uma ficha na lista ini.
// Retorna 1 caso encontre e 0 caso contrário.

int busca (char *ch, ficha *ini) {
    ficha *p = ini->prox;
    if (p == NULL) return 0;
    else if (!(strcmp (ch, p->nome))) return 1;
    busca (ch, ini->prox);
}

// A função abaixo busca e remove uma ficha na lista
// ini. Retorna 1 caso obtenha sucesso e 0 caso contrário.

int buscaeRemove (char *ch, ficha *ini) {
    if (ini->prox == NULL) return 0;
    else {
        ficha *p = ini->prox;
        if (!(strcmp(ch, p->nome))) {
            ini->prox = p->prox;
            free (p);
            return 1;
        }
        buscaeRemove (ch, p);
    }
}

// A função libera() remove da memória a lista ini
// por completa.

void libera (ficha *ini) {
    if (ini->prox == NULL) return;
    else {
        ficha *remove;
        remove = ini->prox;
        ini->prox = remove->prox;
        free (remove);
        libera (ini);
    }
}

Até mais!

Written by rntreis

junho 6, 2012 at 9:15 pm

Publicado em C, programação

Fórmula resolutiva da equação do 2º grau

leave a comment »

Escrevi o seguinte algoritmo para a resolução de equações do segundo grau no domínio dos números reais (como exemplo, o programa resolve 4x²+13x+12 = 0).

/* Escrito por Renato. R. Leme, em 03/06/2012 */
/* e-mail: rntreisleme@gmail.com              */
/* site: https://argcv.wordpress.com           */

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

double *bhaskara (double a, double b, double c);

void main () {
    double *a;
    if (!(a = bhaskara (4, 13, 2)))
        printf ("A equação não pode ser resolvida no domínio dos Reais.\n");
    else
        printf ("x'  = %.2f \nx'' = %.2f\n", a[0], a[1]);
    free (a);
}

/* Esta função recebe a, b e c, de ax² + bx + c e retorna     */
/* um ponteiro para o primeiro número do conjunto de soluções */
/* da equação caso obtenha sucesso em resolvê-la no conjunto  */
/* dos números reais. Retorna NULL caso contrário. */

double *bhaskara (double a, double b, double c) {
    double delta;
    double *solucao = malloc (2 * sizeof (double));
    delta = (b * b) - (4 * a * c);
    if (delta < 0) return NULL;
    solucao[0] = (- b - sqrt (delta)) / (2 * a);
    solucao[1] = (- b + sqrt (delta)) / (2 * a);
    return solucao;
}

Até mais!

Written by rntreis

junho 3, 2012 at 1:49 pm

Publicado em C, dicas, programação

Fibonacci com apenas uma chamada recursiva

leave a comment »

Uma solução clássica para o problema de encontrar um número da sequência de Fibonacci com um algoritmo recursivo é a seguinte:

int calculaFibonacci (int n) {
    if (n < 2) return n;
    else return calculaFibonacci (n - 1) + calculaFibonacci (n - 2);
}

Entretanto, é sabido que duas chamadas recursivas podem pesar bastante.

Pensando nisso, eu escrevi uma solução que usa uma só chamada recursiva aliada a um vetor. Para isso, ao invés de começar os cálculos por n, a função começa por i, que vale 2. A lógica disso é que, sabendo v[i-2] = 0 e v[i-1] = 1, eu posso determinar v[i] (que é v[i-2] + v[i-1]), e, assim, determinar v[i+1…n], usando uma chamada recursiva para cada v[i], até que i seja igual a n e a função tenha achado o que se pede, que é sempre v[n].

Para conseguir o efeito de começar a calcular por i = 2 e usar um vetor v[n] sem que, quando quiser encontrar o número de Fibonacci preterido o usuário da função tenha que especificar esses dois dados à função sem qualquer motivo aparente, eu criei uma função chamada fibonacci(), que funciona como um pacote, simplesmente criando v[n], especificando os dois valores iniciais para v[] e chamando calculaFibonacci() com n, i = 2 e v.

Eis, então, o algoritmo.

#include <stdio.h>

int fibonacci (int n);
int calculaFibonacci (int n, int i, int v[]);

void main () {
    int a = fibonacci (40);
    printf ("%d\n", a);
}

/*  Esta função recebe n >= 0 e devolve o número  */
/*  de fibonacci presente na (n+1)-ésima posição. */

int fibonacci (int n) {
    int v[n];
    v[0] = 0; v[1] = 1;
    return calculaFibonacci (n, 2, v);
}

/*  A função abaixo recebe n >= 0, i = 2 e v[].  */
/*  Preenche o subvetor v[2...n] e retorna v[n]  */
/*  para a função chamadora.                     */

int calculaFibonacci (int n, int i, int v[]) {
    if (i >= n) return ((n == 0) ? 0 : v[i-1] + v[i-2]);
    else v[i++] = v[i-1] + v[i-2];
    calculaFibonacci (n, i, v);
}

Até mais.

Written by rntreis

junho 2, 2012 at 1:29 pm

Publicado em C, dicas, programação