天平称重 二进制解法

天平称重 二进制解法

原文地址

用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。如果只有5个砝码，重量分别是1，3，9，27，81则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。本题目要求编程实现：对用户给定的重量，给出砝码组合方案。例如：用户输入：5程序输出：9-3-1用户输入：19程序输出：27-9+1要求程序输出的组合总是大数在前小数在后。可以假设用户的输入的数字符合范围1~121。

#include <iostream>

#include <string>
#include<sstream>
using namespace std;
int main(){

string scale(int);
for(int i=1;i<=121;i++)
{
cout<<i<<":"<<scale(i)<<'n';
}
 
return 0;

}
string scale(int n)
{
stringstream stream;
int q=1;
string str="";
while(n>0)
{
    int sh=n/3;

if(n%3==1)

{
stream<<q;
string strq;
stream>>strq;
str=("+"+strq+str);
stream.clear();
}
if(n%3==2)
{
sh++;
stream<<q;
string strq2;
stream>>strq2;
str=("-"+strq2+str);
stream.clear();
}
n=sh;
q*=3;

}
return str.substr(1);


}