天平秤杂币问题一般解求解程序

天平秤杂币问题一般解求解程序

（这是我很久之前写的一个程序，目前博客上还没有什么文章，就算充个数把）

本程序的问题描述可参见：Balance puzzle，或者也可以阅读我之前写的一个PPT。

头文件balance.h如下：

/************************************************************************************/
/*        This demo implements the coding method for soving n coins problem         */
/*                   No Copyrights! Feel free to copy it!                           */
/*----------------------------------------------------------------------------------*/
/*Algorithm:                                                                        */
/*1. Violence search the solution for 3<=n<=12                                      */
/*2. Use the induction steps in the proof to get the following solution             */
/************************************************************************************/#include<stdio.h>
#include<malloc.h>
#include<string.h>#define MAX 100;//k is no more than 100typedef struct set{int n;char * * node;
}SET;void convert(char * set[],int n,int k);
int thresh(int k);
SET * searchT(int n,int k,char * a);
SET * search(int n,int k);
void show(int k,bool state,SET * a);
bool check(SET * a); 

#include"balance.h"char * s1[3]={"01","20","12"};
char * s2[4]={"001","010","220","102"};
char * s3[5]={"001","010","220","012","120"};
char * s4[6]={"001","010","022","110","202","021"};
char * s5[7]={"001","010","011","220","202","120","102"};
char * s6[8]={"001","010","011","220","202","012","121","122"};
char * s7[9]={"001","010","011","220","202","120","201","112","122"};
char * s8[10]={"001","010","011","220","202","012","120","102","221","100"};
char * s9[11]={"001","010","111","011","220","202","120","102","221","212","122"};
char * s10[12]={"001","010","111","011","220","202","012","120","102","221","122","200"};/*calculate the threshold (3^k-3)/2*/
int thresh(int k)
{int tmp=1;for(int i=0;i<k;i++)tmp=tmp*3;return (tmp-3)/2;
}/*put k char 'a' ahead of a1*/
char * putch(char a,int k,char * a1)
{int n=strlen(a1);char * result;result=(char *)malloc(n+k+1);for(int i=0;i<n+k;i++){if(i<k)*(result+i)=a;else*(result+i)=*(a1+i-k);}*(result+n+k)='';return result;
}/*make a srting array that add k chars 'c' ahead of each string of a*/
char * * makeSet(char * a[],int n,int k,char c)
{char * * result;result=(char * *)malloc(sizeof(char *)*n);for(int i=0;i<n;i++){*(result+i)=putch(c,k,a[i]);}return result;
}/*make a SET from a string array*/
SET * MakeSET(char * * a,int n)
{SET * result;result=(SET *)malloc(sizeof(set));result->n=n;result->node=a;return result;
}char * * getlow(int n)
{switch(n){case 3:return s1;case 4:return s2;case 5:return s3;case 6:return s4;case 7:return s5;case 8:return s6;case 9:return s7;case 10:return s8;case 11:return s9;case 12:return s10;default:return NULL;}
}SET * below12(int k,int n)
{if(n==3){if(k<3)return MakeSET(getlow(3),3);elsereturn MakeSET(makeSet(getlow(3),3,k-2,'0'),3);}if(n>12||n<3)return NULL;SET * result;char * * tmp;tmp=(char * *)malloc(sizeof(char *)*n);result=(SET *)malloc(sizeof(set));result->n=n;tmp=makeSet(getlow(n),n,k-3,'0');result->node=tmp;return result;
}/*combine two set*/
SET * combine(SET * a,SET * b)
{SET * result;result=(SET *)malloc(sizeof(set));char * * tmp;tmp=(char * *)malloc(sizeof(char *)*(a->n+b->n));for(int i=0;i<a->n+b->n;i++){if(i<a->n)*(tmp+i)=*(a->node+i);else*(tmp+i)=*(b->node+i-a->n);}result->n=a->n+b->n;result->node=tmp;return result;
}char * Inverse(char * a)
{char * result;result=(char *)malloc(strlen(a)+1);for(int i=0;i<strlen(a);i++){if(*(a+i)=='0')*(result+i)='0';else if(*(a+i)=='1')*(result+i)='2';else*(result+i)='1';}*(result+strlen(a))='';return result;
}/*The case when n=(3^k-3)/2*/
SET * searchT(int n,int k,char * a)
{SET * temp,* temp1,* temp2;char * * tmp,c;if(n!=thresh(k))return NULL;tmp=(char * *)malloc(sizeof(char *)*3);if(n==3){if(a[0]=='2'&&a[1]=='2'){char * s1="10",*s2="02",*s3="21";*tmp=s1;*(tmp+1)=s2;*(tmp+2)=s3;}else{char * s1="10",*s2="01",*s3="22";*tmp=s1;*(tmp+1)=s2;*(tmp+2)=s3;}return MakeSET(tmp,3);}else{temp=searchT((n-3)/3,k-1,a+1);if(*a=='1')c='2';elsec='1';*tmp=putch(*a,1,putch('0',k-1,""));*(tmp+1)=putch(c,1,a+1);*(tmp+2)=putch('0',1,Inverse(a+1));temp1=MakeSET(tmp,3);temp2=combine(MakeSET(makeSet(temp->node,temp->n,1,'0'),temp->n),MakeSET(makeSet(temp->node,temp->n,1,'1'),temp->n));temp2=combine(MakeSET(makeSet(temp->node,temp->n,1,'2'),temp->n),temp2);return combine(temp2,temp1);}}/*
The algorithm we used here is different from we 
presented in PPT, since we just simply let the 
uncantained string to be ". 
*/
SET * search(int n,int k)
{int thre=thresh(k),threp=thresh(k-1);if(n==thre)return searchT(n,k,putch('2',k,""));if(n>thre||n<3)return NULL;else if(n<=12)return below12(k,n);else{SET * result,* temp1,* temp2,*temp3,*temp4,*temp5;char * * tmp;if(n<2*threp+1){if(n%2==0){temp1=search(n/2,k-1);temp2=MakeSET(makeSet(temp1->node,temp1->n,1,'1'),temp1->n);temp3=MakeSET(makeSet(temp1->node,temp1->n,1,'2'),temp1->n);return combine(temp2,temp3);}else{temp1=search((n-3)/2,k-1);temp2=search(3,k-1);temp3=MakeSET(makeSet(temp1->node,temp1->n,1,'1'),temp1->n);temp4=MakeSET(makeSet(temp1->node,temp1->n,1,'2'),temp1->n);temp1=MakeSET(makeSet(temp2->node,temp2->n,1,'0'),temp2->n);return combine(combine(temp3,temp1),temp4);}}else if(n==2*threp+2){temp1=search((n-4)/2,k-1);temp2=search(4,k-1);temp3=MakeSET(makeSet(temp1->node,temp1->n,1,'1'),temp1->n);temp4=MakeSET(makeSet(temp1->node,temp1->n,1,'2'),temp1->n);temp1=MakeSET(makeSet(temp2->node,temp2->n,1,'0'),temp2->n);return combine(combine(temp3,temp1),temp4);}else if(n<=3*threp){temp1=search(threp,k-1);temp2=search(n-2*threp,k-1);temp3=MakeSET(makeSet(temp1->node,temp1->n,1,'1'),temp1->n);temp4=MakeSET(makeSet(temp1->node,temp1->n,1,'2'),temp1->n);temp1=MakeSET(makeSet(temp2->node,temp2->n,1,'0'),temp2->n);return combine(combine(temp3,temp1),temp4);}else{int j=n-2-2*threp;temp1=search(threp,k-1);temp2=search(j,k-1);temp3=MakeSET(makeSet(temp1->node,temp1->n,1,'1'),temp1->n);temp4=MakeSET(makeSet(temp1->node,temp1->n,1,'2'),temp1->n);temp1=MakeSET(makeSet(temp2->node,temp2->n,1,'0'),temp2->n);temp5=combine(combine(temp3,temp1),temp4);tmp=(char **)malloc(sizeof(char *)*2);*tmp=putch('1',k,"");*(tmp+1)=putch('2',k,"");return combine(temp5,MakeSET(tmp,2));}}
}bool check(SET * a)
{char ** temp=a->node;int k=strlen(*(a->node)),*tmp;tmp=(int *)malloc(sizeof(int)*k);for(int i=0;i<k;i++)tmp[i]=0;for(int i=0;i<a->n;i++){for(int j=0;j<k;j++){if(*(*(temp+i)+j)=='1')tmp[j]++;else if(*(*(temp+i)+j)=='2')tmp[j]--;}}for(int i=0;i<k;i++)if(tmp[i]!=0)return false;return true;
}

#include"balance.h"int main()
{SET *result;int n,k;printf("Please input the order: ");scanf("%d",&n);printf("Please input the dimension: ");scanf("%d",&k);result=search(n,k);if(result==NULL){printf("Can't find solution!n");system("pause");exit(1);}else{printf("The constructible set is as follow:n");for(int i=0;i<result->n;i++)printf("%st",*(result->node+i));printf("n");}show(1,true,result);system("pause");return 0;
}