Q16 3本のひもで作る四角形

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    struct TyouhoukeiInfo
    {
        internal int YokoHaba;
        internal int TateHaba;
    }

    struct AnswerDef
    {
        internal int SeihoukeiHaba;
        internal TyouhoukeiInfo Tyouhoukei1;
        internal TyouhoukeiInfo Tyouhoukei2;
    }
    static List<AnswerDef> AnswerList = new List<AnswerDef>();

    static void Main()
    {
        int AnswerCnt = 0;
        for (int I = 1; I <= 500; I++) {
            //正方形の面積
            if (I % 4 > 0) continue;
            int wkSeihoukeiHaba = I / 4;
            int MensekiSeihoukei = wkSeihoukeiHaba * wkSeihoukeiHaba;

            TyouhoukeiInfo[] KouhoTyouhoukeiArr = DeriveKouhoTyouhoukeiArr(I);

            int UB = KouhoTyouhoukeiArr.GetUpperBound(0);

            Func<TyouhoukeiInfo, int> DeriveMenseki = pTyouhoukeiInfo =>
                pTyouhoukeiInfo.TateHaba * pTyouhoukeiInfo.YokoHaba;

            for (int J = 0; J <= UB; J++) {
                int MensekiTyouhoukei1 = DeriveMenseki(KouhoTyouhoukeiArr[J]);
                for (int K = J + 1; K <= UB; K++) {
                    int MensekiTyouhoukei2 = DeriveMenseki(KouhoTyouhoukeiArr[K]);
                    if (MensekiTyouhoukei1 + MensekiTyouhoukei2 != MensekiSeihoukei)
                        continue;

                    AnswerDef wkAnswer;
                    wkAnswer.SeihoukeiHaba = wkSeihoukeiHaba;
                    wkAnswer.Tyouhoukei1 = KouhoTyouhoukeiArr[J];
                    wkAnswer.Tyouhoukei2 = KouhoTyouhoukeiArr[K];
                    if (AddAnswer(wkAnswer) == false) continue;

                    Console.Write("解{0}を発見。", ++AnswerCnt);
                    Console.WriteLine("長方形1は{0}*{1}。長方形2は{2}*{3}。正方形の一辺={4}",
                        KouhoTyouhoukeiArr[J].YokoHaba, KouhoTyouhoukeiArr[J].TateHaba,
                        KouhoTyouhoukeiArr[K].YokoHaba, KouhoTyouhoukeiArr[K].TateHaba,
                        wkSeihoukeiHaba);
                }
            }
        }
    }

    //紐の長さを引数として、作成可能な長方形の配列を返す
    static TyouhoukeiInfo[] DeriveKouhoTyouhoukeiArr(int pHimoLen)
    {
        var KouhoTyouhoukeiList = new List<TyouhoukeiInfo>();
        for (int LoopYokoHaba = 1; LoopYokoHaba * 2 <= pHimoLen; LoopYokoHaba++) {
            int RestLen = pHimoLen - LoopYokoHaba * 2;
            if (RestLen % 2 > 0) continue;
            if (RestLen == 0) continue;
            int wkTateHaba = RestLen / 2;

            //長方形の横幅 <= 長方形の縦幅とする 
            if (LoopYokoHaba > wkTateHaba) continue;

            KouhoTyouhoukeiList.Add(
                new TyouhoukeiInfo() { YokoHaba = LoopYokoHaba, TateHaba = wkTateHaba });
        }
        return KouhoTyouhoukeiList.ToArray();
    }

    //既存解の整数倍でなければ、解を追加
    static bool AddAnswer(AnswerDef pAnswer)
    {
        foreach (AnswerDef EachAnswer in AnswerList) {
            if (pAnswer.SeihoukeiHaba % EachAnswer.SeihoukeiHaba > 0)
                continue;
            int Ratio = pAnswer.SeihoukeiHaba / EachAnswer.SeihoukeiHaba;

            if (EachAnswer.Tyouhoukei1.TateHaba * Ratio == pAnswer.Tyouhoukei1.TateHaba
             && EachAnswer.Tyouhoukei1.YokoHaba * Ratio == pAnswer.Tyouhoukei1.YokoHaba
             && EachAnswer.Tyouhoukei2.TateHaba * Ratio == pAnswer.Tyouhoukei2.TateHaba
             && EachAnswer.Tyouhoukei2.YokoHaba * Ratio == pAnswer.Tyouhoukei2.YokoHaba) {
                return false;
            }
        }
        AnswerList.Add(pAnswer);
        return true;
    }
}

実行結果

解1を発見。長方形1は1*9。長方形2は2*8。正方形の一辺=5
解2を発見。長方形1は1*25。長方形2は8*18。正方形の一辺=13
解3を発見。長方形1は2*32。長方形2は9*25。正方形の一辺=17
解4を発見。長方形1は1*49。長方形2は18*32。正方形の一辺=25
解5を発見。長方形1は8*50。長方形2は9*49。正方形の一辺=29
解6を発見。長方形1は2*72。長方形2は25*49。正方形の一辺=37
解7を発見。長方形1は1*81。長方形2は32*50。正方形の一辺=41
解8を発見。長方形1は8*98。長方形2は25*81。正方形の一辺=53
解9を発見。長方形1は1*121。長方形2は50*72。正方形の一辺=61
解10を発見。長方形1は2*128。長方形2は49*81。正方形の一辺=65
解11を発見。長方形1は9*121。長方形2は32*98。正方形の一辺=65
解12を発見。長方形1は18*128。長方形2は25*121。正方形の一辺=73
解13を発見。長方形1は1*169。長方形2は72*98。正方形の一辺=85
解14を発見。長方形1は8*162。長方形2は49*121。正方形の一辺=85
解15を発見。長方形1は9*169。長方形2は50*128。正方形の一辺=89
解16を発見。長方形1は25*169。長方形2は32*162。正方形の一辺=97
解17を発見。長方形1は2*200。長方形2は81*121。正方形の一辺=101
解18を発見。長方形1は18*200。長方形2は49*169。正方形の一辺=109
解19を発見。長方形1は1*225。長方形2は98*128。正方形の一辺=113
解20を発見。長方形1は8*242。長方形2は81*169。正方形の一辺=125

解説

紐の長さごとに、作成可能な長方形を列挙してます。