|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ivan Boldyrev 2:5080/1003 17 Jan 2003 11:21:48
To : Val Krylov
Subject : Re: коммивояжёp
--------------------------------------------------------------------------------
Val Krylov <Val.Krylov@p27.f1900.n5030.z2.fidonet.org> writes:
> Любая pекypсия пpедставима итеpацией. Любая итеpация пpедставима
> pекypсией. Элементаpный алгоpитм вида "нахождение стpоки в тексте",
> напpимеp, достаточно ясно пpедставим и в итеpативной, и в
> pекypсивной фоpме, но в pекypсивном слyчае он сводится лишь к тоннам
> мyсоpа на стеке. Мне нет необходимости пpиводить алгоpитмы к менее
> эффективным фоpмам, благо не пpиходится кодить на Хаскеле.
Делать поиск подстроки лениво, вот вам поиск символа.
/* Хорошая такая хвостовая рекурсия */
const char * findchar(const char *str, char c) {
if (*str) {
if (c==*str)
return str;
else
return findchar(++str, c);
} else
return 0;
}
findchar:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %edx
movb 12(%ebp), %al
movb (%edx), %cl
testb %cl, %cl
je .L2
cmpb %cl, %al
je .L6
movsbl %al,%eax
incl %edx
movl %eax, 12(%ebp)
movl %edx, 8(%ebp)
popl %ebp
jmp findchar
.p2align 4,,7
.L6:
movl %edx, %eax
.L1:
popl %ebp
ret
.p2align 4,,7
.L2:
xorl %eax, %eax
jmp .L1
И кто же вам, уважаемый, в стеке-то намусорил? Руки или компилятор?
--
Ivan Boldyrev
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673
По дороге в не туда...
--- ifmail v.2.15dev5
* Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
