【C算法】第5章 再帰的アルゴリズム (その2)

こつこつ。

• ハノイの塔。非再帰的にも書けたが、いまいちしっくりこない。フレームスタックをもっときっちり作ってしまう手法の方がすっきりするかも。
  
• う、8王妃列挙の再帰アルゴリズムですら理解できない。。。考える。。。がなんだかもやもや。再帰といいつつfor文もつかっているからわかりにくいのかな、それともbranchingという再帰の使い方になれてないからかな？ 再度考える。
  
  
  
  • 3王妃列挙に縮小して考える。
    
  • 3王妃列挙では、一行で、とある配置を表現する。例えば、"111"など。これは全列とも行1に王妃がいる配置を表す。
    
  • 理解するためにset(i=0)をどんどん展開していく。
    

    
    {i=0; for(j0=0 to 2) {pos[i]=j0; set(i=1);}}
    
    {i=0; for(j0=0 to 2) {pos[i]=j0;
                                     {i=1; for(j1=0 to 2) {pos[i]=j1; set(i=2);}}}}
    
    {i=0; for(j0=0 to 2) {pos[i]=j0;
                                     {i=1; for(j1=0 to 2) {pos[i]=j1;
                                                                      {i=2; for(j2=0 to 2) {pos[i]=j2; print()}}}}}}
    
    {i=0; for(j0=0 to 2) {pos[i]=j0;
                                     {i=1; for(j1=0 to 2) {pos[i]=j1;
                                                                      {i=2; for(j2=0 to 2) {pos[i]=j2; for(k=0 to 2) {print pos[k]}}}}}}}
    
    {i=0; for(j0=0 to 2) {pos[i]=j0; 
                                     {i=1; for(j1=0 to 2) {pos[i]=j1;
                                                                      {i=2; for(j2=0 to 2) {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}
    
    {i=0; for(j0=0 to 2) {pos[i]=j0; 
                                     {i=1; for(j1=0 to 2) {pos[i]=j1;
                                                                      {i=2;
                                                                            {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                                            {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                                            {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}}
    
    {i=0; for(j0=0 to 2) {pos[i]=j0; 
                                     {i=1;
                                           {j1=0; {pos[i]=j1;
                                                              {i=2;
                                                                    {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                                    {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                                    {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}};
                                           {j1=1; {pos[i]=j1;
                                                              {i=2;
                                                                    {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                                    {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                                    {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}};
                                           {j1=2; {pos[i]=j1;
                                                              {i=2;
                                                                    {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                                    {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                                    {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}}}
    {i=0;
          {j0 = 0;{pos[i]=j0;
                              {i=1;
                                    {j1=0; {pos[i]=j1;
                                                       {i=2;
                                                             {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                             {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                             {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                    {j1=1; {pos[i]=j1;
                                                       {i=2;
                                                             {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                             {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                             {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                    {j1=2; {pos[i]=j1;
                                                       {i=2;
                                                             {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                             {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                             {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}}}
          {j0 = 1;{pos[i]=j0;
                              {i=1;
                                    {j1=0; {pos[i]=j1;
                                                       {i=2;
                                                             {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                             {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                             {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                    {j1=1; {pos[i]=j1;
                                                       {i=2;
                                                             {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                             {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                             {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                    {j1=2; {pos[i]=j1;
                                                       {i=2;
                                                             {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                             {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                             {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}}}
          {j0 = 2;{pos[i]=j0;
                              {i=1;
                                    {j1=0; {pos[i]=j1;
                                                       {i=2;
                                                             {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                             {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                             {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                    {j1=1; {pos[i]=j1;
                                                       {i=2;
                                                             {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                             {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                             {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}};
                                    {j1=2; {pos[i]=j1;
                                                       {i=2;
                                                             {j2=0; {pos[i]=j2; print pos[0]pos[1]pos[2]}};
                                                             {j2=1; {pos[i]=j2; print pos[0]pos[1]pos[2]]};
                                                             {j2=2; {pos[i]=j2; print pos[0]pos[1]pos[2]]}}}}}}}}
    

    
    
  • これをみて分析すると。
    
  • まず、列iは再帰によって繰り返しを生じている。
    
  • 列iの繰り返しと行j*の繰返しは交互に生じている。
    
  • j0は列0の行配置、j1は列1の行配置、j2は列2の行配置、を生成している。
    
  • 理解したいのはset(i)の作業を日本語で何というか、だ。
    
  • まずset(i)は列iに関する作業であるといえる。
    
  • ただし、それは列i+1に関する作業も含んでいる。
    
  • その連鎖によって、set(0)は列0、列1、列2のすべての作業を含んでいる。
    
  • ところで、「列iに関する作業」というのは具体的に何かというと、列iの各行jのどこに王妃がいるかを印字すること。
    
  • うーむ。よくわからない。
    
  • そうか！set(i=0)を列0に関する作業、と考えるからいけないのだ。これは「列0を起点に、分岐して、王妃を全部列挙する作業」と考えるのか。
    
  • すると、
    

    {i=0; for(j0=0 to 2) {pos[i]=j0; set(i=1);}}

    
    は、列0については、0〜2の通りがあるけど、それはそれぞれの通りについて、「列1を起点に、分岐して、王妃を全部列挙する作業」があるもんだよ、といっている。
    
  • これを繰返していく、と。
    
  • なるほど、再帰による分岐は、階乗とかの再帰とかとはニュアンスがちょっと違う。勉強になった。
    
  
  
• 分割統治法って、再帰的である分割に限るのかな?
  
• うーん。8王妃の分岐限定法アルゴリズムを完全に理解できたわけではないが、分岐限定法自体の考え方は多少わかるので、先に進もう。