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

Đề tài: bài toán về hoán vị theo kiểu hàng đợi

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

    Wink bài toán về hoán vị theo kiểu hàng đợi

    Cho các toa tàu đánh số từ 1, 2, .., n ở đường ray bên phải cần được hoán vị và chuyển sang đường ray bên trái. Mỗi một toa có thể chuyển thẳng sang đường ray bên trái, hay nó có thể chuyển sang đuờng bên cạnh (có vai trò như hàng đợi) và sau này sẽ được chuyển sang đường ray bên trái.




    Một cách tổng quát, với n nhập từ bàn phím những hoán vị nào của dãy 1, 2, .., n có thể nhận được bằng cách dùng hàng đợi như trên, những hoán vị nào là k thể


    theo e nghĩ thì thuật toán là 1 hoán vị là k thể khi nó có ít nhất 3 phần tử(ở bất kì vị trí nào) được xếp theo thứ tự từ lớn đến bé
    VD nhu: n=3 >>> hoán vị không thể là 321
    n=4 >>> hoán vị không thể là 4321, 4213, 4312, 3214, 3421, 1432, 3421.....

    các bác thấy thuattj toán thế có đúng k???

    bác nào viết dùm e đoạn code của hàm lochoanvi cái
    C++ Code:
    1. #include <iostream.h>
    2. #include <conio.h>
    3. int a[100],b[100],c[100],d=0,n;
    4.  
    5. void lochoanvi()
    6. {
    7.  
    8. }
    9. void hoanvi(int i)
    10. {
    11. if (i==n)
    12. {
    13. cout << " Hoan vi " << ++d << " : ";
    14. for (int j=0;j<n;j++)
    15. cout << c[j] << " ";
    16. cout << endl;
    17. }
    18. else
    19. for (int j=0;j<n;j++)
    20. if (b[j]==0)
    21. {
    22. b[j]=1;
    23. c[i]=a[j];
    24. hoanvi(i+1);
    25. b[j]=0;
    26. }
    27. }
    28.  
    29. int main()
    30. {
    31. cout << "Nhap n : ";
    32. cin >> n;
    33. for (int i=0;i<n;i++)
    34. {
    35. a[i]=i+1; b[i]=0;
    36. }
    37. hoanvi(0);
    38. return 0;
    39. }

    Chú ý bỏ code vào thẻ code !
    Đã được chỉnh sửa lần cuối bởi rox_rook : 21-11-2008 lúc 07:14 PM.

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

    sao chẳn có bác nào giúp e thế??? hjx,hjx

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

    các bác giúp dùm e cái!!

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

    Hôm bữa huynh đài post sai, đệ move bài của huynh mà huynh la làng giữ lắm mà ! Còn lần nữa vừa post sai vừa la làng là tui cho cậu lên dĩa nha cậu !
    C++ Code:
    1. #include <iostream>
    2. #include <algorithm>
    3.  
    4. const int SIZE = 5;
    5.  
    6. int G[ SIZE ] = {
    7.     1, 2, 3, 4, 5
    8. };
    9.  
    10. void print( const int* G, const int& SIZE ) {
    11.     for( int o = 0; o < SIZE; ++o ) {
    12.         std::cout << G[ o ] << " ";
    13.     }
    14.     std::cout << std::endl;
    15. }
    16.  
    17. void shift_k_pos( int* G, const int& SIZE, int k_pos ) {
    18.     int* tmp = new int[ SIZE ];
    19.     int pos;
    20.     for( int o = 0; o < SIZE; ++o ) {
    21.         pos = ( o + k_pos + SIZE ) % SIZE;
    22.         tmp[ o ] = G[ pos ];
    23.     }
    24.     std::copy( tmp, tmp + SIZE, G );
    25.     delete[] tmp;
    26. }
    27.  
    28. int main()
    29. {
    30.     shift_k_pos( G, SIZE, 3 );
    31.     print( G, SIZE );
    32.  
    33.     return 0;
    34. }

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

    bạn đã test thử chưa dzay???Nhìn code viết mà chăng hỉu jif lun

    bài này e đã chạy thử bác nào bit tìm độ phức tạp của thuật toán này k?? chỉ mình với


    C++ Code:
    1. #include "iostream.h"
    2. #include "conio.h"
    3. #include "stdio.h"
    4. int a[100],b[100],c[100];
    5. int n,dem=0;
    6. FILE *f1,*f2;
    7. int kiemtra(int c[],int m)
    8. { int i,j,k;
    9.   if (n==2) return 1;
    10.   else
    11.   {  for (i=1;i<=n-2;i++)
    12.        for (j=i+1;j<=n-1;j++)
    13.           for (k=j+1;k<=n;k++)
    14.             if (c[i]>c[j] && c[j]>c[k]) return 0;
    15.   }
    16.      return 1;
    17. }
    18. void thietlap()
    19. {int i;
    20.  for (i=1;i<=n;i++)
    21.    {
    22.       a[i]=i;
    23.       b[i]=0;
    24.       c[i]=0;
    25.    }
    26. }
    27. void inmang(int c[],int m)
    28. { int i;
    29.   for (i=1;i<=m;i++)
    30.   { //printf("%5d",c[i]);
    31.     fprintf(f2,"%3d",c[i]);
    32.   }
    33.     fprintf(f2,"%2c",'\n');
    34.  
    35.   //  cout<<endl;
    36.  
    37. }
    38. void hoanvi(int i)
    39. { int j;
    40.     if (i==n+1)
    41.     { if (kiemtra(c,n)==1)
    42.         {  inmang(c,n);
    43.             dem++;
    44.         }
    45.     }
    46.     else
    47.       for (j=1;j<=n;j++)
    48.       if (b[j]==0)
    49.      {
    50.            c[i]=a[j];
    51.            b[j]=1;
    52.            hoanvi(i+1);
    53.            b[j]=0;        
    54.      }
    55. }
    56. int main()
    57. {
    58.  /* cout<<"Nhap n: ";
    59.   cin>>n; */
    60.  
    61.   f1= fopen("in.inp","r");
    62.   fscanf(f1,"%d",&n);
    63.   fclose(f1);
    64.  
    65.   f2= fopen("out.out","w");
    66.   fprintf(f2,"Nhung hoan vi co the xay ra :\n\n");
    67.   thietlap();
    68.   hoanvi(1);
    69.   if (n<=0) dem=0;
    70.   fprintf(f2,"\nCo tat ca %d ket qua !\n",dem);
    71.   fclose(f2);
    72.  // getch();
    73.   return 0;
    74. }

  6. #6
    Ngày gia nhập
    04 2013
    Bài viết
    8

    Mặc định thắc mắc về thuật toán

    với n=3 thì hoán vị không thỏa mãn là hoán vị 312 chứ không phải 321

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

  1. Tạo report báo cáo theo tuần, theo tháng như thế nào???
    Gửi bởi giadinhvnvn trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 5
    Bài viết cuối: 06-03-2013, 02:37 PM
  2. Làm field theo kiểu theo kiểu trộn văn bản trong templateword
    Gửi bởi bimtocsieuquay trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 26-09-2012, 10:39 AM
  3. Lý thuyết giải thuật Các cách biểu diễn cây nhị phân theo theo phương pháp giản đồ và dấu ngoặc lồng nhau?
    Gửi bởi hoangminh29491 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 05-06-2012, 05:04 PM
  4. Sắp xếp tăng dần theo dường theo dường chéo phụ của ma trận như thế nào các bạn.
    Gửi bởi phanvanngoc trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 1
    Bài viết cuối: 04-05-2011, 11:08 AM
  5. đọc file excel theo tên cột hoặc các cột ko theo thứ tự ???
    Gửi bởi xinbat007 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 14-05-2010, 10:09 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