欧几里得以及进制之间的快捷转换深入理解

1. 欧几里得算法

1.1 欧几里得除法定义

1. $a$a，$b$b两个整数，$b>0$b>0，每次更改整数$c$c的值就一定存在唯一的整数$q$q，$r$r使得等式成立：$a = q \cdot b + r,(c \le r < b + c)$a=q⋅b+r,(c≤r<b+c)

   • 这样一个通用的定理我们应该从最特殊的情况去了解，最特殊的情况也就是r的绝对值最小的时候，这时候$q$q的绝对值是小于$b$b的，但是上面的情况很明显$q$q的绝对值可能是大于$b$b；也就是当$q \cdot b$q⋅b得到正数的时候，$q$q进行增加那么$r$r自然就会往负数方面减少自然绝对值也就增大了，那么我们知道最特殊的情况下$q$q和$r$r都是唯一自然在$q \cdot b$q⋅b增加$r$r较少相同数的时候也是唯一的整数

   • 最特殊的情况：$a = q \cdot b + r,(0 \le r< b + 0)$a=q⋅b+r,(0≤r<b+0)

     

   • 通过我们便于计算都是以上述最特殊的情况进行计算

   • 对于余数$r$r有四个概念（记住整个公式中都是以整数为基础没有小数），也就是$r$r可能取到的值：

     1. 核心思想：区间取值大小固定为$b$b，一方增大另一方就要减少；

     2. 具体五种情况：

        1. 最小非负余数——0作为可能的最小值（0不符合要求可能就更小），上限对应$<b$<b；
        2. 最小正余数——1作为可能的最小值（1不符合要求可能就更小）,上限对应$<b-1$<b−1；
        3. 最大非正余数——0作为可能的最大值（0不符合要求可能就更大），下限对应$>-b$>−b；
        4. 最大负余数——-1作为可能的最大值（-1不符合要求可能就更大），下限对应$>-b+1$>−b+1；
        5. 当r取绝对值最小如下图，$r1$r1必然是小于$\frac{b}{2}$2b​，那么r的取值就是：$- \frac{b}{2} \le r < \frac{b}{2}$−2b​≤r<2b​，$\frac{b}{2} < r \le - \frac{b}{2}$2b​<r≤−2b​；

        

2. 进制之间转换

2.1 进制概念以及意义

1. 进制的意义：

   • 往往人比较容易理解十进制，比如：人的身高：175cm；人的体重75kg。但是计算机是以二进制进行计算或者有时候用到八进制、十六进制进行表达，所以在人与机器之间需要进行转换，对应到实际场景来说就是十进制与其他进制的转换

2. 进制的概念

   • 进制由欧几里得除法推出：$n=({q_0}b + {a_0}) = (({q_1}b + {a_1})b + {a_0}) = > (({q_k}b + {a_k})b + \cdot \cdot \cdot )b + {a_0} = > {q_k}{b^{k - 1}} + \cdot \cdot \cdot + {a_1}b + {a_0}$n=(q0​b+a0​)=((q1​b+a1​)b+a0​)=>((qk​b+ak​)b+⋅⋅⋅)b+a0​=>qk​bk−1+⋅⋅⋅+a1​b+a0​
   • n可以表示成${q_k}{b^{k - 1}} + \cdot \cdot \cdot + {a_1}b + {a_0}$qk​bk−1+⋅⋅⋅+a1​b+a0​这样一种形式，这里的k表示的就是k进制

3. 进制的快捷转换以及为什么能够这样进行转换

   • $16$16（${2^4}$24）可快捷转换$2$2进制，这样一种特例推到一般情况就是两者形成相应的指数关系就是进行快捷转换

     

   • 为什么能够这样进行转换？

     • 答：可从最后欧几里得推导所得的两种形式进行理解，以转换为二进制进行理解，理解如下：

       1. ${q_k}{b^{k - 1}} + \cdot \cdot \cdot + {a_1}b + {a_0}$qk​bk−1+⋅⋅⋅+a1​b+a0​，每一项都可以化成${a_{k - 1}}{b^{k - 1}} \to {({a_{k - 1}})_2}{({2^i})^{k - 1}} \to {({a_{k - 1}})_2}{2^i}^{ \cdot k - 1}$ak−1​bk−1→(ak−1​)2​(2i)k−1→(ak−1​)2​2i⋅k−1，最后一个就是二进制的形式

          

       2. $(({q_k}b + {a_k})b + \cdot \cdot \cdot )b + {a_0}$((qk​b+ak​)b+⋅⋅⋅)b+a0​

          • 关注核心项${q_k}b + {a_k}$qk​b+ak​，其他都是类似的，相互之间进行嵌套，只要这个可以进制转换那么其他的一样没有问题，所以做这样的转换：$A \cdot {16^3} + B \to {(A)_2}{2^{4 \cdot 3}} + {(B)_2} = {(A)_2}{2^{12}} + {(B)_2}$A⋅163+B→(A)2​24⋅3+(B)2​=(A)2​212+(B)2​，和1最后一样也都转换成了二进制，所以转换成功