Problem122 効率的なべき乗計算

問題

nの15乗を求めるのに最も単純な方法では 14 回の掛け算が必要である.
n * n * ・・・ * n = nの15乗

しかし2進法を用いれば, 6 回の掛け算で計算できる.
n * n = nの2乗
nの2乗 * nの2乗 = nの4乗
nの4乗 * nの4乗 = nの8乗
nの8乗 * nの4乗 = nの12乗
nの12乗 * nの2乗 = nの14乗
nの14乗 * n = nの15乗

ところがたった 5 回の掛け算のみでも計算できる.
n * n = nの2乗
nの2乗 * n = nの3乗
nの3乗 * nの3乗 = nの6乗
nの6乗 * nの6乗 = nの12乗
nの12乗 * nの3乗 = nの15乗

m(K) を nのK乗を求めるのに必要最低限な掛け算の回数と定義する.
たとえば m(15) = 5 である.

1 <= K <= 200 に対し、シグマ m(K) を求めよ.

ソース

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

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

        int Answer = 0;
        int PrevM = 0;
        for (int I = 1; I <= 200; I++) {
            int CurrM = DeriveM(I, PrevM);
            Console.WriteLine("m({0})={1}。経過時間={2}", I, CurrM, sw.Elapsed);
            Answer += CurrM;
            PrevM = CurrM;
        }
        Console.WriteLine("Answer={0}", Answer);
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal HashSet<int> ValSet;
    }

    static int DeriveM(int pK, int pPrevM)
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.ValSet = new HashSet<int>();
        WillPush.ValSet.Add(1);
        Stk.Push(WillPush);

        int AnswerLevel = pPrevM + 1;
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //クリア判定
            if (Popped.ValSet.Contains(pK)) {
                if (Popped.Level < AnswerLevel)
                    AnswerLevel = Popped.Level;
                continue;
            }

            //下限値枝切り
            if (AnswerLevel <= Popped.Level + 1)
                continue;


            int[] wkArr = Popped.ValSet.OrderBy(X => X).ToArray();
            int MaxVal = wkArr.Max();

            foreach (int EachInt1 in wkArr) {
                //大きい数は無駄
                if (pK < EachInt1 * 2) break;

                foreach (int EachInt2 in wkArr) {
                    if (EachInt2 < EachInt1) continue;

                    int NewVal = EachInt1 + EachInt2;

                    //大きい数は無駄
                    if (pK < NewVal) break;

                    //昇順に作成していく
                    if (NewVal < MaxVal) continue;

                    if (Popped.ValSet.Contains(NewVal))
                        continue;

                    WillPush.Level = Popped.Level + 1;
                    WillPush.ValSet = new HashSet<int>(Popped.ValSet);
                    WillPush.ValSet.Add(NewVal);
                    Stk.Push(WillPush);
                }
            }
        }
        return AnswerLevel;
    }
}

実行結果

m(190)=10。経過時間=00:01:28.2566784
m(191)=11。経過時間=00:02:18.7473692
m(192)=8。経過時間=00:02:18.7649785
m(193)=9。経過時間=00:02:18.9376300
m(194)=9。経過時間=00:02:19.1127581
m(195)=9。経過時間=00:02:19.2877589
m(196)=9。経過時間=00:02:19.4636268
m(197)=10。経過時間=00:02:22.1859892
m(198)=9。経過時間=00:02:22.3603005
m(199)=10。経過時間=00:02:25.1153621
m(200)=9。経過時間=00:02:25.2896301
Answer=1582

解説

Kが1小さいときのm(K)の値を
深さ制限としての、深さ優先探索を繰り返してます。