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

Đề tài: giúp em bài về liệt kê hoán vị

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

    Wink giúp em bài về liệt kê hoán vị

    em vừa hoc C đang làm bài tập liệt kê các hoá vị của một dãy sô.cơ bản biết về giải thuật nhưng viết code toàn thấy lỗi,các bac viết júp em,nếu bac nào co thời gian thì sưa giúp em code này em đã viết
    HTML Code:
    #include<stdio.h> #define max 10 void nhapso(int a[],int n) { int i; for(i=0;i<n;i++) { printf("\nNhap vao a[%d]=",i); scanf("%d",&a[i]); } } void hoanvi(int a[],int n) { int i,j,tg; for(i=0;i<n-1;i++) { for(j=i;j<n;j++) { if(a[i]>a[j]) { tg=a[i]; a[i]=a[j]; a[j]=tg; } } } for(i=0;i<n;i++) { printf("\t%d",a[i]); } } void hoanvitudien(int *a;int n) { int i,j,k,r,s,tg; j=n-1; while(a[j]>a[j+1]) j=j-1; k=n; while(a[j]>a[k]) k=k-1; { tg=a[j]; a[j]=a[k]; a[k]=tg; } while(s<=r) { { tg=a[r]; a[r]=a[s]; a[s]=tg; } s++;r--; } for(i=0;i<n;i++) { printf("\t%d",a[i]); } } main() { int n,a[max]; printf("\nNhap n:"); scanf("%d",&n); nhapso(a,n); hoanvi(a,n); while(a[0]<a[1]) hoanvitudien(a,n); }

  2. #2
    Ngày gia nhập
    05 2008
    Nơi ở
    Vĩnh Phúc
    Bài viết
    6

    Tớ sửa cho bạn một chút thôi
    Code:
    #include<stdio.h>
    #include<conio.h>
    #define max 10
    void nhapso(int a[],int n)
    {
    	int i;
    for(i=0;i<n;i++)
    {
    	printf("\nNhap vao a[%d]=",i);
    	scanf("%d",&a[i]);
    }
    }
    void hoanvi(int a[],int n)
    {
    	int i,j,tg;
    for(i=0;i<n-1;i++)
    {
    for(j=i;j<n;j++)
    {
    	if(a[i]>a[j])
    	{
    	tg=a[i];
    	a[i]=a[j];
    	a[j]=tg;
    	}
    }
    for (i=0;i<n;i++)
    printf("%d",a[i]);
    }
    for(i=0;i<n;i++)
    {
    	printf("\t%d",a[i]);
    }
    }
    void hoanvitudien(int a[],int n)
    {
    	int i,j,k,r,s,tg;
    j=n-1;
    while(a[j]>a[j+1])
    j=j-1;
    k=n;
    while(a[j]>a[k])
    k=k-1;
    {
    	tg=a[j];
    	a[j]=a[k];
    	a[k]=tg;
    }
    while(s<=r)
    {
    {
    	tg=a[r];
    	a[r]=a[s];
    	a[s]=tg;
    }
    	s++;r--;
    }
    for(i=0;i<n;i++)
    {
    	printf("\t%d",a[i]);
    }
    }
    void main()
    {
    	int n,a[max];
    printf("\nNhap n:");
    scanf("%d",&n);
    nhapso(a,n);
    hoanvi(a,n);
    while(a[0]<a[1])
    hoanvitudien(a,n);
    getch();
    }
    Những chỗ đỏ là tớ sửa và thêm vào. Còn những chỗ xanh thì tớ ko hiểu tại sao s<=r vì chưa có giá trị mà. Có lẽ vì vậy mà nếu chương trình này của bạn nhap >=4 thì khi hoanvitudien se bị loi mat so nhap vao cuối cùng. Tớ ko hiêir bạn viết nên ko giám sửa nữa.
    Bạn thử chạy mà xem.
    C là gì? C là cố. Mà cố quá = quá cố ->

  3. #3
    Ngày gia nhập
    05 2008
    Nơi ở
    HàNội™
    Bài viết
    4

    Code:
    #include<stdio.h>
    #include<conio.h>
    #define max 10
    void nhapso(int *a,int n)
    {
    	int i;
    	for(i=0;i<n;i++)
    	{
    		printf("\nNhap vao a[%d]=",i);
    		scanf("%d",a+i);
    	}
    }
    void khoitaogiatri(int *a,int n)
    {
    	int i,j,tg;
    	for(i=0;i<n-1;i++)
    		for(j=i;j<n;j++)
    		{
    			if(a[i]>a[j])
    			{
    			tg=a[i];
    			a[i]=a[j];
    			a[j]=tg;
    			}
           	        }
    
    for (i=0;i<n;i++)
    printf("\t%d",a[i]);
    printf("\n");
    
    
    }
    
    void hoanvitudien(int a[max],int n)
    {
    	int i,j,k,r,s,tg;
    do
    {
    	j=n-2;
    	while((j>0)&&(a[j]>a[j+1]))
    		j=j-1;
            if(j>0)
            {
    		k=n-1;
    		while(a[j]>a[k])
    			k=k-1;
    	
    		tg=a[j];
    		a[j]=a[k];
    		a[k]=tg;
    	
    		s=j+1;r=n-1;
    		while(s<r)
    
    		{
    			tg=a[r];
    			a[r]=a[s];
    			a[s]=tg;
    		        s++;r--;
    		}
    		for(i=0;i<n;i++)
    		{
    			printf("\t%d",a[i]);
    		}
            	printf("\n");
    	}
    }
    while(j!=0);
    }
    void main()
    {
    	int n,a[max];
    	printf("\nNhap n:");
    	scanf("%d",&n);
    	nhapso(a,n);
    	khoitaogiatri(a,n);
    	hoanvitudien(a,n);
    getch();
    }
    Code lại cho bạn này.Bạn xem lại thuật toán và cách trình bày code cho dễ nhìn nhé

  4. #4
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Xem lại tài liệu giải thuật của tác giả Lê Minh Hoàng.
    Code theo C++, bài viết sinh liệt kê n phần tử, cậu xem thêm và điều chỉnh cho phù hợp với bài của bạn nếu được.
    C++ Code:
    1. #include<iostream.h>
    2. #include<conio.h>
    3. #include<stdlib.h>
    4. #include<fstream.h>
    5. #include<stdio.h>
    6.     int A[13],n,k,i,a,b;
    7. void hoanVi(int x,int y){
    8.     int temp=A[a];
    9.     A[a]=A[b];
    10.     A[b]=temp;
    11. };
    12. void main(){
    13.     clrscr();
    14.     ifstream f("C:\\PERMUTE.INP",ios::in);
    15.     if (f.bad()){
    16.         cout<<"Khong mo file duoc!";
    17.         getch();
    18.         exit(1);
    19.     };
    20.     f.seekg(0,ios::beg);
    21.     f>>n;
    22.     f.close();
    23.     for (int i=1;i<=n;i++)  A[i]=i;
    24.     ofstream f2("C:\\PERMUTE.OUT",ios::out);
    25.     do{
    26.         for(int i=1;i<=n;i++) f2<<A[i]<<" ";
    27.         f2<<endl;
    28.         i=n-1;
    29.         while(i>0 && A[i]>A[i+1])i--;
    30.         if (i>0){
    31.             k=n;
    32.             while (A[k]<A[i]) k--;
    33.             hoanVi(k,i);
    34.             a=i+1;b=n;
    35.             while (a<b){
    36.                 hoanVi(a,b);
    37.                 a++;
    38.                 b--;
    39.             };
    40.         };
    41.     }while(i!=0);
    42.     f2.close();        
    43. };
    Không biết ghi gì luôn ...

  5. #5
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    446

    Mình xin góp 1 code khác thực hiện thuật toán liệt kê các hoán vị của một tập hợp theo một trình tự Gray code tên là Johnson-Steinhaus-Trotter. Một trình tự Gray code là trình tự mà hoán vị sau được tính từ hoán vị trước bằng cách hoán đổi đúng một cặp phần tử. Và trong thuật toán này, cặp ấy luôn là 2 phần tử đứng cạnh nhau trong mảng.

    Do tính chất tối ưu về số phép tính và truy nhập bộ nhớ RAM mà thuật toán này có thể dùng trong các bài toán liệt kê hoán vị trên tập hợp cỡ lớn.


    Ví dụ

    Code:
    So phan tu can hoan vi (toi da 9):5
    1 2 3 4 5
    1 2 3 5 4
    1 2 5 3 4
    1 5 2 3 4
    5 1 2 3 4
    5 1 2 4 3
    1 5 2 4 3
    1 2 5 4 3
    1 2 4 5 3
    1 2 4 3 5
    1 4 2 3 5
    1 4 2 5 3
    1 4 5 2 3
    1 5 4 2 3
    5 1 4 2 3
    5 4 1 2 3
    4 5 1 2 3
    4 1 5 2 3
    4 1 2 5 3
    4 1 2 3 5
    4 1 3 2 5
    4 1 3 5 2
    4 1 5 3 2
    4 5 1 3 2
    5 4 1 3 2
    5 1 4 3 2
    1 5 4 3 2
    1 4 5 3 2
    1 4 3 5 2
    1 4 3 2 5
    1 3 4 2 5
    1 3 4 5 2
    1 3 5 4 2
    1 5 3 4 2
    5 1 3 4 2
    5 1 3 2 4
    1 5 3 2 4
    1 3 5 2 4
    1 3 2 5 4
    1 3 2 4 5
    3 1 2 4 5
    3 1 2 5 4
    3 1 5 2 4
    3 5 1 2 4
    5 3 1 2 4
    5 3 1 4 2
    3 5 1 4 2
    3 1 5 4 2
    3 1 4 5 2
    3 1 4 2 5
    3 4 1 2 5
    3 4 1 5 2
    3 4 5 1 2
    3 5 4 1 2
    5 3 4 1 2
    5 4 3 1 2
    4 5 3 1 2
    4 3 5 1 2
    4 3 1 5 2
    4 3 1 2 5
    4 3 2 1 5
    4 3 2 5 1
    4 3 5 2 1
    4 5 3 2 1
    5 4 3 2 1
    5 3 4 2 1
    3 5 4 2 1
    3 4 5 2 1
    3 4 2 5 1
    3 4 2 1 5
    3 2 4 1 5
    3 2 4 5 1
    3 2 5 4 1
    3 5 2 4 1
    5 3 2 4 1
    5 3 2 1 4
    3 5 2 1 4
    3 2 5 1 4
    3 2 1 5 4
    3 2 1 4 5
    2 3 1 4 5
    2 3 1 5 4
    2 3 5 1 4
    2 5 3 1 4
    5 2 3 1 4
    5 2 3 4 1
    2 5 3 4 1
    2 3 5 4 1
    2 3 4 5 1
    2 3 4 1 5
    2 4 3 1 5
    2 4 3 5 1
    2 4 5 3 1
    2 5 4 3 1
    5 2 4 3 1
    5 4 2 3 1
    4 5 2 3 1
    4 2 5 3 1
    4 2 3 5 1
    4 2 3 1 5
    4 2 1 3 5
    4 2 1 5 3
    4 2 5 1 3
    4 5 2 1 3
    5 4 2 1 3
    5 2 4 1 3
    2 5 4 1 3
    2 4 5 1 3
    2 4 1 5 3
    2 4 1 3 5
    2 1 4 3 5
    2 1 4 5 3
    2 1 5 4 3
    2 5 1 4 3
    5 2 1 4 3
    5 2 1 3 4
    2 5 1 3 4
    2 1 5 3 4
    2 1 3 5 4
    2 1 3 4 5
    Thuật toán

    C Code:
    1. #include<stdio.h>
    2.  
    3. void recursiveJST(int L, int n, int p[], int pi[], int d[],...)
    4. {
    5.     // Systematically generates all permutations of elements of an array
    6.     // and do some action (eg. count, dump,...) on them
    7.     // using Johnson-Steinhaus-Trotter algorithm.
    8.     //
    9.     // Usage and hacking guide:
    10.     // 1. Create arrays p[],pi[],d[] of size = L elements (bytes)
    11.     // 2. Initialize p[]= pi[] = {0,1,2,...,L-1}, d[] = {-1,-1,...,-1}
    12.     // 3. Call recursiveJST(L, 1, p, pi, d,...) to permute p[1..L-1] leaving p[0] fixed (= 0), or
    13.     //    call recursiveJST(L, 0, p, pi, d,...) to permute p[0..L-1],
    14.     //    Read all "HACKING:" comments and change the source code accordingly first!!!
    15.     // 4. Declare and use more param's to identify action performer and/or to pass action-specific info's
    16.     int c,k,i,z;
    17.     if (n < L) // "<" to permute p[0..L-1] and also p[1..L-1]
    18.     {
    19.         recursiveJST(L, n+1, p, pi, d);
    20.         for (c=1; c<n; c++) // HACKING: "c=0" to permute p[0..L-1], "c=1" to permute p[1..L-1]
    21.         {
    22.             // swap p[k], p[k+i] where k = pi[n], i = either +1 or -1
    23.             k = pi[n];
    24.             i = d[n];
    25.             z = p[k+i];
    26.             p[k] = z;
    27.             p[k+i] = n;
    28.             pi[z] = k;
    29.             pi[n] = k+i;
    30.             recursiveJST(L, n+1, p, pi, d);
    31.         }
    32.         d[n] = -d[n];
    33.     }
    34.     else // recursion terminated, do the action
    35.     {
    36.         for(c=1; c<n; c++)
    37.         {
    38.             printf("%d ",p[c]);
    39.         }
    40.         printf("\n");
    41.     }
    42. }
    43.  
    44. int main()
    45. {
    46.     #define N 10
    47.     int p[N] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    48.     int pi[N]= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    49.     int d[N] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
    50.     int L;
    51.     printf("So phan tu can hoan vi (toi da 9):");
    52.     scanf("%d",&L);
    53.     L++;
    54.     recursiveJST(L,1,p,pi,d);
    55.     return 0;
    56. }
    Đã được chỉnh sửa lần cuối bởi Ada : 07-06-2008 lúc 02:24 AM.

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

    Mặc định giúp em bài về liệt kê hoán vị

    Thanks moi nguoi nhieu nha.co mot so cho em chua hieu hom sau em se hoi hom nay xem da bong da keke

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

    Tien day cac bac giai thich ho em cai chuong trinh de quy nay no lam viec tung buoc nhu the nao nha,em vua hoc den cau truc thoi cai chuong trinh bac Ada viet em van con chua hiu >>ga ga.bac ma tien giai thick ho em
    HTML Code:
    Liet ke tat cac cac hoan vi cua n phan tu */ #include <stdio.h> #define MAX 10 int mang[MAX], n; void swap (int *x, int *y) { int tmp; tmp = *x; *x = *y; *y = tmp; } void hoanvi(int k) { int j,dem=0; if (k==1) { printf("\n"); for (j=0; j<n; j++) { printf("%d ", mang[j]); dem=dem+1; } } else for (j=k-1; j>=0; j--) { swap(&mang[k-1], &mang[j]); hoanvi(k-1); swap(&mang[j], &mang[k-1]); } printf("\nso hoann vi la %d",dem); } main() { int i; printf("\nCho biet so phan tu (N < 10) : "); scanf("%d", &n); for (i=0; i<n; i++) mang[i] = i; hoanvi(n); }
    Đã được chỉnh sửa lần cuối bởi nguyenngochoang89 : 08-06-2008 lúc 01:35 AM.

  8. #8
    No Avatar
    PeDieu Khách

    Code:
    void hoanvi(int k)
    
    {
    
      int j,dem=0;
    
    
    
      if (k==1)
    
      {
    
        printf("\n");
    
        for (j=0; j<n; j++)
    
          {
    	printf("%d ", mang[j]);
    	dem=dem+1;
    	}
    	 }	
    
      else
    
        for (j=k-1; j>=0; j--)
    
        {
    
          swap(&mang[k-1], &mang[j]);
    
          hoanvi(k-1);
    
          swap(&mang[j], &mang[k-1]);
    
        }
    
    	printf("\nso hoann vi la %d",dem);
    
    }
    Cài dzòng màu đỏ ở trên để như vậy hok được òi. Dùng đệ qui nghĩa là gọi lại hàm này nhìu lần, mổi lần gọi lại in nó ra? hơn nữa mổi lần gọi lại gán giá trị biến dem = 0; như vậy thì đếm cái jì zậy anh zai?

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

    dung roi
    thi em nghi la no khong chay qua cai lenh nay no chi chay den cai lenh hoanvi(k-1)
    xong no quay lai len ham hoan vi ma ko chay qua cai lenh nay nen moi them vao ma ko dc
    the moi can bro chi xem no chay the nao chu.thanks nhiu hen`
    giờ say mê bên ai em đổ lỗi anh vô tình

  10. #10
    Ngày gia nhập
    05 2008
    Nơi ở
    HàNội™
    Bài viết
    4

    Trích dẫn Nguyên bản được gửi bởi nguyenngochoang89 Xem bài viết
    dung roi
    thi em nghi la no khong chay qua cai lenh nay no chi chay den cai lenh hoanvi(k-1)
    xong no quay lai len ham hoan vi ma ko chay qua cai lenh nay nen moi them vao ma ko dc
    the moi can bro chi xem no chay the nao chu.thanks nhiu hen`
    Phần này mình cũng hiểu mơ hồ lắm.Có ai giải thix dùm

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

  1. Sự cố Nhờ mod chuyển giúp bài "Sắp xếp số thứ tự ngay trong bảng của 1 database?" từ MySQL sang MSSQL giúp!
    Gửi bởi hu-xeko trong diễn đàn Ý kiến, đề xuất và khiếu nại
    Trả lời: 1
    Bài viết cuối: 12-03-2012, 07:48 PM
  2. Mới nhập môn khó quá , cần trợ giúp [Vấn đề của bạn cần muốn giúp là gì ?]
    Gửi bởi cuingo212 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 5
    Bài viết cuối: 22-10-2011, 08:43 AM
  3. Chương trình giúp một học sinh cấp 1 học phép nhân, xử lý hàm rand, giúp mình với?
    Gửi bởi chankx trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 12-05-2009, 08:52 PM
  4. Code giúp add một key vào registry, ai giúp em?
    Gửi bởi olavien trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 12-12-2007, 08:45 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