■100までの総和を求める計算回数とシェル芸について 「計算量」というと色んな誤解を生むので、「計算回数」にのみ焦点を当てる。 ここで言う「計算回数」とは、ループを何回繰り返すかを指すものとする。 平成23年 春期 基本情報技術者 午前 問07 http://情報処理試験.jp/FE23a-am/k07.html 基本情報技術者 Web学習室 http://www5f.biglobe.ne.jp/pafu/kihonweb/gozen/01/1_1.htm ■前振りとして、以下の疑似言語をそのまま実装してみる。 ・ 0 -> 数 ・ 0 -> 合計 ■ ｜ ▲ ｜ ｜ 数 + 1 -> 数 \ ｜ ｜ 合計 + 数 -> 合計 \ ｜ ▼ 数 >= 100 ■ ■シェル芸で書くと、数の計算式と合計の計算式の順番を意識する必要が無い。 というより、そんな順番を意識しないと動かない書き方をしない。 $ total=0;for n in `seq 1 100`;do total=$(($total+$n));done;echo $total 5050 $ total=0;for n in `seq 0 100`;do total=$(($total+$n));done;echo $total 5050 ■例えば、疑似言語通りに数の初期値を0にすると、 100以上が終了条件となるので、101回繰り返す。 $ n=0; total=0; \ while : ;do \ n=$(($n+1)); \ total=$(($total+$n)); \ if [ $n -ge 100 ];then break;fi; \ done 5050 $ echo 'n=0; total=0; \ while : ;do \ n=$(($n+1)); \ total=$(($total+$n)); \ if [ $n -ge 100 ];then break;fi; \ done;echo $total' | /bin/bash -x 2>&1 | grep '+ n=' | wc -l 101 ■初期値が1だと101以上を終了条件とする必要があるが、 その場合、数の計算式と合計の計算式を入れ替える必要がある。 $ echo 'n=0; total=0; \ while : ;do \ n=$(($n+1)); \ total=$(($total+$n)); \ if [ $n -ge 100 ];then break;fi; \ done;echo $total' | sed -e 's/n=0/n=1/' | sh 5049 $ echo 'n=0; total=0; \ while : ;do \ n=$(($n+1)); \ total=$(($total+$n)); \ if [ $n -ge 100 ];then break;fi; \ done;echo $total' | sed -e 's/n=0/n=1/' -e 's/100/101/' | sh 5150 $ echo 'n=0; total=0; \ while : ;do \ n=$(($n+1)); \ total=$(($total+$n)); \ if [ $n -ge 100 ];then break;fi; \ done;echo $total' | sed -e 's/n=0/n=1/' -e 's/100/101/' | \ /bin/bash -x 2>&1 | grep '+ n=' | wc -l 101 ■数の計算式と合計の計算式を入れ替えると 0からでも1からでも同じ結果を得ることが出来る。 ・ 0 -> 数 ・ 0 -> 合計 ■ ｜ ▲ ｜ ｜ 合計 + 数 -> 合計 \ ｜ ｜ 数 + 1 -> 数 \ ｜ ▼ 数 >= 100 ■ $ echo 'n=0; total=0; \ while : ;do \ total=$(($total+$n)); \ n=$(($n+1)); \ if [ $n -ge 100 ];then break;fi; \ done;echo $total' | sed -e 's/n=0/n=1/' -e 's/100/101/' | sh 5050 $ echo 'n=0; total=0; \ while : ;do \ total=$(($total+$n)); \ n=$(($n+1)); \ if [ $n -ge 100 ];then break;fi; \ done;echo $total' | sed -e 's/100/101/' | sh 5050 ■初期値が0でも1でも結果が変わらないということは、 0から始めた場合、1から始めた場合よりも1回多くなる。 $ echo 'n=0; total=0; \ while : ;do \ total=$(($total+$n)); \ n=$(($n+1)); \ if [ $n -ge 100 ];then break;fi; \ done;echo $total' | sed -e 's/n=0/n=1/' -e 's/100/101/' | \ /bin/bash -x 2>&1 | grep '+ n=' | wc -l 101 $ echo 'n=0; total=0; \ while : ;do \ total=$(($total+$n)); \ n=$(($n+1)); \ if [ $n -ge 100 ];then break;fi; \ done;echo $total' | sed -e 's/100/101/' | \ /bin/bash -x 2>&1 | grep '+ n=' | wc -l 102 ■数の計算式、合計の計算式の順にした場合、 1から開始しないように制限する必要があるが、計算回数は常に同じに出来る。 普段意識して避けるようなこういう書き方が問題になる。 (出題傾向と見つかりにくいバグの両方の意味で) $ echo 'n=0; total=0; \ if [ $n -ne 0 ];then echo "n=$n Error!,You must set n=0" >&2;exit 1;fi while : ;do \ n=$(($n+1)); \ total=$(($total+$n)); \ if [ $n -ge 100 ];then break;fi; \ done;echo $total ' | sh $ echo 'n=0; total=0; \ if [ $n -ne 0 ];then echo "Set n=$n Error!,You must set n=0" >&2;exit 1;fi \ while : ;do \ n=$(($n+1)); \ total=$(($total+$n)); \ if [ $n -ge 100 ];then break;fi; \ done;echo $total ' | sed -e 's/n=0/n=1/' | sh Set n=1 Error!,You must set n=1 ■終了条件を前にすると、以下のようになる。 $ echo 'n=0; total=0; \ while [ $n -le 100 ];do \ total=$(($total+$n)); \ n=$(($n+1)); \ done;echo $total' | sh 5050 $ echo 'n=0; total=0; \ while [ $n -le 100 ];do \ total=$(($total+$n)); \ n=$(($n+1)); \ done;echo $total' | /bin/bash -x 2>&1 | grep '+ n=' | wc -l 102 $ echo 'n=0; total=0; \ while [ $n -le 100 ];do \ total=$(($total+$n)); \ n=$(($n+1)); \ done;echo $total' | sed -e 's/n=0/n=1/' | sh 5050 $ echo 'n=0; total=0; \ while [ $n -le 100 ];do \ total=$(($total+$n)); \ n=$(($n+1)); \ done;echo $total' | sed -e 's/n=0/n=1/' | \ /bin/bash -x 2>&1 | grep '+ n=' | wc -l 101 $ echo 'n=0; total=0; \ while [ $n -le 100 ];do \ n=$(($n+1)); \ total=$(($total+$n)); \ done;echo $total' | sed -e 's/100/99/' | sh 5050 $ echo 'n=0; total=0; \ while [ $n -le 100 ];do \ n=$(($n+1)); \ total=$(($total+$n)); \ done;echo $total' | sed -e 's/100/99/' | \ /bin/bash -x 2>&1 | grep '+ n=' | wc -l 101 ■前判定でも数を1から始めると正しい結果を得られないので、 入力チェックが必要となる。 $ echo 'n=0; total=0; \ while [ $n -le 100 ];do \ n=$(($n+1)); \ total=$(($total+$n)); \ done;echo $total' | sed -e 's/100/99/' -e 's/n=0/n=1/' | sh 5049 $ echo 'n=0; total=0; \ while [ $n -le 100 ];do \ n=$(($n+1)); \ total=$(($total+$n)); \ done;echo $total' | sed -e 's/100/99/' -e 's/n=0/n=1/' | \ grep n=1 > /dev/null 2>&1 && echo "Error!" Error! ■ところで、終了条件のために1多く数える必要のないシェル芸では、 計算回数は上記のアルゴリズムより1回少ない。 (コンパイル言語と速度で争う気はありません。) $ echo 'total=0;for n in `seq 1 100`;do total=$(($total+$n));done;echo $total' | \ /bin/bash -x 2>&1 | grep '+ for n in' | wc -l 100 $ echo 'total=0;for n in `seq 1 100`;do total=$(($total+$n));done;echo $total' | \ sed -e 's/seq 1/seq 0/' | \ /bin/bash -x 2>&1 | grep '+ for n in' | wc -l 101 ■再帰の場合も計算回数はシェル芸と同じ。 $ echo '(defun fact (n)(if (= n 1) n (+ n (fact (- n 1)))))(trace fact)(fact 100)' | \ clisp -q | grep 'Trace: FACT' | wc -l 100 $ echo '(defun fact (n)(if (= n 0) n (+ n (fact (- n 1)))))(trace fact)(fact 100)' | \ clisp -q | grep 'Trace: FACT' | wc -l 101 ■もう、どうでもいいことだけれど、引き算でも表せる。 終了条件を複数にすれば良いとしても、 初期値の数にマイナスの数を想定しないといけない場合や ひねくれた考えを求められた場合以外はやらない。 ・ 100 -> 数 ・ 0 -> 合計 ■ ｜ ▲ ｜ ｜ 合計 + 数 -> 合計 \ ｜ ｜ 数 - 1 -> 数 \ ｜ ▼ 数 <= 0 ■ $ echo 'n=100; total=0; \ while : ;do \ total=$(($total+$n)); \ n=$(($n-1)); \ if [ $n -le 0 ];then break;fi done;echo $total' | sh 5050 $ echo 'n=100; total=0; \ while : ;do \ total=$(($total+$n)); \ n=$(($n-1)); \ if [ $n -le 0 ];then break;fi done;echo $total' | /bin/bash -x 2>&1 | grep '+ n=' | wc -l 101 $ echo 'n=100; total=0; \ while : ;do \ total=$(($total+$n)); \ n=$(($n-1)); \ if [ $n -le 0 ];then break;fi done;echo $total' | sed -e 's/le 0/lt 1/' | sh 5050 ■終了条件が残っている再帰もマイナスを扱う際には同じように考慮する必要があります。 $ echo '(defun fact (n)(if (= n 0) n (+ n (fact (+ n 1)))))(trace fact)(fact -100)' | \ clisp -q | tail -1 -5050 ■終了条件という考え方を止めれば簡単になるのが、シェル芸の良いところだと思う。 $ total=0;for n in `seq -100 -1`;do total=$(($total+$n));done;echo $total -5050 $ total=0;for n in `seq -100 0`;do total=$(($total+$n));done;echo $total -5050
