Í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