[已解决]为什么报错

黎子卿

描述
正整数可以才分成若干正整数的和，且可能有多种拆分方法。例如n=4，有4、3+1、2+2、2+1+1、1+1+1+1五种拆分方法。

走n级楼梯，后面的跨步要求大于等于前面的跨步，最大一次允许跨n级，有几种走法。输入n，输出所有可能的走法。

输入
正整数n（n<20）
输出
多行数据，每行表示一种走法
样例输入
4
样例输出
1 1 1 1
1 1 2
1 3
2 2
4

#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int last(string x)
{
        if (x.length() == 0)
        {
                return 0;
        }
        istringstream iss(x);
        string temp;
        while (iss >> temp)
                {
                        temp = temp;
                }
        return stoi(temp);
}
void dfs(int n, string str)
{
        if (n == 0)
        {
                cout << str << endl;
                return;
        }
        for (int i = 1; i <= n; i++)
        {
                if (n >= i and i>=last(str))
                {
                        if (n - i > 0)
                        {
                                dfs(n - i, str + to_string(i) + ' ');
                        }
                        else
                        {
                                dfs(n - i, str + to_string(i));
                        }
                }
        }
}
int main()
{
        int n;
        cin >> n;
        dfs(n, " ");
        return 0;
}

最佳答案

月排行榜 / 总排行榜

isdkz

2023-11-21 16:44:41

这段代码存在一个问题，导致输出的结果不符合预期。在dfs函数中，当n - i > 0时，会将当前的步数添加到字符串str后面，但是在n - i = 0时，却没有添加步数，导致最后一个步数丢失。为了解决这个问题，可以将两个if条件语句合并，并且在递归调用时，无需区分是否为最后一个步数，直接添加即可。以下是修改后的代码：

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int last(string x) {
    if (x.length() == 0) {
        return 0;
    }
    istringstream iss(x);
    string temp;
    while (iss >> temp) {
        temp = temp;
    }
    return stoi(temp);
}

void dfs(int n, string str) {
    if (n == 0) {
        cout << str << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (n >= i and i >= last(str)) {
            dfs(n - i, str + to_string(i) + ' ');
        }
    }
}

int main() {
    int n;
    cin >> n;
    dfs(n, "");
    return 0;
}

在修改后的代码中，我将递归调用的部分进行了简化，不再区分是否为最后一个步数，直接添加到字符串中。这样就可以得到正确的输出结果。

跳转到最佳答案楼层

isdkz

这段代码存在一个问题，导致输出的结果不符合预期。在dfs函数中，当n - i > 0时，会将当前的步数添加到字符串str后面，但是在n - i = 0时，却没有添加步数，导致最后一个步数丢失。为了解决这个问题，可以将两个if条件语句合并，并且在递归调用时，无需区分是否为最后一个步数，直接添加即可。以下是修改后的代码：

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int last(string x) {
    if (x.length() == 0) {
        return 0;
    }
    istringstream iss(x);
    string temp;
    while (iss >> temp) {
        temp = temp;
    }
    return stoi(temp);
}

void dfs(int n, string str) {
    if (n == 0) {
        cout << str << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (n >= i and i >= last(str)) {
            dfs(n - i, str + to_string(i) + ' ');
        }
    }
}

int main() {
    int n;
    cin >> n;
    dfs(n, "");
    return 0;
}

在修改后的代码中，我将递归调用的部分进行了简化，不再区分是否为最后一个步数，直接添加到字符串中。这样就可以得到正确的输出结果。