1. 平衡三進法

1. 平衡三進法
2. 十進法から平衡三進法への変換
3. 天秤ばかりの問題
4. 符号付きの剰余による整数
5. 符号付きの剰余による小数

非負の剰余

任意の被除数 a を正の除数 b で割ったときの整数商を q，剰余を r とすると， \[ a=bq+r \] が成り立つ。 標準的には，非負でできるだけ小さい値の剰余 r を用いる。 そのときの整数商 q は，実数の範囲で求めた商 a÷b の小数部分を切り捨てたものになる。 \[ q=\left \lfloor \frac{a}{b}\right \rfloor,\qquad 0\le r<b \] 特に，被除数 a が整数，除数 b が2以上の整数の場合の剰余 r は 0≤r≤b−1 の範囲の整数になる。

たとえば，整数 a を正の整数 b=3 で割ったときの剰余は 0，1，2 のいずれかになる。 正の整数 b=5 で割ったときの剰余は 0，1，2，3，4 のいずれか， 正の整数 b=7 で割ったときの剰余は 0，1，2，3，4，5，6 のいずれかになる。 この剰余（非負の剰余）を使って標準的なｋ進法の表記ができる。

符号付きの剰余（絶対値最小剰余）

任意の被除数 a を正の除数 b で割ったときの整数商を q，剰余を r とすると， \[ a=bq+r \] が成り立つが， 負の剰余を許して，絶対値が最も小さくなるように剰余 r を定めることもできる。これを絶対値最小剰余という。 そのときの整数商 q は，実数の範囲で求めた商 a÷b の小数部分を四捨五入したものになる。 \[ q=\left \lfloor \frac{a}{b}+\frac{1}{2}\right \rfloor,\qquad -\frac{b}{2}\le r<\frac{b}{2} \] あるいは四捨五入でなく五捨五超入でもよい。 \[ q=\left \lceil \frac{a}{b}-\frac{1}{2}\right \rceil,\qquad -\frac{b}{2}<r\le \frac{b}{2} \] 特に，被除数 a が整数，除数 b が3以上の奇数の場合の剰余 r は −(b−1)/2≤r≤(b−1)/2 の範囲の整数になる。

たとえば，整数 a を正の整数 b=3 で割ったときの剰余は −1，0，1 のいずれかになる。 正の整数 b=5 で割ったときの剰余は −2，−1，0，1，2 のいずれか， 正の整数 b=7 で割ったときの剰余は −3，−2，−1，0，1，2，3 のいずれかになる。 この剰余（絶対値最小剰余）を使って平衡ｋ進法の表記ができる。

三進法（Ternary）

標準的な三進法では，各々の位は 0，1，2 のいずれかになっている。 三進法で 121102 と表される数は，次のように分解できる。 \[ 121102_3=1\times 3^5+2\times 3^4+1\times 3^3+1\times 3^2+0\times 3+2 \] これを十進法で計算すると，三進法の 121102 は十進法の 281 に等しい。

平衡三進法（Balanced Ternary）

平衡三進法では，各々の位は −1，0，1 のいずれかになっている。 数 −1 を文字 M で表すことにすると， 平衡三進法で 10M1M0 と表される数は，次のように分解できる。 \[ \text{10M1M0}_3=1\times 3^5+0\times 3^4+(-1)\times 3^3+1\times 3^2+(-1)\times 3+0 \] これを十進法で計算すると，平衡三進法の 10M1M0 は十進法の 222 に等しい。

使用例

平衡三進法の表記は M=−1 とする。

次のページへ

1 2 3 4 5 Next

2. 十進法から平衡三進法への変換

1. 平衡三進法
2. 十進法から平衡三進法への変換
3. 天秤ばかりの問題
4. 符号付きの剰余による整数
5. 符号付きの剰余による小数

十進法から三進法へ

十進法で 114 と表される数を三進法に変換する。

求めた余りを逆順に並べると，十進法の 114 は三進法で 11020 になる。 この結果が正しいことを確かめるために，最後の行から順に展開していく（最後の行は省く）。 \begin{align*} 4 &=1\times 3+1\\ 12 &=4\times 3+0\\ &=(1\times 3+1)\times 3+0\\ &=1\times 3^2+1\times 3+0\\ 38 &=12\times 3+2\\ &=(1\times 3^2+1\times 3+0)\times 3+2\\ &=1\times 3^3+1\times 3^2+0\times 3+2\\ 114 &=38\times 3+0\\ &=(1\times 3^3+1\times 3^2+0\times 3+2)\times 3+0\\ &=1\times 3^4+1\times 3^3+0\times 3^2+2\times 3+0 \end{align*} したがって，十進法の 114 を三進法で表すと 11020 になる。

十進法から平衡三進法へ

十進法で 114 と表される数を平衡三進法に変換する。 114÷3 の商は ⌊114÷3+0.5⌋ または ⌈114÷3−0.5⌉ によって求める。

求めた余りを逆順に並べると，十進法の 114 は平衡三進法で 111M0 になる。ただし M=−1 とする。 この結果が正しいことを確かめるために，最後の行から順に展開していく（最後の行は省く）。 \begin{align*} 4 &=1\times 3+1\\ 13 &=4\times 3+1\\ &=(1\times 3+1)\times 3+1\\ &=1\times 3^2+1\times 3+1\\ 38 &=13\times 3+(-1)\\ &=(1\times 3^2+1\times 3+1)\times 3+(-1)\\ &=1\times 3^3+1\times 3^2+1\times 3+(-1)\\ 114 &=38\times 3+0\\ &=(1\times 3^3+1\times 3^2+1\times 3+(-1))\times 3+0\\ &=1\times 3^4+1\times 3^3+1\times 3^2+(-1)\times 3+0 \end{align*} したがって，十進法の 114 を平衡三進法で表すと 111M0 になる。

次のページへ

1 2 3 4 5 Next

3. 天秤ばかりの問題

1. 平衡三進法
2. 十進法から平衡三進法への変換
3. 天秤ばかりの問題
4. 符号付きの剰余による整数
5. 符号付きの剰余による小数

片側の皿に分銅を載せる場合

問題：  上皿天秤で試料の重さを測定したい。 試料を左側の皿に，分銅を 右側 の皿に載せて測定するとき， できるだけ少ない個数の分銅を使って，1グラムから100グラムまでの重さを1グラム単位で測定するためには，少なくとも何個の分銅が必要か。またそれらの分銅は何グラムか。

二進法を利用した解答

解説：  1グラム，2グラム，4グラム，8グラム，16グラム，32グラム，64グラムの分銅を用意すると， 各々の分銅について「皿に載せる」「皿に載せない」の2つの状態があるので，7個すべての分銅について 2⁷=128 通りの状態がある。 1グラムの分銅を「皿に載せる」場合は a₀=1，「皿に載せない」場合は a₀=0 とする。 同様にして，2グラム，4グラム，8グラム，16グラム，32グラム，64グラムの分銅により，a₁，a₂，a₃，a₄，a₅，a₆ の値を定めると， 右側の皿に載せた分銅の重さの合計は \[ a_6\times 2^6+a_5\times 2^5+a_4\times 2^4+a_3\times 2^3+a_2\times 2^2+a_1\times 2+a_0\times 1 \] で表される。

これらの7個の分銅により，0グラムから127グラムの重さを1グラム単位で測定することができる。 一つの分銅の状態と一つの重さが一対一対応できるので，これが最適解になる。

解答：  1グラム，2グラム，4グラム，8グラム，16グラム，32グラム，64グラムの7個の分銅を用意する。 一般に，2のべきの重さの分銅を n 個使うと，0 グラムから 2ⁿ−1 グラムまで測定できる。

両側の皿に分銅を載せる場合

問題：  上皿天秤で試料の重さを測定したい。 試料を左側の皿に，分銅を 右側または左側 の皿に載せて測定するとき， できるだけ少ない個数の分銅を使って，1グラムから100グラムまでの重さを1グラム単位で測定するためには，少なくとも何個の分銅が必要か。またそれらの分銅は何グラムか。

平衡三進法を利用した解答

解説：  1グラム，3グラム，9グラム，27グラム，81グラムの分銅を用意すると， 各々の分銅について「右側の皿に載せる」「皿に載せない」「左側の皿に載せる」の3つの状態があるので，5個すべての分銅について 3⁵=243 通りの状態がある。 1グラムの分銅を「右側の皿に載せる」場合は a₀=1，「皿に載せない」場合は a₀=0，「左側の皿に載せる」場合は a₀=−1 とする。 同様にして，3グラム，9グラム，27グラム，81グラムの分銅により，a₁，a₂，a₃，a₄ の値を定めると， 右側または左側の皿に載せた分銅の重さの合計は \[ a_4\times 3^4+a_3\times 3^3+a_2\times 3^2+a_1\times 3+a_0\times 1 \] で表される。

これらの5個の分銅により，−121グラムから121グラムの重さを1グラム単位で測定することができる。 一つの分銅の状態と一つの重さが一対一対応できるので，これが最適解になる。

解答：  1グラム，3グラム，9グラム，27グラム，81グラムの5個の分銅を用意する。 一般に，3のべきの重さの分銅を n 個使うと，−(3ⁿ−1)/2 グラムから (3ⁿ−1)/2 グラムまで測定できる。

試料の重さが整数の場合

試料の重さが整数に限られるという情報が事前に与えられていた場合は，偶数の重さだけ測定できれば十分である。 たとえば，6グラムより重く8グラムより軽いことが分かれば，試料の重さは7グラムに決まる。

分銅を右側の皿だけに載せる場合は 2グラム，4グラム，8グラム，16グラム，32グラム，64グラムの6個を使って 126 グラムまで， 分銅を右側または左側の皿に載せる場合は 2グラム，6グラム，18グラム，54グラム，162グラムの5個を使って 242 グラムまで測定できる。

次のページへ

1 2 3 4 5 Next

4. 符号付きの剰余による整数

1. 平衡三進法
2. 十進法から平衡三進法への変換
3. 天秤ばかりの問題
4. 符号付きの剰余による整数
5. 符号付きの剰余による小数

平衡ｋ進法

基数 k が 3 以上の奇数のとき，任意の数を符号付き数 −(k−1)/2，…，0，1，…，(k−1)/2 の列で表す記数法のことを 平衡 k 進法 という。 実数 x を平衡 k 進法で表した文字列を a_na_n−1…a₀.a₋₁a₋₂… とする。 \[ x=a_n a_{n-1}\cdots a_0 .a_{-1}a_{-2}\cdots \] x が整数の場合は，小数部分（小数点より右側の部分）が0になる。 \[ x=a_n a_{n-1}\cdots a_0 \]

最近接丸めの商と符号付きの剰余

実数を整数に丸める関数を F(x) とする。ここでは最近接丸め（正の場合は四捨五入）を用いる。 \[ F(x)=\left \lfloor x+\frac{1}{2}\right \rfloor \] x は任意の実数，k は正の実数とする。 被除数 x を除数 k で割ったときの整数商 q を F(x/k)=⌊x/k+0.5⌋ によって定めると，剰余 r は符号付きの実数（−k/2≤r<k/2）になる。 \[ q=F\left(\frac{x}{k}\right),\;x=qk+r\implies -\frac{k}{2}\le r\lt \frac{k}{2} \] 特に，x が整数で k が 3 以上の奇数の場合は，r は −(k−1)/2≤r≤(k−1)/2 の範囲の整数になる。 \[ x,k\in \mathbb{Z},\;q=F\left(\frac{x}{k}\right),\;x=qk+r\implies -\frac{k-1}{2}\le r\le \frac{k-1}{2} \]

整数部分の決定

x は整数，k は 3 以上の奇数とする。 x=0 でないとき，x を k で割った商を q₀，剰余を a₀ とする。ただし除法は上に定めたものとする。a₀ は −(k−1)/2≤a₀≤(k−1)/2 の範囲の整数になる。 \[ q_0=F\left(\frac{x}{k}\right)\quad (|q_0|<|x|),\qquad x=q_0 k+a_0\quad \left(-\frac{k-1}{2}\le a_0\le \frac{k-1}{2}\right) \] q₀=0 でないとき，q₀ を k で割った商を q₁，剰余を a₁ とする。 \[ q_1=F\left(\frac{q_0}{k}\right)\quad (|q_1|<|q_0|),\qquad q_0=q_1 k+a_1\quad \left(-\frac{k-1}{2}\le a_1\le \frac{k-1}{2}\right) \] 同様にして除算を繰り返す。q_i−1=0 でないとき，q_i−1 を k で割った商を q_i，剰余を a_i とする。 \[ q_i=F\left(\frac{q_{i-1}}{k}\right)\quad (|q_i|<|q_{i-1}|),\qquad q_{i-1}=q_i k+a_i\quad \left(-\frac{k-1}{2}\le a_i\le \frac{k-1}{2}\right) \] |x|>|q₀|>|q₁|>… より，ある番号 n で q_n=0 になるから，その時点でとりやめる。 \[ q_n=F\left(\frac{q_{n-1}}{k}\right)=0,\qquad q_{n-1}=q_n k+a_n\quad \left(-\frac{k-1}{2}\le a_n\le \frac{k-1}{2}\right) \] 除算の結果を次々に置き換えると，x を k のべきを使って表すことができる。 \begin{align*} x &=q_0 k+a_0\\ &=q_1 k^2+a_1 k+a_0\\ &\qquad \qquad \cdots \\ &=q_{i-1} k^i+a_{i-1} k^{i-1}+\cdots +a_2 k^2+a_1 k+a_0\\ &\qquad \qquad \cdots \\ &=q_{n-1} k^n+a_{n-1} k^{n-1}+\cdots +a_2 k^2+a_1 k+a_0\\ &=a_n k^n+a_{n-1} k^{n-1}+\cdots +a_2 k^2+a_1 k+a_0 \end{align*} したがって，整数 x を 平衡 k 進法で表したときの各位は a_i になる。 \[ x=a_n a_{n-1}\cdots a_2 a_1 a_0 \]

除法の許容範囲

丸め関数 F(x) は，⌊x+(k−1)/(2k)⌋ から ⌈x−(k−1)/(2k)⌉ までの範囲内のものに置き換えてもかまわない。 \[ \left \lfloor x+\frac{k-1}{2k}\right \rfloor \le F(x)\le \left \lceil x-\frac{k-1}{2k}\right \rceil \] なぜなら，x が整数ならば，上の範囲内の F(x) によって同一の結果が得られるからである。 \[ x\in \mathbb{Z}\implies q_0=\left \lfloor \frac{x}{k}+\frac{k-1}{2k}\right \rfloor =\left \lceil \frac{x}{k}-\frac{k-1}{2k}\right \rceil \] たとえば，四捨五入 ⌊x+0.5⌋ を五捨五超入 ⌈x−0.5⌉ に置き換えてもかまわない。 \[ x\in \mathbb{Z}\implies q_0=\left \lfloor \frac{x}{k}+\frac{1}{2}\right \rfloor =\left \lceil \frac{x}{k}-\frac{1}{2}\right \rceil \]

次のページへ

1 2 3 4 5 Next

5. 符号付きの剰余による小数

1. 平衡三進法
2. 十進法から平衡三進法への変換
3. 天秤ばかりの問題
4. 符号付きの剰余による整数
5. 符号付きの剰余による小数

平衡ｋ進法の小数部分

平衡三進法において小数部分の下限は 0.MMM…=−1/2，上限は 0.111…=1/2 である。ただし M=−1 とする。 一般に，平衡 k 進法において実数 x の整数部分を Q，小数部分を R とすると，小数部分 R は次の式の範囲内にある。 \[ -\frac{1}{2}\le R\le \frac{1}{2} \] そこで，実数を整数に丸める関数を f(x)，g(x) とする。 \[ g(x)=\left \lceil x-\frac{1}{2}\right \rceil,\qquad f(x)=\left \lfloor x+\frac{1}{2}\right \rfloor,\qquad g(x)\le f(x) \] 実数 x の整数部分 Q を f(x) によって定めれば，小数部分 R は \[ Q=f(x)\implies -\frac{1}{2}\le R\lt \frac{1}{2} \] 実数 x の整数部分 Q を g(x) によって定めれば，小数部分 R は \[ Q=g(x)\implies -\frac{1}{2}\lt R\le \frac{1}{2} \] となる。

小数部分の決定

整数部分，小数部分は丸め関数 f(x) によって定められたものとすると，実数 x の小数部分 R は −0.5≤R<0.5 の範囲の実数になる。 R=0 でないとき，R に k を掛けた値の整数部分を a₋₁，小数部分を r₋₁ とすると， a₋₁ は −(k−1)/2≤a₋₁≤(k−1)/2 の範囲の整数，r₋₁ は −0.5≤r₋₁<0.5 の範囲の実数になる。 \[ a_{-1}=f(R\times k),\qquad R\times k=a_{-1}+r_{-1}\quad \left(-\frac{1}{2}\le r_{-1}\lt \frac{1}{2}\right) \] r₋₁=0 でないとき，r₋₁ に k を掛けた値の整数部分を a₋₂，小数部分を r₋₂ とすると， a₋₂ は −(k−1)/2≤a₋₂≤(k−1)/2 の範囲の整数，r₋₂ は −0.5≤r₋₂<0.5 の範囲の実数になる。 \[ a_{-2}=f(r_{-1}\times k),\qquad r_{-1}\times k=a_{-2}+r_{-2}\quad \left(-\frac{1}{2}\le r_{-2}\lt \frac{1}{2}\right) \] 同様にして乗算を繰り返す。r_−i+1=0 でないとき，r_−i+1 に k を掛けた値の整数部分を a_−i，小数部分を r_−i とすると， a_−i は −(k−1)/2≤a_−i≤(k−1)/2 の範囲の整数，r_−i は −0.5≤r_−i<0.5 の範囲の実数になる。 ある番号 −m で r_−m=0 になれば，その時点でとりやめる。 r_−i=0 にならなければ無限小数になる。 \[ a_{-i}=f(r_{-i+1}\times k),\qquad r_{-i+1}\times k=a_{-i}+r_{-i}\quad \left(-\frac{1}{2}\le r_{-i}\lt \frac{1}{2}\right) \] 乗算の結果を次々に置き換えると，R を k のべきを使って表すことができる。 \begin{align*} R &=a_{-1} k^{-1}+r_{-1} k^{-1}\\ &=a_{-1} k^{-1}+a_{-2} k^{-2}+r_{-2} k^{-2}\\ &\qquad \qquad \cdots \\ &=a_{-1} k^{-1}+a_{-2} k^{-2}+\cdots +a_{-i} k^{-i}+r_{-i} k^{-i} \end{align*} ある番号 −m で r_−m=0 になる場合は， \[ R=a_{-1} k^{-1}+a_{-2} k^{-2}+\cdots +a_{-m} k^{-m} \] r_−i=0 にならない場合は無限小数で， \[ R=a_{-1} k^{-1}+a_{-2} k^{-2}+\cdots +a_{-i} k^{-i}+\cdots \] となる。 したがって，実数 x の小数部分 R を k 進法で表したときの各位は a_−i になる。 \[ R=0.a_{-1} a_{-2}\cdots a_{-i}\cdots \]

最後のページです

1 2 3 4 5 Home

符号付き数の列で表す記数法

Home  標準記数法  符号付き数の列  正数の列  負の基数