基本情報技術者試験のアルゴリズムをbashで解いてみた。

■基本情報技術者試験のアルゴリズムをbashで解いてみた。
　以下より、すぐにプログラム可能な問題3つを対象とする。

$ w3m -dump http://kanauka.com/category/fe_3_10_26_72.html | grep "○ \|☆ "
          ☆ アルゴリズム(8件)
              ○ 平成21年度春季問題7：2分探索法
              ○ 平成21年度春季問題8：関数の計算
              ○ 平成21年度秋季問題6：クイックソートの処理方法
              ○ 平成22年度春季問題6：ハッシュ表探索
              ○ 平成23年度特別問題6：関数
              ○ 平成23年度特別問題7：流れ図
              ○ 平成23年度特別問題8：クイックソート
              ○ 平成23年度秋季問題7：配列の並び替え


■平成23年度特別問題　問題6

　http://kanauka.com/kakomon/fe/h23t/006.html

関数 f(x，y)が次のように定義されているとき，f(775，527)の値は幾らか。
ここで，x mod yはxをyで割った余りを返す。

f(x, y): if y = 0 then return x else return f(y, x mod y)

■単純な再帰。計算は先に行う。

$ cat f.sh 
#!/bin/bash

if [ $# -ne 2 ];then
  echo "Usage: $0 x y" >&2
  echo "x,y is number" >&2
  exit 1
fi
x=$1
y=$2

if [ "$y" -eq "0" ];then
   echo "return $x"
else
   tmp=$y
   y=$(($x%$y)) 
   echo "/bin/bash f.sh $tmp $y" | `xargs`
fi

$ /bin/bash -x f.sh 775 527
+ '[' 2 -ne 2 ']'
+ x=775
+ y=527
+ '[' 527 -eq 0 ']'
+ tmp=527
+ y=248
+ echo '/bin/bash f.sh 527 248'
++ xargs
+ /bin/bash f.sh 527 248
return 31

■平成23年度特別問題　問題7

　http://kanauka.com/kakomon/fe/h23t/007.html

■「計算するだけで『終了』なの？」というツッコミは置いておいて。。。
　1から100までの総和を求める計算。
　x=0とする。

$ cat souwa.sh 
#!/bin/bash

x=0
i=1
while [ $i -le 100 ];do
  let x=$x+$i
  let i=$i+1
done
echo $x

$ /bin/bash souwa.sh
5050

■平成23年度秋季問題　問題7

　http://kanauka.com/kakomon/fe/h23a/007.html

■単語の配列の入れ方。

$ sudo apt-get install -y wamerican
$ look en* | grep -v \' | head -5
Encarta
Endymion
Eng
Engels
England

$ TANGO=("" ` look en* | grep -v \' | head -5`)
$ echo ${TANGO[@]}
Encarta Endymion Eng Engels England

$ echo ${TANGO[0]}

■仮に「n=3」と置いて、入れ替え。
　「0番目の配列を使うのに消さないんだ。で、終了後は表示しないの？」は置いといて。。。

　TANGO[i]->TABGO[i+1]に入れる。
　while文の書き方は問題文とは異なる。

$ cat tango.sh 
#!/bin/bash

TANGO=("" ` look en* | grep -v \' | head -5`)
echo ${TANGO[@]}

n=3
TANGO[0]=${TANGO[$n]}
let i=$n-1
while [ $i -ge 0 ];do
  TANGO[$(($i+1))]=${TANGO[$i]}
  let i=$i-1
done
TANGO[0]=""
echo ${TANGO[@]}
$ /bin/bash -x tango.sh
+ TANGO=("" ` look en* | grep -v \' | head -5`)
++ grep -v ''\'''
++ look 'en*'
++ head -5
+ echo Encarta Endymion Eng Engels England
Encarta Endymion Eng Engels England
+ n=3
+ TANGO[0]=Eng
+ let i=3-1
+ '[' 2 -ge 0 ']'
+ TANGO[$(($i+1))]=Endymion
+ let i=2-1
+ '[' 1 -ge 0 ']'
+ TANGO[$(($i+1))]=Encarta
+ let i=1-1
+ '[' 0 -ge 0 ']'
+ TANGO[$(($i+1))]=Eng
+ let i=0-1
+ '[' -1 -ge 0 ']'
+ TANGO[0]=
+ echo Eng Encarta Endymion Engels England
Eng Encarta Endymion Engels England