3本のひもで作る四角形

awk

awkネタ

同じ長さの3本のひもを折り曲げて３つの四角形を作ります。
そのうち2本でそれぞれ長方形を作り、残りの1本は正方形を作ります。
このとき、作った２つの長方形の面積の和が、正方形の面積と同じになることがあります。
(ただし、いずれの長方形、正方形も辺の長さは整数)

例)紐の長さが20の時
1本目　縦1×横9の長方形→面積=9
2本目　縦2×横8の長方形→面積=16
3本目　縦5×横5の正方形→面積=25

さらに、ひもの長さを変えてできる長方形と正方形の組をカウントします。
ただし、同じ比で整数倍のものは１つとしてカウント
例)紐の長さが40の時
1本目　縦2×横18の長方形→面積=36
2本目　縦4×横16の長方形→面積=64
3本目　縦10×横10の正方形→面積=100
紐の長さが60の時
1本目　縦3×横27の長方形→面積=81
2本目　縦6×横24の長方形→面積=114
3本目　縦15×横15の正方形→面積=225

紐の長さを1から500まで変化させる時、２つの長方形の面積の和と
正方形の面積が同じなる組が何通りあるか？

簡単に見えてやってみたら難しかったです。
ポイントは下記の通りです。

  • 正方形の1辺は紐の長さの4分の1
  • 縦の長さが決まると、横の長さは紐の長さを2で割って、縦の長さを引く
  • 縦の長さは正方形の1辺よりも短くする。
#!/usr/bin/awk -f

BEGIN{
    N = 500;
    c = 0;
    for(i = 1; i <= N; i++){
        yoko = 0;
        if(i % 4 == 0){                         # 正方形の1辺は整数
            seihou = i / 4;                     # 正方形の1辺はひもの長さの1/4
            for(tate = 1; tate < seihou; tate++){   # 縦の長さは正方形の1辺よりも短くする
                if(i % 2 == 0){                 # 横の長さは整数
                    yoko = i / 2 - tate;        # 横の長さ
                    for(tate2 = 1; tate2 < seihou; tate2++){    #2本目の縦の長さ
                        yoko2 = i / 2 - tate2;                  # 2本目の横の長さ
                        # 正方形の面積は1本目と2本目の長方形面積の和
                        if(seihou * seihou == tate * yoko + tate2 * yoko2){ 
                            c++;
                            answer[c] = seihou * seihou;    # 正方形の面積
                            one[c] = tate * yoko;           # 最初の長方形
                            two[c] = tate2 * yoko2;         # 2本目の長方形
                        }
                    }
                }
            }
        }
    }
    len =  length(answer);          # 配列の個数
    for(i = 1; i <= len; i++){
        for(j = i + 1; j <= len; j++){
            if(one[i]){
                num = one[j] / one[i];          # 1つ目長方形同士の整数倍
                if(two[i] && two[j] / two[i] == num){ # 2つ目長方形同士の整数場
                    if(answer[i] && answer[j] / answer[i] ==  num){ # 正方形同士の整数倍
                        delete answer[j];
                    }
                }
            }
        }
    }
    for(k in answer){
        if(answer[k]){      # 削除されていない配列の個数
            count++;
        }
    }
    print count / 2;        # 縦と横を入れ替えたものを除外
}

実行してみます。

awk -f q16.awk
20

rubyとかだと、ライブラリが揃っているので、もっと短く出来るかもしれません。
awkを使ったアルゴリズムの勉強なので、これで良しとします。