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

Đề tài: Hoán vị | In hoán vị của n. Các bác giúp em!

  1. #1
    No Avatar
    fptcomputer Khách

    Mặc định Hoán vị | In hoán vị của n. Các bác giúp em!

    Em mới học C nên chưa sành lắm, mong anh em chỉ bảo bài toán như thế này:
    nhập một số n hoán vị từ bàn phím và in ra màn hình.
    VD: n=4 in ra là 1234, 3412, 2314.....
    Em xin cám ơn

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Cool re

    Code:
     void SinhHoanVi(int b[],int a[],int n){
      int i,k,r,s,tmp;
      static m=1;
      printf("\n Hoan vi thu %2d: ",m++);
      for(i=1;i<=n;i++)
         printf(" %3d",b[a[i]]);
      tmp=0;
      for(i=1;i<=n;i++)
      if(a[i]!=n-i+1) { tmp=1;
    		    break;
    		    }
      if(tmp==0) return;//Da o hoan vi cuoi cung
      i=n-1;
      //Tim a[i] dau tien tu phai sang trai ma a[i]<a[i+1]
      while(a[i]>a[i+1])i--;
      //Tim a[k] dau tien tu phai sang trai ma a[k]>a[i]
      k=n;
      while(a[k]<a[i]) k--;
      //Doi cho a[k] va a[i]
      tmp=a[i];
      a[i]=a[k];
      a[k]=tmp;
      //Lat nguoc cac phan tu con lai
      r=i+1;
      s=n;
      while(r<s){
        tmp=a[r];
        a[r]=a[s];
        a[s]=tmp;
        r++;
        s--;
        }
        SinhHoanVi(b,a,n);
        }
      void HoanVi_K_PhanTu(int a[],int n,int k){
      int i,j,tmp;
      int b[MAX];
      static m=1;
      printf("\n To hop thu %3d: ",m++);
      Init(b,k);
      SinhHoanVi(a,b,k);
      tmp=0;
      for(i=1;i<=k;i++) if(a[i]!=n-k+i){tmp=1;break;}
      if(tmp==0) return;//Da o to hop cuoi cung
      i=k;
      //Tim a[i] dau tien tu phai sang trai ma a[i]!=n-k+i
      while(a[i]>=n-k+i) i--;
      a[i]=a[i]+1;
      for(j=i+1;j<=k;j++) a[j]=a[i]+j-i;
      HoanVi_K_PhanTu(a,n,k);
      }

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Cool re

    Bạn chạy trong bài tổng quát sau:
    Mình lười tách code ra lắm:
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<alloc.h>
    #include<dos.h>
    #define MAX 100
    #include<ctype.h>
    #include<E:\MAIN\8HAU.CPP>
    //=============================================================
     float *B;
     int *C;
     void Init(int a[],int n){
      int i;
      for(i=1;i<=n;i++)
      a[i]=i;
      }
     void View(int a[],int k){
      int i;
      for(i=1;i<=k;i++) printf("%3d",a[i]);
      getch();
      }
     void ToHop_K_PhanTu(int a[],int n,int k){
      int i,j,tmp;
      static m=1;
      printf("\n To hop thu %2d: ",m++);
      View(a,k);
      tmp=0;
      for(i=1;i<=k;i++) if(a[i]!=n-k+i){tmp=1;break;}
      if(tmp==0) return;//Da o to hop cuoi cung
      i=k;
      //Tim a[i] dau tien tu phai sang trai ma a[i]!=n-k+i
      while(a[i]>=n-k+i)i--;
      a[i]=a[i]+1;
      for(j=i+1;j<=k;j++) a[j]=a[i]+j-i;
      ToHop_K_PhanTu(a,n,k);
      }
     void TatCaTapCon(int a[],int n){
      int k;
      for(k=1;k<=n;k++){
      Init(a,n);
      printf("\n CAC TO HOP CO %d PHAN TU",k);
      ToHop_K_PhanTu(a,n,k);
      }
      }
     void SinhHoanVi(int b[],int a[],int n){
      int i,k,r,s,tmp;
      static m=1;
      printf("\n Hoan vi thu %2d: ",m++);
      for(i=1;i<=n;i++)
         printf(" %3d",b[a[i]]);
      tmp=0;
      for(i=1;i<=n;i++)
      if(a[i]!=n-i+1) { tmp=1;
    		    break;
    		    }
      if(tmp==0) return;//Da o hoan vi cuoi cung
      i=n-1;
      //Tim a[i] dau tien tu phai sang trai ma a[i]<a[i+1]
      while(a[i]>a[i+1])i--;
      //Tim a[k] dau tien tu phai sang trai ma a[k]>a[i]
      k=n;
      while(a[k]<a[i]) k--;
      //Doi cho a[k] va a[i]
      tmp=a[i];
      a[i]=a[k];
      a[k]=tmp;
      //Lat nguoc cac phan tu con lai
      r=i+1;
      s=n;
      while(r<s){
        tmp=a[r];
        a[r]=a[s];
        a[s]=tmp;
        r++;
        s--;
        }
        SinhHoanVi(b,a,n);
        }
      void HoanVi_K_PhanTu(int a[],int n,int k){
      int i,j,tmp;
      int b[MAX];
      static m=1;
      printf("\n To hop thu %3d: ",m++);
      Init(b,k);
      SinhHoanVi(a,b,k);
      tmp=0;
      for(i=1;i<=k;i++) if(a[i]!=n-k+i){tmp=1;break;}
      if(tmp==0) return;//Da o to hop cuoi cung
      i=k;
      //Tim a[i] dau tien tu phai sang trai ma a[i]!=n-k+i
      while(a[i]>=n-k+i) i--;
      a[i]=a[i]+1;
      for(j=i+1;j<=k;j++) a[j]=a[i]+j-i;
      HoanVi_K_PhanTu(a,n,k);
      }
    // Duyet cac cach chia n
    int Next_Division(int &k,int C[]){
     int i,j,R,S,D;
     i=k;
     while(i>0&&C[i]==1) i--;
     if(i>0){
    	      C[i]=C[i]-1;
    	      D=k-i+1;
    	R=D/C[i];
    	S=D%C[i];
    	k=i;
    	if(R>0){
    	for(j=i+1; j<=i+R; j++)
    				C[j] = C[i];
    			k = k+R;
    		}
    		if(S>0){
    			k=k+1; C[k] = S;
    		}
    	}
    	else return 0;
    	return 1;
     }
      int KiemTra(int C[],int k){
      int i=k;
      while(C[i]==1) i--;
      if(i==0) return 1;
       else return 0;
      }
      void Division(int n){
      int k,i,count,C[MAX];
      k=1;
      count=1;
      C[k]=n;
      while(1){
      printf("\n Cach chia thu %3d : ",count++);
      for(i=1;i<=k;i++) printf(" %3d",C[i]);
      if(KiemTra(C,k)==1) return;
      Next_Division(k,C);
       }
     }
    //Duyet cac bo gia tri roi rac
    void Init(int &n,int &k,int H[]){
    	int i,j;
    	float x;
    	C[0]=0;
    	H[0]=0;
    	FILE *fp;
    	fp=fopen("roirac.in","r");
    	fscanf(fp,"%d",&n);
    	for(i=1;i<=n;i++)
    	 fscanf(fp,"%d",&H[i]);
    	k=0;
    	for (i=1; i<=n; i++){
    		printf("\n");
    		for(j=1; j<=H[i]; j++){
    			fscanf(fp,"%f",&x);
    			B[++k]=x;
    		}
    	}
    	fclose(fp);
    }
    int In_Set(int i,int H[]){
    	int canduoi=0, cantren=0,j;
    	for(j=1; j<=i; j++)
    		cantren = cantren + H[j];
    	canduoi=cantren-H[j-1];
    	if (C[i]> canduoi && C[i]<=cantren)
    		return 1;
    	return 0;
    }
    void Result(int count,int n){
    	int i;
    	printf("\n Tap con thu %3d:",count);
    	for(i=1; i<=n ; i++){
    		printf("%8.2f", B[C[i]]);
    	}
    }
    void Try(int i,int k,int n,int H[]){
    	int j;
    	static count=1;
    	for(j = C[i-1]+1; j<=(k-n+i); j++){
    		C[i]=j;
    		if(In_Set(i,H)){
    			if (i==n)  Result(count++,n);
    			else Try(i+1,k,n,H);
    		}
    	}
    }
    void CacBoRoiRac(){
    	int n,k,H[MAX];
    	B = (float *) malloc(MAX *sizeof(float));
    	C = (int *) malloc(MAX *sizeof(int));
    	Init(n,k,H);
    	Try(1,k,n,H);
    	free(B);
    	free(C);
    	getch();
    }
    //****************************************************
    //Giai bai toan cai tui bang nhanh can
    int 	x[MAX], xopt[MAX];
    float	fopt, cost, weight;
    //xopt la phuong an xu li do vat
    //fopt la tong gia tri do vat
    void Init(float A[],float C[], int &n, float &w){
    	int i;
    	FILE *fp;
    	fopt=0;
    	weight=0;
    	fp=fopen("caitui.in","r");
    	if(fp==NULL){
    		printf("\n Khong co file input");
    		delay(2000); return;
    	}
    	fscanf(fp,"%d %f",&n,&w);
    	for(i=1; i<=n;i++) xopt[i]=0;
    	printf("\n\n So luong do vat %2d", n);
    	printf("\n\n Gioi han tui %8.2f", w);
    	printf("\n\n Vecto gia tri su dung:");
    	for(i=1; i<=n; i++) {
    		fscanf(fp,"%f", &C[i]);
    		printf("%8.2f", C[i]);
    	}
    	printf("\n\n Vector trong luong:   ");
    	for(i=1; i<=n; i++){
    		fscanf(fp,"%f", &A[i]);
    		printf("%8.2f", A[i]);
    	}
    	fclose(fp);
    }
    void swap(int n){
    	int i;
    	for(i=1; i<=n; i++)
    		xopt[i]=x[i];
    }
    void Update_Kyluc(int n){
    	if(cost>fopt){
    		swap(n);
    		fopt=cost;
    	}
    }
    void Try(float A[], float C[], int n, float w, int i){
    	int j, t=(w-weight)/A[i];
    	for(j=t; j>=0;j--){
    		x[i]=j;
    		cost = cost + C[i]*x[i];
    		weight = weight + x[i]*A[i];
    		if(i==n) Update_Kyluc(n);
    		else if(cost + C[i+1]*(w-weight)/A[i+1]> fopt){
    			Try(A, C, n, w, i+1);
    		}
    		weight = weight-A[i]*x[i];
    		cost = cost-C[i]*x[i];
    
    	}
    }
    void Result(int n){
    	int i;
    	printf("\n\n Gia tri do vat %8.2f", fopt);
    	printf("\n\n Phuong an toi uu:");
    	for(i=1; i<=n; i++)
    		printf("%3d", xopt[i]);
    }
    //*******************************************************
    //Giai bai toan Nguoi du lich bang phuong phap nhanh can
    int A[MAX], XOPT[MAX];
    void Read_Data(int &n,int C[][20]){
    	int i, j;FILE *fp;
    	fp = fopen("dulich.in","r");
    	fscanf(fp,"%d", &n);
    	printf("\n So thanh pho: %d", n);
    	printf("\n Ma tran chi phi:");
    	for (i=1; i<=n; i++){
    		printf("\n");
    		for(j=1; j<=n; j++){
    			fscanf(fp,"%d",&C[i][j]);
    			printf("%5d", C[i][j]);
    		}
    	}
    }
    int Min_Matrix(int n,int C[][20]){
    	int min=1000, i, j;
    	for(i=1; i<=n; i++){
    		for(j=1; j<=n; j++){
    			if (i!=j && min>C[i][j])
    				min=C[i][j];
    		}
    	}
    	return(min);
    }
    void Init(int n,int &cmin,int &can,int &fopt,int C[][20]){
    	int i;
    	cmin=Min_Matrix(n,C);
    	fopt=32000;
    	can=0;
    	A[1]=1;
    	for (i=1;i<=n; i++)
    		B[i]=1;
    }
    void Result2(int n,int fopt){
    	int i;
    	printf("\n\n\n Hanh trinh toi uu %d:", fopt);
    	printf("\n Hanh trinh:");
    	for(i=1; i<=n; i++)
    		printf("%3d ->", XOPT[i]);
    	printf("%d",1);
    }
    void Swap(int n){
    	int i;
    	for(i=1; i<=n;i++)
    		XOPT[i]=A[i];
    }
    void Update_Kyluc(int n,int &can,int &fopt,int C[][20]){
    	int sum;
    	sum=can+C[A[n]][A[1]];
    	if(sum<fopt) {
    		Swap(n);
    		fopt=sum;
    	}
    }
    void Try(int i,int n,int cmin,int &fopt,int &can,int C[][20]){
    	int j;
    	for(j=2;j<=n;j++){
    		if(B[j]){
    			A[i]=j; B[j]=0;
    			can=can+C[A[i-1]][A[i]];
    			if (i==n) Update_Kyluc(n,can,fopt,C);
    			else if( can + (n-i+1)*cmin< fopt)
    				Try(i+1,n,cmin,fopt,can,C);
    			B[j]=1;can=can-C[A[i-1]][A[i]];
    		}
    	}
    }
    
    
    
    
    //=============================================================
    void main()
    {
     int k,n,a[MAX],chon;
     float 	A[MAX], C[MAX], w;
    
      clrscr();
            textmode(C80);
           textcolor(YELLOW);
           textbackground(BLUE);
           window(1,1,80,25);
     while(1){
     clrscr();
     printf("Menu lua chon:\n");
     printf("\n1- Duyet tat ca cac tap con");
     printf("\n2- Duyet cac to hop k phan tu");
     printf("\n3- Duyet cac hoan vi k phan tu");
     printf("\n4- Duyet cac cach chia so tu nhien n");
     printf("\n5- Duyet cac bo gia tri roi rac");
     printf("\n6- Bai toan cai tui");
     printf("\n7- Bai toan Nguoi du lich");
     printf("\n8- Bai Toan 8 Hau");
     printf("\nZ- Tro lai MENU chinh");
     printf("\nHay chon chuc nang mong muon: ");
     char  ch=toupper(getchar());
    	if(ch=='Z') break;
     switch(ch){
     case '1':
    	printf("\n Nhap n= ");
    	scanf("%d",&n);
    	TatCaTapCon(a,n);
    	break;
     case '2':
    	printf("\n Nhap n va k: ");
    	scanf("%d%d",&n,&k);
    	Init(a,n);
    	printf("\n CAC TO HOP LA:\n");
    	ToHop_K_PhanTu(a,n,k);
    	break;
     case '3':
    	printf("\n Nhap n va k: ");
            printf("\nn=");scanf("%d",&n);
            printf("\nk=");scanf("%d",&k);
    	Init(a,n);
    	HoanVi_K_PhanTu(a,n,k);
            getch();
    	break;
     case '4':
    	printf("\n Nhap n= ");
    	scanf("%d",&n);
    	Division(n);
    	getch();
    	break;
     case '5':CacBoRoiRac();
    	break;
     case '6':
    	Init(A,C,n,w);
    	Try(A,C,n,w,1);
    	Result(n);
    	getch();
    	break;
     case '7':
    	int n,C[20][20],cmin,can,fopt;
    	Read_Data(n,C);
    	Init(n,cmin,can,fopt,C);
    	Try(2,n,cmin,fopt,can,C);
    	Result2(n,fopt);
    	getch();
    	break;
     case '8':
            T_HAU();
     } //end switch
     }//end while
     }//end main

  4. #4
    Ngày gia nhập
    09 2006
    Bài viết
    62

    Bài PoPo post trên là bài toán 8 hậu mà: Tìm cách sắp xếp 8 hậu trên bàn cờ sao cho không cây hậu nào ăn cây hậu nào.

    Tách từ chỗ nào ấy nhỉ.


    Bạn thử xem bài giải này xem. Của 1 người bạn mình
    #include <iostream.h>
    #include <conio.h>
    const Max = 12 ;
    int n ;
    int A[Max] , Free[Max];
    void Enter()
    {
    cout << "nhap n : " ;
    cin >> n ;
    for (int i = 1 ; i<= n ; i ++) Free[i] = 0 ;
    }
    void Try(int i)
    {
    if (i == n+1)
    {
    for (int j = 1 ; j <= n ; j++)
    cout << A[j] ;
    cout <<"\n" ;
    }
    for (int j = 1 ; j <= n ; j++)
    if (Free[j] == 0)
    {
    A[i] = j ; Free[j] = 1 ;
    Try(i+1) ;
    Free[j] = 0 ;
    }
    }

    main()
    {
    clrscr() ;
    Enter() ;
    Try(1) ;
    getch() ;
    }
    Đã được chỉnh sửa lần cuối bởi vie_kainznz : 12-10-2006 lúc 12:16 AM.
    Click here for more Info of Cviet-Translator-Group

    ! be thankful for small blessings...

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Bài này chạy rất tốt.
    Có phải nó giải theo thuật toán sinh kế tiếp không?

  6. #6
    No Avatar
    fptcomputer Khách

    Mặc định Hoán vị | In hoán vị của n. Các bác giúp em!

    Cho em hỏi bác POPOPO mấy ý nhỏ. vì em mới học nên chưa sành bác giải thích các int i,k,r,s,tmp là khai báo gì?.
    chẳng hạn: //tmp là gì giải thích hộ em.
    em xin cám ơn.
    càng chi tiết càng tốt anh nhé.

  7. #7
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Thumbs down re

    Bạn fptcomputer thân mến !
    Về bài này thì chạy theo bài của bạn vie_kainznz là ngắn dễ hiểu và đúng rồi.
    Còn bài của mình nó nằm trong tổng thể một bài tập lớn có nhiều chức năng.
    Việc thêm các chú thích vào trong chương trình là hoàn toàn cần thiết.
    chú giải //tmp chir nó là biến tạm thời (template)
    Chúc bạn vui vẻ.

  8. #8
    No Avatar
    fptcomputer Khách

    cám ơn các bác đã giúp em, nhưng cố một số mã em vẫn chưa hiểu được vì em đang học nên các bác thông cảm. khi các bác post lên xin các bác có chú thích sau mỗi câu lệnh. bài của bác vie_kainznz có thể cho em những chú thích cuối câu lệnh không?.
    em cám ơn nhiều!

  9. #9
    Ngày gia nhập
    10 2010
    Nơi ở
    MỸ THO
    Bài viết
    86

    bạn tham khảo bài này nha
    #include <stdio.h>//su dung nhap xuat bang printf va scanf nen phai khai bao thu vien la <stdio.h>
    #include <conio.h>//khai bao de su dung ham getch()
    #define MAX 10// do dai toi da cua mang
    int mang[MAX], n;//khai bao mang va n
    void swap (int *x, int *y)
    {
    int tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
    }

    void hoanvi(int k)//ham hoan vi cac so
    {
    int j;

    if (k==1)
    {
    printf("\n");
    for (j=0; j<n; j++)
    printf("%d ", mang[j]);
    }
    else
    for (j=k-1; j>=0; j--)
    {
    swap(&mang[k-1], &mang[j]);
    hoanvi(k-1);
    swap(&mang[j], &mang[k-1]);
    }
    }

    void main()
    {
    int i;

    printf("\nCho biet so phan tu (N < 10) : ");
    scanf("%d", &n);
    for (i=0; i<n; i++)
    mang[i] = i;//gan gia tri mang bang gia tri i
    hoanvi(n);//goi ham hoan vi de tinh hoan vi cua n
    getch();//lenh cho
    }
    mình nghĩ vậy là cụ thể lắm rùi đó!
    **********************
    Khôn mà gian ác là khôn độc
    Dạy mà hiền lành là dạy khôn

    **********************
    Phone: 0972 755 699 - 090 5678 164
    Mail: thatbaithilamlai@gmail.com

  10. #10
    Ngày gia nhập
    06 2010
    Nơi ở
    Hà Nội
    Bài viết
    114


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