Cマガ電脳クラブ(第056回) 加算連鎖

問題

数Aがある。Aの倍数を作りたいのだが、あいにく足し算しか使えない。
途中で作った数はそのあと使うことができるものとして、足し算の回数をできるだけ減らしたい。
例えば21倍を作るなら、
 A+A=2A
 A+2A=3A
 2A+3A=5A
 5A+5A=10A
 A+10A=11A
 10A+11A=21A
のように6回の足し算が必要である。ほかにもやり方はあるが、どうやっても5回以下ではできない。
さて、足し算10回まででは作れない最小の倍数は何倍だろうか。

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    //加算の回数の上限
    const int LimitAddCnt = 10;

    struct JyoutaiDef
    {
        internal int AddCnt;
        internal List<string> AddLog;
        internal HashSet<int> CreatedValSet;
    }

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.AddCnt = 0;
        WillPush.AddLog = new List<string>();
        WillPush.CreatedValSet = new HashSet<int>() { 1 };
        stk.Push(WillPush);

        var UnionCreatedValSet = new HashSet<int>();
        int CombiCnt = 0;
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            if (Popped.AddCnt == LimitAddCnt) {
                if (++CombiCnt % 1000000 == 1) {
                    Console.WriteLine("{0}個目の加算の組み合わせを発見。経過時間={1}",
                         CombiCnt, sw.Elapsed);
                    var sb = new System.Text.StringBuilder();
                    Popped.AddLog.ForEach(X => sb.AppendLine(X));
                    Console.WriteLine(sb.ToString());
                }
                UnionCreatedValSet.UnionWith(Popped.CreatedValSet);
                continue;
            }

            //Push処理
            Action<int, int, int> PushSyori = (pWK1, pWK2, pSum) =>
            {
                WillPush.AddCnt = Popped.AddCnt + 1;
                string WkLog = string.Format("{0}+{1}={2}", pWK1, pWK2, pSum);
                WillPush.AddLog = new List<string>(Popped.AddLog) { WkLog };
                WillPush.CreatedValSet = new HashSet<int>(Popped.CreatedValSet) { pSum };
                stk.Push(WillPush);
            };

            int[] wkArr = Popped.CreatedValSet.ToArray();
            int MaxVal = wkArr.Max();
            var wkCreatedValSet = new HashSet<int>(); //作成した和

            for (int I = 0; I <= wkArr.GetUpperBound(0); I++) {
                for (int J = I; J <= wkArr.GetUpperBound(0); J++) {
                    int wkSum = wkArr[I] + wkArr[J];
                    if (wkSum <= MaxVal) continue; //昇順に和を作成していく経路とする
                    if (wkCreatedValSet.Add(wkSum) == false) continue;

                    PushSyori(wkArr[I], wkArr[J], wkSum);
                }
            }
        }
        for (int I = 1; I <= 1024; I++) { //2の10乗 = 1024
            if (UnionCreatedValSet.Contains(I)) continue;
            Console.WriteLine("解は{0}。経過時間={1}", I, sw.Elapsed);
            break;
        }
    }
}

実行結果

省略
9000001個目の加算の組み合わせを発見。経過時間=00:01:14.2006545
1+1=2
1+2=3
2+3=5
2+5=7
7+7=14
7+14=21
3+21=24
2+24=26
5+26=31
24+24=48

10000001個目の加算の組み合わせを発見。経過時間=00:01:22.4590421
1+1=2
1+2=3
1+3=4
4+4=8
1+8=9
9+9=18
4+18=22
3+22=25
18+25=43
1+43=44

解は191。経過時間=00:01:30.0534288

解説

深さ優先探索で発見した作成可能な和を、HashSetジェネリックで管理してます。