■基本情報技術者試験のアルゴリズムを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
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
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
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