与えられた整数を2の非負整数乗の和で表す方法は何通りあるかを求めよ、という問題(POJ 2229)への自分の回答です。
普通に再帰するとスタックオーバーフローでRuntime Errorになるので、スタックを自前で持って関数呼び出しをシミュレーションしたのですが、
gotoを使うというタブーを犯してしまいました…
#include <stdio.h> #if 0 #define DEBUG_STACK #endif #define MOD_BY 1000000000 int memo[21][1000010]; int tansaku(int max,int now) { int stackPointer; static int stack[1000010][4]; int eax=0; int result; int i; stackPointer=0; stack[0][0]=max; stack[0][1]=now; tansaku_start: max=stack[stackPointer][0]; now=stack[stackPointer][1]; #ifdef DEBUG_STACK printf("called sp=%d (%d,%d)\n",stackPointer,max,now); #endif if(now<0)result=0; else if(now==0 || max==0)result=1; else if(memo[max][now]>0) { result=memo[max][now]-1; } else { result=0; for(i=0;i<=max && (1<<i)<=now;i++) { /* result+=tansaku(i,now-(1<<i)); */ stack[stackPointer][0]=max; stack[stackPointer][1]=now; stack[stackPointer][2]=result; stack[stackPointer][3]=i; #ifdef DEBUG_STACK printf("jump sp=%d (max,now,result,i)=(%d,%d,%d,%d)\n", stackPointer,max,now,result,i); #endif stackPointer++; stack[stackPointer][0]=i; stack[stackPointer][1]=now-(1<<i); goto tansaku_start; tansaku_returned: max=stack[stackPointer][0]; now=stack[stackPointer][1]; result=stack[stackPointer][2]; i=stack[stackPointer][3]; #ifdef DEBUG_STACK printf("returned sp=%d eax=%d (max,now,result,i)=(%d,%d,%d,%d)\n", stackPointer,eax,max,now,result,i); #endif result+=eax; if(result>=MOD_BY)result-=MOD_BY; } memo[max][now]=result+1; } #ifdef DEBUG_STACK printf("return sp=%d eax=%d\n",stackPointer,result); #endif if(stackPointer>0) { eax=result; stackPointer--; goto tansaku_returned; } return result; } int main(void) { int N=0; scanf("%d",&N); printf("%d\n",tansaku(20,N)); return 0; }
使い方ヒント: 「これは臭う」という行を見付けたら、各行のをクリックしてマーキングしておきましょう(要Twitter OAuth認証)
コメント投稿には、twitter認証が必要です。
Twitter認証
これって、力業で答え出すものでなくて… 多分ビットをカウントするのでは?