�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.
Errata do livro "M�todos
Num�ricos para Resolu��o de Problemas
L�gicos"
de Walter Del Picchia
mnprpl_errata.txt
(834bytes)
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.
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
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)
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%.
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%).
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.")
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);
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
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)
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