可変進数と不定次元配列の解決(プログラミング)

更新日時:2021/03/10

数学数列整数プログラミング

GOODされた数:19 回

プロローグ

どうも、安田です。
今回は、プログラミングをする際に、非常に実用的な概念を見つけたので、それをするための数学の理論についてここに残しておこうと思います。

今回扱うのは、可変進数という名前を付けましたが、桁ごとに何進数かが変わるという数についてです。この理論はプログラミングにおいて、次元が定まらない配列を作成する場合に役立ちます。(これについては後ほど書きます)

本論

可変進数の定義

可変進数をどの文字でおくかなどの事を毎回書くのは非効率なので、最初に以下のように定義しておきます。

可変進数$X$ は $n$ 桁であり、 $ 1 \leqq k \leqq n $ に対して $k$ 桁目が $p_k$ 進数で表される数であり、その値は $a_k$ である。

プログラミングにおいて、$n$ が不定な場合、$n$次元配列を定義しようと思ってもできるような言語は少ないと思います。
この可変進数は、$n$ が不定であり $n$ 次元配列を定義できないという場合に、1次元配列として一般化するという手法に用いる事が出来ます

可変進数の実値計算

プログラムで言えば、n次元配列から1次元配列へと変更した時のインデックスの決定方法にあたるのが、このセクションです。

ここでは、$X$の実際の値を数式でどのように書くかを考えます。これは、その桁より下の桁で、何通りの整数を表せるか を数える事により解決します。これは、その桁で1つ値が大きくなることにより、その桁より下の桁で表せる場合の数の分だけ$X$の値が増加するからです。

$k-1$ 桁までで、各桁の値の選び方は \[ \prod_{l=1}^{k-1} p_l \] なので、 \[ X = \sum_{k=1}^{n} \left( a_k \prod_{l=1}^{k-1} p_l \right) \]

実際のプログラムで書く場合は、これが一般化された1次元配列でのインデックスとなり、$n$でforループを用いる事によりインデックスを計算でき、不定な$n$に対してもプログラムとしてコーディングする事が可能です。

可変進数への変換

やはり多次元配列を用いようとするプログラムという事は、何かしらインデックスを区別すべき部分があるという事です。そこで、可変進数において何桁目がどの数字かという事も求める必要がありますので、その解決方法にあたるのがこのセクションです。

$p_k = \mathrm{Const.}$ の場合では普段あまりという概念を使いますが、一般化された可変進数ではあまりの言い換え(一般化)を用います。

まず、10進数の場合の余りの一般公式で例をあげますと、以下ような計算です。

10進数の $Y$ に対して、$k$ 桁目以降の桁を表示する場合 \[ \left\lfloor \frac{Y}{10^{k-1}} \right\rfloor \] であるので、$k$桁目の数字を計算する場合は、 \[ \left\lfloor \frac{Y}{10^{k-1}} \right\rfloor - 10 \left\lfloor \frac{Y}{10^k} \right\rfloor \] である。

上の式は例えば 14392 という10進数の数があった場合、 3桁目であれば $143 - 140 = 3$ によって求めるという事です。 このように余りを一般化し、可変進数にもこれを適応します。

$X$ に対して、$k$ 桁目以降の桁を表示する場合 \[ \left\lfloor X \prod_{l=1}^{k-1} \frac{1}{p_l} \right\rfloor \] であるので、$k$桁目の数字を計算する場合は \[ \left\lfloor X \prod_{l=1}^{k-1} \frac{1}{p_l} \right\rfloor - p_k \left\lfloor X \prod_{l=1}^{k} \frac{1}{p_l} \right\rfloor \] である。

これにより、任意の桁の値を求める事ができます。なお、ガウス記号は単純に型キャストにより解決可能です。

使い道

次元が定まらない配列を使う事があるのか、という事ですが、場合分けの情報処理などをする場合に必要となります。
例えば、ユーザーの入力した深度に合わせたコラッツ数列の樹形図を作ろうと思った場合、インデックスが1つのものと2つのものがユーザーの決めた値の分だけ生成される必要があります。

その他に、再帰関数の回避にも使う事が出来ます。再帰関数であまりにも大量の再帰呼び出しをするとスタックオーバーフローのエラーが出てしまうので、その場合などにも使えます。

このように、今回は非常に実用的な理論を立てる事ができました。それでは、お疲れさまでした。

この記事いいね!


コメント送信フォームまで飛ぶ

この記事には0件のコメントがあります。


変換


※上の変換器は、TeXが正しいかどうかの確認に使ってください。
※TeXを入力する場合は、コメント本文に、$\$$ または、$\verb|\|$[, $\verb|\|$]で囲った中にTeX表示をそのまま挿入してください。
※URLは、自動的にハイパーリンクに変形されます。
※他のコメントに返信する場合は、「#コメント番号」を挿入してください。
※日本語を含まないコメントはスパムと認定されます。
※Comment including no japanese will be regarded as spam.