n枚硬币问题（假币问题）——分治法（减治法）

1、8枚硬币问题

在8枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道的是假币与真币相比较是轻还是重。可以通过一架天平来比较两组硬币：

减治法将原问题一分为三，8枚硬币分别表示a,b,c,d,e,f,g,h，从8枚中取6枚在天平两端各放3枚比较，三种结果：

a+b+c>d+e+f

a+b+c=d+e+f

a+b+c<d+e+f

如下所示判定树是完整表示整个判定过程：

 

代码就比较好写，直接按照判定树的过程即可：

/*8枚硬币中有一枚为假币，不知假币是轻是重，
天平只能比较轻重(元素只能相加和比较)*/
#include<stdio.h>
bool v;
int index;
int EightCoin(int B[]){
	int a,b,c,d,e,f,g,h;
	a=B[0];b=B[1];c=B[2];d=B[3];
	e=B[4];f=B[5];g=B[6];h=B[7];
	if(a+b+c>d+e+f){
		if(a+e>d+b){
			if(a>h){index=1;v=1;return a;}
			else if(a==h) {index=4;v=0;return d;}
		}
		else if(a+e==d+b){
			if(c>h){index=3;v=1;return c;}
			else if(c==h) {index=6;v=0;return f;}
		}
		else{
			if(b>h) {index=2;v=1;return b;}
			else if(b==h) {index=5;v=0;return e;}
		}
	}
	else if(a+b+c==d+e+f){
		if(g>h){
			if(g>a){index=7;v=1;return g;}
			else if(g==a){index=8;v=0;return h;}
		}
		else if(g<h){
			if(h>a){index=8;v=1;return h;}
			else if(h==a){index=7;v=0;return g;}
		}
	}
	else{
		if(a+e>d+b){
			if(e>h){index=5;v=1;return e;}
			else if(e==h){index=2;v=0;return b;}
		}
		else if(a+e==d+b){
			if(f>h){index=6;v=1;return f;}
			else if(f==h){index=3;v=0;return c;}
		}
		else{
			if(d>h){index=4;v=1;return d;}
			else if(d==h) {index=1;v=0;return a;}
		}
	}
}
int main(){
	int B[100],t;
	for(int i=0;i<8;i++)
	scanf("%d",&B[i]);	
	t=EightCoin(B);
	printf("The location of the fake coin is %d.\n",index);
	if(v==0)printf("The fake coin is low.\n");
	else printf("The fake coin is high.\n");
	printf("The quality of the fake coin is %d.\n",t);	
	return 0;
}
/*
1 1 1 1 1 1 1 2
3 3 3 1 3 3 3 3
5 3 3 3 3 3 3 3
*/

2、拓展——n枚硬币问题

n枚硬币中有1枚假币，n枚硬币中有一枚为假币，不知假币是轻是重，天平只能比较轻重(元素只能相加和比较)，减治法将问题一分为三：

#include<stdio.h>
#define inf 10000
//可优化剪枝 找到即停止(其他优化方法) 
int EightCoin(int b[],int n,int v){
	int b1[50],b2[50],b3[50],n1;
	int t1=0,t2=0,t3=0,s1=0,s2=0,s3=0;
	int d,d1,d2,d3,d4,d5,d6,d7,d8;
	//if(n/3==0)将n分为三组处理（网上大多一分为二） 
	n1=n;
	if(n%3==2)n1=n+1;//若n=8,三组存3 3 2,而不是 2 2 4 
	for(int i=0;i<n;i++){
		if(i<(n1/3)){
			b1[t1++]=b[i];
			s1+=b[i];
		}
		else if(i<(n1/3*2)){
			b2[t2++]=b[i];
			s2+=b[i];
		}
		else {
			b3[t3++]=b[i];
			s3+=b[i];
		}
	}
	
	if(n==3){
		if(b1[0]!=b2[0]){
			if(b1[0]!=v)return b1[0];
			else return b2[0];
		}
		else if(b1[0]!=b3[0]){
			if(b1[0]!=v)return b1[0];
			else return b3[0];
		}
		else if(b2[0]!=b3[0]){
			if(b2[0]!=v)return b2[0];
			else return b3[0];
		}
		else return inf;
	}
	if(n==4){
		if(b1[0]!=b2[0]){
			if(b1[0]!=v)return b1[0];
			else return b2[0];
		}
		else if(b3[0]!=b3[1]){
			if(b3[0]!=v)return b3[0];
			else return b3[1];
		}
		else return inf;
	}
	if(n==5){
		if(s1!=s2){
			if(b1[0]!=b2[0]){
				if(b1[0]!=v)return b1[0];
				else return b2[0];
			}
			else{
				if(b1[1]!=v)return b1[1];
				else return b2[1];
			}
		}
		else if(v!=b3[0]){
			return b3[0];
		}
		else return inf;
	}
	if(n==6){
		if(s1!=s2){
			if(b1[0]!=b2[0]){
				if(b1[0]!=v)return b1[0];
				else return b2[0];
			}
			else{
				if(b1[1]!=v)return b1[1];
				else return b2[1];
			}
		}
		else if(b3[0]!=b3[1]){
			if(b3[0]!=v)return b3[0];
			else return b3[1];
		}
		else return inf;
	}
	if(n==7){
		if(s1!=s2){
			if(b1[0]!=b2[0]){
				if(b1[0]!=v)return b1[0];
				else return b2[0];
			}
			else{
				if(b1[1]!=v)return b1[1];
				else return b2[1];
			}
		}
		else {
			d1=EightCoin(b3,t3,v);
			if(d1!=inf)d=d1;
		}
	}
	if(n==8){
		if(s1!=s2){
			d2=EightCoin(b1,t1,v);
			if(d2!=inf)d=d2;
			d3=EightCoin(b2,t2,v);
			if(d3!=inf)d=d3;
		}
		else{
			if(b3[0]!=v)return b3[0];
			else if(b3[1]!=v)return b3[1];
			else return inf;
		}
	}
    if(s1>s2){
    	d4=EightCoin(b1,t1,v);
    	if(d4!=inf)d=d4;
    	d5=EightCoin(b2,t2,v);
    	if(d5!=inf)d=d5;
	}
    else if(s1==s2){
    	d6=EightCoin(b3,t3,v);
    	if(d6!=inf)d=d6;
	}
    else {
    	d7=EightCoin(b1,t1,v);
    	if(d7!=inf)d=d7;
    	d8=EightCoin(b2,t2,v);
    	if(d8!=inf)d=d8;
	}
    return d;
}
int main(){
	int b[100],d,n,v=0;
	printf("Input n:\n");
	scanf("%d",&n);
	printf("Input the quality of n coin(the quality of the fake coin isnot beyond 10000):\n");
	for(int i=0;i<n;i++)
	scanf("%d",&b[i]);
	if(n==1) printf("The quality of the fake coin is %d.\n",b[0]);
	else if(n==2){
		printf("Cannot judge!\n");
	}
	else {
		if(b[0]==b[1])v=b[0];
		else if(b[0]==b[2])v=b[0];
		else if(b[1]==b[2])v=b[1];
		d=EightCoin(b,n,v);
		printf("The quality of the real coin is %d.\n",v);
	    printf("The quality of the fake coin is %d.\n",d);
	}
	return 0;
}
/*
13
4 4 4 4 4 4 4 4 4 4 8 4 4
25
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 25
5 
6 3 6 6 6

*/

正如代码注释，还可以有很大的优化，等有时间再来。Ps:这是算法设计与分析的实验报告