进制与进制转换

平时，我们在生活中都是由十进制来表示数字，而计算机由于物理性质使用二进制来存储和计算数据。

而我们所说的k进制数字，就是每一位上由0，1，2，3……k-1所组成的数字，常考的进制有二、八、十、十六进制。

十六进制中的11~16分别是abcdef。

十进制转k进制

我们一般使用短除法来实现任意进制的转换，若要将s 转换为 b 进制，将 s 每次除以 b，得到的余数的逆序列是 b 进制表示的结果。

每次用当前的数除以 2，得出商和余数，将商写在下方，余数写在右方，除到商为1为止。

k进制转十进制

本质上就是算出每个进制位上的值实际上是多少，累加得出最终的结果。
比如：

2、8、16进制之间的转换

对于这3中进制有更简单的转换方法

例如将二进制的10101转为八进制，首先按照3为补齐，如010，101，每三位合并出一个八进制数变成26。

而八进制转二进制、八转十六、十六转八也都是同理，按三位隔开即可。

浮点数进制转换

k 进制浮点数的处理相对而言算是一个难点，关键在于如何理解不在十进制下的小数表示。

例如将101.11转换为二进制数字

而其实有的十进制小数无法转换为二进制小数，而且转换起来比较复杂，所以一般不会考察。

还有一类考察 2、8、16 进制的小数之间的互相转换。类似于整数的互相转换，补齐位数后来做。

现在将二进制的101.11转换为八进制，以小数点位基准，前后都是3位为一组，不足的补0，为101.110，结果为5.6。

数值编码–浮点数编码

在计算机中存储的小数之所以被称为“浮点数”，与它的存储方式是分不开的。目前通用的存储方式为 IEEE 二进制浮点数算术标准（IEEE 754），浮点数由三部分组成：

1. 符号：负数为 1，正数为 0
2. 2.尾数：一个二进制小数
3. 阶码：表示 2 的多少次幂
   浮点数的值就是 {符号}阶码*2^尾数，因为用类似科学计数法的方式存储小数，所以我们往往对计算机存储的小数称为浮点数，也就是“浮动小数点的数”。

计数基本原理

加法原理

具体是指：做一件事情，完成它有n类方式，第一类方式有M1种方法，第二类方式有M2种方法，……，第n类方式有Mn种方法，那么完成这件事情共有M1+M2+……+Mn种方法。

例如：现有乘火车、飞机、轮船 33 种交通方式可供选择，而火车、飞机、轮船分别有 k1，k2，k3 个班次，那么共有 k1+k2+k3种方式可以到达。

乘法原理

具体是指：做一件事，完成它需要分成n个步骤，做第一 步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法。那么完成这件事共有 N=m1×m2×m3×…×mn 种不同的方法。

例如一个 8 位的二进制数有 2^8种，因为每一位都有 2 种选择，根据乘法原理得出。

排列组合

排列数

排列数就是从n个不同元素中，任取m个元素（被取出的元素各不相同），按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。

排列数公式为：A（m,n)=n * (n-1) * (n-2) * …… * (n-m+1)

组合数

组合数就是从n个不同元素中，任取m个元素（被取出的元素各不相同），取出的元素不分顺序，叫做从n个不同元素中取出m个元素的一个排组合。

组合数公式为：C(m,n)=A(m,n)/A(n,n)

并且C(m,n)=C(n-m,n)

时间复杂度

在进行算法分析的时候，我们通常会用语句总的执行次数T（n）是关于问题规模n的函数，f（n）是问题规模n的某个函数，进而分析T（n）随着n的变化情况并确定T（n）的数量级，也就是算法的时间量度，记作T（n）=O（f（n））。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        a++; //语句 1
    }
}
for (int i = 1; i <= n; i++) {
    b++; //语句 2
}
while (n) {
    n = n / 2; //语句 3
}
p+=10;//语句4

语句1的时间复杂度为O（n^2)
语句2的时间复杂度为O（n）
语句3的时间复杂度为O（logn）
语句4时间复杂度为O（1）

函数递归计算过程较为复杂就不过多介绍了。

有问题欢迎在评论区提出，也可以私信交流