5个砝码 表示1~121

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

要求程序输出的组合总是大数在前小数在后。可以假设用户的输入的数字符合范围1~121。

解析：看5个数字分别是3^0 3^1 3^2 3^3 3^4，和三进制一样故想到用 3进制加减问题

例如  80   按3进制转化    进制    1    3      9    27   81

                                   对应数     2    2      2     2     0    即  54+18+9+1

但是题目要求只能由 1   3    9   27   81  加减组成 

  若当前位为2 则向前进一位  并把当前为转化为-1   ；若当前位为3，直接进位，当前位清0

                                    进制    1    3      9    27   81

                               对应数     -1   0     0    0    1    即  81-1

代码如下

#include<iostream> using namespace std; int main() { int b[5] = {1,3,9,27,81}; int a[5] = {0};//表示当前位数 int n; while (cin >> n) { for (int j = 0; j<5; j++) a[j] = 0; int i = 0; while (n > 0)//3进制转化过程 { a[i++] = n % 3; n = n / 3; } for (int j = 0; j < i; j++) { switch (a[j]) { case 2: a[j] = -1; a[j + 1]++; break; case 3: a[j] = 0; a[j + 1]++; } } i--; for (int j=i; j >= 0; j--) { if (j == i)//针对输出的第一位 { if (i<4&&a[j + 1] != 0)//检验最高位的前一位是否为0（此时i应该<4,若等于4直接输出） { cout << a[j + 1] * b[j + 1]; if(a[j]*b[j]!=0)//最高位的前一位不为0，说明当前为产生了进位，可能为0 cout<<a[j]*b[j]; } else cout << a[j] * b[j]; } else { int num = a[j] * b[j]; if (num > 0) cout << '+' << num; else if (num < 0) cout << num; } } cout << endl; } return 0; }