N> = 10のときにこのコードがフリーズするのはなぜですか？

Question

これはC++ 11で書かれたプログラムです。

text.inの値がN <の場合、このプログラムは正常に動作します。しかし、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] 

を定義し、N < 9場合は、あなたがそれでそう1から

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

sumの範囲で最初のインデックスnと

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

を読み取り/書き込みsumはそれより低い40; N>=9,sumが40より大きい場合N == 9の場合、sum == 45; N == 10の場合はsum == 55、 N == 11の場合はsum = 66です。

したがって、N == 11で、dp[66][k]と書くと、最初のインデックスの正当な値が39のときになります。

災害のための素晴らしいレシピ。