我必須為 C 中的硬幣找零問題撰寫遞回解決方案。該問題提供了一組不同價值的硬幣和一個代表要支付的金額的價值。該問題要求根據手頭的硬幣提供支付款項的方式的數量。
我堅持這個：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long recursive(int amount, vector<long>& input_vector, long ways, vector<long>::const_iterator current) {
if (amount < 0)
return ways;
for (auto iter = current; iter != input_vector.end(); iter) {
cout << "amount: " << amount << ", current coin: " << *iter << '\n';
ways = recursive(amount - *iter, input_vector, 0, iter);
cout << "ways: " << ways << '\n';
}
return ways;
}
long getWays(int n, vector<long> c) {
sort(c.begin(), c.end(), greater<long>());
return recursive(n, c, 0, c.begin());
}
int main() {
int amount = 32;
vector<long> coinages = {2, 5, 6, 10};
cout << "Solution is: " << getWays(amount, coinages) << endl;
return 0;
}
答案應該是 27，但我得到 0？即使我在主程式末尾省略了 eturn 0，我仍然得到 0。所以我有點沮喪，我的邏輯在這里不起作用，我對如何以不同的方式解決這個問題一無所知。
uj5u.com熱心網友回復：
如果amount是 0，這是一個答案，return 1要添加到ways. 如果您低于 0, dead end street, return 0，則不會添加任何內容。
if (amount == 0)
return 1;
if (amount < 0)
return 0;
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/537107.html
標籤：C 递归