有 2 克、5 克、7 克三种重量的砝码,每种都有无穷多个。 现在要凑出总重恰好 N 克,最少需要多少个砝码? 如果凑不出 N 克,输出 -1。c++编程递归,并无其他头文件和数组和函数入门级萌新级别适合初学者理解
时间: 2024-04-15 15:29:49 浏览: 20
明白了,你需要一个 C++ 程序来计算凑出总重恰好 N 克所需的最少砝码数量。下面是一个使用递归的简单实现:
```cpp
#include <iostream>
using namespace std;
int minWeights(int N) {
// 如果 N 为负数,表示无法凑出总重恰好 N 克
if (N < 0) {
return -1;
}
// 如果 N 等于 0,表示已经凑出总重恰好 N 克
else if (N == 0) {
return 0;
}
// 递归计算凑出总重恰好 N 克所需的最少砝码数量
else {
// 分别计算选择 2 克、5 克、7 克砝码后的情况,并取最小值
int min2 = minWeights(N - 2);
int min5 = minWeights(N - 5);
int min7 = minWeights(N - 7);
// 如果三种情况都无法凑出总重恰好 N 克,则返回 -1
if (min2 == -1 && min5 == -1 && min7 == -1) {
return -1;
}
// 否则取三种情况中的最小值,并加上当前选择的砝码数量 1
else {
int minCount = min(min(min2, min5), min7);
return minCount + 1;
}
}
}
int main() {
int N;
cout << "请输入要凑出的总重(单位:克):";
cin >> N;
int minCount = minWeights(N);
cout << "凑出总重恰好 " << N << " 克所需的最少砝码数量为:" << minCount << endl;
return 0;
}
```
这段代码使用递归来计算凑出总重恰好 N 克所需的最少砝码数量。首先判断特殊情况:如果 N 为负数,表示无法凑出总重恰好 N 克;如果 N 等于 0,表示已经凑出总重恰好 N 克。对于其他情况,递归地计算选择 2 克、5 克、7 克砝码后的情况,并取最小值。如果三种情况都无法凑出总重恰好 N 克,则返回 -1;否则取三种情况中的最小值,并加上当前选择的砝码数量 1。
注意:这段代码使用了递归,对于较大的 N 可能会导致递归深度过大,导致堆栈溢出。如果需要处理较大的 N,可以考虑使用循环或动态规划等方法来优化。