用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。 如果只有5个砝码,重量分别是1,3,9,27,81。则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。 本题目要求编程实现:对用户给定的重量,给出砝码组合方案。 例如: 用户输入: 5
程序输出: 9-3-1
用户输入: 19
程序输出: 27-9+1
输入: 41
输出: 81-27-9-3-1
# include "stdafx.h"
int chosen[5];
void Print( int weight[], int n ){
for( int i = 0; i < n; i++ )
{
if( chosen[i] ){
if( chosen[i] == -1 )
cout << "-" << weight[i];
else
cout << "+" << weight[i];
}
}
cout << endl;
}
bool Weighting( int weight[], int n, int curIdx, int total ){
bool retVal = false;
if( 0 == total ){
Print( weight, n );
return true;
}
for( int i = curIdx; i < n && !retVal; i++ ){
//
// 左物右砝.
// 砝码在左边.
if( !retVal ){
chosen[i] = 1;
retVal &= Weighting( weight, n, i + 1, total - weight[i] );
}
// 砝码在右边.
if( !retVal ){
chosen[i] = -1;
retVal &= Weighting( weight, n, i + 1, total + weight[i] );
}
chosen[i] = 0;
}
return retVal;
}
int main(){
int weight[] = { 1, 3, 9, 27, 81 };
int num;
cin >> num;
Weighting( weight, sizeof(weight)/sizeof(int), 0, num );
}