Recursividade - Torre de Hanói

As seguintes definições foram adotadas nesta solução:

1) as torres foram nomeadas de 'A' (origem), 'B' (destino) e 'X' (apoio);
2) os discos empilhados na torre de origem são identificados numericamente mantendo a relação
   com os seus tamanhos, ficando sempre empilhados em ordem decrescente em uma determinada
   torre: do maior na base ao menor no topo da pilha;

Exemplo para 3 discos:

      |         |         |
      1         |         |
      2         |         |
    __3__     __|__     __|__

   Torre A   Torre X   Torre B

Conforme as regras desse problema, discos maiores não podem sobrepor discos menores em uma
determinada torre, sendo que a movimentação deles é livre entre as torres, desde de que
seja um disco por vez.

Para resolver o problema, a pilha de discos na torre de origem deve ser movida para a torre
de destino, usando uma torre extra para apoio à movimentação. 
 
Um algoritmo aplicando recursividade facilita a solução, pois devemos mover uma possível
pilha de discos que esteja sobre um disco maior em uma determinada torre antes de poder
mover esse disco maior para outra torre:


    função recursiva( disco, origem, destino, apoio ){

        se ( disco > 1 )
        {
            // mover antes para a torre de apoio uma possível pilha sobre um disco
            // que necessita ser movido para a torre de destino:
 
            recursiva( disco - 1, origem, apoio, destino );
        }

        // agora podemos mover o disco para a torre de destino após a pilha sobre ele
        // ter sido movida para a torre de apoio:

        escreva( "mover disco ", disco, " da torre ", origem, " para torre ", destino );

        se ( disco > 1 )
        {
            // mover a pilha de discos que está na torre de apoio para a de destino,
            // ficando esta sobre o disco que foi movido antes:

            recursiva( disco - 1, apoio, destino, origem );
        }
    }

    função principal(){
        recursiva( 3, 'A', 'B', 'X');
    }


Após a execução do algoritmo acima, a disposição dos discos nas torres será:

      |         |         |
      |         |         1
      |         |         2
    __|__     __|__     __3__

   Torre A   Torre X   Torre B 

A seguir temos o programa escrito na linguagem C:

#include <stdio.h>

int passo, qtd;

void function( int disco, char origem, char destino, char apoio ){
    if ( disco < 1 ) return;
    if ( disco > 1 ) function( disco - 1, origem, apoio, destino );
    printf( "\nPasso %d: mover disco %d de %c para %c", ++passo, disco, origem, destino );
    if ( disco > 1 ) function( disco - 1, apoio, destino, origem );
}

int main(void) {
    passo = 0;
    qtd = 3;
    function( qtd, 'A', 'B', 'X' );
    return 0;
}


Saída produzida pelo programa acima:

Passo 1: mover disco 1 de A para B
Passo 2: mover disco 2 de A para X
Passo 3: mover disco 1 de B para X
Passo 4: mover disco 3 de A para B
Passo 5: mover disco 1 de X para A
Passo 6: mover disco 2 de X para B
Passo 7: mover disco 1 de A para B


Para testar o programa acima, utilize a plataforma ideone.com:

https://ideone.com/qtypyY


Bom estudo e até a próxima.

Usando Threads na plataforma Windows

O Código a seguir apresenta uma demonstração simples de uso de programação multi-thread
na linguagem C. A plataforma utilizada é a gcc em ambiente Windows 7.


//== Inicio do código ===================================================

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


//== principal include para uso de threads na plataforma Windows ========

#include <windows.h>


//== uma função qualquer para ser acessada da thread secundária =========

double tarefa( int i, double j )
{
    return (i * j);
}


//== estrutura de dados para passagem de argumentos ====================

typedef struct {
    int a;
    double b;
    double (*task)( int, double );
} DataArgs;


//== função para a thread secundária ===================================

DWORD WINAPI MyThreadFunction( LPVOID lpParam )
{
    DataArgs *args = (DataArgs *)lpParam;

    int z;

    FILE *fh = fopen( "k:/log.txt", "w" );

    for ( z=0; z<1000; z++ )
    {
        double resultado = args->task( args->a+z, args->b );
        fprintf( fh, "\nThread SECUNDARIA: %d\t%f", z,resultado );
    }

    fclose ( fh );

    return 0;
}


//== thread main =======================================================

int main()
{
    int x;


//  declaração de estrutura de dados para servirem como argumentos 
//  para a função da thread secundária

    DataArgs dados;
    dados.a = 20;
    dados.b = 3.141592;
    dados.task = tarefa;

    HANDLE  hThreadArray;
    DWORD   dwThreadIdArray;

//  criação da thread secundária

    hThreadArray = CreateThread(
        NULL,                   // default security attributes
        0,                      // use default stack size
        MyThreadFunction,       // thread function name
        &dados,                 // argument to thread function
        0,                      // use default creation flags
        &dwThreadIdArray );     // returns the thread identifier

    if ( hThreadArray == NULL )
    {
        puts( "\nErro ao criar Thread.\n" );
        return 1;
    }

//  outras coisas da thread main

    for (x=0; x < 1000000; x ++)
    {
        printf( "\nThread MAIN: %f", sqrt( x ) );
    }
    return 0;
}

//== fim do código ====================================================


Links de referência:

    https://msdn.microsoft.com/en-us/library/windows/desktop/ms682516(v=vs.85).aspx
    https://msdn.microsoft.com/en-us/library/windows/desktop/ms682512(v=vs.85).aspx


Bom estudo e até a próxima.

Tornando constante o ponteiro ou a memória apontada

O código a seguir apresenta a diferença entre tornar constante o valor do ponteiro ou valor na memória por ele apontada.

#include <stdio.h>  // scanf(), printf() 
#include <stdlib.h> // calloc(), free()

int main()
{

// declarar constante o conteúdo da memória apontada, mas
// o ponteiro poderá ser alterado
    const int *x = (const int *) calloc( 1, sizeof(int) );

// aviso por modificar o conteúdo da memória apontada
    scanf("%d", x);

// erro por tentar modificar o conteúdo da memória apontada
//    *x = 3210;

// declarar constante o conteúdo do ponteiro, mas
// o conteúdo da memória apontada poderá ser modificado
    int * const w = (int * const) calloc( 1, sizeof(int) );

// erro por tentar alterar o ponteiro
//    w = x;

// modificando o conteúdo da memória apontada
    *w = 123456;

    printf("x: %d\n", *x );
    printf("w: %d\n", *w );

// modificando o ponteiro
    x = w;

    printf("x: %d\n", *x );

    free( (void*)x );
    free( (void*)w );

    return 0;
}

Uso de array por meio de alocação dinâmica de memória

A proposta deste código é usar alocação dinâmica de memória para suprir a função de array bi-dimensional:

double ptr[100][2];

Para tanto, esta declaração é substituída pela alocação de memória:

double **ptr = (double **) malloc(100*sizeof(double*));

Para cada ocorrência de *(ptr+j), sendo j de 0 a 99, alocar memória:

*(ptr+j)=(double *) malloc(2*sizeof(double));

O acesso aos elementos do array bi-dimensional ou da memória alocada dinamicamente pode ser feita da mesma forma:

*(*(ptr+j)+k))

ou

ptr[j][k],

variando j de 0 a 99, k de 0 a 1.

Aproveitando este projeto, também são apresentadas as funcionalidades de acesso ao relógio do sistema e formatação de data e hora.

Para a geração de dados, foi usada a função de randomização com parâmetros de faixa de valores, casas decimais e escala desejada.

Na impressão de dados numéricos, foi usada a configuração do ambiente de execução por meio da função 'setlocale()', tornando as saídas com ponto decimal em vírgulas.

#include <stdio.h> // printf(), fflush(), getchar(), stdin
#include <stdlib.h>       // malloc(), free(), srand(), rand(), RAND_MAX
#include <time.h>         // time_t, struct tm, time(), localtime()
#include <locale.h> // setlocale()

int main(){

 // dias da semana
 char dia[][14] = { 
  "Domingo", 
  "Segunda-Feira", 
  "Terça-Feira", 
  "Quarta-Feira",
        "Quinta-Feira", 
  "Sexta-Feira", 
  "Sábado" 
 };

 // data/hora em milésimos de segundos desde zero hora de 1900
 // ( time_t é um 'long long int' )
 time_t agora;
 
 // struct para relogio/calendario
 struct tm *calendario;

 // controle de loops
 int j, k;
 
 // declarar e alocar memória para 100 ponteiros de 'double'
 double **ptr = (double **) malloc(100*sizeof(double*));
 
 // para cada 1 dos 100 ponteiros de 'double' alocar memória para 2 'double'
 for (j=0; j<100;j++){
  *(ptr+j)=(double *) malloc(2*sizeof(double));
 }

 // inicializar a sequencia de randomização (semente) usando a hora corrente do sistema
 srand( (unsigned) time( NULL ) );

 // obter a hora corrente do sistema
 time( &agora );

 // converter a hora do sistema em estrutura 'hh:mm:ss, dd/mm/yy, weekDay, yearDay'
 calendario = localtime( &agora );

 // usar configurações regionais do sistema
 setlocale( LC_ALL, "" );

 // imprimir data e hora correntes
 printf( "%s - %02d/%02d/%04d - %02d:%02d:%02d - %dº dia do ano", 
  dia[calendario->tm_wday], // dia da semana (0=domingo, ..., 6=sábado)
  calendario->tm_mday,  // dia do mês
  calendario->tm_mon+1, // mês (0=janeiro, ..., 11=dezembro)
  calendario->tm_year+1900, // anos decorridos de 1900
  calendario->tm_hour,  // horas do dia (00~23)
  calendario->tm_min,  // minutos da hora (00~59)
  calendario->tm_sec,  // segundos do minuto (00~59)
  calendario->tm_yday+1 ); // dia do ano (0~365)
 
 // inicialização dos dados no array bi-dimensional
 for (j=0; j<100;j++){

  for (k=0; k<2; k++){

   *(*(ptr+j)+k) = 

    // gerar valores numéricos aleatórios
    // de 0.0 a 10.0 em intervalos de 0.125
    
    (int)(((double)rand() // 0 a RAND_MAX
    / (RAND_MAX+1))  // RAND_MAX
    * ((10.125 - 0.0) * 8.0)// faixa desejada * Ajuste de escala e casas decimais
    + 0.0)   // Deslocamento da faixa
    / 8.0;   // Ajuste de escala e casas decimais

  }
 }

 // impressão dos dados do array bi-dimensional
 for (j=0; j<100;j++){
  printf("\n");
  for (k=0; k<2; k++){
   printf( "%8.4lf\t", 
    //*(*(ptr+j)+k)
    ptr[j][k]
    );
  }
 }

 // liberar a memória de 2 'double' para cada um dos 100 ponteiros
 for (j=0; j<100;j++){
  free(*(ptr+j));
  *(ptr+j) = NULL;
 }

 // liberar a memória dos 100 ponteiros para 'double'
 free(ptr);
 ptr=NULL;

 // aguardar que teclem ENTER para encerrar o programa
 fflush(stdin);
 getchar();
 
 // return-code de encerramento do programa
 return 0;

}

Passando referência de uma função como argumento na chamada de outra função

No código a seguir, a função opera recebe 3 argumentos:

• 1º argumento: um ponteiro para uma função que recebe 2 argumentos inteiros;
• 2º argumento: um inteiro;
• 3º argumento: um inteiro;

A função desejada para ser executada é passada no 1º argumento. Os outros argumentos são repassados para a função que será executada.

#include <stdio.h>

// declaração da assinatura da função a ser passada como argumento para

// outra função 

int (*f) (int, int);

int somar(int a, int b){

       return a+b;

}

int subtrair(int a, int b){

        return a-b;

}

int opera(int (*g) (int, int), int a, int b){

         return g(a, b);

}

int main(){

       printf( "\nsoma: %d\n", opera(somar, 25, 30 ));

       printf( "\nsubtração: %d\n", opera(subtrair, 25, 30 ));

       f = somar;

       printf( "\noutra soma: %d\n", opera(f, 25, 230 ));        

       f = subtrair;

       printf( "\noutra subtração: %d\n", opera(f, 25, 230 )

       return 0;

}

Para testar, foi usado o site ideone.com

Como separar os dígitos de um número inteiro

Mais uma pequena solução para um pequeno problema.

Agora a situação é para separar os dígitos de um numero inteiro, permitindo aplicações como cálculos de dígitos de verificação (DV) ou dígito para auto conferência (DAC) de identificações como RG, CPF, CNPJ, etc.

Vejam o código a seguir:


#include

int main()
{
    long long int numero = 876543210987654321LL;

    do{
        printf( "\n%d" , (int)(numero % 10) );
    } while ( numero /= 10  );

    return 0;
}

Cópia de tela da execução:

Bom estudo e até a próxima.

Como obter a parte inteira de um número real

Para um pequeno problema, uma solução também pequena.

Considere a situação onde se tenha um número real (double) e deseja-se separar a parte inteira da fracionada. Restrição: não usar qualquer biblioteca pronta.

Vejam o código a seguir.

#include

int main()
{

    double areaAmbiente = 3.7999999999;
    double areaEmbalagem = 1.8;

    int qtdEmbalagensInteger = areaAmbiente / areaEmbalagem;
    double qtdEmbalagensReal = areaAmbiente / areaEmbalagem;

    printf( "\n %d %c %10.4f ",
           qtdEmbalagensInteger,
           (qtdEmbalagensInteger < qtdEmbalagensReal ? 
            '<' : qtdEmbalagensInteger > qtdEmbalagensReal ? 
                  '>' : '='),
           qtdEmbalagensReal );

    qtdEmbalagensInteger += 
               qtdEmbalagensInteger < qtdEmbalagensReal ? 1 : 0;

    printf( "\nEmbalagens requeridas: %d",
           qtdEmbalagensInteger);

    return 0;

}

Bom estudo e até a próxima.

Cursos gratuitos -- Algoritmos -- Coursera + Princeton

O site Coursera oferece muitos cursos gratuitos promovidos por renomadas universidades de todo o mundo:

https://www.coursera.org/

Em destaque, deixo aqui a sugestão para estudo de algoritmos:

Algorithms, Part I - https://www.coursera.org/course/algs4partI
Algorithms, Part II - https://www.coursera.org/course/algs4partII

Robert Sedgewick, Kevin Wayne

Este curso aborda o conteúdo essencial que qualquer programador sério necessite conhecer sobre algoritmos e estruturas de dados, com ênfase em aplicações e análise científica de performance em implementações na linguagem de programação Java.


O livro texto recomendado é:

Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne [ Amazon · Pearson · InformIT ] 


Link para consulta: http://algs4.cs.princeton.edu/home/

Bom estudo.

Tutorial de Ponteiros e Arrays em C

Um excelente tutorial sobre ponteiros, arrays, strings, alocação dinâmica de memória, struct e typedef em C Ansi:


http://cesarakg.freeshell.org/pointers.html


Bom estudo.

Lista genérica para dados estruturados

Continuando com a abordagem de typedef struct, apresento mais alguns exemplos e um em especial que é o da definição de um node em uma lista ligada.

Na estrutura No, são usados ponteiros do tipo void, pois não sabemos que tipo de estrutura será usado na aplicação.

Para testar a lista ligada, foram usados exemplos com estruturas pre-definidas: Paciente e Salario.

No caso de strings, também é apresentado um exemplo de lista com os nomes dos dias da semana sem haver a necessidade de definir previamente uma estrutura.

A seguir o código na linguagem C Ansi:

---

#include &ltstdio.h&gt
#include &ltstdlib.h&gt
#include &ltstring.h&gt


// exemplo de dados estruturados e algumas funções relacionadas

typedef struct{
    int prontuario;
    char nome[40];
    int idade;
    char rg[13];
} Paciente;


Paciente* criaPaciente( int prontuario, char *nome, int idade, char *rg ){

    Paciente *tmp = (Paciente *) calloc( sizeof(Paciente), 1 );

    tmp->prontuario = prontuario;
    strcpy( tmp->nome, nome );
    tmp->idade = idade;
    strcpy( tmp->rg, rg );

    return tmp;

}


void mostraPaciente( Paciente *tmp ){

    printf("\n\nPaciente: \t[%05d] [%-40s]\nIdade: \t\t[%3d]\t\tRG: [%-13s]\n",
           tmp->prontuario,
           tmp->nome,
           tmp->idade,
           tmp->rg
           );

}


// outro exemplo de dados estruturados

typedef struct{
    double salario;
    char *cargo;
} Salario;


Salario* criaSalario( double salario, char *cargo ){

    Salario *tmp = (Salario *) calloc( sizeof( Salario ), 1 );

    tmp->salario = salario;
    tmp->cargo = cargo;

    return tmp;

}


// estruturas e funções de uma lista generica

typedef struct{
    void *dados;
    void *proximo;
    void *anterior;
} No;


typedef struct{
    No *primeiro;
    No *corrente;
    No *ultimo;
    int tamanho;
} Lista;


Lista* criaLista(){

    Lista *tmp = (Lista *) calloc( sizeof(Lista),1);

    tmp->primeiro = NULL;
    tmp->corrente = NULL;
    tmp->ultimo = NULL;
    tmp->tamanho = 0;

    return tmp;

}


void insereElemento( Lista *lst, void *dat ){

    No *no = (No *) calloc( sizeof(No), 1 );

    no->anterior = lst->ultimo;
    no->dados = dat;
    no->proximo = NULL;

    lst->ultimo = no;

    if ( lst->tamanho == 0 ){
        lst->primeiro = no;
    } else {
        //No *tmp = no->anterior;
        //tmp->proximo = no;
        ((No *) no->anterior)->proximo = no;
    }

    lst->tamanho++;

}


void destroiLista( Lista *tmp ){

    tmp->corrente = tmp->primeiro;

    while ( tmp->tamanho > 0 ){

        No *proximo = tmp->corrente->proximo;
        free( tmp->corrente->dados );
        free( tmp->corrente );
        tmp->corrente = proximo;
        tmp->tamanho --;
    }

    free( tmp );

}


// outras funções do programa

void pausa(){
    printf( "\ntecle ENTER" );
    fflush( stdin );
    getchar();
    system( "cls" );
}


int main()
{
    Lista *pacientes = criaLista();

    insereElemento( pacientes, criaPaciente( 1200, "Antonio", 89, "123.456.123-1" ) );
    insereElemento( pacientes, criaPaciente( 1300, "Maria", 81, "987.654.432-2" ) );
    insereElemento( pacientes, criaPaciente( 1400, "Joao", 84, "765.234.546-3" ) );
    insereElemento( pacientes, criaPaciente( 1500, "Francisco", 78, "453.765.897-5" ) );

    printf( "\nListagem Normal:\n" );

    pacientes->corrente = pacientes->primeiro;
    while ( pacientes->corrente != NULL ){
        mostraPaciente((Paciente *) pacientes->corrente->dados);
        pacientes->corrente = pacientes->corrente->proximo;
    }

    pausa();

    printf( "\nListagem Invertida:\n" );

    pacientes->corrente = pacientes->ultimo;
    while ( pacientes->corrente != NULL ){
        mostraPaciente((Paciente *) pacientes->corrente->dados);
        pacientes->corrente = pacientes->corrente->anterior;
    }
    pausa();

    destroiLista( pacientes );
    pacientes = NULL;


    // outro exemplo

    Lista *semana = criaLista();

    insereElemento( semana, "Segunda-Feira" );
    insereElemento( semana, "Terca-Feira" );
    insereElemento( semana, "Quarta-Feira" );
    insereElemento( semana, "Quinta-Feira" );
    insereElemento( semana, "Sexta-Feira" );
    insereElemento( semana, "Sabado-Feira" );
    insereElemento( semana, "Domingo" );

    printf( "\nDias da Semana:\n" );

    semana->corrente = semana->primeiro;
    while ( semana->corrente != NULL ){
        printf("\n%-s\n", (char *) semana->corrente->dados);
        semana->corrente = semana->corrente->proximo;
    }
    pausa();

    destroiLista( semana );
    semana = NULL;


    // mais um outro exemplo

    Lista *salarios = criaLista();

    insereElemento( salarios, criaSalario( 1200.00, "Estagiario" ) );
    insereElemento( salarios, criaSalario( 1600.00, "Motorista" ) );
    insereElemento( salarios, criaSalario( 1900.00, "Secretaria" ) );
    insereElemento( salarios, criaSalario( 2300.00, "Vendedor" ) );
    insereElemento( salarios, criaSalario( 3400.00, "Programador" ) );
    insereElemento( salarios, criaSalario( 4500.00, "Analista" ) );
    insereElemento( salarios, criaSalario( 6720.00, "Gerente" ) );

    printf( "\nTabela de Salarios:\n" );

    salarios->corrente = salarios->primeiro;
    while ( salarios->corrente != NULL ){
        Salario *tmp = (Salario *) salarios->corrente->dados;
        printf("\n%-15s - %12.2f\n", tmp->cargo, tmp->salario );
        salarios->corrente = salarios->corrente->proximo;
    }
    pausa();

    destroiLista( salarios );
    salarios = NULL;

    return 0;

}

---

Bom estudo e até a próxima.

Usando typedef, struct, malloc e free

A seguir temos alguns exemplos de fácil compreensão.

---

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

typedef struct{
    int id;
    char name[30];
} elemento;

typedef struct node{
    struct node *next;      // forma correta
    // node *previous;      // declaração errada
    elemento *dados;
} node;

typedef struct tag{
    int key;
    int value;
} tag;

int main()
{
    elemento *prod = (elemento *) malloc( sizeof( elemento ));

    prod->id = 123;
    strcpy( prod->name, "teste");

    node *n = (node *) malloc( sizeof(node));

    n->next = NULL;
    n->dados = prod;

    free( n->dados );
    free( n );

    tag *a = (tag *) malloc( sizeof( tag ));

    a->key = 12;
    a->value = 14;

    free( a );

    struct tag *b = (struct tag *) malloc( sizeof( struct tag ));

    b->key = 120;
    b->value = 140;

    free( b );

    struct point3d {
        int x;
        int y;
        int z;
    };

    struct point3d *ptr = (struct point3d *) malloc( sizeof( struct point3d ));

    ptr->x = 10;
    ptr->y = 20;
    ptr->z = 30;

    free( ptr );

    typedef struct point{
        int x;
        int y;
    } point;

    point *q = (point *) malloc( sizeof( point ));

    q->x = 39;
    q->y = 67;

    free( q );

    return 0;
}

---

Link relacionado ao assunto:

RE: typedef struct vs struct
http://www.netalive.org/codersguild/posts/1753.shtml

The Most Expensive One-byte Mistake - ACM Queue

Para quem ainda não entendeu o uso do terminador NUL nas strings em C ( "demo\0' ):


The Most Expensive One-byte Mistake - ACM Queue


e outras escolhas.


Saudações.


Josimar

Uma mensagem de encerramento de mais um ano

Rodem o código e vejam a mensagem.

#include <stdio.h> void PrintBitMap( unsigned long long int bitmap ){     if ( bitmap > 1ULL ) PrintBitMap( bitmap / 2ULL );     printf("%c", ( bitmap % 2ULL ) ? '*' : ' '); } unsigned long long int bitmap[13] = {       0x1000000000000000LL, 0x10000000114447CELL,     0x100000001B444111LL, 0x1000000015444111LL,     0x1000000011444111LL, 0x100000001138410ELL,     0x1000000000000000LL, 0x100039E78438E78ELL,     0x1000451444411451LL, 0x100045E7847DF451LL,     0x1000451504451451LL, 0x100039E48439178ELL,     0x1000000000000000LL  }; void main(){     for (int i=0; i<13; i++) {         PrintBitMap( bitmap[i] );         printf("\n");     }     fflush(stdin);     getchar(); }

Até a próxima.

Matrizes e Vetores Equivalentes

O código a seguir apresenta a técnica de alocação dinâmica de vetor (matriz linha ou matriz coluna) na linguagem de programação C. Foi usado o Borland C-Builder 6.

O usuário poderá definir o tamanho de uma matriz bi-dimensional e em seguida fornecer os valores para cada elemento, que neste estudo de caso é do tipo inteiro.

A função "sizeof(int)" retorna o tamanho em bytes para cada elemento da matriz[m][n].

Com a função "malloc( m * n * sizeof( int ) )" são alocados bytes na memória RAM suficientes para armazenar a quantidade de elementos ( int ) que compõem a matriz[m][n]. Esta função retorna um ponteiro do tipo (void*) sendo necessária a conversão para ponteiro do tipo (int*).

Para a entrada de dados, o algoritmo percorre de maneira bi-dimensional a matriz[m][n], sendo necessária a conversão dos índices m e n para a posição efetiva no vetor:

posição no vetor = t * n + u

onde:

t : linha corrente na matriz[m][n]

u: coluna corrente na matriz[m][n]

n : quantidade de colunas por lina na matriz[m][n]

Na segunda parte do código, o algoritmo percorre linearmente o vetor de dados que armazena a matriz[m][n] desejada, e para informação é calculada de maneira inversa os índices correntemente sendo impressos:

v = t / n (divisão inteira)

w = t % n (resto de divisão inteira)

onde:

t : posição corrente no vetor

n : quantidade de colunas por linha na matriz[m][n]

v : linha corrente da matriz[m][n]

w : coluna corrente da matriz[m][n]

Antes de analisar o código, acompanhe o diagrama de blocos a seguir:

Agora temos o código na linguagem C:

//--------------------------------------------------------------------- #pragma hdrstop //--------------------------------------------------------------------- /*     Alocação dinâmica de memória     Estudo de caso: matrizes e vetores equivalentes     malloc, free, fflush, printf, scanf */ #include <stdio.h> #include <stdlib.h> #pragma argsused int main(int argc, char* argv[]) {     int *A;     int m, n, c, t, u, valor;     printf("Matriz A[m][n]:\n");     fflush(stdin);     printf("Digite valor de m:");     scanf("%d",&m);     printf("Digite valor de n:");     scanf("%d",&n);     // Alocar recurso de memória RAM ----------     c = m * n;     A = (int*) malloc( c * sizeof( int ) );     // ----------------------------------------     if ( A == NULL )     {         printf("\n\nErro ao alocar memoria RAM!!!\n");         printf("\n\nTecle ENTER para encerrar");         fflush(stdin);         getchar();         return 1;     }     printf("\nDigite os elementos da matriz A[%d][%d]\n", m, n);     for ( t=0; t<m; t++ )     {         for ( u=0; u<n; u++ )         {             printf("Digite elemento[%d][%d]:", t, u);             scanf("%d", &valor);             A[ t * n + u ] = valor;         }     }     printf("\n\nMatriz A[%d][%d]:\n", m, n);     for ( t=0; t<c; t++ )     {         printf("\nA[%d][%d]=%d", (t / n), (t % n), A[t]);     }     printf("\n\nTecle ENTER para encerrar");     fflush(stdin);     getchar();     // Liberar recurso de memória RAM -----     free(A);     // ------------------------------------     return 0; } //---------------------------------------------------------------------

 

Links sugeridos para outros esclarecimentos:

http://www.ime.usp.br/~pf/algoritmos/aulas/aloca.html

http://en.wikipedia.org/wiki/Malloc

http://cplus.about.com/od/learningc/ss/pointers_7.htm

http://informatica.hsw.uol.com.br/programacao-em-c29.htm

 

Cópias de tela da execução do código aqui apresentado:

Para estudo, desenvolver uma aplicação para multiplicar duas matrizes bi-dimensionais:

C[m][j] = A[m][n] . B[i][j]

restrições:

• n igual a i
• m, n, i, j maiores que zero

Links com fundamentos matemáticos para multiplicação de matrizes:

• http://www.eng.uerj.br/~marcelo/matriz.html
• http://pt.wikipedia.org/wiki/Matriz_(matem%C3%A1tica)
• http://pessoal.sercomtel.com.br/matematica/medio/matrizes/matrizes.htm
• http://msdn.microsoft.com/pt-br/library/8667dchf.aspx

 

Bom estudo e até a próxima.

Código em C para ler código de tecla pressionada

As funções getch() e kbhit() da biblioteca CONIO proporcionam funcionalidades para monitoramento de teclas pressionadas, permitindo obter o código da tecla sem precisar aguardar que o usuário pressione ENTER, como ocorre com a getchar() padrão.

 

//--------------------------------------------------------------------------- #pragma hdrstop #include <stdio.h>      // printf #include <conio.h>      // kbhit, getch //--------------------------------------------------------------------------- #pragma argsused int main(int argc, char* argv[]) {     int keycode, normalkey;     while ( keycode != 27 )         // ESCAPE     {         // aguardar uma tecla ser pressionada         while ( ! kbhit() ) ;         // ler o código da tecla pressionada         keycode = getch();         // keycode = 0 se for tecla especial         normalkey = keycode;         // se tecla especial,         // pegar o próximo código para identificar a tecla pressionada         if ( !normalkey )             keycode = getch();         if      ( normalkey && keycode >= 48 && keycode <= 57 )             printf("\nteclou digito %c = %d = valor decimal %d",                     keycode, keycode, (keycode - 48) );         else if ( normalkey && keycode >= 65 && keycode <= 90 )             printf("\nteclou letra maiuscula %c = %d",                     keycode, keycode);         else if ( normalkey && keycode >= 97 && keycode <= 122 )             printf("\nteclou letra minuscula %c = %d",                     keycode, keycode);         else if ( !normalkey && keycode >= 59 && keycode <= 68 )             printf("\nteclou F%1d = %d",                     (keycode - 58), keycode);         else if ( !normalkey && keycode >= 133 && keycode <= 134 )             printf("\nteclou F%2d = %d",                     (keycode - 122), keycode);         else if ( normalkey && keycode == 27 )             printf("\nteclou ESCAPE = %d", keycode);         else if ( normalkey && keycode == 8 )             printf("\nteclou BACKSPACE = %d", keycode);         else if ( normalkey && keycode == 9 )             printf("\nteclou TAB = %d", keycode);         else if ( normalkey && keycode == 13 )             printf("\nteclou CARRIAGE-RETURN (ENTER) = %d", keycode);         else if ( normalkey && keycode == 10 )             printf("\nteclou LINE-FEED (CTRL-ENTER) = %d", keycode);         else if ( !normalkey && keycode == 75 )             printf("\nteclou SETA A ESQUERDA = %d", keycode);         else if ( !normalkey && keycode == 77 )             printf("\nteclou SETA A DIREITA = %d", keycode);         else if ( !normalkey && keycode == 72 )             printf("\nteclou SETA PARA CIMA = %d", keycode);         else if ( !normalkey && keycode == 80 )             printf("\nteclou SETA PARA BAIXO = %d", keycode);         else if ( !normalkey && keycode >= 82 && keycode <= 83 )             printf("\nteclou %s = %d",                     (keycode == 82 ? "INSERT\0" : "DELETE\0"), keycode);         else if ( !normalkey && keycode == 71 )             printf("\nteclou HOME = %d", keycode);         else if ( !normalkey && keycode == 79 )             printf("\nteclou END = %d", keycode);         else if ( !normalkey && keycode == 73 )             printf("\nteclou PAGE-UP = %d", keycode);         else if ( !normalkey && keycode == 81 )             printf("\nteclou PAGE-DOWN = %d", keycode);         else             printf("\nteclou %c = %d (%s)",                     keycode, keycode, (normalkey ? "normal\0" : "especial\0") );     }     return 0; } //---------------------------------------------------------------------------

 

Com o código acima, espero ter apresentado dicas para os exercícios propostos em sala de aula.

 

Bom estudo e até a próxima.

Trabalhando com cadeias de caracteres (strings)

O código apresentado a seguir foi escrito em C e se propõe a demonstrar o uso de cadeias de caracteres.
A aplicação é bastante simples, envolvendo uma lista de nomes de frutas previamente estabelecida e a interação com o usuário para que este faça uma consulta.
Dado um nome de fruta, o algoritmo fará uma busca seqüencial na lista a partir do primeiro elemento.
Se o nome for localizado, será indicado em qual posição da lista e o nome apresentado com efeito especial: letra por letra pausadamente e com barulho de máquina de datilografia.

O programa foi testado na plataforma MS Windows XP e Borland C Builder.

//--------------------------------------------------------------------------- #pragma hdrstop //--------------------------------------------------------------------------- #include <stdio.h>      // printf, scanf, fflush #include <windows.h>    // Sleep, Beep #define MAX_FRUTAS 5 #define MAX_COMPR 12 #pragma argsused int main(int argc, char* argv[]) {         char frutas[MAX_FRUTAS][MAX_COMPR] =                 {                         { 'a', 'b', 'a', 'c', 'a', 'x', 'i' },                         { "mamao" },                         { "laranja" },                           "banana",                           "kiwi"                 };         char nome[MAX_COMPR];         int i, j;         printf("\nDigite um nome de fruta: ");         scanf("%s", nome);         printf("\nVoce digitou %s", nome);         // Pesquisa do nome na lista         for (i=0; i<MAX_FRUTAS && strcmp( frutas[i], nome ) ; i++) ;         if ( i == MAX_FRUTAS )         {                 printf("\nNome nao catalogado");         }         else         {                 printf("\nLocalizada em %d", i);                 printf("\n\n"); //              for (j=0; j<MAX_COMPR && frutas[i][j] != '\0'; j++)                 for (j=0; j<MAX_COMPR && nome[j] != '\0'; j++)                 { //                      putchar( frutas[i][j] );                         putchar( nome[j] );                         Beep(3700, 5);  // frequencia (Hz), duracao (s)                         Beep(300,2);                         Beep(80,8);                         Sleep(500);     // hibernar (ms)                 }         }         fflush( stdin );        // limpar buffer da entrada padrão         getchar();         return 0; } //---------------------------------------------------------------------------

Bom estudo e até a próxima.

Código C do Programa de Estatística

 

O programa aqui apresentado foi escrito com base nos diagramas de blocos comentados em sala de aula. Este código foi testado nas plataformas Borland C Builder e Linux GCC.

//--------------------------------------------------------------------------- //    Estatistica.c //    Josimar Nunes de Oliveira //    20/Set/2008 //--------------------------------------------------------------------------- #pragma hdrstop // bibliotecas referenciadas #include <stdio.h>   // printf, scanf, getchar #include <math.h>    // pow, sqrt #include <string.h>  // strcmp // constantes figurativas #define MAX     5000        // capacidade máxima de dados                             // para o array de termos da amostra #define BATCH   "--batch"   // parâmetro de execução do programa:                             // lote ou interativo // criando macro definições #define RaizQuadrada(x) sqrt(x) #define Potencia(x,y) pow(x,y) #pragma argsused int main(int argc, char* argv[]) {     // declaração de variáveis locais da função "main"     int proc_interativo;     int a[MAX], vmin, vmax, s, i, n, q;     float vmed, ss, dp;     // verificar argumentos de execução do programa     proc_interativo = 1;     if ( argc > 1 )     {         if ( strcmp(argv[1], BATCH) == 0 && argc == 2)         {             proc_interativo = 0;         }         else         {             printf("\n\nSintaxe:\n\n");             printf("\t./progteste [--batch] [< arqentrada] [> arqsaida]\n\n");             // término prematuro -- erro de sintaxe             return 1;         }     }     // entrada do parâmetro "n"     if ( proc_interativo )     {         printf("\n\nInforme qual o n-ésimo termo: ");     }     scanf("%d", &n);     // validar o parâmetro "n" fornecido pelo usuário     if (n >= MAX)     {         if ( proc_interativo )            {             printf("\n\nErro: excedeu capacidade do programa!!!\n\n");         }         // término prematuro do programa -- erro de capacidade         return 2;     }     // quantidade de termos na amostra     q = n + 1;     // entrada dos termos { a0, a1, a2, ..., aN }     // e armazenagem em array     for (i=0; i<=n; i++)     {         if ( proc_interativo )         {             printf("\nDigite o valor[ %d ] : ", i);         }         scanf("%d", &a[i]);     }     // obtenção dos termos de valores mínimo e máximo     // usando o primeiro elemento "a[0]" como referência     vmin = a[0];     vmax = a[0];     for (i=1; i<=n; i++)     {         if ( a[i] < vmin )         {             vmin = a[i];         }         if ( a[i] > vmax )         {             vmax = a[i];         }     }     // obter somatório dos termos     s = 0;     for (i=0; i<=n; i++)     {         s = s + a[i];     }     // cálculo da média aritmética     vmed = (float)s / (float)q;     // obter somatorio dos quadrados da diferença entre termos e média     ss = 0;     for (i=0; i<=n; i++)     { //      ss = ss + pow( (double)((float)a[i] - vmed), 2);         ss = ss + Potencia( (double)((float)a[i] - vmed), 2);     }     // medida estatística denominada "variância"     ss = ss / (float)q;     // cálculo da medida estatística "desvio padrão" //  dp = sqrt(  ss );     dp = RaizQuadrada( ss );     // saída dos cálculos     printf("\n\nResumo Estatistico\n");     printf("\nQuantidade de termos: %d", q    );     printf("\nSomatorio dos termos: %d", s    );     printf("\nValor minimo........: %d", vmin );     printf("\nValor medio.........: %f", vmed );     printf("\nValor maximo........: %d", vmax );     printf("\nVariancia...........: %f", ss   );     printf("\nDesvio padrao.......: %f", dp   );     printf("\n\n\nListagem da Amostra\n");     for ( i=0; i<=n; i++ )      {          printf("\nTermo[ %04d ] = \t%d", i, a[i]);      }     printf("\n\n");     // aguardar usuário teclar ENTER em modo interativo     getchar();     getchar();     // término normal do programa     return 0; }

No caso do Linux GCC, a linha de comando usada para compilação é:

gcc progteste.c -o progteste -lm

Nos próximos posts irei estender comentários de partes deste programa. Por enquanto apenas publiquei o código desenvolvido em sala de aula para servir de referência para construção de novos programas.

A seguir temos uma cópia de tela da execução no modo "batch":

Até mais.

Exercício da intersecção entre duas equações de 2º grau

Diagrama de blocos construído com o software DIA:

 

A ferramenta de apoio DIA pode ser obtida em:

http://downloads.sourceforge.net/dia-installer/dia-setup-0.96.1-8.exe

 

 

A seguir temos o algoritmo escrito em "portugol" nativo do software VISUALG:

 

algoritmo "intersecção"
// Função :
// Autor :
// Data : 29/08/2008
// Seção de Declarações
var
a, b, c, d, eh, f, i, j, k, delta, x, x1, x2 : real
Resp : caracter

inicio
// Seção de Comandos
escreva("Digite a primeira equação:")
leia(a, b, c)
escreva("Digite a segunda equação:")
leia(d, eh, f)
se ( a = 0 ) ou ( d = 0 ) entao
   Resp <- "Equações inválidas"
senao
   i <- ( a - d )
   j <- ( b - eh )
   k <- ( c - f )
   se ( i = 0 ) entao 
      se ( j = 0 ) entao
         se ( k = 0 ) entao
            Resp <- "Qualquer x Real"
         senao
            Resp <- "sem solução Real"
         fimse
      senao
         x <- ( - k / j )
         Resp <- "X = " + Numpcarac( x ) 
      fimse
   senao
      delta <- ( j ^2 - 4 * i * k )
      se ( delta < 0 ) entao
         Resp <- "sem solução Real"
      senao
         se ( delta = 0 ) entao
            x <- ( -j / 2 * i )
            Resp <- "X = " + Numpcarac( x )
         senao
            x1 <- ( ( -j + raizq( delta ) ) / 2 * i )
            x2 <- ( ( -j - raizq( delta ) ) / 2 * i )
            Resp <- "X1 = " + Numpcarac( x1 ) + "   X2 = " + Numpcarac( x2 )
         fimse
      fimse
   fimse
fimse
escreva( Resp )
fimalgoritmo

 

 

VisuAlg pode ser obtido em:
http://www.apoioinformatica.inf.br/

E seu manual em:

http://hermes.ucs.br/carvi/cent/dpei/haklauck/algoritmos/Linguagem_Visualg2.0.pdf

 

Bom estudo e até a próxima.

Linguagem C - variáveis tipo "int"

 

Vejam teste utilizando Microsoft Visual Studio 2008 C++ 9.0 para demonstrar o tamanho em bytes alocados para cada variação de uso do tipo "int":

É isso aí.

Até a próxima.

Reescrevendo o algoritmo para resolver o problema da equação 2º grau

Utilizando um editor de textos, como o Microsoft Word, Open Office ou mesmo o Notepad, facilmente podemos organizar os passos que constituem a lógica para resolver o problema apresentado:

 

Podemos encontrar sintaxes variadas para o pseudo-código, também largamente difundido como "Português Estruturado", até mesmo com forte influência da linguagem de programação Pascal. Nessa linha de abordagem, a sintaxe praticamente constitui uma versão da linguagem Pascal traduzida para a língua portuguesa. A título de exemplo, o algoritmo acima poderia ter o seguinte aspecto:

 

Links de interesse:

• VisuAlg
  http://hermes.ucs.br/carvi/cent/dpei/haklauck/algoritmos/Linguagem_Visualg2.0.pdf
  http://www.apoioinformatica.inf.br/
• Notepad++
  http://notepad-plus.sourceforge.net/uk/download.php

Pretendo direcionar o esforço que seria dispendido para aprender e dominar a "linguagem PASCAL VisuAlg", para um melhor aprimoramento, fixação e desenvolvimento na linguagem de programação C/C++ e testar os algoritmos diretamente numa plataforma realista, como por exemplo os compiladores Embarcadero(ex-CodeGear(ex-Borland)) C/C++ Builder, Microsoft C++ DotNet e GNU/Linux GCC.

 

 

Bom estudo e até a próxima.