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

Đề tài: Vấn đề về thuật toán sinh kế tiếp

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

    Talking Vấn đề về thuật toán sinh kế tiếp

    trên diễn đàn có một bài về thuật toán sinh kế tiếp nhưng chỉ sử dụng đối với dãy bit,nhưng bây giờ mình có thể dựa trên ý tưởng đó để làm một bài toán sau: giả sử một dãy số khoảng 5 phần tử 1 2 3 4 5,bây giờ làm sao để in ra tất cả các trường hợp của chuỗi này với diều kiện:
    +không có bất cứ phần tử nào của mảng trùng nhau
    +các phần tử của mảng phải nhỏ hơn k(giả sử cho k=9)

    (Thật ra mình đưa ra vấn đề này là để giải quết bài toán đề thi olympic, hình như bài này nó nằm trong topic này thì phải)

    Code:
    #include <stdio.h>
    #include <conio.h>
     int i,n,ok=1,count=0;
     char *s;
    void init (void)
     {
       printf("\n Nhap vao n:");scanf("%d",&n);
       for (i=1;i<=n;i++)
        s[i]='0';
     }
    void result(void)
     {
       printf("\nKet qua buoc thu %d: ",++count);
       for (i=1;i<=n;i++)
        printf("%3c",s[i]);
     }
    void next_bit_string (void)
     {
       i=n;
        while (s[i]=='1') {s[i]='0';i--;}
        if (i==0) ok=0;
        s[i]='1';
     }
    
    void main ()
    {
     clrscr();
     init();
     while(ok)
       {
          result();
          printf("\n");
          next_bit_string();
       }
     getch();
    }

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

    code ở trên chỉ là code của thuật toán sinh kế tiếp, bác nào biét hướng giải post lên anh em xem nha!!thanks

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

    Cái này hình như post sang post giải thuật mới đúng chứ nhỉ ^^ ! Mình chưa hiểu ý bạn lắm về cái liệt kê ra đó. Hoán vị có được tính là 1 liệt kê không nhỉ ?
    Mình có làm vài bài dạng này, ý tưởng thì có lẽ cuối tuần mình suy nghĩ rồi nói với bạn sau nhé. Mình có vài bài tương tự, bạn coi thử xem có giúp được gì không ! Thân !

    PHP Code:
    /* 1 dãy x[1..n] goi là 1 hoán vi hoàn toàn cua tap {1,2...n} néu nó là 1 hoán vi thoa mãn x[i] != i V- i : 1 <= i <= n. Hay viet chuong trinh liet ke tat ca cac hoan vi hoan toan cua tap tren ( n vao tu ban phim ).*/
    #include <iostream>
    #include <iomanip>
    #include <conio.h>
    #include <stdio.h>

    using std::cout;
    using std::cin;
    using std::endl;
    using std::setw;

    const 
    int size 100;

    int A[size], SUB[size];
    int n;

    void swap int &rint &c)
    {
               
    int temp r;
               
    c;
               
    temp;
    }
    void SORT ()
    {
              for ( 
    int r 0nr++ )
              {
                      for ( 
    int c 0nc++ )
                      {
                              if ( 
    A[r] < A[c] )
                              {
                                      
    swapA[r], A[c] );
                              }
                      }
              }
    }
    bool CHECK()
    {
           
            for ( 
    int r 0nr++ )
            {
                    if ( 
    A[r] == SUB[r] )
                    {
                            return 
    false;         
                    }
                           
            }
    }
    int main()
    {
          
    int i,k,a,b,x;
          
    cout << " Enter the number array's elements need to be permutated: ";  cin  >> n;
          
          
    0;
          do
          {
                  
    cout << "Enter the element: "cin >> A[x];
                  
    x++;
          }while ( 
    );    
         
          
          
    SORT();
          
          for ( 
    0ni++ ) cout << A[i] << setw(5);
          for ( 
    0ni++ ) SUB[i] = A[i];

          
    cout << "\n\n";
          
    cout << "-------Permutation Algorithm--------------" << "\n\n";
          
    /* PERMUATION ALGORITHM */
          
    do
          {
                  if ( 
    CHECK() != false )                
                  {
                          for ( 
    0ni++ )  
                                  
    cout << A[i] << ","  << setw(3);
                  }
                  
    cout << "\n\n"getch();
                  
                  
    2;
                  while ( 
    >= && ( A[i] > A[i+1] ) ) /* Check whether it is a final configuration ( or not ) ?*/
                          
    i--;
                  
                  
                  if ( 
    >= )
                  {
                          
    ;
                          while ( 
    A[k] < A[i] )
                                  
    k--;
                          
                          
    swap A[k], A[i] );
                          
    1;
                          
    1;
                                        while ( 
    )
                                        {
                                                
    swap A[a], A[b] );
                                                
    a++;
                                                
    b--;
                                        }
                  }              
                          
          }
          while ( 
    >= );
          
          return 
    0;
          
    system ("PAUSE");

    PHP Code:
    /*Liet ke các tap con cua tap S gòm n so nguyen { S[1], S[2],...S[n] } nhap vào 
    tù bàn phím, nhung chi liet ke cac tap con co max - min <=T ( T cho truoc ).*/

    #include <iostream>
    #include <iomanip>
    //#include <conio.h>
    #include <stdio.h>


    using std::cout;
    using std::cin;
    using std::endl;
    using std::setw;


    const 
    int size 100;
    int A[size], TEMP[size];
    int nL;

    void SORT()
    {
            for ( 
    int i 0ni++ )
            {   
                    for ( 
    int j 1nj++ )
                    {
                            if ( 
    A[j] > A[i] )
                            {
                                    
    int temp A[i];
                                    
    A[i] = A[j];
                                    
    A[j] = temp;
                            }
                     }
            }
    }
    bool LIMIT_CHECK()
    {
            
    int max;
            
    int min;

            for ( 
    int i 1ni++ )
            {
                    
    min TEMP[0];
                    
    max TEMP[0];
                    if ( 
    min TEMP[i] ) min TEMP[i];
                    if ( 
    max TEMP[i] ) max TEMP[i];
            }    
          
            if ( 
    max min <= ) return true;
            else                  return 
    false;
    }        

    int main()
    {
            
    cout << "How many element would you like: "cin >> n;
            
            
    int x 0;
            do 
            {
                    
    cout << "Enter the element " << << " : ";
                    
    cin >> A[x];
                    
    x++;
                    
    cout << endl;
            } while ( 
    );
           
            
    cout << "Enter the limitation: "cin >> L;
                    

                
          for ( 
    int x 0nx++ ) TEMP[x] = 0;
          
          
    int POS;
          do 
          {
                  
    SORT();
                  if ( 
    LIMIT_CHECK() )  
                  {
                            for ( 
    int x 0nx++ )
                            {
                                        if ( 
    TEMP[x] != 
                                                
    cout << TEMP[x] << setw(4);
                            }
                  }
                  
    cout << endlcin.get();
                  
                          
                          
    POS n-1;
                          while ( 
    POS >= && TEMP[POS] != 0  POS--;
                                  
                          if ( 
    POS >= )
                          {
                                  
    TEMP[POS] = A[POS] ;
                                          for ( 
    int j POS 1nj++ )
                                                  
    TEMP[j] = 0;
                                          
                          }
          }
          while ( 
    POS >= );
            
          
          return 
    0;
          
    system ("PAUSE");

    Đề bài mình có ghi trên phần code đó.

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

    bạn à, mình quên post cái dụ: các hoán vị không được xem là một liệt kê, ví dụ ta có 1 2 3 4 5,sau đó bạn khong duoc sinh ra tiếp la 1 2 3 5 4, hay 1 2 4 3 5,

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

    Bạn coi lại đoạn code thứ nhất nhé, nó đúng là cái đề bài của bạn đó.
    Thật ra mình đưa ra vấn đề này là để giải quết bài toán đề thi olympic
    Bài này chỉ là liệt kê tổ hợp thông thường thôi mà?
    Bạn có thể tham khảo ebook của tác giả Lê Minh Hoàn có trong kho ebook "cái tài liệu cần để tự học giải thuật" . Sách viết rất hay và rõ ràng về những bài liệt kê dạng này.
    Thân !

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

  1. MacBook Pro 2012 - Đẳng cấp trong từng chi tiết - Giá bất ngờ cho Học Sinh - Sinh Viên!!!
    Gửi bởi nvhuu.nmslaptop trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 20
    Bài viết cuối: 27-05-2013, 12:48 PM
  2. Thuật toán C++ Thuật toán sinh tổng con kế tiếp trong C++ như thế nào?
    Gửi bởi ducvietphan trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 21-10-2012, 08:13 PM
  3. Trả lời: 6
    Bài viết cuối: 31-07-2012, 09:12 PM
  4. Thuật toán sinh kế tiếp!
    Gửi bởi meohoang8x trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 17-10-2007, 07:44 PM
  5. Nhờ chi dẫn hộ: Thuật toán sinh kế tiếp
    Gửi bởi meohoang8x trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 9
    Bài viết cuối: 02-07-2007, 07:58 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