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:這是算法設計與分析的實驗報告