2010-12-13

処理を言葉で表す

R n進法てふ

2進法について(こちらから)
$X=\sum_{i=0}^{k-1} 2^i \times a_i$ とてふを使って書くには

[tex:X=\sum_{i=0}^{k-1} 2^i \times a_i]

とはてなブログでは書く
N進法でk桁の数値は10進法ではいくつになるかは

n<-4
k<-5
NISHIN<-sample(0:(n-1),k,replace=TRUE)
NISHIN
sum(n^{0:(k-1)}*NISHIN)

のようにRで書いて、それを実行すると

> n<-4
> k<-5
> NISHIN<-sample(0:(n-1),k,replace=TRUE)
> NISHIN
[1] 1 2 2 3 1
> sum(n^{0:(k-1)}*NISHIN)
[1] 489

のようになる
処理は言葉で説明できるとよい

n<-4 # n進法のn
k<-5 # 桁数
# n進法でk桁の数値の各桁の値をランダムに作る
# 各桁の値は0,1,...,(n-1)。それをk個ランダムにとった、重複順列の作成
NISHIN<-sample(0:(n-1),k,replace=TRUE)
NISHIN
# 各桁の10進法での値は2^(keta数-1)。その値が各桁の値の数分あるので足し合わせ
sum(n^{0:(k-1)}*NISHIN)

- 0,1順列の発生はこちらも参照

さて、N進法を10進法にする方法が示された
では10進法の数値をN進法に直すにはどうすればよいだろうか
さらに、一般的に、N進法の数値をM進法に直すにはどうすればよいだろうか
どうすればよいか、というときに、言葉でどうやるかを決めて(アルゴリズム)、それを実装する(Rのコードにする)
これを考えるときに、次のようなことが気になる
- ある自然数(１から始めて何番目に大きいか、という数。何進法で表すかによらない数)は、N進法ではNによらず一意に表せる。 $X=\sum_{i=0}^{k-1} N^i \times n_i$ と書くとき、Nによらず、 $(n_i)$ は一意
- 進法と進法とである自然数を表すとき
  - $\sum_{i=0} N^i \times n_i = \sum_{j=0} M^j \times m_j$ となる
  - $M=N^p$ という関係のとき、 $(n_i)$ と $(m_j)$ の関係は簡単に定まる
- ある自然数が一意に表せるということからは、素因数分解が連想される
- $N,M$ の関係が積で対応するときには簡単であるということからも、素因数分解が連想される
- さて…
単純に考えるために、ととが互いに素であるとする
- [tex:N
  - 今、 $M=\sum_{i=0}^{k_M} \mu_i \times N^i$ と $N$ 進法で $k_M+1$ 桁表されるとする
- このとき、ととの最小公倍数はである
  - $C$ は、 $M$ 進法では、2桁 $N$ で、小さい位から $0,N$ で表される
  - $C$ は、 $N$ 進法では、 $k_M+2$ 桁で、小さい位から $0,\mu_0,\mu_1,...,\mu_{k_M}$ と表される
  - $C$ は、 $N\times M$ 進法では、２桁で、小さい位から $0,1$ で表される
- このように書いてくると、進法と進法とが「相性が良い」のは、
  - $C$ は、 $N$ 進法では、 $k_M+2$ 桁で、小さい位から $0,\mu_0,\mu_1,...,\mu_{k_M}$ と表されるの部分で、0が多いから
図形的に考える
- 今、0から始まる数直線を考える
- 単位長さごとに、印がついている
- これを折りたたむのがn進法
- 2進法では、k桁で考えれば、k次元の単位超立方体の頂点を(0,0,...0),(1,0,...,0),(0,1,0,...,0),(1,1,0,...,0),(0,0,1,0,...,0)というように規則的に埋めていく処理
- 3進法では、この超立方体の辺の長さが１伸びて、２になっている
- n進法では、超立方体の辺の長さが(n-1)になっている
- $4=2^2$ 進法は、2進法なら立体になっているところを、平面につぶす作業
- $N,M$ の関係が $M\not = N^p$ のときには、単純に押しつぶすことができないことが、両者の表記の移行が面倒な理由
- そこに最小公倍数が出てくるのは、最小公倍数の頂点は、ルールが見つけやすい「基準点」の役割を果たすから