後輩からプログラムを書くとき、アルゴリズムはわかってもプログラムに直すことが出来ない、for文やスタックなどをどう使えば良いのかわからない、難しいというぼやきを受けた。現在彼はトップコーダーにチャレンジしていて、そんな話になったのだが、その会話の中で一つ思ったことがあるので言葉にしてみようと思う。
出来ない理由は理解してないからだけじゃ？
まず、プログラムというのは事象の表現方法の一つである。つまり言語だ。プログラム言語なのだから言語で当然なのだが。つまり、本質的にプログラムを書くことと、日本語を書くことに大した差はない。日本語で曖昧さがなく、ある事象について説明できるならプログラムでも当然書くことが出来る。え？出来ないこといっぱいある？それは、曖昧さが残っているか、もしくは言語の表現力と聞き手（計算機）の理解力の問題になってくる。そこには今は目をつむろう。
ということは、当然プログラムが書けると言うことは、日本語で説明できなくてはならない。それも曖昧さなく、だ。なんとなく、ではいけない。（トライ＆エラーで何となく出来てしまったってこともまーあるっちゃあるが。）
そんな事から、プログラムが書けないってのは単に日本語で説明できるぐらいきっちり理解してないからってだけだよね、ってのが私の意見でした。
森を見て木を見ず
しかし、どーも、後輩の話を聞いていると案外そうでもない様な気がしてきた。いったいどういうときが書けないのか、最も彼が簡単だと思う問題の例を聞いてみたら、「1からnまでの数字を使った全ての順列を求める」といった問題をあげてくれた。
なるほど、小学生でも解ける問題だ。普通下図の様に解くだろう。
実際彼も紙の上ではこの様に解く。効率ウンヌンという話はおいておくとして、これをそのまま愚直にプログラムにするだけなら以下の様に書けばいい。なにも難しいことはない。
public static void method(int n){ //下準備 int[] ret = new int[n]; List<Integer> list = new ArrayList<>(); for(int i=1;i<=n;i++)list.add(i); _method(ret, 0,list);//実際の処理 } //resultは順列の結果 //indexはresultのどこに結果を入れるか //listはresultに入れることが出来る残っている数 public static void _method(int[] result,int index,List<Integer> list){ if(list.size()==1){//最後の処理 result[index] = list.get(0); print(result);//結果を出力 return; } for(int i=0,e=list.size();i<e;i++){ //使える数字から数kを取り出し、結果に格納 int k = list.get(i); result[index] = k; //使える数から数kを取り除いたリストを作成する List<Integer> clone = new ArrayList<>(list);//クローンの作成 clone.remove(i);//数kを取り除く ※iはkのインデックス //result[index+1以降の値は_methodに投げる _method(result,index+1,clone); } }
まず何よりも動くことが重要だ。解ければ良いのだ。高速化は後でやれば良い。
私としては、愚直に手でやる方法をプログラムにしただけなのだが、これでも彼にとっては難しいと感じたらしい。当然手で解けるというとは理解している。体を動かす方法のような言葉で説明できないことではない。
しかし、どうもその説明の仕方が悪いのではないかと思う。私が説明するなら、「使っていない数の中から数を小さい順に一つ選び、並びに加える。以下の数列も同様にして作ったら、次に小さい数を一つ選び、同様にして数列を作っていく。全ての数を使い切るまで繰り返す。」 一方で、彼がごにょごにょ言っていたことをまとめると、「使っていない数を小さい順に並べて、次に一つ前に戻って今より大きな数にして並びを作って、さらにその一つ前に戻って後は同様に作っていく」と言ったところか。
要するに、処理全体を説明しようとしてしまっている。なるほど、これでは彼が言う「for文を使うのが難しい」ということになってしまうだろう。
プログラムとは（シングルスレッドなら）、上から下まで一繋がりの処理を記述したものであるというのは、よく聞く説明だ。実際、処理を走らせるときにはその通りなのだが、プログラムを書く上でこのように認識しているのはまずい。プログラムは処理のブロックが連なったものだと考える方が良いだろう。プログラムを書くには、よほど簡単な物でもない限り如何に処理をブロック分けするかが問題になるのだ。突き詰めれば抽象化という話になるかもしれない。
森を見て複雑だ！と言っていては森を作ることは始まらない。森を作りたければ、とにかく木を植えれば良いのだ。森を見て木を見ずではプログラムを書くのは難しい。
で、どう教えるの？
要するに、ブロック単位で処理を考えると言うことをマスターさせれば、私の後輩の問題点は解決する。で、それをどう教えればいいのかだ。帰宅してから、悩んでいる。処理を追うんじゃない、ブロックを見るんだ、似ているところを探すんだ！と叫ぶだけでは、意味がない。如何にブロックに区切るのか、類似点を探し出すのかの方法を教えなくてはならない。場数を踏め、経験則だ、ではただの老害だ。
まずは、分解できそうな物を探してみることだ。一番最初に出力結果を見てみることをおすすめする。出力が複数あるなら、一つの出力を作ることが一つのブロックだ。さらに、今回の様に一つの出力結果をさらに分解できないかも確認してみよう。数列という一つの出力を作成するには、一個一個の要素を作っていかなくてはならない。その部分もブロックである。
もちろん、結果は単なるスカラー量という場合にはどうにもならない。そんなときには処理の状態を決めている物を探してみると良いだろう。ほとんどのプログラム、アルゴリズムには状態という物がある。例えば処理している内容だったり、フラグ変数だったりだ。そういった状態が変化するポイントを探してみよう。状態が変化するところから次にまた変化するところまでは一つのブロックになる可能性が高い。
次に、とりあえず見つけてきたブロックに汎用性があるかないかを考える。ここでやってる事って、他の所でも同じ事言えないかな？って考えてみる。そうやって探してると、全く同じではないけど、大体同じ事やってるところがあることに気がつくと思う。
ブロックを考えた、汎用性有りそうなブロックも見つけた、で、次にどうやってプログラムに落とし込むのか。まずはそのブロックを関数にしなさい。いきなりループ文で考える必要はない。関数にしてしまうと、他のループとの繋がりや影響をぶった切れるので非常に考えるのが楽になる。関数に必要な変数も戻り値も、まずは空でいい。関数を書きながら後々必要な物を決めていけば良い。一般的には、出力を格納する変数と、状態を決める変数などが必要になってくる。次のループをするには、同じ関数を関数内から呼べばよい。
さて、何とかプログラムに落とし込むことが出来たでしょうか？ おめでとう。しかし、関数型言語でない一般のプログラム言語はこの書き方では効率が悪いことが多い。効率が気になるなら、次にようやく関数をループに展開することを考えよう。すでに動く物があって、それを展開するって言うのは、とっかかりがない状態よりかなり精神的にも楽なはずだ。
こんなかんじでどうだろうか。実際に効果があるのか、後輩で実験してみるしかないのだが。
ついでに、上で示したプログラムを効率を追求し、ループに展開してみた。とにかく、速度とメモリ重視にしたため、上記のように小さい順に出力する、ということを省いた。メモリを使わず、かつ、計算量も変えない為にはこの実装しか思いつかなかった。
public static void method2(int n){ int[] memo = new int[n];//関数スタックに相当するデータ int[] result = new int[n];//元のメソッドの引数resultと同じ int[] list = new int[n];//元のメソッドの引数listを最適化した物 for(int num=1;num<=n;num++)list[num-1]= num; int index = 0;//元のメソッドの引数indexと同じ while(index>=0){ int i = memo[index];//元のメソッドのループ変数iと同じ int k = list[i];//数k result[index]= k; memo[index]++;// = i++ if(index==n-1){//list.size()==1と同じ print(result);//出力 //以下は_methodのreturn;に相当する index--; while(index>=0 ){ //listを元に戻す作業 i = memo[index]-1; k = list[i]; list[i]=list[n-index-1]; list[n-index-1] = k; if(i!=n-index-1)break;//_methodoでいえばi < eが成立するところまで戻る index--; } }else{ //以下はkを除いたlistのクローンを作り、 //残りの処理を_methodに投げるのと同等の処理 //メモリ効率化の為に、使用した数を使用していない数と //場所を交換することでlistを作るのと同等の事を行う。 //ただし、listの中の数の大小関係は保たれない //もう一個配列増やして大小関係維持することも出来るけど、 //遅くなる list[i]=list[n-index-1]; list[n-index-1] = k; index++; memo[index]=0; } } }
