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.