Archive for the "Teoria" Category

Tabela Verdade [Atualizado]

agosto 10th, 2010
{ No Comments }

Por definição. Tabela-verdade é o conjunto de todas as possibilidades combinatórias entre valores de diversas variáveis lógicas (binários), as quais se encontram em apenas duas situações (V)erdadeiro ou (F)also, e um conjunto de operadores lógicos.

A lógica binária, ou bitwise operation é a base de todo o cálculo computacional. Na verdade, são estas operações mais básicas que constituem todo o poderio dos computadores. Qualquer operação, por mais complexa que pareça, é traduzida internamente pelo processador para estas operações.
Por isso dizemos então que o computador trabalha apenas com zeros e uns.

As operações que podemos aplicar sobre esses valores lógicos estão abaixo restritos:

Operador NOT (!)

O operador unário NOT, ou negação binária resulta no complemento do operando, i.e., será um bit ’1′ se o operando for ’0′, e será ’0′ caso contrário, conforme podemos confirmar pela tabela de verdade:

A ¬A
1 0
0 1

Implementação em C

A = 0;
B = !A;

Operador AND (&&)

O operador binário AND, ou conjunção binária devolve um bit 1 sempre que ambos operandos sejam ’1′, conforme podemos confirmar pela tabela de verdade:

A B A ∧ B
1 1 1
1 0 0
0 1 0
0 0 0

Implementação em C

 if (variavel1 && variavel2) { /*código*/ }

Operador OR (||)

O operador binário OR, ou disjunção binária devolve um bit 1 sempre que pelo menos um dos operandos seja ’1′, conforme podemos confirmar pela tabela de verdade:

A B A ∨ B
1 1 1
1 0 1
0 1 1
0 0 0

Implementação em C

if ( variavel1 || variavel2 ) {
  /* Código */
}

Existe também outros operadores, como o NAND e o XOR, para mais informações, segue alguns links:

Wikibooks: Introdução à programação/Lógica

Organização e estruturas de Computador – Lógica Digital

 

[Atualização]

Para quem quiser brincar com portas lógicas, acesse http://logic.ly/demo/

[Atualizado]

Introdução a lógica, UFSC - http://www.inf.ufsc.br/ine5365/introlog.html

Programação, Teoria , ,

Recursão

setembro 24th, 2009
{ No Comments }

Um assunto simples, porém complexo:

Mais afinal, o que é recursão?
Em programação, a maneira mais simples de explicar o que é recursão é dizer que ela é um método de programação no qual um função chama a si mesma.

A chamada de um método para ele mesmo, é igual a chamada de qualquer outro método, exemplo de método recursivo que calcula o fatorial n!:

Fatorial

O fatorial de um número é dado pela multiplicação de seus antecessores, ou seja, se n é igual 3, então seu fatorial será 3 * 2 * 1. O fatorial de 0! (zero) é igual a 1.

int fat(int num){
    int fato;

    if (num == 1)
       return (1);
    else
        fato = num * fat (num-1);
    return fato;
}

Em qualquer algorítimo recursivo, devemos nos atentar a necessidade de um ponto de parada, ou  seja, uma condição aonde a recursão irá parar de se chamar.

No exemplo acima, essa condição é quando o fatorial for igual a 0 (Zero), na fórmula (desenho acima): Retorne 1 Se N for igual a 0

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

int fat(int num){
    int fato;

    if (num == 1)
       return (1);
    else
        fato = num * fat (num-1);
    return fato;
}

int main(void){
     int numero;
     printf("\nEntre com um numero positivo.");
     scanf("%u", &numero);
     printf("O fatorial de %u vale %u.\n", numero, fat(numero));
}

Chamando o método fatorial(3), queremos calcular 3 * 2 * 1.
-> 3 * fatorial(2) retorna (6)
-> -> 2 * fatorial(1) retorna (2)
-> -> -> 1 * fatorial(0) retorna (1)

Explicando o fluxo do programa:

1) O método fatorial recebe o valor de x igual a 3, verifica se x é igual a 0 (zero), como não é igual a 0 (zero), então calcula 3 multiplicado por fatorial(2), neste ponto estamos fazendo uma chamada recursiva.

2) O método fatorial recebe o valor de x igual a 2, verifica se x é igual a 0 (zero), como não é igual a 0 (zero), então calcula 2 multiplicado por fatorial(1).

3) O método fatorial recebe o valor de x igual a 1, verifica se x é igual a 0 (zero), como não é igual a 0 (zero), então calcula 1 multiplicado por fatorial(0).

4) O método fatorial recebe o valor de x igual a 0 (zero), verifica se x é igual a 0 (zero), então para a execução do método e retorna o valor 1.

5) Volta para o método fatorial(1) na linha 26 e faz a multiplicação de x que vale 1 pelo resultado do fatorial(0) que é 1, ou seja 1 * 1 e retorna o valor 1.

6) Volta para o método fatorial(2) na linha 26 e faz a multiplicação de x que vale 2 pelo resultado do fatorial(1) que é 1, ou seja 2 * 1 e retorna o valor 2.

7) Volta para o método fatorial(3) na linha 26 e faz a multiplicação de x que vale 3 pelo resultado do fatorial(2) que é 2, ou seja 3 * 2 e retorna o valor 6.

8) Volta para o método que chamou o fatorial(3), neste caso o método main na linha 7, guarda o resultado do fatorial(3) que é 6, dentro da variável resp, e imprime o resultado da variável resp na linha 8.

Idéias e mais informações: Blog do Rafael Sakurai, Vale a visita, observem o exemplo de colocar valores em ordem crescente.

Mais links:

Read more…

Teoria