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ố 12 kết quả

Đề tài: [C/C++] Tìm hoán vị củ N phần tử

  1. #1
    No Avatar
    Duy Thanh Khách

    Mặc định [C/C++] Tìm hoán vị củ N phần tử

    Bạn nào biết làm ơn giúp mình doan code bài tìm hoán vi cua n phần tử:
    ví dụ nhập n=3.sẽ in ra:
    123
    132
    213
    231
    312
    321
    cảm ơn nhiều !

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    uhm một bài toán hay đấy tạm thời thì kidkid chưa có cách giải , nếu mà tính số hoán vị thì dễ nhưng in số hoán vị thì có vấn đề đây ! Để nghĩ thử xem ?

  3. #3
    Ngày gia nhập
    04 2007
    Nơi ở
    hà nội
    Bài viết
    9

    Bài này nếu mình không nhầm thì Thuật toán ở đây là dùng phương pháp sinh(Thầy mình dạy vậy không biết tên có đúng không?).Ý nghĩa của phương pháp này là dùng để giải quyết bài toán liệt kê tất cả các tổ hợp thỏa mãn điều kiện nào đó.Sao cho không được bỏ sót hoặc lặp lại tổ hợp nào.
    Bài toán có thể giải được nếu thỏa mãn 2 điều kiện:
    -Có thể xác định được một thứ tự trên tập tất cả các cấu hình tổ hợp cần liệt kê.Từ đó có thể xác định được cấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đã xác định.
    -Xây dựng một thuật toán từ cấu hình chưa phải là cuối cùng đang có,đưa ra cấu hình kế tiếp.
    Thuật toán nói đến ở trên gọi là thuật toán sinh.Cấu trúc chung của nó như sau:
    Bước 1:Tạo cấu hình ban đầu.
    Bước 2: Đưa ra cấu hình đang có.
    Bước 3: Nếu cấu hình đang có là cấu hình cuối cùng thì kết thúc thuật toán:ngược lại thì sinh cấu hình kế tiếp và quay lại bước 2.
    Vấn đề cơ bản đặt ra ở đây là Xây dựng thuật toán sinh cấu hình kế tiếp cấu hình đang có.
    Có thể lấy ra một ví dụ điển hình là Bài toán liệt kê tất cả các hoán vị của N phần tử từ tập X={1,2,3,....,n}
    Giải:Mỗi hoán vị từ n phần tử của X có thể biểu diễn bởi bộ có thứ tự n thành phần a={a1,a2,a3,....,an} thỏa mãn a1,a2...an thuộc X và mỗi phần tử đôi một khác nhau.Tức là mỗi hoán vị là một sắp xếp lôn xộn các phần tử của Tập X.
    Và trên tập các hoán vị của tập X có thể xác định một thứ tự đơn giản như sau:Hoán vị a={a1,a2,a3...,an} được coi là đứng trước hoán vị b={b1,b2,b3....bn}nếu tồn tại chỉ số k(1<=k<=n) sao cho a1=b1,a2=b2,a3=b3....ak-1=bk-1,ak<bk.Thứ tự như vậy được gọi là thứ tự "Từ Điển".Chẳng hạn bài của bạn nêu ra chính là một trường hợp của bài toán này.Với X={1,2,3} thì các hoán vị từ 3 phần tử của X được liệt kê theo thứ tự từ điển như sau:
    1 2 3
    1 3 2
    2 1 3
    3 1 2
    3 2 1
    Như vậy theo thứ tự từ điển thì hoán vị đầu tiên là (1,2,3...n) và hoán vị cuối cùng là (n,n-1....3,2,1).
    Vậy giả sử a={a1,a2,a3...an} là môt hoán vị chưa phải là hoàn vị cuối cùng thì hoán vị kế tiếp của a được xác định như sau:
    -Tìm từ phải qua trái trong hoán vị đang có chỉ số k đầu tiên thỏa mãn ak<ak+1.
    -Trong các phần tử ở bên phải của ak và lớn hơn ak tìm phần tử nhỏ nhất a i.
    -Đổi chỗ hai phần tử ak và ai.
    -lật ngược đoạn các phần tử từ ak+1 đến an.
    Mục đích của thuật toán đến đây bạn thấy chỉ là nhằm đưa lần lượt các số phía sau dãy hoán vị về phía trước và ngược lại,để đạt được cấu hình cuối cùng mong muốn.
    Mình lại lấy thêm một ví dụ nữa để bạn hiểu.VD với n=6 và hoán vị đang xét là
    a=(3,6,2,5,4,1) thì chỉ số k cần tìm là k=3 (vì a3=2<a4=5).Chỉ số i=5 (vì a5=4).Đổi chỗ a3 và a5 ta được hoán vị (3,6,4,5,2,1)và lật ngược đoạn từ ak+1 tức là đoạn từ a4 đến a6 (Đoạn 5,2,1) ta được hoán vị kế tiếp cần tìm là(3,6,4,1,2,5).
    Như vậy mình đã trình bầy sơ qua về thuật toán sinh.Còn bạn muốn viết chương trình cụ thể để giải bài toán hoán vị có thể áp dụng thuật toán trên vào code của bạn.Vì bạn không nói rõ đề ra như thế nào nên mình không thể viết code cho bạn mà chỉ hướng dẫn bạn như vậy.Nếu bạn áp dụng tốt thì chắc là sẽ giải quyết được thôi.Hi vọng bạn hiểu và chúc bạn thành công.
    Đã được chỉnh sửa lần cuối bởi hikaru007 : 19-04-2007 lúc 11:03 PM.
    >> Yêu nhau cởi áo cho nhau, Ghét nhau trợn mắt : "Áo đâu ? Mặc vào !!! <<

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bài này khá cơ bản ! cho bạn code nè
    Code:
    #include <iostream>
    #include <iomanip>
    #include <conio.h>
    
    using std::cout;
    using std::cin;
    using std::endl;
    using std::setw;
    
    const int size = 100;
    int A[size];
    
    void swap ( int &r, int &c)
    {
            int temp = r;
            r = c;
            c = temp;
    }
    void main()
    {
          int n,i,k,a,b;
          cout << " Enter the number array's elements need to be permutated: ";  cin  >> n;
         
          for ( i = 0; i < n; i++ ) A[i] = i+1;
          for ( i = 0; i < n; i++ ) cout << A[i] << setw(5);
          
          cout << "\n\n";
          cout << "-------Permutation Algorithm--------------" << "\n\n";
          /* PERMUATION ALGORITHM */
          do
          {
                  for ( i = 0; i < n; i++ )  
                          cout << A[i] << ","  << setw(3);
                  
                  cout << "\n\n"; cin.get();
                  
                  i = n - 2;
                  while ( i >= 0 && ( A[i] > A[i+1] ) ) /* Check whether it is a final configuration ( or not ) ?*/
                          i--;
                  
                  
                  if ( i >= 0 )
                  {
                          k = n - 1 ;
                          while ( A[k] < A[i] )
                                  k--;
                          
                          swap ( A[k], A[i] );
                          a = i + 1;
                          b = n - 1;
                                        while ( a < b )
                                        {
                                                swap ( A[a], A[b] );
                                                a++;
                                                b--;
                                        }
                  }              
                          
          }
          while ( i >= 0 );
          getch();
    }

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Hix thằng bạn mình nó nói thế này nè 4 vòng for ***g nhau , nếu mà có cặp i j k l nào đó trùng nhau thì không in ra , ngoài ra in hết là xong ?

  6. #6
    No Avatar
    Leon88 Khách

    Mặc định [C/C++] Tìm hoán vị củ N phần tử

    Mình cũng xin post 1 đoạn code của mình

    #include<iostream.h>
    #include<conio.h>
    int n,i,j;
    int a[100],b[100],c[100];
    void hoanvi()
    {
    int k;
    for (k=1;k<=n;k++)
    if (b[k]==0)
    {
    j++;
    c[j]=a[k];
    b[k]=1;
    if (j==n)
    {
    cout<<"\n";
    for (i=1;i<=n;i++) { cout<<c[i]; }
    }
    hoanvi();
    b[k]=0;
    j--;
    }
    }
    main()
    {
    clrscr();
    cout<<"Nhap vao n : ";
    cin>>n;
    for (i=1;i<=n;i++) {a[i]=i;b[i]=0;} /*Muon nhap gi vao mang A[] cung dc*/
    j=0;
    hoanvi();
    }

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

    #include<conio.h>
    #include<stdio.h>
    #include<stdlib.h>
    #define true 1
    #define false 0
    int *B,*A,n;
    void init(int*B,int n)
    {
    for (int i=1;i<=n;i++)
    B[i]=true;
    }
    void process(int A[],int n,int count)
    {
    printf("\nhoan vi thu %5d:",count);
    for(int i=1;i<=n;i++) printf("%d",A[i]);
    }
    void Try(int i,int n,int &count)
    {
    for(int j=1;j<=n;j++)
    if(B[j])
    {
    A[i]=j;
    B[j]=false;
    if(i==n)
    {
    count++;
    process(A,n,count);
    }
    else
    Try(i+1,n,count);
    B[j]=true;
    }
    }
    void main()
    {
    clrscr();
    printf("nhap so phan tu ");
    scanf("%d",&n);
    A=(int*)malloc(n*sizeof(int));
    B=(int*)malloc(n*sizeof(int));
    init(B,n);
    int count =0;
    Try(1,n,count);
    free(A);free(B);
    getch();
    }

    bài hoàn chỉnh

  8. #8
    Ngày gia nhập
    01 2007
    Nơi ở
    TP HCM
    Bài viết
    11

    Theo tôi thì bạn nên kiếm cuốn các bài giảng chuyên đề của thầy Lê Minh Hoàng ở trong 4rum đọc nó để có kiến thức rộng hơn thay vì chỉ kiếm code của nó để trả bài
    Chúc vui.

  9. #9
    Ngày gia nhập
    11 2008
    Nơi ở
    ĐH Công Nghệ - ĐHQG Hà Nội
    Bài viết
    28

    Trích dẫn Nguyên bản được gửi bởi Leon88 Xem bài viết
    Mình cũng xin post 1 đoạn code của mình
    Cảm ơn bạn, đoạn code của bạn hay lắm. Mình đang cần giải thuật đệ quy của bài này.

  10. #10
    Ngày gia nhập
    10 2008
    Bài viết
    2

    Mình nghĩ thuật toán này .Mọi người cho ý kiến
    B1.Ta tính số hoán vị là n!
    Ta dùng hàm đếm hoán vị là count
    Ta đổi chỗ a[0] cho a[1]; in ra ;tăng count
    Ta đổi chỗ a[1] cho a[2]; in ra;tăng count
    ...............

    Ta đổi chỗ a[n-2] cho a[n-1]; in ra;tăng count
    Cho đến khi count=n!-1 thì thôi

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

  1. Trả lời: 6
    Bài viết cuối: 31-07-2013, 07:51 PM
  2. Mỹ phẩm Thu Huyền: Bộ mỹ phẩm trị nám, tàn nhang Bride Korea - call 0906.260.160
    Gửi bởi kimkim8910 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-03-2012, 10:49 PM
  3. phần merge module bị thiếu crystal report phải làm thế nào ?
    Gửi bởi manhluc88 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 1
    Bài viết cuối: 06-01-2011, 01:11 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