Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 11 kết quả

Đề tài: Thuat toan ban tron viết trên C như thế nào?

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

    Wink Thuat toan ban tron viết trên C như thế nào?

    Trong đám cưới của Péc-xây và An-đrơ-nét có 2N hiệp sĩ, được đánh số từ 1 đến 2N. Mỗi hiệp sĩ có không quá N-1 kẻ thù. Hãy giúp Ca-xi-ô-bê, mẹ của An-đrơ-nét xếp 2N hiệp sĩ ngồi quanh một bàn tròn sao cho không có hiệp sĩ nào phải ngồi cạnh kẻ thù của mình. Mỗi hiệp sĩ sẽ cho biết những kẻ thù của mình khi họ đến sân rồng.
    Dữ liệu: Vào từ file văn bản PARTY.INP
    • Dòng đầu tiên chứa số nguyên N (1<=N<=100).
    • Dòng thứ i trong số 2N dòng tiếp theo cho biết các kẻ thù của hiệp sĩ thứ i, số đầu tiên trong mỗi dòng cho biết số kẻ thù của hiệp sĩ i và các số sau liệt kê các kẻ thù.
    Kết quả: Ghi ra file văn bản PARTY.OUT
    • Dòng duy nhất bao gồm 2N số là thứ tự các hiệp sĩ ngồi cạnh nhau.

    PARTY.INP
    3
    2 2 3
    2 1 3
    2 1 2
    2 5 6
    2 4 6
    2 4 5
    PARTY.OUT
    1 4 2 5 3 6
    mình không biết dùng thuật toán gì để làm cách.nếu ai có đoạn mã c đưa lên mình tham khảo được không

  2. #2
    Ngày gia nhập
    01 2009
    Bài viết
    165

    bạn thử dùng thuật toán quay lui xem,giải thuật là chọn 1 người đầu tiên có số kẻ thù là ít nhất rối chọn người thứ 2 ứng với cách chọn người thứ nhất ,chọn nhười thứ 3 ứng với người thứ 2 ,mỗi lấn xếp thì phải xét xem việc chọn người tiếp theo có khả thi ko nếu ko thì lập tức quay lại bước lần xét trước đó để chọn người khác,mỗi lần xếp xong 1 người thì lưu lại để sau này ko phải xét nữa,nói giải thuật thì dễ nhưng làm thì khó lắm ,bạn cố gắng nha!

  3. #3
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    Kiểu này là cực kỳ bó tay với sinh viên Việt Nam, lười nhác, bị động thiếu suy nghĩ. Toàn thấy post bài lên chờ ai đó làm hộ rồi mang về nộp. Không chịu làm lấy đâu ra làm được, không chịu chia sẻ, cứ muốn người khác chia sẻ là sao?

    Hãy tư duy lại đi mấy bạn sinh viên Việt Nam yêu quý.
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

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

    Trích dẫn Nguyên bản được gửi bởi Dreaminess Xem bài viết
    Kiểu này là cực kỳ bó tay với sinh viên Việt Nam, lười nhác, bị động thiếu suy nghĩ. Toàn thấy post bài lên chờ ai đó làm hộ rồi mang về nộp. Không chịu làm lấy đâu ra làm được, không chịu chia sẻ, cứ muốn người khác chia sẻ là sao?

    Hãy tư duy lại đi mấy bạn sinh viên Việt Nam yêu quý.
    Sao lại quơ đũa cả nắm thế anh Dr. Chắc anh muốn toàn Mem nhiệt tình ở đây "Làm thịt" anh à

  5. #5
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Mới đây có bạn rất vô tư lớn tiếng chửi toàn thể diễn đàn vì không ai giúp bạn đó giải bài tập, liệu mọi người nghĩ sao.

    Vẫn biết là học lập trình không dễ, mới học thì rất muốn và cần người có kinh nghiệm giúp đỡ, nhưng cứ ỉ lại vào người khác liệu có tiến bộ nổi không.

    mình không biết dùng thuật toán gì để làm cách.nếu ai có đoạn mã c đưa lên mình tham khảo được không
    Bạn input file vào một mảng 2 chiều, 2n hàng 2n cột, kẻ thù thứ j của hiệp sĩ j thì gán ô đó =1 ngược lại bằng 0

    Duyệt ma trận trên, tại hàng i chọn j không thù (kiểm tra xem đã ngồi chưa) xếp ngồi cạnh, tiếp xét đến j (nói chung sẽ xét nhảy cóc lung tung cho đến khi full mảng phụ lưu 2n hiệp sĩ)

    Bạn thử trước đi đã nhé.

    @Edit: sử dụng thuật toán quay lui để đảm bảo in được cấu hình cần thiết nếu tồn tại ít nhất 1 cấu hình.
    Đã được chỉnh sửa lần cuối bởi QuangHoang : 08-04-2009 lúc 09:42 AM.

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

    Mặc định Thuat toan ban tron viết trên C như thế nào?

    Trích dẫn Nguyên bản được gửi bởi QuangHoang Xem bài viết
    Mới đây có bạn rất vô tư lớn tiếng chửi toàn thể diễn đàn vì không ai giúp bạn đó giải bài tập, liệu mọi người nghĩ sao.
    Thứ rác rưởi này thì mấy anh chấp làm gì. Bài tập thì tự mình làm. Nếu sai thì up lên để các mem text lỗi dùm chứ ai đâu ở không ngồi gõ lóc cóc để giúp.

  7. #7
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Không quan tâm tác giả còn cần nữa không, bài tập trên khá hay tiện H đang học mấy cái đó nên làm và share code thui.
    C Code:
    1. #include <stdio.h>
    2. #define MAX 100
    3. /*
    4. */
    5. int a[MAX][MAX], b[MAX], n;
    6. FILE *fi, *fo;
    7.  
    8. /**All functions**/
    9. void InputFile(char *filename);
    10. void BackTracking(int x, int t);
    11.  
    12.  
    13. /**Main program**/
    14. int main()
    15. {
    16.     InputFile("Input.txt");
    17.     BackTracking(1,1);
    18.     return 0;
    19. }
    20.  
    21.  
    22. /*Input from file*/
    23. void InputFile(char *filename)
    24. {
    25.     fi = fopen(filename,"rt");
    26.     fscanf(fi,"%d",&n);
    27.     printf("%d\n",n);
    28.  
    29.     int i,j;
    30.  
    31.     /*Khoi tao gia tri ban dau cho 2 mang a, b*/
    32.     for (i=1; i<=2*n; i++) b[i] = 0;
    33.     for (i=1; i<=2*n; i++)
    34.         for (j=1; j<=2*n; j++) a[i][j] = 0;
    35.  
    36.     /*Tien hanh doc file nhap gia tri 0\1 cho mang a*/
    37.     fprintf(fi,"\n");
    38.     for (i=1; i<=2*n; i++)
    39.     {
    40.         int x,y;
    41.         fscanf(fi,"%d",&x);
    42.         for (j=0; j<x; j++)
    43.         {
    44.             fscanf(fi,"%d",&y);
    45.             a[i][y] = 1;
    46.         }
    47.         fprintf(fi,"\n");
    48.     }
    49.  
    50.     /* Show hang*/
    51.     for (i=1; i<=2*n; i++)
    52.     {
    53.         for (j=1; j<=2*n; j++) printf("%4d ",a[i][j]);
    54.         printf("\n");
    55.     }
    56.     printf("\n");
    57.     fclose(fi);
    58. }
    59.  
    60. int Check(int i)
    61. {
    62.     int j;
    63.     for (j=1; j<=2*n; j++)
    64.         if(b[j]==i) return 0;
    65.     return 1;
    66. }
    67.  
    68. /*Print solutions on screen*/
    69. void Print()
    70. {
    71.     int i;
    72.     for (i=1; i<=2*n; i++) printf("%4d ",b[i]);
    73.     printf("\n");
    74. }
    75.  
    76. /*Print file, if you want*/
    77. void PrintFile(char *filename)
    78. {
    79. }
    80.  
    81. /*Search using back tracking
    82.    - x la cac phan tu lan luot cua mang b
    83.    - t la hang dang xet tai mang a
    84. */
    85. void BackTracking(int x, int t)
    86. {
    87.     int i;
    88.     for (i=1; i<=2*n; i++)
    89.         if (!a[t][i] && !b[x] && Check(i))
    90.         {
    91.             b[x] = i;
    92.             if (x==2*n && !a[i][b[1]]) Print();  // !a[i][b[1]] thang cuoi voi thang dau
    93.             else BackTracking(x+1,i);
    94.             b[x] = 0;
    95.         }
    96. }
    File input
    3
    2 2 3
    2 1 3
    2 1 2
    2 5 6
    2 4 6
    2 4 5
    Bài H làm liệt kê tất cả các cấu hình ra, còn nếu muốn in file thì hoàn thành nốt hàm in file rồi sửa một chút hàm Backtracking là ok.

  8. #8
    Ngày gia nhập
    01 2009
    Bài viết
    165

    theo mình thì bài này dùng thuật toán quay lui đệ quy kết hợp với kĩ thuật nhánh cận là hay nhất ko biết có đúng ko.cách này mình dùng cho bài 8 hậu thấy cũng ok .
    Đã được chỉnh sửa lần cuối bởi kimduquan : 08-04-2009 lúc 08:24 PM.

  9. #9
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Code trên là đệ quy quay lui đó bạn.

  10. #10
    Ngày gia nhập
    05 2009
    Bài viết
    1

    em thử làm lại bài này rùi mà vẫn chưa ổn ! bác nào cao tay ấn cho em lời khuyên về bài này của em nhé

    C Code:
    1. #include <stdio.h>
    2. #include<conio.h>
    3. #include<stdlib.h>
    4.  
    5. #define MAX 100
    6. /*      */
    7.     int a[MAX][MAX], b[MAX], n;
    8.     FILE *fi, *fo;
    9.  
    10. /**All functions**/
    11.     void InputFile();
    12.     void BackTracking(int x, int t);
    13.     void PrintFile();
    14.  
    15.  
    16. /**Main program**/
    17.     int main()
    18.     {
    19.         clrscr();
    20.         InputFile();
    21.         BackTracking(1,1);
    22.         PrintFile();
    23.         return 0;
    24.     }
    25.  
    26.  
    27. /*Input from file*/
    28.     void InputFile()
    29.     {
    30.         char filename[50];
    31.         printf("Nhap FileName = ");
    32.         scanf("%s",&filename);
    33.         fi = fopen(filename,"rt");
    34.         if(fi==NULL)
    35.         {
    36.             printf("khong doc duoc file");
    37.             getch();
    38.             exit(0);
    39.         }
    40.         fscanf(fi,"%d",&n);
    41.         printf("%d\n",n);
    42.  
    43.         int i,j;
    44.  
    45. /*Khoi tao gia tri ban dau cho 2 mang a, b*/
    46.         for (i=1; i<=2*n; i++) b[i] = 0;
    47.         for (i=1; i<=2*n; i++)
    48.         for (j=1; j<=2*n; j++) a[i][j] = 0;
    49.  
    50. /*Tien hanh doc file nhap gia tri 0\1 cho mang a*/
    51.         fprintf(fi,"\n");
    52.         for (i=1; i<=2*n; i++)
    53.     {
    54.         int x,y;
    55.         fscanf(fi,"%d",&x);
    56.         for (j=0; j<x; j++)
    57.     {
    58.         fscanf(fi,"%d",&y);
    59.         a[i][y] = 1;
    60.     }
    61.     fprintf(fi,"\n");
    62.     }
    63.  
    64. /* Show hang*/
    65.     for (i=1; i<=2*n; i++)
    66.     {
    67.         for (j=1; j<=2*n; j++) printf("%4d ",a[i][j]);
    68.         printf("\n");
    69.     }
    70.     printf("\n");
    71.     fclose(fi);
    72.     }
    73.  
    74.     int Check(int i)
    75.     {
    76.         int j;
    77.         for (j=1; j<=2*n; j++)
    78.         if(b[j]==i) return 0;
    79.         return 1;
    80.     }
    81.  
    82. /*Print solutions on screen*/
    83.     void Print()
    84.     {
    85.         int i;
    86.         for (i=1; i<=2*n; i++) printf("%4d ",b[i]);
    87.         printf("\n");
    88.     }
    89.  
    90. /*Print file, if you want*/
    91.     void PrintFile()
    92.     {
    93.         char filename[50];
    94.         FILE* f;
    95.         printf("\nNhap FileName = ");
    96.         scanf("%s",&filename);
    97.         f = fopen(filename,"wt");
    98.         if(f==NULL)
    99.         {
    100.             printf("khong ghi duoc file");
    101.             getch();
    102.             exit(0);
    103.         }
    104.         for(int i=0;i<=2*n;i++)
    105.             fprintf(f,"%d \t",b[i]);
    106.         fclose(f);
    107.     }
    108.  
    109. /*Search using back tracking
    110.         - x la cac phan tu lan luot cua mang b
    111.         - t la hang dang xet tai mang a
    112. */
    113.     void BackTracking(int x, int t)
    114.     {
    115.         int i;
    116.         for (i=1; i<=2*n; i++)
    117.         if (!a[t][i] && !b[x] && Check(i))
    118.     {
    119.     b[x] = i;
    120.     if (x==2*n && !a[i][b[1]]) Print(); // !a[i][b[1]] thang cuoi voi thang dau
    121.     else BackTracking(x+1,i);
    122.     b[x] = 0;
    123.     }
    124. }

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

  1. Lập trình C thuat toan doi ngay ra thu
    Gửi bởi z8kun trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 04-12-2012, 10:14 AM
  2. Uu nhuoc diem cua cac thuat toan
    Gửi bởi jackiechan_2912 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 04-12-2012, 12:09 AM
  3. cong ty dich thuat dich tất cả các ngôn ngữ trên thế giới
    Gửi bởi quocquang356 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 12-08-2012, 09:51 AM
  4. Bài tập C++ sua loi thuat toan first fit
    Gửi bởi no_name trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 01-04-2012, 09:02 PM
  5. thuat toan djikstra viet bang c++ voi. giup em demo
    Gửi bởi hoangdieu trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 1
    Bài viết cuối: 07-05-2010, 06:02 PM

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