离散数学/数字表示

介绍

您已经熟悉写下一个数字，并让它表示十、百等等的特定组合。这是一种数字表示形式，但还有其他形式。我们将探讨进制和连分数。

进制

您已经熟悉十进制数表示法。例如，数字 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, ...