Project Euler : Problem 39 『Integer right triangles』

問題

projecteuler.net
日本語→Problem 39 - PukiWiki

周長から斜辺以外の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;
        }
    }
}