砝码组合(dfs)

时间:2023-12-06 16:48:50

砝码组合 

题目内容:
用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码,重量分别是1,3,9,27,81。
则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。
本题目要求编程实现:对用户输入的重量(1~121),
给出砝码组合方案(用加减式表示,减代表砝码放在物品盘)。
例如:
输入:
5
输出:
9-3-1

输入:
19
输出:
27-9+1

要求程序输出的组合总是大数在前小数在后。
输入描述
用户输入的重量(1~121),

输出描述
给出砝码组合方案(用加减式表示,减代表砝码放在物品盘)。

输入样例
19

输出样例
27-9+1

思路:dfs

1,3,9,27,81 每个数都有三种状态, 即不取, 加上, 减去

v[i] = 0; //表示不取

v[i] = 1; //表示加上

v[i] = -1; //表示减去

#include <stdio.h>
#include <string.h> int v[], n;
int s[] = {, , , , };
void dfs(int pos, int sum){
if(sum == n){
int i = ;
while(true){ //找到所取的数中 最大的那个数 根据数据给的范围 只会为加号
if(v[i] != ){
printf("%d", s[i]);
break;
}
i--;
}
for(int j = i-; j >= ; j--){
if(v[j] == ) printf("+%d", s[j]);
else if(v[j] == -) printf("-%d", s[j]);
}
return;
}
if(pos >= ) return; // 1、不取
dfs(pos+, sum);
//2、加
v[pos] = ;
dfs(pos+, sum+s[pos]);
v[pos] = ;
//减
v[pos] = -;
dfs(pos+, sum-s[pos]);
v[pos] = ;
}
int main(){
memset(v, , sizeof(v));
scanf("%d", &n);
dfs(, ); //从位置 0 开始 起始的和是 0
return ;
}