桃の天然水 このページをアンテナに追加

2017-07-23

[]BashProject Euler(9) 再帰 BashでProject Euler(9) 再帰を含むブックマーク BashでProject Euler(9) 再帰のブックマークコメント

前回の例にあるように関数はふつうに再帰できます。

gcd() {
    local n=$1
    local m=$2
    if [ $n -eq 0 ]; then
        echo $m
    elif [ $m -eq 0 ]; then
        echo $n
    else
        local d=`gcd $m $((n%m))`
        echo $d
    fi
}

d=`gcd 110 150`
echo $d     # 10

Pythonのジェネレータっぽいのもできます。実際には全然遅延評価していませんが。

#!/bin/bash

combinations() {
    a=()
    while [ $# -gt 1 ]; do
        a+=($1)
        shift
    done
    n=$1
    if [ $n -eq 1 ]; then
        for e in ${a[@]}; do
            echo $e
        done
    else
        m=${#a[@]}
        for((i=0; i<=$m-$n; ++i)); do
            for s in `combinations ${a[@]:i+1:m} $((n-1))`; do
                echo ${a[i]},$s
            done
        done
    fi
}

combinations 2 3 4 5 6 7 3

最後に、分割統治法の例として、マージソートを書いてみましょう。

#!/bin/bash

merge_sort() {
    local a=($@)
    L=${#a[@]}
    if [ $L -eq 1 ]; then
        echo $1
    else
        mid=$((L/2))
        b=(`merge_sort ${a[@]:0:mid}`)
        c=(`merge_sort ${a[@]:mid}`)
        L1=${#b[@]}
        L2=${#c[@]}
        k=0
        l=0
        while((k < L1 && l < L2)); do
            n1=${b[k]}
            n2=${c[l]}
            if((n1 <= n2)); then
                echo $n1
                ((k += 1))
            fi
            if((n1 >= n2)); then
                echo $n2
                ((l += 1))
            fi
        done
        
        for(( ; k < L1; ++k)); do
            echo ${b[k]}
        done
        for(( ; l < L2; ++l)); do
            echo ${c[l]}
        done
    fi
}

merge_sort 4 1 7 2 5 6 3

2017-05-27

[]BashProject Euler(8) 二次元配列 BashでProject Euler(8) 二次元配列を含むブックマーク BashでProject Euler(8) 二次元配列のブックマークコメント

Bashには二次元配列はもちろんありません。それらしいことを実現するにはかつてのPerl4のように例えばカンマで区切るようなことをしなければなりません。

#!/bin/bash

N=$1
table=()
for y in `seq 1 $N`; do
    b=()
    for x in `seq 1 $N`; do
        b+=($((x*y)))
    done
    table+=(`echo ${b[@]} | tr -s ' ' ','`)
done

for v in ${table[@]}; do
    echo $v
done

s=0
for((i=0; i<N; ++i)); do
    a=(`echo ${table[$i]} | tr -s ',' ' '`)
    let s+=${a[$i]}
done
echo $s

上は、九九(引数が9なら)の表を作って、対角成分の和を取っています。

1行分の配列を作って、trコマンドでカンマ区切りの文字列にして配列の要素にします。逆に要素を取り出すときは、trコマンドでスペース区切りにして配列にします。


これで、Problem 9が解けます。この問題は真面目に解くと素因数分解が必要です。それを二次元配列で表します。例えば、48=2^3*3は、

2,3 3,1

と表します。

続きを読む

2017-05-20

[]BashProject Euler(7) 配列 BashでProject Euler(7) 配列を含むブックマーク BashでProject Euler(7) 配列のブックマークコメント

Bashに配列はあります。ただ、とても遅いです。

white spaceで区切って()で括ると配列になります。

#!/bin/bash

a=(1 2)
a+=(3)
echo ${a[@]}    # 1 2 3

a+=(3)は、見た通り要素を追加しています。

これは本当に追加なのでしょうか。多くの要素を追加して、経過時間を調べればだいたいわかります。

#!/bin/bash

N=$1
a=()
for n in `seq 1 $N`; do
    a+=($n)
done

これを、引数を変えてtimeで時間計測すると

arg    100000  1000000 10000000
real 0m0.656s 0m6.357s 1m4.420s

線形のようですね。

ちなみに、構築だけならこのほうが速いです。

#!/bin/bash

N=$1
a=(`seq 1 $N`)

3倍くらい速かったです。

参照は、次のようにします。

a=(1 2 3 4 5)
echo ${a[0]}    # 1

他の参照方法は、

echo ${a[@]}        # 1 2 3 4 5
echo ${a[@]:1:3}    # 2 3 4

2つ目は、0-baseの開始位置と長さを指定しています。

値の代入は、

a[1]=3

これで、Problem 7が解けます。エラトステネスの篩のややこしいバージョンになっていますが。

続きを読む