LoginSignup
1

More than 3 years have passed since last update.

【C#】Project euler 61問目

Last updated at Posted at 2020-01-17

はじめに

C#を用いてProjectEulerに挑戦している人の記録です。VisualStudio2017で、1つのフォームアプリの中に問題番号のボタンを作成し、そのボタンをクリックすると結果をラベルに表示するという形式でやっています。

詰まって期間が空きました。あきらめかけていましたが何とかできました。

61問目

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.

三角数

P_{3,n} = \frac {n(n+1)}{2} \\
1, 3, 6, 10, 15, ...

四角数

P_{4,n} = n^2 \\
1, 4, 9, 16, 25, ...

五角数

P_{5,n} = \frac {n(3n-1)}{2} \\
1, 5, 12, 22, 35, ...

六角数

P_{5,n} = n(2n-1) \\
1, 6, 15, 28, 45, ...

七角数

P_{5,n} = \frac {n(5n-3)}{2} \\
1, 7, 18, 34, 55, ...

八角数

P_{5,n} = n(3n-2) \\
1, 8, 21, 40, 65, ...

3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.

  1. この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
  2. それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
  3. 4桁の数の組で上の2つの性質をもつはこの組だけである.

三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.

 private void button61_Click(object sender, EventArgs e)
        {
            const int NeedsCornerCnt = 6;
            CalcCorner();

            var stk = new Stack<StackState2>();
            StackState2 WillPush;

            foreach (int Each in cornerDict[3])
            {
                WillPush.cornerList = new List<int>() { 3 };
                WillPush.ValList = new List<int>() { Each };
                stk.Push(WillPush);
            }

            while (stk.Count > 0)
            {
                StackState2 Popped = stk.Pop();

                if (Popped.cornerList.Count == NeedsCornerCnt)
                {
                    for(int i = 0; i < Popped.cornerList.Count; i++)
                    {
                        textBox1.Text = string.Format("{0}角数の{1}", Popped.cornerList[i],Popped.ValList[i]);
                    }
                    label1.Text = string.Format("合計={0}", Popped.ValList.Sum());
                    for(int i=0;i< Popped.cornerList.Count; i++)
                    textBox1.AppendText(string.Format("{0}角数の{1}, ", Popped.cornerList[i], Popped.ValList[i]));
                    continue;
                }

                for (int i = 3; i <= 8; i++)
                {
                    if (Popped.cornerList.Contains(i)) continue;

                    foreach(int Each in cornerDict[i])
                    {
                        int ValsCnt = Popped.ValList.Count;
                        int LastVal = Popped.ValList[ValsCnt - 1];

                        Func<int, int, bool> isVisit = (pLast, pTop) =>
                        {
                              return pLast % 100 == pTop / 100;
                        };

                        if (isVisit(LastVal, Each) == false) continue;
                        if (ValsCnt == NeedsCornerCnt - 1 && isVisit(Each, Popped.ValList[0]) == false) continue;

                        WillPush.cornerList = new List<int>(Popped.cornerList) { i };
                        WillPush.ValList = new List<int>(Popped.ValList) { Each };
                        stk.Push(WillPush);
                    }
                }
            }


        }

        static void CalcCorner()
        {
            Action<List<int>, Func<int, int>> calcCorner = (pList, pFunc) =>
              {
                  int n = 1, Result;
                  do
                  {
                      Result = pFunc(n++);
                      if (1000 <= Result && Result <= 9999) pList.Add(Result);
                  } while (Result <= 9999);
              };
            for (int i = 3; i < 9; i++) cornerDict[i] = new List<int>();

            calcCorner(cornerDict[3], n => n * (n + 1) / 2);
            calcCorner(cornerDict[4], n => n * n);
            calcCorner(cornerDict[5], n => n * (3 * n - 1) / 2);
            calcCorner(cornerDict[6], n => n * (2 * n - 1));
            calcCorner(cornerDict[7], n => n * (5 * n - 3) / 2);
            calcCorner(cornerDict[8], n => n * (3 * n - 2));
        } 

ラムダ式、探索アルゴリズム、まだよくわかっていないので勉強していきます。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1