トップページに戻る    次の増井さんの書籍の問題へ    前の増井さんの書籍の問題へ

Q21 排他的論理和で作る三角形


C#のソース

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

class Program
{
    static void Main()
    {
        int ZeroCnt = 0;
        for (int I = 0; true; I++) {
            int[] PascalSankakukeiArr = DerivePascalSankakukeiArr(I);

            Console.Write("{0}段目 ", I + 1);
            Array.ForEach(PascalSankakukeiArr, X => Console.Write("{0}", X));
            Console.WriteLine();

            ZeroCnt += PascalSankakukeiArr.Count(X => X == 0);
            if (ZeroCnt >= 2014) {
                Console.WriteLine("2014番目の0が出力されるのは{0}段目", I + 1);
                break;
            }
        }
    }

    //パスカルの三角形の指定段目の配列を返す
    static int[] DerivePascalSankakukeiArr(int pLimitY)
    {
        var PascalSankakukeiList = new List<int[]>();
        PascalSankakukeiList.Add(new int[] { 1 });

        for (int LoopY = 1; LoopY <= pLimitY; LoopY++) {
            var CurrLineList = new List<int>();

            for (int LoopX = 0; LoopX <= LoopY; LoopX++) {
                if (LoopX == 0) CurrLineList.Add(1);
                else if (LoopX == LoopY) CurrLineList.Add(1);
                else {
                    int Val1 = PascalSankakukeiList[LoopY - 1][LoopX - 1];
                    int Val2 = PascalSankakukeiList[LoopY - 1][LoopX];
                    CurrLineList.Add(Val1 ^ Val2);
                }
            }
            PascalSankakukeiList.Add(CurrLineList.ToArray());
        }
        return PascalSankakukeiList[pLimitY];
    }
}


実行結果

省略
2014番目の0が出力されるのは75段目


解説

パスカルの三角形を順に求めてます。