silvercoin.cpp

动态规划解银币问题(C++实现)

#include <iostream.h>
const int MAXNUM = 65535;
const int n = 9;
int m[n];
int MinTimes[n + 1], BestDiv[n + 1];

int max(int x, int y){
	if (x > y) return x;
	else return y;
}

int CatchBadCoin(int beginPos, int endPos, int bestDiv){
	static int times = 1;

	int number = endPos - beginPos + 1;
	if (number == 1){
		return beginPos;
	}
	else{
		if (number == 2){
			cout << "　　第 " << times++ << " 次："
				<< "比较 m[" << beginPos << "] "
				<< "和 m[" << endPos << "]." << endl;
			if (m[beginPos] > m[endPos])
				return beginPos;
			else
				return endPos;
		}
		else{
			// Divide all the coins into three parts: k, k and n-2k.
			int sumOfM1 = 0, sumOfM2 = 0;
			for (int i = beginPos; i < beginPos + bestDiv; i++)
				sumOfM1 += m[i];
			for (int j = beginPos + bestDiv; j < beginPos + 2 * bestDiv; j++)
				sumOfM2 += m[j];

			// Does M[0..k-1] == M[k..2k-1] ?
			cout << "　　第 " << times++ << " 次："
				<< "比较 m["
				<< beginPos << ".." << (beginPos + bestDiv - 1)
				<< "] 和 m["
				<< (beginPos + bestDiv) << ".." << (beginPos + 2 * bestDiv - 1)
				<< "]" << endl;
			int newBeginPos, newEndPos, newBestDiv;
			if (sumOfM1 == sumOfM2){
				newBeginPos = beginPos + 2 * bestDiv;
				newEndPos = endPos;
			}
			else{
				if (sumOfM1 > sumOfM2){
					newBeginPos = beginPos;
					newEndPos = beginPos + bestDiv - 1;
				}
				else{
					newBeginPos = beginPos + bestDiv;
					newEndPos = beginPos + 2 * bestDiv - 1;
				}
			}
			newBestDiv = BestDiv[newEndPos - newBeginPos + 1];
			return CatchBadCoin(newBeginPos, newEndPos, newBestDiv);
		}
	}
}

void GetMinTimesAndBestDiv(int n){
	if (n == 0 || n == 1) {
		MinTimes[n] = 0;
		BestDiv[n] = 0;
	}
	else{
		int minTimes = MAXNUM, curTimes = MAXNUM, bestDiv = 0;
		for (int k = 1; k <= n / 2; k++){
			curTimes = max(MinTimes[n-2*k] + 1, MinTimes[k] + 1);
			if (curTimes < minTimes){
				minTimes = curTimes;
				bestDiv = k;
			}
		}
		MinTimes[n] = minTimes;
		BestDiv[n] = bestDiv;
	}
}
		
void main(){
	for (int i = 0; i < n; i++)
		m[n] = 0;
	m[n-1] = 1;
	
	// Step 1: Determine best division for a centain number
	//			(e.g. i) of silver coins.
	/*
	cout << "总共 " << n << " 个银币，其中有一个不合格。"
		<< "其重量如下所示：" << endl;
	for (i = 0; i < n; i++)
		cout << "　　第 " << i+1 << " 个，\t重量为 " << m[i] << endl;
	*/
	for (int j = 0; j <= n; j++)
		GetMinTimesAndBestDiv(j);
	cout << endl << "理论上，在最坏情况下：" << endl
		<< "　　最少比较（使用天平）次数\t\t" << MinTimes[n] << endl
		<< "　　最佳划分点 K（K，K，N－2ｘK）\t" << BestDiv[n] << endl;
	
	cout << endl << "而实际上，" << endl;

	// Step between 1 and 2: Check MinTimes and BestDiv.
	/*
	for (j = 0; j <= n; j++)
		cout << "MinTimes[" << j << "] = " << MinTimes[j] << ", "
			<< "BestDiv[" << j << "] = " << BestDiv[j] << "." << endl;
	*/

	// Step 2: Using weight comparer to find out the bad coin.
	int BadCoinID = CatchBadCoin(0, n - 1, BestDiv[n]);
	cout << endl << "由此可见，不合格的银币为 第 " << (BadCoinID + 1)
		<< " 个，它的重量为 " << m[BadCoinID] << endl;
}