トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

Cマガ電脳クラブ(第130回) こだ割り数

問題

ここにあげた整数は、「左端からN桁で切ってできる数はすべてNで割りきれる」という性質を持つ。
 7620543270
実際、たとえば762は3で、7620543は7で、7620543270は10で割りきれるのがわかる。
このような数を「こだ割り数」と呼ぶことにする。最大のこだ割り数はいくつだろうか。
なお,左端の数字に0(ゼロ)は使えない。


ソース

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

class Program
{
    struct JyoutaiDef
    {
        internal int KetaSuu;
        internal decimal CurrVal;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.KetaSuu = 1;
        for (int I = 1; I <= 9; I++) {
            WillPush.CurrVal = I;
            stk.Push(WillPush);
        }

        int MaxKeta = 0;

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

            if (MaxKeta <= Popped.KetaSuu) {
                MaxKeta = Popped.KetaSuu;
                Console.WriteLine("{0}桁の解{1}を発見", Popped.KetaSuu, Popped.CurrVal);
            }

            for (int I = 0; I <= 9; I++) {
                WillPush.KetaSuu = Popped.KetaSuu + 1;
                WillPush.CurrVal = Popped.CurrVal * 10 + I;
                if (WillPush.CurrVal % WillPush.KetaSuu == 0)
                    stk.Push(WillPush);
            }
        }
    }
}


実行結果

省略
20桁の解96685896604836004260を発見
21桁の解966858966048360042609を発見
22桁の解9668589660483600426096を発見
22桁の解9068584050968400006092を発見
22桁の解8468047260244656728072を発見
22桁の解7412580810843600420006を発見
22桁の解7264565640241056724082を発見
23桁の解72645656402410567240820を発見
23桁の解40285216807290082800921を発見
24桁の解402852168072900828009216を発見
24桁の解360852885036840078603672を発見
25桁の解3608528850368400786036725を発見


解説

Decimal型で値を管理してます。

Int型の配列を使用したソースは、第069回 こだ割り数で扱ってます。
(第069回と第130回は、同じ問題であるため)