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
Hoán vị | In hoán vị của n. Các bác giúp em!
Trả lời cùng với trích dẫn
re
! be thankful for small blessings...
re
