递归程序中的分段错误
Segmentation fault in recursive program
我在做硬币题,题目是这样说的,
Given a set of coin values coins = {c1, c2,..., ck}
and a target sum
of money n
, our task is to form the sum n
using as few coins as
possible.
假设你有 9 美元,并且你有一套 {6,5,1}
所以,最少没有。 9 美元的 sum/change 将是 ( 6+1+1+1=9)
即 4
.
我试着用这个公式递归地做:
solve(x) = min( solve(x−6)+1, solve(x−5)+1, solve(x−1)+1 )
,但我不知道为什么我的代码中出现分段错误。
网上有很多代码,但我想知道我在这里做错了什么,我是递归的新手,请帮助我,代码在这里:
//my code
#include<bits/stdc++.h>
using namespace std;
int solve (int x, int a[], int n)
{
if (x < 0)
{
return INT_MAX;
}
if (x == 0)
{
return 0;
}
int best = INT_MAX;
for (int i = 0; i < n; i++)
{
best = min (best, solve (x - a[i], a, n) + 1);
}
return best;
}
int main ()
{
int a[] = { 6, 5, 1 };
int x = 9;
int n = 3;
cout << solve (x, a, n);
return 0;
}
代码取自:https://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/
#include <iostream>
using namespace std;
int minCoins(int coins[], int m, int amount) {
if (amount == 0) return 0;
int res = INT_MAX;
for (int i = 0; i < m; i++) {
if (coins[i] <= amount) {
int sub_res = minCoins(coins, m, amount - coins[i]);
if (sub_res != INT_MAX && sub_res + 1 < res) { // avoid overflow
res = sub_res + 1;
}
}
}
return res;
}
int main() {
int coins[] = { 6, 5, 1 };
int amount = 9;
cout << "Min coins is "
<< minCoins(coins, sizeof(coins) / sizeof(coins[0]), amount)
<< endl;
return 0;
}
关于问题:
您的分段错误来自以下行:
best = min (best, solve (x - i, a, n) + 1);
原因是:x-i
总是会给你相同的值,所以如果你 运行 程序没有调试,你的程序就会崩溃。所以不要尝试调试它,因为要花很多时间才能看到崩溃。
对于初学者更改为:best = min (best, solve (x - a[i], a, n) + 1);
.
修复第 1 部分后,if 情况:if (x < 0) return INT_MAX;
会导致问题,并且 return 始终是相同的值,即:-INT_MAX
。所以你需要再次检查“if cases”。
您尝试实现的算法不正确,请参阅此算法的pseudo-code:
minchange(M):
if M = 0:
return 0
v <- infinity
for c in denominations <= M:
v <- min { minchange(M - c) + 1, v }
return v
更好地使用:sizeof(a) / sizeof(a[0])
而不是 int n = 3
。
我在做硬币题,题目是这样说的,
Given a set of coin values
coins = {c1, c2,..., ck}
and a target sum of moneyn
, our task is to form the sumn
using as few coins as possible.
假设你有 9 美元,并且你有一套 {6,5,1}
所以,最少没有。 9 美元的 sum/change 将是 ( 6+1+1+1=9)
即 4
.
我试着用这个公式递归地做:
solve(x) = min( solve(x−6)+1, solve(x−5)+1, solve(x−1)+1 )
,但我不知道为什么我的代码中出现分段错误。
网上有很多代码,但我想知道我在这里做错了什么,我是递归的新手,请帮助我,代码在这里:
//my code
#include<bits/stdc++.h>
using namespace std;
int solve (int x, int a[], int n)
{
if (x < 0)
{
return INT_MAX;
}
if (x == 0)
{
return 0;
}
int best = INT_MAX;
for (int i = 0; i < n; i++)
{
best = min (best, solve (x - a[i], a, n) + 1);
}
return best;
}
int main ()
{
int a[] = { 6, 5, 1 };
int x = 9;
int n = 3;
cout << solve (x, a, n);
return 0;
}
代码取自:https://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/
#include <iostream>
using namespace std;
int minCoins(int coins[], int m, int amount) {
if (amount == 0) return 0;
int res = INT_MAX;
for (int i = 0; i < m; i++) {
if (coins[i] <= amount) {
int sub_res = minCoins(coins, m, amount - coins[i]);
if (sub_res != INT_MAX && sub_res + 1 < res) { // avoid overflow
res = sub_res + 1;
}
}
}
return res;
}
int main() {
int coins[] = { 6, 5, 1 };
int amount = 9;
cout << "Min coins is "
<< minCoins(coins, sizeof(coins) / sizeof(coins[0]), amount)
<< endl;
return 0;
}
关于问题:
您的分段错误来自以下行:
best = min (best, solve (x - i, a, n) + 1);
原因是:x-i
总是会给你相同的值,所以如果你 运行 程序没有调试,你的程序就会崩溃。所以不要尝试调试它,因为要花很多时间才能看到崩溃。 对于初学者更改为:best = min (best, solve (x - a[i], a, n) + 1);
.修复第 1 部分后,if 情况:
if (x < 0) return INT_MAX;
会导致问题,并且 return 始终是相同的值,即:-INT_MAX
。所以你需要再次检查“if cases”。您尝试实现的算法不正确,请参阅此算法的pseudo-code:
minchange(M): if M = 0: return 0 v <- infinity for c in denominations <= M: v <- min { minchange(M - c) + 1, v } return v
更好地使用:
sizeof(a) / sizeof(a[0])
而不是int n = 3
。