問題3 解説

 この問題は 再帰 (recursion) を使って解いてくれることを期待して(再帰を理解しているかどうかを見るために)出題した.

 問題文の絵を眺めていると,直ぐに次のことに気付くであろう.総数 n 個の正方形を指定されているような辞書式順序で,一番左に m 個以下の正方形が積まれているように並べる並べ方を F(n, m) で表すことにすると,次のような漸化式(再帰方程式)が得られる:

 F(0, m)  =  何もしない
 F(n, m)  =   [m 個の正方形を縦に積む] F(n - m, m) ;
   [m - 1 個の正方形を縦に積む] F(n - m + 1, m - 1) ;
     ・・・
   [m - i 個の正方形を縦に積む] F(n - m + i, m - i) ;
     ・・・
   [1 個の正方形を置く] F(n - 1, 1) ;

 これをそのまま再帰的なプログラムとして書けばよい([ ] の部分では出力を行う).

 このような 2 変数の再帰を思い付けば問題ないが,以下では,n だけに注目した再帰しか思いつかなかった場合についても考えてみよう.求める並び方を求める関数を f(n) とする.f(n) では,上記で [ ] の部分を実行するのと同じ順序で,正方形の並べ方を記録に残しておいて,f(0) のときにその記録を出力する(実は,この方法は本質的に上述の方法と同じものである).この "記録" を行うためには スタック (stack) を用いる.下記のプログラムでは,スタックを配列 S で表し,i をプッシュすることを push(S, i) で,S のトップの要素をポップすることを pop(S) で表している:

  関数 f(n)  /* 総計 n 個の正方形を積む */
  begin
   if (n>0) then
   begin
    for i = n downto 1 do
    begin
     if (i≦S[top]) then  /* S[top] はスタック S のトップ */
     begin
      push(S, i) ;  f(n - i) ; 
       /* 直前に積んだ正方形の個数 S[top] 以下の正方形を,残り総数 n - i 個積む */
      pop(S) ;  /* S[top] を最左とする場合を終了したので S からポップする */
     end
    end
   end
   else
   begin
    if (S が空でない) then
    begin
     print(S) ;   /* スタック S の内容を逆順に(底からトップへ向かって)出力する */
    end
   end
  end

 上述の 2 つの再帰的アルゴリズムのいずれにおいても再帰には重複する計算がないので,実行時間は n に比例する時間しかかからない.あるPC上で実行してみた結果によると,解の個数と,それを求めるのにかかった時間は以下の通りであった(解の個数は漸化式で求められる):

  n = 80  5 秒  15796497
  n = 90  2 分  56634173
  n = 100  8 分  190569292

ということは,実行にはさほど時間はかからないものの,すでに n = 80 で出力ファイルのサイズが 15 MB 以上になり,馬鹿でかいものとなってしまうので,出題では n<30 とした.