Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: Code tìm chu trình Euler của mình. Xin test và nhận xét giúp mình

  1. #1
    Ngày gia nhập
    09 2011
    Bài viết
    4

    Mặc định Code tìm chu trình Euler của mình. Xin test và nhận xét giúp mình

    Sau khi tìm và đọc các mã giả cũng như code của những bài Tìm chu trình Euler ở trên internet (trong đó có congdongcviet) dùng Stack hoặc đệ quy thì mình thấy... ko hiểu . Rồi mình tự viết từng bước một theo cách mà mình hiểu. Mình đã test thử nhiều lần với nhiều đồ thị rồi nhưng sợ vẫn còn sai sót chỗ nào đấy nên mang lên đây nhờ các bạn test dùm.
    Mình là thành viên mới rất mong các bạn giúp đỡ Cám ơn các bạn.

    C++ Code:
    1. #include <iostream.h>
    2. #include <stdio.h>
    3. #include <conio.h>
    4. #include <iomanip.h>
    5. #include <process.h>
    6.  
    7. int MT[10][10],n;
    8.  
    9. // DOC DU LIEU TU FILE
    10. void LoadFile(char *path)
    11. {
    12.     FILE *fp=fopen(path,"rt");
    13.     if(fp==NULL)
    14.     {
    15.         cout<<"File Error !!!";
    16.         getch();
    17.         exit(1);
    18.     }
    19.     fscanf(fp,"%d",&n);
    20.     for(int i=0;i<n;i++)
    21.         for(int j=0;j<n;j++)
    22.             fscanf(fp,"%d",&MT[i][j]);
    23.     fclose(fp);
    24.     for(i=0;i<n;i++)
    25.     {
    26.         for(int j=0;j<n;j++)
    27.             cout<<setw(3)<<MT[i][j];
    28.         cout<<endl;
    29.     }
    30. }
    31.  
    32. // TINH SO CANH CUA DO THI
    33. int SoCanhDT()
    34. {
    35.     int i,j,tongsobac=0;
    36.     for(i=0;i<n;i++)
    37.         for(j=0;j<n;j++)
    38.             tongsobac+=MT[i][j];
    39.     return tongsobac/2;
    40. }
    41.  
    42. // TIM BAC CUA MOT DINH TRONG DO THI
    43. int TimBac(int x)
    44. {
    45.     int i,bacx=0;
    46.     for(i=0;i<n;i++) bacx+=MT[x][i];
    47.     return bacx;
    48. }
    49.  
    50. // KIEM TRA XEM CO CHU TRINH EULER HAY KHONG
    51. int CoCTEuler()
    52. {
    53.     int b;
    54.     for(int i=0;i<n;i++)
    55.     {
    56.         b=TimBac(i);
    57.         if(b%2==1) return 0;
    58.     }
    59.     return 1;
    60. }
    61.  
    62. // TIM CHU TRINH EULER
    63. void Euler(int xp)
    64. {
    65.     int bacxp=TimBac(xp),sc=SoCanhDT();
    66.     int i=xp;
    67.     cout<<setw(3)<<i;
    68.     for(int c=0;c<sc;c++)
    69.     {
    70.         for(int j=0;j<n;j++)
    71.         {
    72.             if(j==xp&&bacxp==1&&c<sc-1) j++;
    73.             if(MT[i][j]!=0)
    74.             {
    75.                 if(i==xp||j==xp) bacxp--;
    76.                 cout<<setw(3)<<j;
    77.                 MT[i][j]--;
    78.                 MT[j][i]--;
    79.                 i=j;
    80.                 break;
    81.             }
    82.         }
    83.     }
    84. }
    85.  
    86. void main()
    87. {
    88.     clrscr();
    89.     char *path;
    90.         int xp;
    91.     cout<<"Nhap duong dan den file input: ";
    92.     cin>>path;
    93.     LoadFile(path);
    94.     cout<<"Do thi "<<n<<" dinh ";
    95.     if(CoCTEuler())
    96.     {
    97.         cout<<"co chu trinh Euler.\nChon dinh xuat phat [0.."<<n-1<<"]: ";
    98.         cin>>xp;
    99.         cout<<"Chu trinh Euler xuat phat tu "<<xp<<":\n";
    100.         Euler(xp);
    101.     }
    102.     else cout<<"khong co chu trinh Euler";
    103.     getch();
    104. }

    p/s: Code mình viết bằng Borland C đó

  2. #2
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Để chọn mỗi cạnh cần phải kiểm tra đảm bảo xoá cạnh đó không làm tăng số thành phần liên thông, mình ko thấy phần đó trong code của bạn. Bỏ qua nếu mình đọc chưa kỹ hoặc chưa hiểu ý tưởng của bạn nha

  3. #3
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,006

    Có trouble đấy,
    ví dụ đoạn này :

    char *path;
    cin>>path;


    where is malloc or new ??
    ^_,^

    Tổng hợp các câu chuyện hài hước vui nhộn, sử dụng Speech Synthesis để đọc : https://www.youtube.com/channel/UCLk...Tjrg/playlists


    Bùi Tấn Quang

  4. #4
    Ngày gia nhập
    09 2011
    Bài viết
    4

    Trích dẫn Nguyên bản được gửi bởi fbchicken Xem bài viết
    Để chọn mỗi cạnh cần phải kiểm tra đảm bảo xoá cạnh đó không làm tăng số thành phần liên thông, mình ko thấy phần đó trong code của bạn. Bỏ qua nếu mình đọc chưa kỹ hoặc chưa hiểu ý tưởng của bạn nha
    Mình ko hiểu ý bạn lắm? Mà bạn đã chạy thử chưa vậy?
    Ý tưởng của mình là
    - Tìm số bậc của đỉnh xuất phát (xp) và số cạnh của đồ thị.
    - Mỗi lần đi ra hoặc đi đến đỉnh xp thì bậc của đỉnh xp sẽ giảm đi 1.
    - Trong trường hợp đỉnh sắp đến là đỉnh xp và bậc của đỉnh xp bằng 1 (chỉ còn 1 đường đó để về) mà lại chưa đi hết các cạnh thì phải tìm đỉnh khác để đi tiếp.
    Đỉnh i là đỉnh hiện tại, đỉnh j là đỉnh dự định sẽ đi.
    Nếu có cạnh nối i,j thì in ra cạnh đó, cho i=j, rồi xóa cạnh đi, break;
    Ngược lại thì tìm đỉnh khác để đến.

    Trích dẫn Nguyên bản được gửi bởi langman Xem bài viết
    Có trouble đấy,
    ví dụ đoạn này :

    char *path;
    cin>>path;


    where is malloc or new ??
    trước mình học thì thầy dạy viết dạng
    char path[50];
    rồi cin.getline(path,50);

    nhưng ko hiểu sao giờ mình viết vậy nó chẳng báo lỗi gì cả và chạy bình thường Mình dùng Borland đó.
    Đã được chỉnh sửa lần cuối bởi Zon : 19-09-2011 lúc 03:50 PM.

  5. #5
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,006

    Để giải thích detail cho bạn hiểu vấn đề thì ko khó, nhưng cũng khá dài vì lý do kiến thức cơ bản của bạn về con trỏ có trouble.


    Để hiểu sâu vấn đề bạn có thể tìm hiểu thêm ở đây http://diendan.congdongcviet.com/showthread.php?t=42977

    trích dẫn 1 phần từ bài viết
    A. Sai lầm thường gặp khi làm việc với xâu kí tự
    đối với xâu kí tự thì các bạn phải nhớ được những trường hợp sau
    1. Chưa có bộ nhớ đã sử dụng như đúng rồi >>>> sai lè ra

    char *xau;
    gets(xau); // vẫn biên dịch được
    //nhưng khi chạy sẽ sinh ra lỗi run-time
    // ở 1 số trình biên dịch cùi bắp ngày xưa thì có thể ko bị lỗi đâu
    // nhưng sai thì vẫn là sai, code này sai thuộc loại chưa cấp phát
    ^_,^

    Tổng hợp các câu chuyện hài hước vui nhộn, sử dụng Speech Synthesis để đọc : https://www.youtube.com/channel/UCLk...Tjrg/playlists


    Bùi Tấn Quang

  6. #6
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Mặc định Code tìm chu trình Euler của mình. Xin test và nhận xét giúp mình

    Trích dẫn Nguyên bản được gửi bởi Zon Xem bài viết
    Mình ko hiểu ý bạn lắm? Mà bạn đã chạy thử chưa vậy?
    Ý tưởng của mình là
    - Tìm số bậc của đỉnh xuất phát (xp) và số cạnh của đồ thị.
    - Mỗi lần đi ra hoặc đi đến đỉnh xp thì bậc của đỉnh xp sẽ giảm đi 1.
    - Trong trường hợp đỉnh sắp đến là đỉnh xp và bậc của đỉnh xp bằng 1 (chỉ còn 1 đường đó để về) mà lại chưa đi hết các cạnh thì phải tìm đỉnh khác để đi tiếp.
    Đỉnh i là đỉnh hiện tại, đỉnh j là đỉnh dự định sẽ đi.
    Nếu có cạnh nối i,j thì in ra cạnh đó, cho i=j, rồi xóa cạnh đi, break;
    Ngược lại thì tìm đỉnh khác để đến.
    Mình chưa chạy thử và cũng chưa đọc kỹ code của bạn. Nhưng nhìn thoáng qua thì không thấy phần chọn cạnh để không mất liên thông. Theo như ý tưởng bạn trình bày thì cũng không thấy phần đó.

    Ví dụ cho đồ thị là hình giống cái đồng hồ cát gồm 2 tam giác ABC và BDE nhé (5 đỉnh, 6 cạnh AB, BC, AC, BD, BE, DE)
    Code của bạn giả sử đi từ A. Lần đầu tiên chọn cạnh AB đi đến B. Lần thứ 2 liệu code của bạn có chọn cạnh BC không? Nếu đi theo cạnh BC thì đồ thị sẽ mất liên thông và bạn không thể đi đến D và E được nữa.

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

    Trích dẫn Nguyên bản được gửi bởi langman Xem bài viết
    Để giải thích detail cho bạn hiểu vấn đề thì ko khó, nhưng cũng khá dài vì lý do kiến thức cơ bản của bạn về con trỏ có trouble.


    Để hiểu sâu vấn đề bạn có thể tìm hiểu thêm ở đây http://diendan.congdongcviet.com/showthread.php?t=42977

    trích dẫn 1 phần từ bài viết
    Cám ơn bạn, bài khá dài, mình sẽ đọc từ từ

    Trích dẫn Nguyên bản được gửi bởi fbchicken Xem bài viết
    Mình chưa chạy thử và cũng chưa đọc kỹ code của bạn. Nhưng nhìn thoáng qua thì không thấy phần chọn cạnh để không mất liên thông. Theo như ý tưởng bạn trình bày thì cũng không thấy phần đó.

    Ví dụ cho đồ thị là hình giống cái đồng hồ cát gồm 2 tam giác ABC và BDE nhé (5 đỉnh, 6 cạnh AB, BC, AC, BD, BE, DE)
    Code của bạn giả sử đi từ A. Lần đầu tiên chọn cạnh AB đi đến B. Lần thứ 2 liệu code của bạn có chọn cạnh BC không? Nếu đi theo cạnh BC thì đồ thị sẽ mất liên thông và bạn không thể đi đến D và E được nữa.
    Mình đã test rồi, đúng là với cái đồ thị như vậy thì nó ko đi hết dc các cạnh Bạn có cách nào giải quyết ko? Cho mình xin ý kiến.

  8. #8
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Trích dẫn Nguyên bản được gửi bởi Zon Xem bài viết

    Mình đã test rồi, đúng là với cái đồ thị như vậy thì nó ko đi hết dc các cạnh Bạn có cách nào giải quyết ko? Cho mình xin ý kiến.
    Hmmm ý kiến thì dễ thôi nhưng bạn phải đọc lý thuyết để nắm được thuật toán rồi hẵng implement chứ! Giờ mình có đưa ra ý kiến thì cũng là copy-paste lại mô tả thuật toán từ nguồn khác mà thôi, bạn tự google rồi đọc đi còn nhanh hơn

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

    Trước khi viết mình cũng đã đọc thuật toán từ nhiều nơi nhưng hầu như chỉ đưa thuật toán hoặc code mà ko giải thích khiến mình khó hiểu, càng đọc càng rối (có lẽ do IQ mình hơi có giới hạn :">).
    Bạn có cách giải thích nào dễ hiểu ko? Giúp mình với :-)

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

  1. Test giúp phần mềm Quản lý tiền thiếu Vật tư nông nghiệp (code using C#)
    Gửi bởi suka trong diễn đàn Dự án & Source code C#, ASP.NET
    Trả lời: 5
    Bài viết cuối: 11-02-2011, 03:14 PM
  2. bộ test lớn cho bài toán tìm đường đi ngắn nhất. Giúp mình?
    Gửi bởi nothing1010 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 30-10-2010, 09:56 PM
  3. Test giúp code danh sách liên kết
    Gửi bởi arikawoa trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 21-09-2010, 04:54 PM
  4. Mọi người test đoạn code này cho mình cái
    Gửi bởi tungk58t2 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 10-12-2008, 10:13 PM
  5. code tìm chu trình euler bằng đệ quy
    Gửi bởi mylinh 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: 30-05-2008, 08:06 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