MC102MN

Um teste de mesa precisa de duas coisas: um programa para ser executado (de preferência com as linhas numeradas) e uma folha de papel para você escrever o estado da memória. Nessa folha, você construirá várias tabelas (uma para cada escopo, como foi estudado na aula passada) na seguinte forma:

Linha	Variavel1	Variavel2	…	VariavelN

Na coluna Linha você escreverá qual linha do código você está executando agora (o valor de M segundo o nosso modelo de computador com uma CPU e uma memória) e nas colunas correspondentes às variáveis você escreverá o valor atual de cada uma daquelas variáveis. Ao entrar em um novo escopo por um if, for, ou algo assim (ou seja: sem sair da função), você pode adicionar as variáveis declaradas nesse escopo à direita da sua tabela (lembrando-se de apagá-las depois). Ao executar uma função, você precisa criar uma nova tabela, completamente diferente, para representar o escopo daquela execução daquela função. Ao sair da função, você vai descartar aquela tabela (já que aquelas variáveis não existem mais). Às vezes, para facilitar o entendimento, quando o código inclui expressões complicadas, vale a pena, além de colocar colunas para as variáveis, colocar colunas para as expressões.

Como isso tudo deve ter ficado muito abstrato, vamos ao nosso primeiro programa exemplo.

O programa que iremos testar é

1   #include <stdio.h>
2   int main(int argc, char *argv[]) { 
3     int a = le_int(), b = le_int(), c = le_int();
4     if (a <= b) {
5       if (b <= c) {
6         printf("%d %d %d\n", a, b, c);
7       } else if (a <= c) {
8         printf("%d %d %d\n", a, c, b);
9       } else {
10        printf("%d %d %d", c, a, b);
11      }
12    } else {
13      if (a <= c) {
14        printf("%d %d %d", b, a, c);
15      } else if (c <= b) {
16        printf("%d %d %d", c, b, a);
17      } else {
18        printf("%d %d %d", b, c, a);
19      }
20    }
21    return 0;
22  }

Vamos agora fazer o teste de mesa para os valores de a, b e c iguais a 10, 12 e 3. Primeiro vamos escrever a tabela

Linha	a	b	c

Agora vamos começar o programa

Linha	a	b	c
3	10	12	3

À medida em que os valores na tabela vão mudando, vamos riscando os valores velhos e escrevendo os novos embaixo. Assim, continuando a execução do programa,

Linha	a	b	c
3	10	12	3
4

Como na linha quatro testamos a <= b (o que é 1, já que a = 10 e b = 12), continuamos para a linha 5

Linha	a	b	c
3	10	12	3
4
5

Na linha 5 testamos se b <= c, o que é 0, já que b = 12 e c = 3. Assim, vamos para a linha 7

Linha	a	b	c
3	10	12	3
4
5
7

Na linha 7 testamos se a <= c, o que é 0, então vamos para a linha 9

Linha	a	b	c
3	10	12	3
4
5
7
9

Como na linha 9 temos um else, se chegamos nela sempre entramos no else. Vamos então para a linha 10.

Linha	a	b	c
3	10	12	3
4
5
7
9
10

A linha 10 executa um printf, então o programa imprime 3 10 12, o que é exatamente o que queríamos que ele fizesse.

No programa de ordenação da seção anterior só usamos condicionais o tempo inteiro. Talvez seja mais fácil entender um programa de ordenação com menos níveis. Vamos agora estudar o seguinte programa:

1   #include <stdio.h>
2   int main(int argc, char *argv[]) { 
3     int a = le_int(), b = le_int(), c = le_int(), tmp;
4     if (c < a) {
5       tmp = c;
6       c = a;
7       a = tmp;
8     }
9     if (b < a) {
10      tmp = b;
11      b = a;
12      a = tmp;
14    }
14    if (c < b) {
15      tmp = c;    
16      c = b;
17      b = tmp;
18    }
19    printf("%d %d %d", a, b, c);
20    return 0;
21  }

Primeiro, começamos com a nossa tabela:

Linha	a	b	c	tmp

Como nesse programa temos a variável tmp, ela também precisa estar na tabela. Só pra mostrar a equivalência, vamos usar o mesmo exemplo da seção anterior (ou seja: a, b e c são iguais a 10, 12 e 3). Começamos o programa pela linha 3:

Linha	a	b	c	tmp
3	10	12	3	não definido

Vamos então para a linha 4

Linha	a	b	c	tmp
3	10	12	3	não definido
4

Como a linha quatro testa se c < a (e isso é verdade, já que c = 3 e a = 10), vamos para a linha 5

Linha	a	b	c	tmp
3	10	12	3	não definido
4
5

A linha 5 atribui c a tmp e vai pra linha 6

Linha	a	b	c	tmp
3	10	12	3	não definido
4				3
5
6

Na linha 6, atribuímos o valor de a a c e vamos pra linha 7

Linha	a	b	c	tmp
3	10	12	3	não definido
4			10	3
5
6
7

Na linha 7, atribuímos o valor de tmp a a e vamos para a linha 8

Linha	a	b	c	tmp
3	10	12	3	não definido
4	3		10	3
5
6
7
8

A linha 8 não faz nada. Vamos para a linha 9

Linha	a	b	c	tmp
3	10	12	3	não definido
4	3		10	3
5
6
7
8
9

Na linha 9 testamos se b < a, o que é falso, já que a é 3 e b é 12. Vamos então para a linha 14.

Linha	a	b	c	tmp
3	10	12	3	não definido
4	3		10	3
5
6
7
8
9
14

Na linha 14 testamos se c < b, o que é 1, já que c = 10 e b = 12. Vamos então para a linha 15

Linha	a	b	c	tmp
3	10	12	3	não definido
4	3		10	3
5
6
7
8
9
14
15

A linha 15 atribui o valor de c a tmp e vai para a linha 16

Linha	a	b	c	tmp
3	10	12	3	não definido
4	3		10	3
5				10
6
7
8
9
14
15
16

Na linha 16 atribuímos o valor de b a c e vamos para a linha 17

Linha	a	b	c	tmp
3	10	12	3	não definido
4	3		10	3
5			12	10
6
7
8
9
14
15
16
17

Na linha 17 atribuímos o valor de tmp a b e vamos para a linha 18

Linha	a	b	c	tmp
3	10	12	3	não definido
4	3	10	10	3
5			12	10
6
7
8
9
14
15
16
17
18

A linha 18 não faz nada, vamos para a linha 19

Linha	a	b	c	tmp
3	10	12	3	não definido
4	3	10	10	3
5			12	10
6
7
8
9
14
15
16
17
18
19

Na linha 19 imprimimos "3 10 12", e de novo temos os números em ordem. Como a linha 20 só faz retornar o valor de main, podemos parar por aqui.

Existe uma técnica muito útil em computação para você aproximar a função inversa de uma função monotônica que é a técnica da bijeção. O objetivo é, dado , calcular , que é tal que . Para isso, podemos usar uma ferramenta muito usada em computação que é a busca binária. Numa busca binária, você mantém sempre um intervalo onde você tem certeza que o valor que você quer está. A busca binária é um processo iterativo, e a cada momento ela faz o seguinte: se , então a recebe o valor do meio do intervalo (). Senão, b recebe esse valor. A cada iteração, então, o intervalo é reduzido pela metade (o que é a mesma coisa que dizer que você ganha um bit de precisão a cada iteração). Quando o intervalo é discreto (por exemplo, só existem n valores possíveis entre a e b), essa busca termina em passos. Quando o intervalo é contínuo, você precisa de aproximadamente passos para chegar a um valor tal que .

Isso obviamente pode ser usado para calcular a raiz quadrada de um número. Vamos então usar o seguinte programa:

1   #include <stdio.h>
2   double f(double x) {
3     return x*x;
4   }
5
6   double inverte_f(double x, double a, double b) {
7     double m = (a + b)/2;
8     if (f(m) < x) {
9       a = m;
10    } else {
11      b = m;
12    }
13    printf("%lf\n", m);
14    m = (a+b)/2;
15    if (f(m) < x) {      
16      a = m;             
17    } else {             
18      b = m;             
19    }                    
20    printf("%lf\n", m);  
21    m = (a+b)/2;         
22    if (f(m) < x) {      
23      a = m;             
24    } else {             
25      b = m;             
26    }                    
27    printf("%lf\n", m);  
28    m = (a+b)/2;         
29    return m;
30  }
31  
32  int main(int argc, char *argv[]) {
33    printf("%lf", inverte_f(2, 1., 1.5));
34    return 0;
35  }

Vamos construir nossa tabela, agora lidando com o fato de que teremos que usar mais de uma tabela porque temos várias funções:

main	linha

O programa começa pela linha 33, então

main	linha
	33

A linha 33 vai executar inverte_f, então criamos uma tabela pra inverte_f:

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido

A linha 7 define o valor de m e vai para a linha 8

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8				1.25

A linha 8 executa f, então precisamos criar uma tabela pra f

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8				1.25

f	linha	x
	3	1.25

f então vai retornar 1.5625. Como isso é menor que x, o if é verdadeiro e vamos para a linha 9 em inverte_f

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8				1.25
	9

A linha 9 atribui o valor de m a a e vai para a linha 10

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9
	10

Na linha 10, como estamos saindo do if, não executamos o bloco else. Vamos então para a linha 13

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9
	10
	13

Na linha 13 o programa imprime o valor de m, que é 1.25, e vamos para a linha 14

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9
	10
	13
	14

A linha 14 define um novo valor de m e vamos para a linha 15

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9				1.375
	10
	13
	14
	15

A linha 15 executa f novamente, então precisamos criar outra tabela para f:

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9				1.375
	10
	13
	14
	15

f	linha	x
	3	1.375

F então vai retornar 1.89065, que ainda é menor que x = 2, então entramos no if mais uma vez

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9				1.375
	10
	13
	14
	15
	16

A linha 16 vai redefinir a = m e vamos para a 17

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9		1.375		1.375
	10
	13
	14
	15
	16
	17

Na linha 17 não entramos no else, já que saímos do if, e vamos direto para a linha 20.

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9		1.375		1.375
	10
	13
	14
	15
	16
	17
	20

Na linha 20 imprimimos o valor de m, que é 1.375. Reparem que já está mais próximo de 1.414, que é o que queremos. Vamos então para a linha 21

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9		1.375		1.375
	10
	13
	14
	15
	16
	17
	20
	21

Na linha 21 redefinimos m e vamos para a linha 22

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9		1.375		1.375
	10				1.4375
	13
	14
	15
	16
	17
	20
	21
	22

Na linha 22, pela última vez, executamos f(1.4375)

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9		1.375		1.375
	10				1.4375
	13
	14
	15
	16
	17
	20
	21
	22

f	linha	x
	3	1.4375

F retorna 2.06 e a comparação dá falso (já que 2.06 é maior que 2), então vamos para a linha 25

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25		1.25
	9		1.375		1.375
	10				1.4375
	13
	14
	15
	16
	17
	20
	21
	22
	25

Na linha 25 redefinimos b para ter o valor de m e vamos para a linha 26

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25	1.4375	1.25
	9		1.375		1.375
	10				1.4375
	13
	14
	15
	16
	17
	20
	21
	22
	25
	26

Na linha 26 não acontece nada, e vamos para a linha 27.

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25	1.4375	1.25
	9		1.375		1.375
	10				1.4375
	13
	14
	15
	16
	17
	20
	21
	22
	25
	26
	27

Na linha 27 imprimimos m, que agora é 1.4375, bem mais perto do valor desejado. Vamos para a linha 28.

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25	1.4375	1.25
	9		1.375		1.375
	10				1.4375
	13
	14
	15
	16
	17
	20
	21
	22
	25
	26
	27
	28

Na linha 28 redefinimos m, que agora é 1.40625 e vamos para a linha 29

main	linha
	33

invertef	linha	x	a	b	m
	7	2	1.	1.5	não definido
	8		1.25	1.4375	1.25
	9		1.375		1.375
	10				1.40625
	13
	14
	15
	16
	17
	20
	21
	22
	25
	26
	27
	28
	29

Na linha 29 retornamos o valor de m e saímos da função inverte_f.

main	linha
	33

Finalmente, na linha 33, o programa imprime 1.40625 e vai para a linha 34

main	linha
	33
	34

Nessa linha main retorna e saímos do programa.