1. Си / Говнокод #19299

    −44

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    72. 72
    73. 73
    74. 74
    75. 75
    76. 76
    77. 77
    78. 78
    79. 79
    80. 80
    81. 81
    82. 82
    83. 83
    84. 84
    85. 85
    86. 86
    87. 87
    88. 88
    89. 89
    90. 90
    #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 при выходе из области видимости фукнции.

    Запостил: j123123, 13 Января 2016

    Комментарии (18) RSS

    • ava Dummy00001 13.01.2016 11:41 # +1

      > бред, связанный с рекурсией. Типа он считал что ее нельзя реализовать через сраные циклы

      народ очень быстро забывает мат. часть. в русском к слову это проще: рекуррентная функция vs. рекурсивная функция. в англиском и то и другое называется рекурсией, а в русском первое ссылается на определение функции (фиб определена рекуррентно), а второе ссылается на реализацию (фиб можно реализовать с/без рекурсии.)

      PS доказательство можно строить проще: процессора (или абстрактно машина Тюринга) не умеют рекурсию. они могут ее реализовать, но рекурсится им просто нет куда: они есть "простые" конечные автоматы. что собственно ты выше и реализовал.
      Ответить

      • ava roman-kashitsyn 13.01.2016 11:51 # 0

        > в англиском и то и другое называется рекурсией
        Пруфы-то будут? См. recurrence equation / relation.
        Ответить

        • ava Dummy00001 13.01.2016 11:58 # −1

          у них в CS образовании не используется: все в лоб зовут рекурсией. пару раз с америкосами на эту тему общался. мне даже курсы и учебники показывали: понятие рекуррентности не вводится.
          Ответить

          • ava roman-kashitsyn 13.01.2016 12:55 # −1

            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
            Ответить

            • ava Dummy00001 13.01.2016 13:05 # 0

              то что мне показывали был более новый учебный материал. но может еще в разных универах различаться.

              но и на форумах (где я первый раз проблему видел), и знакомые от туда, толпы народа с понятием "recurrence" не встречались.
              Ответить

            • ava 3_14dar 13.01.2016 20:46 # 0

              Бетонная математика?
              Ответить

    • ava TarasB 13.01.2016 12:53 # +1

      гораздо проще же рекурсию сэмулировать, зачем этот ад
      Ответить

      • ava Dummy00001 13.01.2016 13:07 # 0

        почему ад. очень даже симпатичная стэковая машина. и всего лишь страница кода.
        Ответить

    • ava chtulhu 13.01.2016 13:28 # 0

      >Надо короче сделать локальный #define чтобы он автоматически #undef при выходе из области видимости фукнции.

      директивы препроцессора обрабатываются еще до лексического анализа
      Ответить

      • ava dxd 13.01.2016 13:56 # 0

        Нужен второй препроцессор и переопределение фигурных скобок!
        Ответить

    • ava 3_dar 13.01.2016 20:15 # −1

      AAAAAAAAAA, ГОТО через return
      Ответить

    • ava d_fomenok 13.02.2016 19:42 # 0

      перчать
      Ответить

    • ava jey-val-star 25.08.2021 04:25 # 0

      На следующий день Руслан выиграл свои первые крупные соревнования. Его поздравляли все - ребята из секции, несколько школьных друзей, команда тренеров, даже соперники. Все, кроме собственной семьи.
      Ответить

    Добавить комментарий