離散數學/數字表示

介紹

您已經熟悉寫下一個數字，並讓它表示十、百等等的特定組合。這是一種數字表示形式，但還有其他形式。我們將探討進位制和連分數。

進位制

您已經熟悉十進位制數表示法。例如，數字 2818 等於

2×10³+8×10²+1×10¹+8×10⁰

我們可以用任何數字替換這裡的 10，從而得到不同的數字。一般來說，我們可以用以下公式用 b 進製表示整數 n

a_kb^k+a_k-1b^k-1+...+a₀b⁰

其中 a_i 均小於 b。

我們將 b 進位制數字寫成 (a_ka_k-1...a₀)_b。

例如，如果我們有 6 進位制數字 243，我們將它寫成 (243)₆。當我們在十進位制中時，我們只需寫下數字：例如，十進位制數字 155 只是寫成 155。

然而，給定一個 b 進位制數字，我們如何將其轉換為我們自然的十進位制系統？同樣，我們如何將十進位制數字轉換為 b 進位制？

前者相對容易，後者更難。

將b進位制轉換為10進位制

我們只需使用 b 進位制數字的定義將 b 進位制數字轉換為十進位制 - 也就是說，我們只需將它乘開。

例如

(919)₁₂=9×12²+12¹+9=1317。

將10進位制轉換為b進位制

然而，這項任務稍微困難一些，並且有幾種方法可以執行此任務。

一種方法是使用 數論 部分中的除法演算法來寫下每一步。例如，如果我們想將 1317 轉換為 12 進位制

1317 = 12 × 109 + 9

109 = 12 × 9 + 1

9 = 12 × 0 + 9

因此，在 12 進制中，(919)₁₂=1317。

實數

我們剛剛看到了如何將整數從一個進位制轉換為另一個進位制，但我們如何處理實數的轉換呢？

回想一下，在十進位制中，我們將數字 11.341 寫成

1×10¹+1×10⁰+3×10^-1+4×10^-2+1×10^-3

因此，我們可以擴充套件上面 b 進位制數字的定義，使其為

a_kb^k+a_k-1b^k-1+...+a₀b⁰+a_-1b^-1+...

其中 a_i 均小於 b，並且總和可以終止或無限進行。

同樣，我們如何將這些數字從一個進位制轉換為另一個進位制？我們可以轉換整數部分，但小數部分（小於 1 的部分）怎麼辦？

將小數部分n轉換為b進位制

假設我們想將十進位制的 .341 轉換為 6 進位制。

我們使用以下規則寫一個表

$c_{i}=\lfloor {6\gamma _{i-1}}\rfloor$

$\gamma _{i}=6\gamma _{i-1}-c_{i}$

i      ci                   γi                6γi
0      0                   .341                2.046
1      2                   .046                0.276
2      0                   .276                1.656
3      1                   .656                3.936
4      3                   .936                5.616
5      5                   .616                3.696
6      3                   .696                4.176
7      4                   .176                1.056
8      1                   .056                0.336
9      0                   .336                2.016

看起來這個展開將永遠進行下去！我們需要計算更多 i 的值，看看我們是否會遇到 γ_i 的重複值，從而確定我們是否得到重複。

因此，我們有近似值，即 .341 接近於 (.20135341)₆。（使用定義計算此值。我們的近似值有多接近？）

如果我們得到一個 b 進製表示形式，例如看起來像 (.18191819181918191819...)_b，我們將這種表示形式稱為週期性。我們通常將其寫成

$(.{\overline {1819}})_{b}$

我們使用相同的程式將小數轉換為 b 進位制，方法是將上面的 6 替換為 b。

將小數部分n轉換為10進位制

我們有一個巧妙的技巧可以用來將 b 進位制的小數 n 轉換為十進位制，前提是表示形式是重複的。讓我們看一個例子

考慮$(.{\overline {3145}})_{7}=\alpha$。然後

$(3145.{\overline {3145}})_{7}=7^{4}\alpha$

現在

$(3145)_{7}+(.{\overline {3145}})_{7}=7^{4}\alpha$

即

$(3145)_{7}+\alpha =7^{4}\alpha$

然後

$(3145)_{7}=7^{4}\alpha -\alpha$

$(3145)_{7}=(7^{4}-1)\alpha$

最後

${(3145)_{7} \over 7^{4}-1}=\alpha$

將 (3145)₇ 轉換為 10 進位制，我們得到以下結果

$\alpha =1111/2400$

連分數

從某種意義上說，b 進製表示很好，但它在精度方面有一些缺點。我們無法使用 b 進製表示來可靠地表示數字${\sqrt {2}}$。這就是 連分數 表示派上用場的地方，它在二次無理數方面有一些很好的性質。

連分數 是以下形式的數字

$q_{0}+{1 \over q_{1}+{1 \over q_{2}+{1 \over q_{3}+\ldots }}}$

由於這種表示法顯然相當繁瑣，我們將其簡化為

$[q_{0};q_{1},q_{2},q_{3},\ldots ]$

我們再次問自己，如何進行這種數字表示之間的轉換？同樣，從連分數表示轉換更容易，而從其他表示轉換到連分數則更復雜。

從連分數表示轉換

我們只需使用連分數的定義來進行轉換。這看起來可能很困難，但實際上相當簡單，具體取決於從哪一端開始。讓我們看一個例子

考慮

$\alpha =[3;1,2,5]$

現在，我們從右到左進行計算。首先，我們有分數

${1 \over 5}$

下一個數字 2 告訴我們執行

$2+{1 \over 5}=11/5$

然後取倒數得到

${5 \over 11}$

現在下一個數字1告訴我們要執行

$1+{5 \over 11}={16 \over 11}$

然後取倒數得到

${11 \over 16}$

現在我們必須加上q₀，它始終大於1，然後得到結果

$\alpha ={59 \over 16}$

轉換為連分數表示

再次，我們建立一個表格。

考慮分數12/22，並在表格中使用以下規則

$\theta _{i}=\theta _{i-1}^{-1}-q_{i-1}$

$q_{i}=\lfloor \theta _{i}^{-1}\rfloor$

i   θi      θi-1     qi
0   12/22   .       0
1   12/22   22/12   1
2   5/6     6/5     1
3   1/5     5/1     5

(由於下一行將全是0，所以停止)

因此，現在12/22的連分數為[0; 1, 1, 5]。

將週期連分數轉換為二次無理數

首先，我們要注意週期連分數（其中q_i序列重複）的一個很好的性質，即

每個週期連分數都是形如下的數

${a\pm {\sqrt {b}} \over c}\ \mathrm {for} \ a,b,c\in \mathbb {Z}$

例如，考慮連分數

${\begin{matrix}\alpha &=&[2;2,1,2,2,1...]\\&=&[2;{\overline {2,1,2}}]\end{matrix}}$

現在

$[2;{\overline {2,1,2}}]=[2;2,1,{\overline {2,2,1}}]$

我們可以將其改寫為

$\alpha =2+{1 \over {2+{1 \over {1+{1 \over \alpha }}}}}$

現在我們可以簡化得到

$\alpha =2+{1 \over {2+{1 \over {\alpha +1 \over \alpha }}}}$

$\alpha =2+{1 \over {2+{\alpha \over \alpha +1}}}$

$\alpha =2+{1 \over {3\alpha +2 \over \alpha +1}}$

$\alpha =2+{\alpha +1 \over 3\alpha +2}$

$\alpha ={7\alpha +5 \over 3\alpha +2}$

$\alpha {(3\alpha +2)}={7\alpha +5}$

$\alpha {(3\alpha +2)}-5=7\alpha$

$3\alpha ^{2}+2\alpha -5=7\alpha$

$3\alpha ^{2}+2\alpha -7\alpha -5=0$

$3\alpha ^{2}-5\alpha -5=0$

這是一個二次方程，可以解出

$\alpha ={\frac {5+{\sqrt {85}}}{6}}$.

注意，我們可以將連分數始終寫成 (aα+b)/(cα+d)=α 的形式，這說明每個二次無理數都有一個重複的連分數表示

收斂值

假設我們有一個表示數字 n 的連分數 [q₀; q₁, ... ]。讓我們檢查一下分數序列 [q₀]，[q₀; q₁]，[q₀; q₁, q₂] 等等。序列中的每個元素被稱為 收斂值。事實證明，收斂值序列提供了對 n 的最佳有理數逼近。

這些可以從連分數表示中計算出來，也可以從計算表中計算出來。讓我們取 ${\sqrt {6}}$.

像以前一樣繼續，但是新增一個額外的 -1 行，並設定 u_-1=1，v_-1=0。根據規則進行迭代

$u_{i+1}=q_{i+1}u_{i}+v_{i-1}$

$v_{i+1}=q_{i+1}v_{i}+v_{i-1}$

${\begin{matrix}i&\theta _{i}&\theta _{i}^{-1}&q_{i}&u_{i}&v_{i}\\-1&&&&1&0\\0&{\sqrt {6}}&&2&2&1\\1&2-{\sqrt {6}}&1+{\sqrt {3/2}}&2&5&2\\2&-1+{\sqrt {3/2}}&2+{\sqrt {6}}&4&22&9\\3&-2+{\sqrt {6}}&1+{\sqrt {3/2}}&2&49&20\\\end{matrix}}$

該序列重複，連分數為 [2; 2, 4, 2, 4, ... ]。我們可以繼續這個過程生成更多的收斂分數，收斂分數為 2, 5/2, 22/9, 49/20, ...