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

    +134

    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
    #include <stdio.h>
    #define max(x,y) ((x>y)?x:y)
    #define N 255
    typedef unsigned char uchar;
    
    uchar s,t,x,y,z,n,S[10000],FO[N+N*(N-1)/2];
    uchar mask[]={1,2,4,8,16,32,64,128};
    int TOP=0;
    unsigned int COUNTER=0,AO[N];
    FILE *in;
    
    int pop(){
    //if the top element in the stack is passed and stack is not empty,
    //find next parent vertex
    while(S[TOP]>128 && TOP>0) TOP-=S[TOP]-128;
    return(TOP);
    }
    
    int push(){		//add new elements to the stack
    int tmp=TOP,i,j,k;		//tmp is a temporary variable 
    x=S[TOP-S[TOP]+1];	//x is a parent vertex
    for(i=1;i<=FO[AO[x]];i++){
       y=FO[AO[x]+i];	//y is a neigbour of x 
       if(!test(y)){	//y is visited? if not keep going
         k=max(y/8+1,S[TOP]-2);	//copy set P(x) to the new set P(y)
         S[++tmp]=y;
         for(j=0;j<k;j++,S[++tmp]=0);
         S[++tmp]=k+2;
         for(j=1;j<=S[TOP]-2;j++) S[tmp-j]=S[TOP-j];
         S[tmp-(y/8+1)]|=mask[y-(y/8)*8];	//add child y to P(y)
       }
    }
    S[TOP]+=128;	//drop flag for the vertex x
    TOP=tmp;	//the last child y become parent
    }
    
    int test(int j){	//does vertex j in the set P(TOP)?
    z=((j/8+1)>S[TOP]-2)?0:(S[TOP-(j/8+1)] & mask[j-(j/8)*8])?1:0;
    return(z);
    }
    
    int inc(){	//the path was found
    COUNTER++;
    S[TOP]+=128;
    }
    
    int main(){
    int i,j,k;
    in=fopen("Data15.txt","r");	//open file
    fscanf(in," %d %d",&i,&n);		//read the number of vertices
    for(k=n,i=0;k>=0;k--){
       fscanf(in,"%d %d",&j,&FO[i]);
       j=FO[i];
       for(AO[n-k]=++i-1;j>0;j--,i++){
          fscanf(in,"%d ",&FO[i]);
       }
    }
    printf("Type first and end nodes: ");	//type s and t separated by space
    scanf("%d %d",&s,&t);
    S[0]=s;
    for(j=1;j<=s/8+1;S[j++]=0);
    S[j]=s/8+3;
    TOP=j;
    S[TOP-(s/8+1)]|=mask[s-(s/8)*8];
    while(pop()>=0) (test(s) && test(t))?inc():push(); //launch breadth-search algorithm
    printf("# of paths in the graph b/w s=%d and t=%d equals %d\n",s,t,COUNTER);
    return(0);
    }

    разбирая старый CD бэкап откопал лабу...(знаю,знаю что продакшн кошернее, и на сях не пишу со студенчества)
    хотел вайпнуть безжалости но вспомнил про говнокодосайт.
    помоему код люто доставляет.

    прога подсчитывает полное число путей в графе между заданными вершинами s и t.
    граф считывается из файла в формате: "номер_вершины степень_вершины {достижимые_вершины_через_пробел}"
    (по коду видно)

    Запостил: govnyuk, 13 Марта 2014

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

    • а чё. даже стиль проглядывается.
      Ответить
    • > #define max(x,y) ((x>y)?x:y)
      Фу-фу-фу. Сразу 2 заповеди макроёбства нарушил ;)
      Ответить
      • Какая вторая?
        Ответить
        • Когда пишешь function-like макрос:
          - оборачивай весь макрос в скобки;
          - оборачивай все аргументы в скобки;
          - юзай каждый аргумент ровно один раз;
          - называй макрос КАПСОМ.

          Так что тут даже 3 заповеди нарушено :)
          Ответить
          • Ms кладет на две из них:
            http://msdn.microsoft.com/en-us/library/windows/desktop/dd757150(v=vs.85).aspx
            Да и как реализовать макрос максимума с однократным упоминанием аргумента?
            Ответить
            • > Да и как реализовать макрос максимума с однократным упоминанием аргумента?
              Никак :) А нахуя зачем?
              Ответить
              • как зачем? мы ж на говнокоде.
                Ответить
              • В крестах можно юзать лямбды и деклтайп.
                В гцц можно делать примерно то же самое расширениями.

                Берем "лямбды" отсюда. http://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html
                #define maxint(a,b) ({int _a = (a), _b = (b); _a > _b ? _a : _b; })


                Смешиваем с местным деклтайпом http://gcc.gnu.org/onlinedocs/gcc/Typeof.html
                #define max(a,b) \
                       ({ typeof (a) _a = (a); \
                           typeof (b) _b = (b); \
                         _a > _b ? _a : _b; })
                Ответить
                • И чем это лучше инлайн-функции? Ну кроме того, что работает с любыми типами.
                  Ответить
                  • Собственно именно тем, что работает с любыми типами, особенно учитывая то, что, емнип, в сишечке нету перегрузки функций даже в последнем стандарте.
                    Ну и плюс всякие фишки типа _Generic.
                    Ответить
            • даже в сишке уже есть inline-функции.
              Ответить
            • > Ms кладет на две из них
              Да M$ много на что кладет, включая здравый смысл... Чего только стоит их #define interface struct, о котором тут когда-то писал Дефекейт.

              P.S. Офттопик: вчера ставил вижуалку 2013 экспресс и словил разрыв шаблона - она изкоробки умеет в git.
              Ответить
              • > умеет в git
                что, и про гитовый index она тоже знает? а отдельные ханки позволяет добавлять как git add --interactive ?
                Ответить
                • > что, и про гитовый index она тоже знает?
                  Насколько я понял, там libgit2 юзается в качестве бекенда.

                  Ветки, ремоуты, логи, чекауты - умеет. С индексом судя по всему работает, т.к. позволяет коммитить не все файлы. Лениво на эту виртуалку ставить консольного git'а чтобы проверить что там происходит в реале... Да и ставил вижуалку я только чтобы затестить на кроссплатформенность несколько моментов в коде...

                  Отдельные ханки не умеет, работает только на уровне целых файлов. Кстати, а есть ли хоть одна IDE, которая умеет?
                  Ответить

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