階段で立ち話

awkネタ

ある階段を下からAさんが上がっていくと同時に、上からBさんが降りてきます。
階段は1段ずつ上がる(降りる)必要はなく、最大で3段まで飛ばして進む(一気に
4段進む)ことが出来ます。
ただし、何段飛ばすときも、1回の移動にかかる時間は同じとします。2人が同時
に1回ずつ移動する時、「2人が同じ段に止まるような動き方」が何通りあるかを
考えます。(階段は十分な幅があり、すれ違うことが出来ますので、ぶつかること
はありません。また、同じ段に止まった時点で移動は終了するものとします)
例えば、4段の階段があったとき、次の4通りがあります

	A	B	移動方法
(1)	0→1→2	4→3→2	A,Bともに1段ずつ移動
(2)	0→1	4→1	Aは1段移動、Bは2段飛ばして移動
(3)	0→2	4→2	A,Bともに1段飛ばして移動
(4)	0→3	4→3	Aは2段飛ばして移動、Bは1段移動

10段の階段で同じように移動したとき、2人が同じ段に止まるのは何通りあるかを
求めてください

AがBよりも上の段に達した場合は探索を止めます。

#!/usr/bin/awk -f

BEGIN{
    N = 10;         # 階段の段数
    STEPS = 4;      # 一気に進める段数

    # Aさんは0の位置から、BさんはNの位置からスタート
    print move(0, N);
}


function move(a, b,cnt,da,db){
    if(a > b){      # AさんがBさんよりも上になれば
        return 0;   # 終了
    }
    if(a == b){     # 同じ段に止まれば
        return 1;   # カウント
    }
    cnt = 0;
    for(da = 1; da <= STEPS; da++){
        for(db = 1; db <= STEPS; db++){
            cnt += move(a + da, b - db);
        }
    }
    return cnt;
}

今回も再帰処理です。
仮引数にcnt,da,dbを入れるのを忘れないでください。
実行してみます。

awk -f q15.awk 
201

沢山ありますね。