當N> = 10時，這段代碼爲什麼會凍結？

Question

這是一個用C++ 11編寫的程序。

當text.in的值爲N < 10此程序正常工作。然而，當N增加到11時，它會凍結，似乎永遠持續下去。爲什麼會這樣呢？

#include <cstdio> 
using namespace std; 

int dp[40][391]={0}; 

int main() { 
    FILE* in = fopen("text.in","r"); 
    FILE* out = fopen("text.out","w"); 
    int N; 
    fscanf(in,"%d",&N); 
    int sum = N*(N+1)/2; 
    for (int i=0; i<=N; i++) dp[0][i]=1; 
    if (sum%2==1) {fprintf(out,"0"); return 0;} 
    for (int n=1; n<=sum; n++) { 
     for (int k=1; k<=N; k++) { 
      if (n-k>=0) dp[n][k]=dp[n-k][k-1]; 
      dp[n][k]+=dp[n][k-1]; 
     } 
    } 
    fprintf(out,"%d",dp[sum/2][N]/2); 
    return 0; 
} 

Answer 1

我很驚訝與N == 9一起使用。

您定義

int dp[40][391] 

和你讀/寫在它

if (n-k>=0) dp[n][k]=dp[n-k][k-1]; 
    dp[n][k]+=dp[n][k-1]; 

帶有第一索引n與範圍從1到sum其中

int sum = N*(N+1)/2; 

所以如果N < 9， sum是低於40;如果N>=9，sum大於40 [sum == 45對於N == 9; sum == 55 for N == 10; sum = 66對於N == 11。

因此，如果您使用N == 11編寫dp[66][k]，那麼當第一個索引的最高合法值爲39時。

精彩的災難食譜。