Нашли или выдавили из себя код, который нельзя назвать нормальным,
на который без улыбки не взглянешь?
Не торопитесь его удалять или рефакторить, — запостите его на
говнокод.ру, посмеёмся вместе!
#include <stdio.h>
#include <stdlib.h>
void push(unsigned int a, unsigned int **stackpp)
{
**stackpp = a;
(*stackpp)++;
}
unsigned int pop(unsigned int **stackpp)
{
(*stackpp)--;
return **stackpp;
}
unsigned int fib(unsigned int a)
{
unsigned int stack[10000] = {0};
unsigned int *stackp = stack;
// локальные дефайны
#define PUSH(x) push(x, &stackp)
#define POP() pop(&stackp)
relative_label:
PUSH( (int)(&&result - &&relative_label ) );
PUSH(a);
goto shit;
result:
return POP();
shit:
while(stackp != stack)
{
unsigned int tmp = POP();
//printf("tmp = %u\n", tmp); отладочная перчать
fflush(stdout);
if (tmp == 0)
{
int _ret = POP();
PUSH(0);
goto *(&&relative_label + _ret);
}
else if (tmp == 1)
{
int _ret = POP();
PUSH(1);
goto *(&&relative_label + _ret);
}
else
{
PUSH(tmp-2); // предварительно сохраняем
PUSH( (int)(&&after_p1 - &&relative_label) );
PUSH(tmp-1);
continue;
after_p1: ;
unsigned int tmp1 = POP(); // возвращенное значение
unsigned int tmp2 = POP(); // предварительно сохраненное
PUSH(tmp1);
PUSH( (int)(&&after_p2 - &&relative_label) );
PUSH(tmp2);
continue;
after_p2: ;
unsigned int val = POP()+POP();
int _ret = POP();
PUSH(val);
goto *(&&relative_label + _ret);
}
}
// ERROR - стек размотался. Такого быть не должно
exit(-1);
// убираем локальные дефайны
#undef PUSH
#undef POP
}
int main(void)
{
for(unsigned int i = 0; i < 30; i++)
{
printf("%u ", fib(i));
}
return 0;
}
Этим кодом я доказывал одному типу какой-то бред, связанный с рекурсией. Типа он считал что ее нельзя реализовать через сраные циклы со стеком(или может просто хотел посмотреть на такую реализацию).
Надо короче сделать локальный #define чтобы он автоматически #undef при выходе из области видимости фукнции.
> бред, связанный с рекурсией. Типа он считал что ее нельзя реализовать через сраные циклы
народ очень быстро забывает мат. часть. в русском к слову это проще: рекуррентная функция vs. рекурсивная функция. в англиском и то и другое называется рекурсией, а в русском первое ссылается на определение функции (фиб определена рекуррентно), а второе ссылается на реализацию (фиб можно реализовать с/без рекурсии.)
PS доказательство можно строить проще: процессора (или абстрактно машина Тюринга) не умеют рекурсию. они могут ее реализовать, но рекурсится им просто нет куда: они есть "простые" конечные автоматы. что собственно ты выше и реализовал.
у них в CS образовании не используется: все в лоб зовут рекурсией. пару раз с америкосами на эту тему общался. мне даже курсы и учебники показывали: понятие рекуррентности не вводится.
Ok, открываем Concrete mathematics: a foundation for computer science (THIS BOOK IS BASED on a course of the same name that has been taught annually at Stanford University since 1970), глава первая
1 Recurrent Problems
1.1 The Tower of Hanoi
1.2 Lines in the Plane
1.3 The Josephus Problem
На следующий день Руслан выиграл свои первые крупные соревнования. Его поздравляли все - ребята из секции, несколько школьных друзей, команда тренеров, даже соперники. Все, кроме собственной семьи.
народ очень быстро забывает мат. часть. в русском к слову это проще: рекуррентная функция vs. рекурсивная функция. в англиском и то и другое называется рекурсией, а в русском первое ссылается на определение функции (фиб определена рекуррентно), а второе ссылается на реализацию (фиб можно реализовать с/без рекурсии.)
PS доказательство можно строить проще: процессора (или абстрактно машина Тюринга) не умеют рекурсию. они могут ее реализовать, но рекурсится им просто нет куда: они есть "простые" конечные автоматы. что собственно ты выше и реализовал.
Пруфы-то будут? См. recurrence equation / relation.
но и на форумах (где я первый раз проблему видел), и знакомые от туда, толпы народа с понятием "recurrence" не встречались.
директивы препроцессора обрабатываются еще до лексического анализа