2023-02-13

JavaScriptでコラッツ予想

プログラミング算数

　コラッツ予想をJavaScriptで作ってみた。
JavaScriptとか久しぶりに触るから結構忘れてて困った困った。

コラッツ予想

　ある値に対して次の操作をくり返しおこなうと1になる、という予想。

数 n が偶数ならば n / 2
数 n が奇数ならば 3 × n + 1

　言ってることは全然難しくないので小学生でも理解できるけど、未だに証明されていない難問。
たしか、証明に1億円の賞金がかけられていたはず。

コラッツ予想

　数字を入力するとコラッツ操作を実行する(1以上の値でお願い)

結果

コード

<script>
        function CollatzProblem() {
            let result = "";
            let number = document.getElementById("number").value;
            result += number;

            while (number != 1) {
                result += " -> ";
                if (number % 2 == 0) number = number / 2;
                else number = number * 3 + 1;
                result += number;
            }

            document.getElementById("id_result").innerHTML = result;
        }
</script>

<input type="number" min="1" step="1" id="number">
<button onclick="CollatzProblem()">計算</button>


<p id="id_result">結果</p>

コラッツ予想: この未解決問題を解くのは君かもしれない (PINE BOOK 出版)

作者:松友　慶,PINE BOOK 出版

Amazon

永遠についての証明 (角川文庫)

作者:岩井圭也
KADOKAWA

Amazon

コラッツの問題証明と別解へのガイド版: 21世紀の算数整数譜

作者:河﨑弘之

Amazon

2022-12-18

C#で順列を求める

C# プログラミング算数

　組み合わせをやったなら順列もやらんとならんのでやった。
順列の結果だけ見てアルゴリズム自体は自分で考えるので作るのに4日かかった。

コード

using System.Numerics;

public partial class MathPlus
{
    /// <summary>
    /// 順列クラス
    /// </summary>
    public class Permutation
    {
        /// <summary>
        /// 要素の数
        /// </summary>
        private int _n;

        /// <summary>
        /// 選択する個数
        /// </summary>
        private int _k;

        private int[] _elements;

        /// <summary>
        /// 順列の数
        /// </summary>
        public BigInteger Count { get { return this.Permutaton_Count(); } }

        /// <summary>
        /// コンストラクタ
        /// P(n, n)
        /// </summary>
        /// <param name="n">要素の数</param>
        public Permutation(int n)
        {
            this._n = n;
            this._k = n;
            this._elements = Enumerable.Range(1, this._n).ToArray();

        }

        /// <summary>
        /// コンストラクタ
        /// P(n, k)
        /// </summary>
        /// <param name="n">要素の数</param>
        /// <param name="k">選択する個数</param>
        public Permutation(int n, int k)
        {
            this._n = n;
            this._k = k;
            this._elements = Enumerable.Range(1, this._n).ToArray();
        }

        /// <summary>
        /// P(n, k)を計算する
        /// </summary>
        /// <returns>順列 P(n, k) の数</returns>
        private BigInteger Permutaton_Count()
        {
            var numerator = new BigInteger(1);
            var denominator = new BigInteger(1);

            for (int i = 2; i <= this._n; i++)
            {
                numerator *= i;
            }

            for (int i = 2; i <= this._n - this._k; i++)
            {
                denominator *= i;
            }

            return numerator / denominator;
        }

        /// <summary>
        /// 順列の反復子を得る
        /// </summary>
        /// <returns>P(n, k)の反復子</returns>
        public IEnumerable<int[]> GetEnumerable()
        {
            while (true)
            {
                yield return this.Result();

                if (this.IsMaximum()) break;

                this.Update();
            }

            yield break;
        }

        /// <summary>
        /// 順列の配列を更新する
        /// </summary>
        private void Update()
        {
            for (int i = this._k - 1; i >= 0; i--)
            {
                if (this._elements[i] != this._n)
                {
                    var idx = this.SearchNumberIndex(i);

                    if (idx >= 0)
                    {
                        this.Swap(i, idx);
                        this.Sort(i);
                        break;
                    }
                }
            }
        }

        /// <summary>
        /// elements の ihead より後から
        /// elements[ihead] より大きくて最も小さい値をもつインデックスを探す
        /// </summary>
        /// <param name="ihead">arrを参照するインデックス</param>
        /// <returns>インデックス</returns>
        private int SearchNumberIndex(int ihead)
        {
            var n = this._elements[ihead];
            var v = int.MaxValue;
            var idx = -1;

            for (int i = ihead + 1; i < this._elements.Length; i++)
            {
                if (n < this._elements[i] & v > this._elements[i]) {
                    v = this._elements[i];
                    idx = i;
                }
            }

            return idx;
        }

        /// <summary>
        /// 値のスワップ
        /// </summary>
        /// <param name="idx1">交換するインデックス1</param>
        /// <param name="idx2">交換するインデックス2</param>
        private void Swap(int idx1, int idx2)
        {
            var tmp = 0;
            tmp = this._elements[idx1];
            this._elements[idx1] = this._elements[idx2];
            this._elements[idx2] = tmp;
        }

        /// <summary>
        /// arr配列のidxインデックスより後を小さい順にソートする
        /// </summary>
        /// <param name="idx">インデックス</param>
        private void Sort(int idx)
        {
            var elcopy = new int[this._elements.Length - (idx + 1)];

            if(elcopy.Length == 0) return;

            for (int i = 0; i < elcopy.Length; i++)
                elcopy[i] = this._elements[idx + 1 + i];

            Array.Sort(elcopy);

            for (int i = 0; i < elcopy.Length; i++)
                this._elements[idx + 1 + i] = elcopy[i];
        }

        /// <summary>
        /// 順列配列が最大値になっているか判定する
        /// </summary>
        /// <returns>true:最大値, false:非最大値</returns>
        private bool IsMaximum()
        {
            for (int i = 0; i < this._k; i++)
            {
                if (this._elements[i] != (this._n - i)) return false;
            }

            return true;
        }

        /// <summary>
        /// 順列配列からkサイズ切り出す
        /// </summary>
        /// <returns>kサイズ順列配列</returns>
        private int[] Result()
        {
            var r = new int[this._k];

            for (int i = 0; i < r.Length; i++) r[i] = this._elements[i];

            return r;
        }
    }
}

使い方

こんなふうに書くと

var permutation = new MathPlus.Permutation(3, 3);

foreach (var item in permutation.GetEnumerable())
{
    Console.WriteLine($"[{string.Join(",", item)}]");
    Thread.Sleep(10);
}

Console.WriteLine(($"個数:{permutation.Count}"));

こうなる

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
個数:6

なんで再帰使わないの？

　巨大な数突っ込んだら異様なほど遅いからだよ！

2度解く!!確率・順列と組合せ

旺文社

Amazon

順列都市〔上〕

作者:グレッグイーガン
早川書房

Amazon

これならわかる! 図解場合の数と確率

作者:佐藤敏明
ナツメ社

Amazon

2022-12-18

C#で組み合わせのパターンを求める(更新版)

C# プログラミング算数

pongeponge.hatenablog.jp
　前回、説明にもならない説明をポチポチ書いてて「elementsいらんくない？」と思ったので省いた。

using System.Numerics;

public partial class MathPlus
{
    public class Combination
    {
        /// <summary>
        /// 要素の個数
        /// </summary>
        private int _n;

        /// <summary>
        /// 選択する個数
        /// </summary>
        private int _k;

        private int[] _pattern;

        /// <summary>
        /// 組み合わせの数
        /// </summary>
        public BigInteger Count { get { return this.Combination_Count(); } }

        /// <summary>
        /// コンストラクタ
        /// </summary>
        /// <param name="n">要素の個数</param>
        /// <param name="k">選択する個数</param>
        public Combination(int n, int k)
        {
            this._n = n;
            this._k = k;
            this._pattern = Enumerable.Range(1, this._k).ToArray();
        }

        /// <summary>
        /// 組み合わせの数を求める
        /// </summary>
        /// <returns>組み合わせの数</returns>
        private BigInteger Combination_Count()
        {
            var numerator = new BigInteger(1);
            var denominator = new BigInteger(1);
            var n = this._n;
            var k = this._k;
            var tmp = 1L;

            if (this._k > this._n - this._k) k = this._n - this._k;

            for (int count = 1; count <= k; count++)
            {
                numerator *= n;
                n--;

                denominator *= tmp;
                tmp++;
            }

            return numerator / denominator;
        }

        /// <summary>
        /// 組み合わせパターンを得る
        /// </summary>
        /// <returns>組み合わせパターンの反復子</returns>
        public IEnumerable<int[]> GetEnumerable()
        {
            if (this._pattern.Length == 0) yield break;

            while (this._pattern[this._pattern.Length - 1] != this._n + 1)
            {
                yield return this._pattern;

                Update();
            }

            yield break;
        }

        /// <summary>
        /// 参照の更新
        /// </summary>
        private void Update()
        {
            for (int i = this._pattern.Length - 1; i >= 0; i--)
            {
                if (this._pattern[i] != this._n + 1)
                {
                    this._pattern[i]++;

                    for (int r = i + 1; r < this._pattern.Length; r++)
                    {
                        this._pattern[r] = this._pattern[r - 1] + 1;
                    }
                }

                if (this._pattern[this._pattern.Length - 1] != this._n + 1) break;
            }
        }
    }
}

　やっぱりelementsいらんかったわ。

場合の数 2―作業性の特訓書き上げて解く組み合わせ (思考力算数練習張シリーズ 24)

認知工学

Amazon

中学入試分野別集中レッスン算数場合の数 (中学入試分野別集中レッスン)

作者:粟根秀史
文英堂

Amazon

合格する算数の授業数の性質編 (中学受験「だから、そうなのか! 」とガツンとわかる)

作者:松本亘正,教誓健司
実務教育出版

Amazon

2022-12-17

C#で組み合わせのパターンを求める

C# プログラミング算数

　前回は組み合わせの総数を求めた。
今回は組み合わせのパターンを求める。
いやー、yield return 便利ですね。

組み合わせ

　多分中学くらいで学ぶやつ。

例題

例として「1から4が書かれた4枚のカードがある。3枚の組み合わせを全部書き出しなさい」という問題を出されたとする。

　[1, 2, 3, 4]のカードから3枚を選ぶ組み合わせは、次の4通り。

[1, 2, 3] [1, 2, 4] [1, 3, 4] [2, 3, 4]

　重要なのは「組み合わせ」であって、「順序」は関係ないということ。
[1, 2, 3] のカードの組は [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2]と同じものと考える。

コード

　考えてできあがったのがコレ。

using System.Numerics;

public partial class MathPlus
{
    public class Combination
    {
        /// <summary>
        /// 要素の個数
        /// </summary>
        private int _n;

        /// <summary>
        /// 選択する個数
        /// </summary>
        private int _k;

        private int[] _elements;
        private int[] _idxset;

        /// <summary>
        /// 組み合わせの数
        /// </summary>
        public BigInteger Count { get { return this.Combination_Count(); } }

        /// <summary>
        /// コンストラクタ
        /// </summary>
        /// <param name="n">要素の個数</param>
        /// <param name="k">選択する個数</param>
        public Combination(int n, int k)
        {
            this._n = n;
            this._k = k;
            this._elements = Enumerable.Range(1, this._n).ToArray();
            this._idxset = Enumerable.Range(0, this._k).ToArray();

        }

        /// <summary>
        /// 組み合わせの数を求める
        /// </summary>
        /// <returns>組み合わせの数</returns>
        private BigInteger Combination_Count()
        {
            var numerator = new BigInteger(1);
            var denominator = new BigInteger(1);
            var n = this._n;
            var k = this._k;
            var tmp = 1L;

            if (this._k > this._n - this._k) k = this._n - this._k;

            for (int count = 1; count <= k; count++)
            {
                numerator *= n;
                n--;

                denominator *= tmp;
                tmp++;
            }

            return numerator / denominator;
        }

        /// <summary>
        /// 組み合わせパターンを得る
        /// </summary>
        /// <returns>組み合わせパターンの反復子</returns>
        public IEnumerable<int[]> GetEnumerable()
        {
            if (this._idxset.Length == 0) yield break;

            while (this._idxset[this._idxset.Length - 1] != this._n)
            {
                yield return this.Result();

                Update();
            }

            yield break;
        }

        /// <summary>
        /// 参照の更新
        /// </summary>
        private void Update()
        {
            for (int i = this._idxset.Length - 1; i >= 0; i--)
            {
                if (this._idxset[i] != this._n)
                {
                    this._idxset[i]++;

                    for (int r = i + 1; r < this._idxset.Length; r++)
                    {
                        this._idxset[r] = this._idxset[r - 1] + 1;
                    }
                }

                if (this._idxset[this._idxset.Length - 1] != this._n) break;
            }
        }

        /// <summary>
        /// 組み合わせパターンの生成
        /// </summary>
        /// <returns>組み合わせパターン</returns>
        private int[] Result()
        {
            List<int> c = new List<int>();

            foreach (var i in this._idxset) c.Add(this._elements[i]);

            return c.ToArray();
        }

    }
}

　Program.csをこんなふうに書いて実行する。

var combination = new MathPlus.Combination(5, 3);

foreach (var item in combination.GetEnumerable())
{
    Console.WriteLine($"[{string.Join(",", item)}]");
    Thread.Sleep(100);
}

Console.WriteLine(($"個数:{combination.Count}"));

実行結果

[1,2,3]
[1,2,4]
[1,2,5]
[1,3,4]
[1,3,5]
[1,4,5]
[2,3,4]
[2,3,5]
[2,4,5]
[3,4,5]
個数:10

なぜよくある再帰を使用したコードにしないの？

　コピペしてC(400000, 1000)を計算させたらメモリバカ食いして死んだから。

説明

　説明書こうとしたものの、めんどくさくなったので省いたけど書いたほうがいいのかな？

まずコンストラクタが呼び出される。

/// <summary>
/// コンストラクタ
/// </summary>
/// <param name="n">要素の個数</param>
/// <param name="k">選択する個数</param>
public Combination(int n, int k)
{
    this._n = n;
    this._k = k;
    this._elements = Enumerable.Range(1, this._n).ToArray();
    this._idxset = Enumerable.Range(0, this._k).ToArray();
}

　ここで1からnの要素が入ってる配列 elements と、要素の参照する場所を格納したサイズkの配列 idxset を作る。
C(5, 3)だと次のような初期値になる。

elements

idxset

　idxset は elements に対する参照の集合なので、
idxset[0](値は0) は elements[0](値は1)
idxset[2](値は2) は elements[2](値は3) を指し示す。
仮に idxset[2]の値が4だと elements[4] の値5になる。
インデックス(index)の集合(set)だからidxsetなんていう名前にしたけど、もっと他にいい名前があるかもしれない。

　idxset をサイズ k で確保してることから感の鋭い諸兄におかれましては既にお分かりの通り、 idxset を使って「組み合わせ」が作られます。

　次にコイツが来る。

/// <summary>
/// 組み合わせパターンを得る
/// </summary>
/// <returns>組み合わせパターンの反復子</returns>
public IEnumerable<int[]> GetEnumerable()
{
    if (this._idxset.Length == 0) yield break;

    while (this._idxset[this._idxset.Length - 1] != this._n)
    {
        yield return this.Result();

        Update();
    }

    yield break;
}

　yield break や yield return はマイクロソフトのサイトを参考にしてもらうとする。
learn.microsoft.com

　まず最初に idxset.Length が0、つまりidxsetのサイズが0の時は何もせずに即終了宣言。
参照が無いならどうにもならんし。

　次にwhileループに入る。
ループ条件は「idxsetの配列のケツが n と同じではない」こと。
C(n, k) = C(5, 3) の場合

idxsetの配列の最後尾が5　=>　ループ終了
idxsetの配列の最後尾が5以外　=>　ループ継続

ということになる。

　最初の関門を通り抜けると Result による出力。
idxsetの値を頭から参照していく。

index	0	1	2	3	4
elements	1	2	3	4	5

idxset

今は[0][1][2]なので、elements の index [0][1][2]を参照し [1][2][3] を結果として返す。

　次に idxset を更新するための Update に入る。

/// <summary>
/// 参照の更新
/// </summary>
private void Update()
{
    for (int i = this._idxset.Length - 1; i >= 0; i--)
    {
        if (this._idxset[i] != this._n)
        {
            this._idxset[i]++;

            for (int r = i + 1; r < this._idxset.Length; r++)
            {
                this._idxset[r] = this._idxset[r - 1] + 1;
            }
        }

        if (this._idxset[this._idxset.Length - 1] != this._n) break;
    }
}

　一番外側のforによってidxsetを最後尾から見ていく。
状態はこう。

index	0	1	2
idxset	0	1	2

i : 2
idxset[i] : 2

　まず idxset[i] が n になってないか確認する。
C(n, k) = C(5, 3) なので n は5、対する idxset[i] は2なので idxset[i] != n はtrueとなりifの中に入る。

　ifの中ではまず最初に idxset[i] の値に1加える。

index	0	1	2
idxset	0	1	3

i : 2
idxset[i] : 3

　次に i より後ろの配列を idxset[i]+1 から始まる値で昇順で更新する。
今は i : 2 であり、idxset の index に2以上はないので何もせず抜ける。

　ifを抜ければ idxset の最後尾が n になってないか再び確認。
nならばforを続行、nでないならforを抜ける。
最初のアップデートが終わった時点でこうなる。

index	0	1	2	3	4
elements	1	2	3	4	5

idxset

　whileに戻り、idxsetの最後尾がn(5)ではないのでループ続行、出力を行う。
idxsetが[0][1][3]なので、elementsのindexを参照し出力は[1][2][4]となる。
再びUpdateを通り抜けるとidxsetが更新され[0][1][4]となり、[1][2][5]が出力となる。

　次にUpdateに入ると最後尾に+1されidxsetは[0][1][5]。
idxsetの最後尾が5なのでbreakに到達せずforループが回り、iの値が1減り i : 1 となる。
idxset[i]に1を加える処理が走ってこうなる。