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

Đề tài: Thuật toán hoán vị n số nguyên

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

    Mặc định Thuật toán hoán vị n số nguyên

    Nói thật là không biết thuật toán này có được gọi là khó hay không mà sao không thể giải nổi, kể cả copy bài giải của người khác vào xem mà cũng không hiểu

    Mọi người xem và trả lời cho boy mấy câu hỏi có nêu trong bài luôn nghe, thanks mọi người nhiều

    Code:
    #include <iomanip.h>
    #include <conio.h>
    #include <stdio.h>
    #include <iostream.h>
    #include <stdlib.h>
    
    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 << " Go vao day so cac phan tu can hoan vi: ";  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 << "#######################NTA#######################" << "\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--;                   // ở đây có i-- với tác dụng gì
                          cout<<i<<endl;
    
    
    	     // if ( i >= 0 )    //if o day khong can` dung ko
    	      //{
    		      k = n - 1 ;
    		      while ( A[k] < A[i] )      //o day la so sanh a[n-2] va a[n-1] ?
    			      k--;   //neu k-- thi se luon chay vong while vi A[i-1] < A[i] la dieu tat nhien
    
    		      swap ( A[k], A[i] );             // o tren khai bao ham la swap(int &,int&) ma sao o duoi nay
     		      				       // co the dua vao ham` la cac mang?	
    		      a = i + 1;                            //2 dong nay` co tac dung gi`
    		      b = n - 1;
    				    while ( a < b )                  //tai sao van tiep tuc chay vong while
    				    {
    					    swap ( A[a], A[b] );     //chay ham trong while de lam gi`
    					    a++;                      // vi sao phai la a++ va b--
    					    b--;
    				    }
    	    //  }
    
          }
          while ( i >= 0 );
          getch();
    }

  2. #2
    Ngày gia nhập
    02 2008
    Bài viết
    1,009

    Nói thật là không biết thuật toán này có được gọi là khó hay không mà sao không thể giải nổi, kể cả copy bài giải của người khác vào xem mà cũng không hiểu

    Mọi người xem và trả lời cho boy mấy câu hỏi có nêu trong bài luôn nghe, thanks mọi người nhiều
    nếu cậu năm nay lên năm thứ hai thì chắc đã học môn toán rời rạc rồi,hãy đọc lại lý thuyết toán rời rạc đi,vấn đề này trong diễn đàn thì rất nhiều mà trong sách vở cũng rất lắm

    cậu có thể đọc lý thuyết của trường mình:
    2.4.1. Sinh các hoán vị:
    Có nhiều thuật toán đã được phát triển để sinh ra n! hoán vị của tập {1,2,...,n}. Ta sẽ mô tả một trong các phương pháp đó, phương pháp liệt kê các hoán vị của tập {1,2,...,n} theo thứ tự từ điển. Khi đó, hoán vị a1a2...an được gọi là đi trước hoán vị b1b2...bn nếu tồn tại k (1  k  n), a1 = b1, a2 = b2,..., ak-1 = bk-1 và ak < bk.
    Thuật toán sinh các hoán vị của tập {1,2,...,n} dựa trên thủ tục xây dựng hoán vị kế tiếp, theo thứ tự từ điển, từ hoán vị cho trước a1 a2 ...an. Đầu tiên nếu an-1 < an thì rõ ràng đổi chỗ an-1 và an cho nhau thì sẽ nhận được hoán vị mới đi liền sau hoán vị đã cho. Nếu tồn tại các số nguyên aj và aj+1 sao cho aj < aj+1 và aj+1 > aj+2 > ... > an, tức là tìm cặp số nguyên liền kề đầu tiên tính từ bên phải sang bên trái của hoán vị mà số đầu nhỏ hơn số sau. Sau đó, để nhận được hoán vị liền sau ta đặt vào vị trí thứ j số nguyên nhỏ nhất trong các số lớn hơn aj của tập aj+1, aj+2, ..., an, rồi liệt kê theo thứ tự tăng dần của các số còn lại của aj, aj+1, aj+2, ..., an vào các vị trí j+1, ..., n. Dễ thấy không có hoán vị nào đi sau hoán vị xuất phát và đi trước hoán vị vừa tạo ra.
    Code:
    Thí dụ 11:
    Tìm hoán vị liền sau theo thứ tự từ điển của hoán vị 4736521.
    Cặp số nguyên đầu tiên tính từ phải qua trái có số trước nhỏ hơn số sau là a3 = 3 và a4 = 6. Số nhỏ nhất trong các số bên phải của số 3 mà lại lớn hơn 3 là số 5. Đặt số 5 vào vị trí thứ 3. Sau đó đặt các số 3, 6, 1, 2 theo thứ tự tăng dần vào bốn vị trí còn lại. Hoán vị liền sau hoán vị đã cho là 4751236.
    procedure Hoán vị liền sau (a1, a2, ..., an) (hoán vị của {1,2,...,n} khác (n, n1, ..., 2, 1))
    j := n  1
    while aj > aj+1
    j := j  1 {j là chỉ số lớn nhất mà aj < aj+1}
    k := n
    while aj > ak
    k := k - 1 {ak là số nguyên nhỏ nhất trong các số lớn hơn aj và bên phải aj}
    đổi chỗ (aj, ak)
    r := n
    s := j + 1
    while r > s
    đổi chỗ (ar, as)
    r := r - 1 ; s := s + 1
    {Điều này sẽ xếp phần đuôi của hoán vị ở sau vị trí thứ j theo thứ tự tăng dần.}

  3. #3
    Ngày gia nhập
    10 2007
    Bài viết
    43

    @coder_gate: thank bạn nhiều
    tuy bài trả lời của bạn rất chi tiết nhưng thực sự mình tệ mấy khoản này lắm
    Thực ra học lập trình chỉ là để biết sơ sơ vừa đủ ra trường thôi
    mình học mạng nên sẽ ưu tiên cho mạng hơn, ko tìm hiểu sâu về lập trình
    Bạn nếu có thể hãy giúp mình giải đáp những thắc mắc đó nghe
    mình cảm ơn nhiều lắm, mình học theo kiểu này chứ kiểu tư duy cao thì mình chịu ^^

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

    tuy bài trả lời của bạn rất chi tiết nhưng thực sự mình tệ mấy khoản này lắm
    Thực ra học lập trình chỉ là để biết sơ sơ vừa đủ ra trường thôi
    mình học mạng nên sẽ ưu tiên cho mạng hơn, ko tìm hiểu sâu về lập trình
    Bạn nếu có thể hãy giúp mình giải đáp những thắc mắc đó nghe
    mình cảm ơn nhiều lắm, mình học theo kiểu này chứ kiểu tư duy cao thì mình chịu ^^
    Bạn học chủ yếu về mạng, rất tốt. Nhưng lập trình sẽ giúp bạn tăng khả năng tư duy, hiểu rõ về hệ cách hoạt động của máy tính và phần mềm. Một số giải thuật của lập trình cũng rất hữu dụng trong lĩnh vực mạng.
    Mình viết vậy để bạn thấy hữu ích và yêu lập trình hơn. Chúc bạn học tốt!

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

  1. Thuật toán tìm số nguyên tố?
    Gửi bởi comeonbaby trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 92
    Bài viết cuối: 22-03-2017, 08:39 PM
  2. Bài tập C giải thuật nhập vào số nguyên n in ra n số nguyên tố đầu tiên?
    Gửi bởi LTC trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 48
    Bài viết cuối: 25-04-2013, 07:40 PM
  3. thuật toán số nguyên tố????
    Gửi bởi anhtbok trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 9
    Bài viết cuối: 30-03-2012, 10:33 AM
  4. Tìm và in ra các số nguyên tố thỏa mãn đề bài bằng C, thuật toán của mình sai ở đâu?
    Gửi bởi piavg trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 8
    Bài viết cuối: 16-11-2011, 04:03 PM
  5. Lập trình C xin code cài đặt thuật toán sàng nguyên tố để liệt kê các số nguyên tố 2->480000
    Gửi bởi ngocdung_088 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 23
    Bài viết cuối: 06-12-2010, 11:53 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