Pongeponge

Project Euler : Problem 39 『Integer right triangles』

〇△□(まるさんかくしかく)のくにのおうさま (PHPにこにこえほん)


周長から斜辺以外の1辺を求める

直角三角形の各辺をa,b,cとする(cは斜辺)、周長をpとすると、
a+b+c=p    (1)
となる。


 斜辺cはピタゴラスの定理により
c = \sqrt{\mathstrut a^{2}+b^{2}}
よって(1)は
a + b + \sqrt{\mathstrut a^{2}+b^{2}} = p    (2)
となる。


 pとaの値が決まっていてbを求めたい場合、(2)から
\sqrt{\mathstrut a^{2} + b^{2}} = p - a - b
a^{2} + b^{2} = (p - a - b)^{2}    (3)
a^{2} + b^{2} = p^{2} + a^{2} + b^{2} - 2pa - 2pb + 2ab


0 = p^{2} - 2pa - 2pb + 2ab
p^{2} - 2pa + 2b(a - p) = 0
2b(a - p) = -p^{2} + 2pa


b = \frac{-p^{2} + 2pa}{2(a - p)}
b = \frac{p(2a - p)}{2(a - p)}    (4)


というわけで(4)式を使ってbの値を決めることができる。


三角形になるかどうかの判定

 p, a,それとさっき求めたbの値を使って三角形になるかどうかの判定は(3)式を使う


コード
using System.Diagnostics;

namespace Problem39
{
    class Program
    {
        static void Main(string[] args)
        {
            P39 p = new P39();
            Debug.WriteLine(p.Solve());
        }
    }

    class P39
    {
        /// <summary>
        /// コンストラクタ
        /// </summary>
        public P39()
        {

        }

        /// <summary>
        /// 解く
        /// </summary>
        /// <returns></returns>
        public int Solve()
        {
            int maxPatternCount = 0;
            int maxP = 1;

            for (int p = 1; p <= 1000; p++)
            {
                int patternCount = SetSides(p);

                if (patternCount > maxPatternCount)
                {
                    maxPatternCount = patternCount;
                    maxP = p;
                }
            }

            return maxP;
        }

        /// <summary>
        /// 斜辺以外の辺を決める
        /// </summary>
        /// <param name="p">週長</param>
        /// <returns>三角形になるパターン数</returns>
        private int SetSides(int p)
        {
            int patternCount = 0;

            for (int a = 1; a < p / 2; a++)
            {
                int b = (p * (2 * a - p)) / (2 * (a - p));

                if (a > b) break;

                if (IsMakeTriangle(p, a, b) == true)
                {
                    patternCount++;
                }
            }

            return patternCount;
        }

        /// <summary>
        /// 三角形になるか?
        /// </summary>
        /// <param name="p">周長</param>
        /// <param name="a">辺1</param>
        /// <param name="b">辺2</param>
        /// <returns></returns>
        private bool IsMakeTriangle(int p, int a, int b)
        {
            if (a * a + b * b == (p - a - b) * (p - a - b))
            {
                //Debug.WriteLine(string.Format("{0},{1},{2}:{3}", a, b, a * a + b * b, a + b + Math.Sqrt(a * a + b * b)));
                return true;
            }

            return false;
        }
    }
}
答え

840
思ったより多い。



キクタニ トライアングル 15cm 打棒・吊り皮付き T-15

キクタニ トライアングル 15cm 打棒・吊り皮付き T-15

エーモン 三角停止板 国家公安委員会認定品(交F08-1) 6648

エーモン 三角停止板 国家公安委員会認定品(交F08-1) 6648

まる・さんかく・しかく

まる・さんかく・しかく