第十届 蓝桥杯样题 —— 5个砝码

【5个砝码】

用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。

  如果只有5个砝码，重量分别是1，3，9，27，81。则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。

  本题目要求编程实现：对用户给定的重量，给出砝码组合方案。

例如：

用户输入：

  5

  程序输出：

  9-3-1

  用户输入：

  19

  程序输出：

   27-9+1

  要求程序输出的组合总是大数在前小数在后。

  可以假设用户的输入的数字符合范围1~121。

【解题思路提示】

我们把已知的砝码序列记为：x1, x2, x3, x4, x5, x6 (这里多加一个标准砝码，为解题叙述方便)

  对于任意给定的重量x，如果刚好等于xi 则问题解决。

  否则一定会位于两个标准砝码重量的中间，不妨设为：xi < x < xj

  令 a = x – xi,  b = xj – x

  则，x 要么可以表示为： xi + a, 要么可以表示为： xj – b

  这样问题就归结为怎样表示出 a 或 b

  另一思路：对于每个xi，可以乘以一个系数ki，再求和。

  ki的数值无外乎：-1 0 1

  这样，因为标准砝码的数量的很少的，我们就可以多层循环暴力组合ki来求解。

  还有更“土气”但有效的思路：既然输入范围只有120左右，如果对每一种情况都做人工求解，只要列一个大表，等查询的时候，直接输出答案就好了啊！但…这似乎是个耗时的工程…

代码

#include  using namespace std; int weights[5]={1,3,9,27,81}; int main() { int n; cin>>n; //  a*1+b*3+c*9+d*27+e*81==n //  a,b,c,d,e都属于（-1,0,1） for(int a=-1;a<=1;a++) { for(int b=-1;b<=1;b++) { for(int c=-1;c<=1;c++) { for(int d=-1;d<=1;d++) { for(int e=-1;e<=0;e++) { if(a*1+b*3+c*9+d*27+e*81==n) { if(e==1) cout<<81; if(d==1&&e==1) cout<<'+'<<27; if(d==1&&e==0) cout<<27; if(d==-1) cout<<'-'<<27; if(c==1&&(e==1||d==1)) cout<<'+'<<9; if(c==1&&e==0&&d==0) cout<<9; if(c==-1) cout<<'-'<<9; if(b==1&&(e==1||d==1||c==1)) cout<<'+'<<3; if(b==1&&e==0&&d==0&&c==0) cout<<3; if(b==-1) cout<<'-'<<3; if(a==1&&(e==1||d==1||c==1||b==1)) cout<<'+'<<1; if(a==1&&e==0&&d==0&&c==0&&b==0) cout<<1; if(a==-1) cout<<'-'<<1; } } } } } } return 0; }