Quicksort em DrRacket

A seguir uma adaptação (com a adição de definições locais e a consideração de elementos iguais) do algoritmo que pode ser encontrado aqui para o quicksort em DrRacket.

;; maiores : lista-de-números número -> lista-de-números
;; Retorna uma lista composta dos elementos da lista passada
;; como parâmetro que são maiores do que o número dado.
(define (maiores ldn n)
  (cond
    [(empty? ldn) empty]
    [(> (first ldn) n) (cons (first ldn) (maiores (rest ldn) n))]
    [else (maiores (rest ldn) n)]))

;; menores : lista-de-números número -> lista-de-números
;; Retorna uma lista composta dos elementos da lista passada
;; como parâmetro que são menores do que o número dado.
(define (menores ldn n)
  (cond
    [(empty? ldn) empty]
    [(< (first ldn) n) (cons (first ldn) (menores (rest ldn) n))]
    [else (menores (rest ldn) n)]))

;; iguais : lista-de-números número -> lista-de-números
;; Retorna uma lista composta dos elementos da lista passada
;; como parâmetro que são iguais ao o número dado.
(define (iguais ldn n)
  (cond
    [(empty? ldn) empty]
    [(= (first ldn) n) (cons (first ldn) (iguais (rest ldn) n))]
    [else (iguais (rest ldn) n)]))

;; quic-ksort : lista-de-números -> lista-de-números
;; Organiza uma lista de números em ordem crescente.
(define (quick-sort ldn)
  (cond
    [(empty? ldn) empty]
    [else (local 
            ( (define esq (menores ldn (first ldn)))
              (define cen (iguais ldn (first ldn)))
              (define dir (maiores ldn (first ldn))) )
            (append (quick-sort esq) cen (quick-sort dir)))]))

;; Testes
(quick-sort (list -4 -4 -2 -5 2 6 3 -2 -7))
(quick-sort (list 9 8 7 6 5 4 3 2 1 0 1 1))

Coloridinho: http://pastebin.com/pMLwnMhe

Cálculo de raiz cúbica

O algoritmo abaixo resolve o seguinte exercício:

/* Autor: Renato Reis Leme
 * e-mail: rntreisleme@gmail.com
 * site: https://argcv.wordpress.com */

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

int main () {
    int i = 0, nmaxi;
    float tol;
    double r, x0, x1, resultado;

    printf ("Digite o número a ser calculado: ");
    scanf ("%lf", &r);
    printf ("Digite uma aproximação inicial: ");
    scanf ("%lf", &x0);
    printf ("Digite a tolerância: ");
    scanf ("%f", &tol);
    printf ("Digite o número máximo de iterações: ");
    scanf ("%d", &nmaxi);

    do {
        if (i % 2 == 0) x1 = (x0 - ((pow (x0, 3) - r) / (3 * (pow (x0, 2)))));
        else x0 = (x1 - ((pow (x1, 3) - r) / (3 * (pow (x1, 2)))));
        i++;
    } while ((i < nmaxi) && (fabs (x1 - x0) > tol));

    resultado = (i % 2 == 0) ? x0 : x1;

    printf ("\nO resultado aproximado é: %lf\n\n", resultado);
    printf ("\nNúmero de iterações: %d\n\n", i);
    return 0;
}

Range() em C

Eis uma versão bastante simples da função range(), presente em muitas linguagens de script e que tem por finalidade gerar uma sequência de números (crescente ou decrescente), de acordo com os dados fornecidos em sua chamada.

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

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

int *range (int ini, int fim, int vari);

void main () {
    int *v, i;
    v = range (22, 102, 2);
    for (i = 0; i < (102-22)/2+1; i++) printf ("%d ", v[i]);
    printf ("\n\n");
    v = range (102, 21, -5);
    for (i = 0; i < (102-22)/5+1; i++) printf ("%d ", v[i]);
    printf ("\n\n");
}

/* A função gera uma sequência que vai de ini à, no máximo,
 * fim. Caso bem sucedida, retorna o vetor v[n], com valores
 * tais que v[a] = v[a-1] + vari. Caso contrário,
 * retorna NULL. */

int *range (int ini, int fim, int vari) {
    if ((ini > fim && vari > 0) || (ini < fim && vari < 0))
        return NULL;
    else {
        int i, j, n = (fim - ini) / vari + 1;
        int *v = malloc (n * sizeof (int));
        for (j = 0, i = ini; j < n; j++, i += vari)
            v[j] = i;
        return v;
    }
}

Classe de busca em vetores genéricos em C++

O algoritmo a seguir fornece uma classe capaz de realizar uma busca num vetor qualquer.

Através de templates, um objeto da classe Busca pode trabalhar com qualquer tipo de dado que um determinado vetor estiver armazenando através de um único método. Não tendo, portanto, a necessidade de se criar métodos específicos.

Como exemplo, o programa cria um vetor v[] de caracteres e um outro v2[] de números inteiros e realiza a busca, com o objeto Buscador, tanto recursivamente quanto iterativamente.

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

#include <iostream>
using namespace std;

class Busca {
public:
    template <class tipo> int iterativa (tipo x, int n, tipo *v);
    template <class tipo> int recursiva (tipo x, int n, tipo *v);
};

/* As duas funções abaixo recebem x, n e v[0...n-1].
 * Devolvem um índice k tal que v[k] = x. Mas, se tal k
 * não existir, devolvem -1. */

template <class tipo>
int Busca::iterativa (tipo x, int n, tipo *v) {
    int k = n - 1;
    for (k; k >= 0 && v[k] != x; k--);
    return k;
}

template <class tipo>
int Busca::recursiva (tipo x, int n, tipo *v) {
    return (n == 0 || v[n-1] == x) ? n-1 : recursiva (x, n-1, v);
}

int main () {
    char v[] = {'a', 'b', 'v', 'j', 'h', 'w', 'x'};
    int v2[] = {3, 4, 2, 8, 19, 34, 77, 88};
    Busca Buscador;

    cout << "Busca iterativa: índice do char 'v' em v[]: " << Buscador.iterativa ('v', 7, v);
    cout << "\n";
    cout << "Busca iterativa: índice do int 19 em v2[]: " << Buscador.iterativa (19, 8, v2);
    cout << "\n\n";
    cout << "Busca recursiva: índice do char 'v' em v[]: " << Buscador.recursiva ('v', 7, v);
    cout << "\n";
    cout << "Busca recursiva: índice do int 19 em v2[]: " << Buscador.recursiva (19, 8, v2);
    cout << "\n";

    return 0;
}

Até mais!

Ordenação por seleção

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!

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

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

 

😀

Manipulação de Lista Encadeada

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!

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

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!

Fibonacci com apenas uma chamada recursiva

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.

A função system()

Uma função bastante interessante que temos em C é system(), cujo protótipo encontra-se no arquivo-cabeçalho stdlib.h e é o que se segue:

int system (const char *string)

Com ela, você pode chamar comandos do sistema em seu programa. Por exemplo, a seguinte chamada

system ("dir");

devolve o conteúdo da pasta na qual o seu programa está.

Para exemplo simples, fiz um programinha que faz uso do pacman do Arch Linux através de system(). Confira.

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

void main() {
    char nome[100];
    char comando[200] = "sudo pacman -S ";

    printf("Digite o nome do programa: ");
    gets(nome);

    strcat(comando, nome);

    printf("\n");

    system(comando);
}

É fácil perceber que com uma simples alteração no array comando podemos adaptar o programa para funcionar em outras distribuições (em Debian e derivados, poderíamos usar “sudo apt-get install “, por exemplo).

Até mais.