编程论坛 → C语言论坛

代码实现出现问题，希望大神能来指正

楚川杉发布于 2020-03-10 23:14， 2491 次点击

在洛谷新手村做的题（递归题+记忆化搜索）：

只有本站会员才能查看附件，请登录

只有本站会员才能查看附件，请登录

正常的话输入50,50,50应该输出w(50, 50, 50) = 1048576，但是不知道为什么每次输出的值都不一样且不是答案，所以想请大神帮忙看看为什么为这样

以下是我的代码

程序代码：

#include<iostream>
#include<string.h>
using namespace std;

long long r[25][25][25]={0};
int w(int a,int b,int c){
    if(a<=0||b<=0||c<=0) return 1;
    else if(r[a][b][c]!=0) return r[a][b][c];
    else if(a>20||b>20||c>20){
    r[20][20][20]=w(20,20,20);
     return r[20][20][20];
     }
    else if(a<b&&b<c){
    r[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    }
    else r[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    return r[a][b][c];
}
int main(){
    int a,b,c;

    while(1){
    cin>>a>>b>>c;
    memset(r,0,sizeof(r));
    if(a==-1&&b==-1&&c==-1) break;
    cout<<"w("<<a<<','<<b<<','<<c<<")="<<w(a,b,c);
    }
}

11 回复

#2

八画小子2020-03-10 23:20

越界了

#3

楚川杉2020-03-10 23:21

输入：
0 0 0
1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
17 17 18
19 17 18
21 -21 20
-1 -1 -11
-1 -1 -1

正确会输出：
w(0, 0, 0) = 1
w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1
w(17, 17, 18) = 131072
w(19, 17, 18) = 524271
w(21, -21, 20) = 1
w(-1, -1, -11) = 1

我的代码输出：

只有本站会员才能查看附件，请登录

#4

八画小子2020-03-10 23:24

只有本站会员才能查看附件，请登录

#5

楚川杉2020-03-10 23:25

回复 2楼八画小子

哦~，我知道了输入 50 50 50的时候r[a][b][c]!=0 那里越界了，return了野值

#6

楚川杉2020-03-10 23:25

回复 4楼八画小子

谢谢您的解答

#7

forever742020-03-10 23:35

查表应该放第三，不该放第二。

#8

楚川杉2020-03-10 23:45

回复 7楼 forever74

还是不行

只有本站会员才能查看附件，请登录

#9

楚川杉2020-03-11 00:04

回复 7楼 forever74

解决啦，谢谢

#10

hbccc2020-03-11 08:44

学习了

#11

return_02020-03-12 10:12

加油

#12

lin51616782020-03-13 23:40

真按照题目要求的做递归
哪怕你加一个数组做优化也是很糟糕的实现
从前往后计算会简单很多
一共才21*21*21个数据
打表
然后三层循环 0到21 直接算就完事了
把输入数据超出0-20这个范围的数据做一个约束
然后直接输出数组元素就完事了

程序代码：

#include <stdio.h>
int main(int argc, char *argv[])
{
    int arr[25][25][25];
    for(int x = 0; x < 21; ++x)
        for(int y = 0; y < 21; ++y)
            for(int z = 0; z < 21; ++z)
                if(x == 0 || y == 0 || z == 0)
                    arr[x][y][z] = 1;
                else if(x < y && y < z)
                    arr[x][y][z] = arr[x][y][z-1] + arr[x][y-1][z-1]-arr[x][y-1][z];
                else
                    arr[x][y][z] = arr[x-1][y][z] + arr[x-1][y-1][z] + arr[x-1][y][z-1] - arr[x-1][y-1][z-1];
    printf("%d\n", arr[20][20][20]);
    return 0;
}

1