第十届 蓝桥杯样题 —— 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 <iostream> 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; }

总结

以上是生活随笔为你收集整理的第十届 蓝桥杯样题 —— 5个砝码的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。