Índice

Algoritmos e Métodos

Algoritmo é um procedimento que envolve conjunto de operações para resolução de um problema.
Métodos, aqui, não têm nada a ver com programação orientada a objetos, e sim fragmentos que podem ser usados em algoritmos.
Esta seção tem por objetivo apresentar alguns algoritmos e métodos diferentes e/ou interessantes. O porém é que muitos estão codificados em linguagem C.



PiratasDoTietê Errata do livro "Métodos Numéricos para Resolução de Problemas Lógicos"

de Walter Del Picchia
mnprpl_errata.txt (834bytes)



PiratasDoTietê Algumas funções geométricas

Aqui estão algumas funções que implementei em C:
(2D) o 'Convex.c': testa se um ponto (x,y) pertence a um dado triângulo (xa,ya)(xb,yb)(xc,yc).
[3D] o 'Convex3d.c': testa se um ponto (x,y,z) pertence a um tetraedro (xa,ya,za)(xb,yb,zb)(xc,yc,zc)(xd,yd,zd).
[2D] o 'Intersec.c': testa se dois segmentos de reta se interseccionam, pondendo-se calcular o ponto de intersecção.
[3D] o 'Intersec3d.c': testa se um triângulo e um segmento se cruzam no espaço.
Baixar 'convex.zip (7,47kb)'

[2D] seleclin: função para seleção de linhas com o cursor, tendo como critério a proximidade. Acompanha programa demonstração para Windows e um pequeno tutorial do algoritmo.
Baixar 'seleclin.zip (15,0kb)'

[2D] seleclinbox: outra função para seleção de linhas, agora com um cursor retangular, o critério é que a linha que está sob o cursor é selecionável. Pode-se com algumas modificações utilizar para recorte (cerceamento ou 'clipping') de linhas. Também acompanha um programa demonstração para Windows.
Baixar 'seleclinbox.zip (8,7kb)'

Todas estas funções têm como base segmentos representados por funções paramétricas, com o parâmetro variando de 0 a 1.




PiratasDoTietê Livro: Numerical Recipes In C - Segunda Edição (NRC)

Este clássico livro agora está disponível na Web. 'Numerical Recipes in C' (NRC) é um livro que desenvolve muitos algoritmos matemáticos úteis e implementa-os em C.
Disponível no formato .pdf ('Acrobat Reader').
O livro tem de ser baixado aos muitos pedaços (seções), então caso não queira se aventurar a baixar todo o livro (muitos Mb) pode-se inicialmente baixar o índice, arquivo 'c0-2.pdf', e a seguir escolher quais seções serão baixadas.
http://www.fizyka.umk.pl/nrbook/bookcpdf.html 

Mas nem tudo são flores, na página do link a seguir são apontados erros encontrados neste livro, alguns bastante grosseiros.
http://amath.colorado.edu/computing/Fortran/numrec.html


PiratasDoTietê Cálculo de raiz quadra

Implementação de um algoritmo iterativo para cálculo da raiz quadrada de um número, pelo método de François Viete, acompanha uma pequena dedução nos comentários do código fonte em C: Viete.zip (1,16kb)



PiratasDoTietê Fórmula de Stirling para o cálculo aproximado do fatorial de um número

O fatorial de 'n' é aproximadamente 'sqrt(2*Pi*n)*exp(n*ln(n/exp(1)))'.
Precisão: quanto maior o valor de 'n' maior a precisão da aproximação, por exemplo enquanto para n=4 a precisão é de 2,1%, para n=10 a precisão é de 0,8% e para n=20 a precisão pula pra 0,4%.



PiratasDoTietê Fórmula de Pizer para cálculo aproximado de distâncias 2D

Uma distância aproximada 'd' entre os pontos 1 e 2, (x1,y1) e (x2, y2) respectivamente, é dada por:
d=(a+b+2*Max(a,b))/3
com 'a' e 'b' valendo:
a=abs(x1-x2)
b=abs(y1-y2)
Precisão: erro máximo de 5,7%.
Uma implementação em linguagem C (Veja mais no tópico 'Cronômetro' abaixo):
float Pizer(register int a, register int b){

return ((a+b+2*(a>b?a:b))/3);

}

Como sugerido pelo Prof. Dr. Jorge Pimentel Cintra este cálculo aproximado pode ser útil na seleção de elementos na tela com o 'mouse', além de observar que se for necessário somente a comparação de distâncias pode-se suprimir a divisão por 3.
Note que podemos calcular distâncias aproximadas em 3D utilizando a função acima:
 Pizer(Pizer(a,b),c);

com: c=abs(z1-z2)
Porém o erro máximo aumenta substancialmente (11%).



PiratasDoTietê Dispositivo de Duff

Achei no FAQ de C de Steve Summit, é específico para as linguagens C/C++:

"Duff's Device" it's a devastatingly deviously unrolled byte-copying loop, devised by Tom Duff while he was at Lucasfilm. In its "classic" form, it looks like:
register n = (count + 7) / 8; /* count > 0 assumed */

switch (count % 8)

{

case 0: do { *to = *from++;

case 7: *to = *from++;

case 6: *to = *from++;

case 5: *to = *from++;

case 4: *to = *from++;

case 3: *to = *from++;

case 2: *to = *from++;

case 1: *to = *from++;

} while (--n > 0);

}

where count bytes are to be copied from the array pointed to by from to the memory location pointed to by to (which is a memory-mapped device output register, which is why to isn't incremented). It solves the problem of handling the leftover bytes (when count isn't a multiple of 8) by interleaving a switch statement with the loop which copies bytes 8 at a time.
(Believe it or not, it *is* legal to have case labels buried within blocks nested in a switch statement like this. In his announcement of the technique to C's developers and the world, Duff noted that C's switch syntax, in particular its "fall through" behavior, had long been controversial, and that "This code forms some sort of argument in that debate, but I'm not sure whether it's for or against.")



PiratasDoTietê Ano bissexto

Também encontrei no FAQ de C de Steve Summit, serve pra testar se o ano é bissexto:
if (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0))

printf("O ano de %d e' bissexto", year);

else

printf("O ano de %d nao e' bissexto", year);





PiratasDoTietê Dia da semana fornecida uma data

FAQ de C de Steve Summit:
...código de Tomohiko Sakamoto:
int dayofweek(int y, int m, int d) /* 0 = Sunday */

{

static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};

y -= m < 3;

return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;

}


Aplicação prática deste código e o do ano bissexto: um calendário.
cal.zip



PiratasDoTietê Cronômetro

Do Help do LCC-Win32 (compatível com ANSI e POSIX):
#include <time.h>

#include <stdio.h>

void main(void)

{

double timedif;

double time1 = (double)clock();

time1 = time1/(double)CLOCKS_PER_SEC;

/*

O codigo a cronometrar dever ser posto aqui
*/

timedif = (((double)clock()) / (double)CLOCKS_PER_SEC) - time1;

printf("The elapsed time is %f seconds\n",timedif);

}

Aplicação prática: comparação do desempenho (rapidez) da fórmula de Pizer para cálculo aproximado de distâncias com o método de cálculo exato (Pitágoras) bem como verificação da influência da otimização do compilador. Baixar o código fonte 'ellapsed.zip' (1.35kb)



PiratasDoTietê Links

Aqui estão alguns links onde são encontrados diversos algoritmos.
1. Ir para Album de algoritmos.
2. Ir para www.softpanorama.org/Algorithms/algorithms.shtml


Índice
rymaeda@yahoo.com
http://www.ioxio.com.br