argcv

codes and stuff

Archive for the ‘programação’ Category

Quicksort em DrRacket

leave a comment »

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

Written by rntreis

dezembro 16, 2012 at 11:15 am

Publicado em programação

Cálculo de raiz cúbica

leave a comment »

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;
}

Written by rntreis

setembro 29, 2012 at 5:16 pm

Publicado em C, programação

Range() em C

leave a comment »

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;
    }
}

Written by rntreis

agosto 16, 2012 at 3:56 pm

Publicado em C, dicas, programação

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

leave a comment »

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!

Written by rntreis

agosto 9, 2012 at 6:13 pm

Publicado em Cpp, programação

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