题目描述
5个砝码 用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。 如果只有5个砝码，重量分别是1，3，9，27，81。则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。 本题目要求编程实现：对用户给定的重量，给出砝码组合方案。
输入
例如： 用户输入： 5
输出
程序输出： 9-3-1
样例输入
5 19
样例输出
9-3-1 27-9+1把给出的书换成三进制，如果某一位是2，可以转化成下一位对应的数减去这一位的数，
即三进制数121第二位是2×3^1=6，可以变为1*3^2 - 1*3^1=6。
#include <stdio.h> #include <algorithm> #include <math.h> #include <string.h> using namespace std; int len, n, a[20]; struct data{ int x; int d; }ans[20], p[200]; int G3() { int i; while(n) { a[len]=n%3; n/=3; len++; } len--; for(i=1; i<=len/2; i++) swap(a[i], a[len-i+1]); } int quen(int j) { if(p[j-1].x==p[j-2].x) { p[j-2].d=p[j-2].d*3; p[j-1].x=0; } j--; if(p[j-1].d==p[j-2].d) quen(j); } int main() { int i, anslen, j; while(scanf("%d", &n)!=EOF) { memset(ans, 0, sizeof(ans)); memset(p, 0, sizeof(p)); len=1; G3(); anslen = 0; for(i=1; i<=len; i++) { if(a[i]==1) { ans[anslen].x=1; ans[anslen].d=pow(3, len-i); anslen++; } if(a[i]==2) { ans[anslen].x=1; ans[anslen].d=pow(3, len-i+1); anslen++; ans[anslen].x=0; ans[anslen].d=pow(3, len-i); anslen++; } } j = 0; i = 0; p[j]=ans[i]; j++; for(i=1; i<anslen; i++) { p[j++]=ans[i]; while(p[j-1].d==p[j-2].d) { if(p[j-1].x==p[j-2].x) quen(j); else j-=2; } } printf("%d", p[0].d); for(i=1; i<j; i++) { if(p[i].d==p[i+1].d) i+=2; if(p[i].x==1) printf("+%d", p[i].d); else printf("-%d", p[i].d); } printf("\n"); } return 0; }
