天平称重问题

天平称重问题

天平称重问题：

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

本题目要求编程实现：对用户给定的重量，给出砝码组合方案。
例如：
用户输入：
5
程序输出：
9-3-1
用户输入：
19
程序输出：
27-9+1

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

#include<stdio.h>
#include <stdlib.h>
#include <string.h>
char* reve(char *s) //用于“+”“-”号转换
{int n = strlen(s);for (int i = 0; i < n;i++){if (s[i]=='-'){s[i] = '+';}else if (s[i]=='+'){s[i] = '-';}}char *p = (char *)malloc(n + 2);memset(p, 0, n + 2);p[0] = '-';strcat(p, s);return p;
}
//1：1
//2：3-1
//3：3
//4：3+1
//5：9-3-1
//。。。
char* f(int x)
{char *p = (char *)malloc(1024);memset(p, 0, 1024);//找规律，当X大于（3的n次方的二分之一）时，需要做减法；当x小于（3的n次方的二分之一）时，做加法。int a = 1;while (a < x) a *= 3;if (a == x){_itoa(a, p, 10);return p;}if (x <= a / 2){int m = x - a / 3;char *p1 = f(m);_itoa(a/3, p, 10);strcat(p, "+");return strcat(p, p1);}char *h = reve(f(a - x));_itoa(a, p, 10);strcat(p, h);return p;
}void main(){for (int i = 1; i < 100; i++){char*p=f(i);printf("%d : %sn", i, p);}
}

方法2

余数代表增加或减少，以19和22为例

#include<stdio.h>
#include<stdlib.h>
#include<string.h>char * f2(int n){char*p = (char*)malloc(1024);memset(p, 0, 1024);int q = 1;  //表示权重while (n > 0){int sh = n / 3;  //表示商并进行保存if (n % 3 == 1)  //等于1表示要加上{char arr[1024] = { 0 };strcpy(arr, p);memset(p, 0, 1024);strcat(p, "+");char arr1[1024] = { 0 };_itoa(q, arr1, 10);strcat(p, arr1);strcat(p, arr);}if (n % 3 == 2)  //等于2表示要减去{sh++;     //让他的下一位满足除3的条件，就是将最大的权重补上eg：27char arr[1024] = { 0 };strcpy(arr, p);memset(p, 0, 1024);strcat(p, "-");char arr1[1024] = { 0 };_itoa(q, arr1, 10);strcat(p, arr1);strcat(p, arr);}n = sh;  //商进行更新q *= 3;  //将权重更新}return p+1;
}void main(){for (int i = 1; i < 100; i++){char*p = f2(i);printf("%d : %sn", i, p);}
}