Алгоритм Нахождения Эйлерова Цикла

Тема в разделе "C/C++/C#", создана пользователем Spark, 15 июн 2012.

  1. Spark

    Spark Гость

    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    #define NMAX 20

    int prov2(int n,int g[][NMAX])
    {
    int i,j,t=0,k=0;
    for (i=0;i<n;i++)
    {for (j=0;j<n;j++) k+=g[j];
    if (k%2!=0) t++;
    if (t>2) return 7;
    k=0;
    }
    return 0;
    }

    void Poisk(int v, int n,int g[][NMAX], int *no, int res[NMAX])
    {
    int stack[NMAX]={0},ns=0,V=0,i,j;

    stack[ns++]=v;
    while (ns!=0)
    {
    V=0;
    v=stack[ns-1];
    for (i = 0; i < n; i++) V+=g[v];
    if (V==0) ns--,res[(*no)++]=v;
    else
    {
    i=0;
    while (g[v]!=1) i++;
    g[v]=0;
    g[v]=0;
    stack[ns++]=i;
    }
    }
    }

    int VVOD(int *n,int g[][NMAX])
    {
    int i,j;
    FILE *f;
    if ((f=fopen("<адрес входного файла>","r"))!=NULL)
    {
    fscanf(f,"%d",n);
    if ((*n<2)||(*n>20)) return 5;
    if (feof(f)) return 4;
    for (i=0;i<(*n);i++)
    for (j=0;j<(*n);j++)
    fscanf(f,"%d",&g[j]);
    }
    else return 3;
    return 0;
    }
    int marker(int n, int massiv[], int metka)
    {
    int result=0;
    for (int i = 0; i < n; i++) if (massiv==metka) result++;
    return result;
    }

    int prov1(int n,int g[][NMAX])
    {
    int v=0;
    int *massiv=(int*)malloc(sizeof(int)*n);
    for (int i=0; i < n; i++) massiv=1;
    massiv[v]=2;
    while (marker(n,massiv,2)!=0)
    {
    for (int i=0; i < n; i++) if (massiv==2){ v=i; break;}
    for (int i=0; i < n; i++) printf("%d\n",massiv);
    printf("\n");
    massiv[v]=3;
    for (int j=0; j < n; j++) if ((g[v][j]==1)&&(massiv[j]==1)) massiv[j]=2;
    }
    for (int i=0; i < n; i++) if (massiv==1) return 6;

    return 0;
    }

    void Vyvod(int pr)
    {
    switch (pr)
    {
    case 5: {printf("nedopustimoe kolichestvo vershin");getch();break;}
    case 3: {printf("net vhodnogo faila");getch();break;}
    case 4: {printf("file pust");getch();break;}
    case 6: {printf("net ejlerova puty: graf nesvjazniy");getch();break;}
    case 7: {printf("net ejlerova puty: vershin nechetnoy stepeny bolee2");getch();break;}
    default:
    ;
    }
    }

    int main()
    {
    int i,j,k,n,no=0,g[NMAX][NMAX],t[NMAX][NMAX],res[NMAX];

    if (VVOD(&n,g)!=0) {Vyvod(VVOD(&n,g));return 0;}

    if (prov1(n,g)==6) {Vyvod(prov1(n,g));return 0;}
    if (prov2(n,g)==7) {Vyvod(prov2(n,g));return 0;}
    j=0;
    while (j<n)
    { no=0;
    for (i = 0; i < n; i++) for (k = 0; k < n; k++) t[k]=g[k];

    Poisk(j,n,t,&no,res);
    k=0;
    for (i = 0; i < no-1; i++)
    {
    if (g[res][res[i+1]]==1) k++;
    }
    if (k==no-1) break;
    printf ("\nno= %i\n",no);
    j++;
    }
    for (i = no-1; i >=0; i--)
    {
    printf("%d\n", res);
    }
    getch();
    return 0;

    }

    //---------------------------------------------------------------------------
    Подскажите, пожалуйста, есть ли тут ошибки и, если не трудно, то киньте экзэшник. Заранее благодарю!
     
Загрузка...

Поделиться этой страницей