Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 24 kết quả

Đề tài: tìm chu trình euler với lập trình C

  1. #1
    Ngày gia nhập
    11 2008
    Bài viết
    1

    Red face tìm chu trình euler với lập trình C

    xin chào các tiền bối -xin các tiền bối chỉ giùm chương trình tìm chu trình và đường đi euler với ( viết bằng C).... xin cám ơn...

  2. #2
    Ngày gia nhập
    09 2007
    Bài viết
    724

    Mặc định Thuật toán tìm chu trình euler

    Đây cho bạn thuật toán đệ qui nè.

    C Code:
    1. int RunAlgEuler(int iStart)
    2. {
    3.     for(int i=0; i<g.GetN(); i++)
    4.     {
    5.         int tmp = g[iStart,i]; // với g là ma trận kề
    6.         if(tmp>0)
    7.         {
    8.             g[i][iStart] = tmp-1;
    9.             g[iStart][i] = tmp-1;
    10.             RunAlg(i);
    11.         }
    12.     }
    13.     sOutput.Push(iStart); // đẩy đỉnh iStart vào stack
    14.     return 1;
    15. }

  3. #3
    Ngày gia nhập
    12 2008
    Nơi ở
    Here isn't Infomations
    Bài viết
    10

    bạn ơi ! bạn có thể share cho mình đoạn code của CT này ko ? nhap vao` 1 ma trận kề rồi tìm chu trình euler !

  4. #4
    Ngày gia nhập
    05 2008
    Bài viết
    224

    uhm , bạn zkday cho đi , mình cũng đang học toán rời rạc đến phần này mà chỉ viết bằng pascal khó hiểu lắm .thanks
    Em có thấy nắng vàng kỷ niệm
    Hạ ngồi ru thanh thản những môi cười
    Thuở ngồi ngóng tay choàng tay nỗi nhớ
    Vin tay vào tháng năm chơi vơi...

  5. #5
    Ngày gia nhập
    09 2007
    Bài viết
    724

    @cafelanh,bocc14: ngay tại thread số 2 đó bạn .

    g là ma trận kề đó bạn.

    còn thằng soutput bạn có thể dùng stact của thư viện stl mà phải không?

  6. #6
    Ngày gia nhập
    12 2008
    Nơi ở
    Here isn't Infomations
    Bài viết
    10

    Mặc định tìm chu trình euler với lập trình C

    vậy thì mình cần thêm đoạn code nhập ma trận kề nữa ....ko biết trong này có không vậy zkday2628

  7. #7
    Ngày gia nhập
    09 2007
    Bài viết
    724

    vậy thì mình cần thêm đoạn code nhập ma trận kề nữa ....ko biết trong này có không vậy zkday2628
    Bạn ơi. Bạn làm ơn đọc cái code giùm mình tý được không?

    Cái của mình đưa lên là để cho bạn xem là làm cái này theo phương pháp đệ qui thôi. còn bạn phải triển khai làm sao để thành chương trình, đó là bạn phải làm ( vì đây là bài tập của bạn mà phải không nào )

  8. #8
    Ngày gia nhập
    12 2008
    Nơi ở
    Here isn't Infomations
    Bài viết
    10

    Mặc định tìm chu trình euler

    tại lâu quá ko mò lại C++ , mình cũng hơi thiếu cơ sở ....hôm nay lại phải làm 1 bài về "xác định và xuất ra xem đồ thị G có phải là đồ thị Euler không , nếu có hãy xuất ra một chu trình Euler. "
    hàm ở trên có thể giải quyết dc việc này , viẹc còn lại là mình phải xây 1 thêm 1 doạn code để nhập ma trận vào duyệt phải ko bạn ?

    Sẵn đây bạn có thể test giùm mình cái này dc kô ?

    C Code:
    1. // Bai 6: Thuat Toan xac dinh chu trinh Euler tren do thi G
    2.  
    3. // EULER.CPP
    4.  
    5. #include <stdio.h>
    6. #include <conio.h>
    7.  
    8. #define TRUE 1
    9. #define FALSE 0
    10.  
    11. #define VAIN 99
    12. #define MAX 10
    13.  
    14. int G[MAX][MAX];    // Ma Tran ke Dinh-Dinh (co Khuyen)
    15. int S[MAX][MAX];    // Ma Tran danh dau Cung da su dung
    16. int Pred[MAX];      // Mang Nua-Bac-Trong cua 1 Dinh
    17. int Succ[MAX];      // Mang Nua-Bac-Ngoai cua 1 Dinh
    18. int path[MAX];      // Mang duong di cua chu trinh
    19.  
    20. int N,k,l=0;
    21. void ReadData();
    22. void PrintData();
    23. int Check(int k);
    24. void Euler();
    25.  
    26.  
    27. void main()
    28. {
    29.     ReadData();
    30.     PrintData();
    31.     Euler();
    32. }
    33.  
    34. void ReadData()
    35. {
    36.     int i,j;
    37.     FILE* f=fopen("c:\\borlandc\\thuvien\\ltdt2\\EU_in.txt","rt");
    38.     if (f==NULL)    { printf("\nError Loading File!\n");    return; }
    39.     fscanf(f,"%d",&N);// gia tri dau tien cho biet so dinh cua Do Thi G
    40.     for(i=1;i<=N;i++)
    41.     {
    42.         Succ[i]=Pred[i]=0;
    43.         for(j=1;j<=N;j++)
    44.         {
    45.             S[i][j]=FALSE;   // danh dau Cung khong con su dung nua
    46.             fscanf(f,"%d",&G[i][j]);//lan luot doc cac phan tu MT ke
    47.         }
    48.     }
    49.     fclose(f);
    50.     for(i=1;i<=N;i++)
    51.         for(j=1;j<=N;j++)
    52.           if(G[i][j]>0)
    53.           { S[i][j]=TRUE;Succ[i]++;Pred[j]++;}  // Tinh Bac moi Dinh
    54. }
    55.  
    56. void PrintData()
    57. {
    58.     clrscr();
    59.     int i,j;
    60.     printf("\nMa Tran Ke G[%d*%d]:\n",N,N);
    61.     for(i=1;i<=N;i++)
    62.     {
    63.         for(j=1;j<=N;j++)
    64.             printf("%4d",G[i][j]);
    65.         printf("\n");
    66.     }
    67.  
    68. }
    69.  
    70. void Euler()
    71. {
    72.     FILE *g=fopen("c:\\borlandc\\thuvien\\ltdt2\\EU_out.txt","wt");
    73.     int i;
    74.     for(i=1;i<=N;i++)
    75.         if((Pred[i]+Succ[i])%2) // neu co dinh bac Le
    76.         {
    77.             printf("\nTon tai Dinh %d Bac Le!",i);
    78.             printf("\nKhong co chu trinh Euler\n");
    79.             fclose(g);
    80.             return;
    81.         }
    82.     printf("\nDo thi co chu trinh Euler\n");
    83.  
    84.     int k,ok;  // kiem tra va in ra man hinh chu trinh Euler 1 net ve
    85.  
    86.     printf("\nKet qua kiem tra xuat phat tu dinh 1:\n");
    87.  
    88.     for(k=2;k<=N;k++)       // kiem tra xuat phat tu Dinh 1
    89.     {
    90.         if((G[1][k]!=0))    // co Cung noi Dinh 1 voi Dinh k
    91.         {
    92.           S[1][k]=FALSE;    // danh dau Cung(1,k) da duoc su dung
    93.           ok=Check(k);  // xet tiep Dinh k
    94.           if(ok==FALSE)
    95.            S[1][k]=TRUE;//duong nay khong nen qua Dinh k=>tra danh dau
    96.             else // ok==TRUE
    97.             {
    98.               //printf(" %d",k);//lan luot hien thi nguoc cac Dinh da qua
    99.               printf("Tong so dinh cua chu trinh : %d\n",l+2);
    100.               fprintf(g,"%d\n",l+2);
    101.               printf("Cac dinh cua duong di chu trinh :\n");
    102.               printf("1 %d ",k);
    103.               fprintf(g,"1 %d ",k);
    104.               for(int r=l-1;r>=0;r--)
    105.                 {
    106.                   printf("%d ",path[r]);
    107.                   fprintf(g,"%d ",path[r]);
    108.                 }
    109.               fclose(g);
    110.               getch();
    111.               return;
    112.             }
    113.         }
    114.     }   // end for
    115. }
    116.  
    117. int Check(int k)    // tiep tuc kiem tra, xuat phat tu Dinh k
    118. {
    119.     int i,j,ok;
    120.     for(i=1;i<=N;i++)
    121.     {
    122.       if((S[k][i]==TRUE)&&(G[k][i]!=0))//co Cung tu k den cac Dinh con lai ?
    123.       {
    124.          S[k][i]=FALSE;// neu co, danh dau khong su dung lai Cung(k,i) nua
    125.          ok=Check(i);       // xet tiep Dinh i den cac Dinh khac
    126.          if(ok==FALSE)
    127.          S[k][i]=TRUE;//lan nay khong nen qua Dinh i => bo danh dau
    128.          else
    129.            {
    130.                    //printf(" %d",i);
    131.                    path[l]=i;
    132.                    l++;
    133.                    return TRUE;
    134.         }
    135.       }
    136.     }
    137.     for(i=1;i<=N;i++)   // khi khong con Cung di tu Dinh k nua
    138.       for(j=1;j<=N;j++) // quet duyet do thi G xem da het Cung chua?
    139.         if(S[i][j]==TRUE)   // neu con sot Cung tren Ma Tran danh dau S =>
    140.           return FALSE;//huong di theo Dinh k nay la sai=>chon Dinh k khac
    141.       return TRUE;  // thanh cong , tra ve cac dinh nguoc tren duong di Euler
    142. }

    mình đang sài visual C++ Epress Edit 2008 .... , khi test thì nó ko chạy đc ...không biết nguyên nhan gì ?

    bị lỗi này : " The System can not find the file specified " .
    Đã được chỉnh sửa lần cuối bởi bocc14 : 10-12-2008 lúc 09:03 PM.

  9. #9
    Ngày gia nhập
    09 2007
    Bài viết
    724

    Mặc định tìm chu trình euler

    Với C bạn không nên dùng với 2k8

    nên chuyển sang C++ vì code của nó uyển chuyển và đẹp hơn nhiều so với C.

    Mình chưa đọc kỹ code của bạn nhưng có 1 số điều bạn chú ý khi dùng bộ VS (ở đây mình dùng bản pro - có free mà )

    - khi dùng nó bạn thêm cái #include "stdafx.h"
    - với C++ thì thao tác với file bạn dùng thằng: std::fstream dễ chịu hơn nhiều.
    - Bên VS ko có thằng clrscr() thay vào đó bạn dùng:
    std::system("cls");
    - để dừng màn hình thì bạn dùng thằng: std::system("pause");
    - ....
    - bỏ cái kiểu viết void main đi anh bạn . thay vào đó nên viết là int main() (vì sao thì kiếm cái bài của anh Dr - Tại sao nên có câu lệnh return trong main. (cái tiêu đề này ko nhớ rõ vì khá lâu rùi) )

    C Code:
    1. void Euler()
    2. {
    3.     FILE *g=fopen("c:\\borlandc\\thuvien\\ltdt2\\EU_out.txt","wt");
    4.     int i;
    5.     for(i=1;i<=N;i++)
    6.         if((Pred[i]+Succ[i])%2) // neu co dinh bac Le
    7.         {
    8.             printf("\nTon tai Dinh %d Bac Le!",i);
    9.             printf("\nKhong co chu trinh Euler\n");
    10.             fclose(g);
    11.             return;
    12.         }
    13.     printf("\nDo thi co chu trinh Euler\n");
    14.  
    15.     int k,ok;  // kiem tra va in ra man hinh chu trinh Euler 1 net ve
    16.  
    17.     printf("\nKet qua kiem tra xuat phat tu dinh 1:\n");
    18.  
    19.     for(k=2;k<=N;k++)       // kiem tra xuat phat tu Dinh 1
    20.     {
    21.         if((G[1][k]!=0))    // co Cung noi Dinh 1 voi Dinh k
    22.         {
    23.           S[1][k]=FALSE;    // danh dau Cung(1,k) da duoc su dung
    24.           ok=Check(k);  // xet tiep Dinh k
    25.           if(ok==FALSE)
    26.            S[1][k]=TRUE;//duong nay khong nen qua Dinh k=>tra danh dau
    27.             else // ok==TRUE
    28.             {
    29.               //printf(" %d",k);//lan luot hien thi nguoc cac Dinh da qua
    30.               printf("Tong so dinh cua chu trinh : %d\n",l+2);
    31.               fprintf(g,"%d\n",l+2);
    32.               printf("Cac dinh cua duong di chu trinh :\n");
    33.               printf("1 %d ",k);
    34.               fprintf(g,"1 %d ",k);
    35.               for(int r=l-1;r>=0;r--)
    36.                 {
    37.                   printf("%d ",path[r]);
    38.                   fprintf(g,"%d ",path[r]);
    39.                 }
    40.               fclose(g);
    41. //            getch();
    42.               return;
    43.             }
    44.         }
    45.     }   // end for
    46. }

    - edit: bạn thêm trên chổ #include thằng: #include "stdafx.h"
    - và nếu dùng mấy cái std thì thêm thêm: #include "iostream"

  10. #10
    Ngày gia nhập
    12 2008
    Nơi ở
    Here isn't Infomations
    Bài viết
    10

    FILE *g=fopen("c:\\borlandc\\thuvien\\ltdt2\\EU_out.txt ","wt");
    cái này thì VS chạy dc ko , mình thấy có chương trình borlandc trong đó ...

    mình chưa dc học int main ....hix ko biết thay void main = int main có bình thường ko bạn . dù sao cũng cảm ơn bạn nhìu !

Các đề tài tương tự

  1. Kỹ thuật C++ Làm sao để đánh dấu đường đã đi qua trong chu trình Euler?
    Gửi bởi chuong01 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 13-06-2010, 11:53 AM
  2. <Bài toán ghép chữ dùng chu trình Euler>
    Gửi bởi anhoa1608 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 09-09-2009, 09:13 AM
  3. Đồ thị Euler. Toán rời rạc viết bằng C
    Gửi bởi kimtaitokk trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 08-04-2009, 04:58 PM
  4. Help Mình ! Đồ Thị Euler trên C++
    Gửi bởi bocc14 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 11-12-2008, 10:31 AM
  5. Mã nguồn C | Chu trình Euler !
    Gửi bởi Forlorn_hope trong diễn đàn Thủ thuật, Tutorials và Mã nguồn C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 16-03-2008, 11:54 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn