动态规划方法来计算斯特林的数 [英] Dynamic programming approach to calculating Stirling's Number

问题描述

  INT s_dynamic（INT N，INT K）{
    INT MAXJ = N-K;

    INT *改编=新INT [MAXJ + 1];

    的for（int i = 0; I＆LT; = MAXJ; ++ I）
        改编[I] = 1;

    的for（int i = 1; I＆LT; = K ++ I）
        对于（INT J = 1; J＆LT; = MAXJ; ++ j）条
            ARR [J] + = I *常用3 [J-1]。

    返回ARR [MAXJ]
}
 

下面是我尝试使用动态规划确定Stirling数。

有定义如下：

  

S（N，K）= S（N-1，K-1）+ K S（N-1，k）时，如果1所述; K＆LT; ñ

     

S（N，K）= 1，如果k = 1 OU K =ñ

似乎确定，对不对？除了当我运行我的单元测试...

  partitioningTest .. \ SRC \ Test.cpp的：44 3025 == s_dynamic（9,3）预计：3025不过是：4414
 

有人能看到我在做什么错了？

谢谢！

顺便说一句，这里的递归解决方案：

  INT s_recursive（INT N，INT K）{
    如果（K = = 1 ||满足K == N）
        返回1;

    返回s_recursive（N-1，K-1）+ K * s_recursive（N-1，k）的;
}
 

解决方案

中找到的错误。 你已经计算的动态Stirlings号码阵列对于k = 1（S（N，1）= 1对于所有的n）。 你应该开始计算S（N，2） - 即：

 的for（int i = 2; I＆LT; = K ++ I）// i = 2，而不是1
  对于（INT J = 1; J＆LT; = MAXJ; ++ j）条
    ARR [J] + = I *常用3 [J-1]。
 

int s_dynamic(int n,int k) {
    int maxj = n-k;

    int *arr = new int[maxj+1];

    for (int i = 0; i <= maxj; ++i)
        arr[i] = 1;

    for (int i = 1; i <= k; ++i)
        for(int j = 1; j <= maxj; ++j)
            arr[j] += i*arr[j-1];

    return arr[maxj];
}

Here's my attempt at determining Stirling numbers using Dynamic Programming.

It is defined as follows:

S(n,k) = S(n-1,k-1) + k S(n-1,k), if 1 < k < n

S(n,k) = 1, if k=1 ou k=n

Seems ok, right? Except when I run my unit test...

partitioningTest ..\src\Test.cpp:44 3025 == s_dynamic(9,3) expected:    3025    but was:    4414    

Can anyone see what I'm doing wrong?

Thanks!

BTW, here's the recursive solution:

int s_recursive(int n,int k) {
    if (k == 1 || k == n)
        return 1;

    return s_recursive(n-1,k-1) + k*s_recursive(n-1,k);
}

解决方案

Found the bug. You already computed your dynamic array of Stirlings numbers for k=1 (S(n,1)=1 for all n). You should start computing S(n,2) - that is:

for (int i = 2; i <= k; ++i) //i=2, not 1
  for(int j = 1; j <= maxj; ++j)
    arr[j] += i*arr[j-1];

这篇关于动态规划方法来计算斯特林的数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！