本文题目难度标识：🟩简单，🟨中等，🟥困难。

进制转换

令 N 是一个十进制数，它表示为下面的形式：

N=aknk+ak−1nk−1+⋯+a1n+a0+b1n−1+b2n−2+...++bl−1n−(l−1)+bln−lN=a_{k}n^k+a_{k-1}n^{k-1}+\dots+a_{1}n+a_{0}+b_{1}n^{-1}+b_{2}n^{-2}+...++b_{l-1}n^{-(l-1)}+b_{l}n^{-l}

可记为 (akak−1……a1a0.b1b2…bl−1bl)n(a_{k}a_{k-1}\dots\dots a_{1}a_{0}.b_1b_2\dots b_{l-1}b_{l})_{n}。其中十进制的下标 10 可以省略。

n 进制数转十进制数

给出一个 n 进制数 (akak−1……a1a0.b1b2…bl−1bl)n(a_{k}a_{k-1}\dots\dots a_{1}a_{0}.b_1b_2\dots b_{l-1}b_{l})_{n}，我们可以快速通过上面的式子得出十进制数 N。

十进制数转 n 进制数

简单来说就是两步：

  • 整数部分取余除以基，最先取得的余数为最低位
  • 小数部分乘基取整，最先取得的整数为最高位
  • 最后结果拼接

接下来就是理解部分，设十进制数 N=I+DN=I+D，其中 II 表示 NN 的整数部分，DD 表示其小数部分。

我们先理解「整数部分取余除以基」。观察：

I=aknk+ak−1nk−1+⋯+a1n+a0=(aknk−1+ak−1nk−2+⋯+a1)n+a0\begin{aligned} I=&a_{k}n^k+a_{k-1}n^{k-1}+\dots+a_{1}n+a_{0} \\ =& (a_{k}n^{k-1}+a_{k-1}n^{k-2}+\dots+a_{1})n + a_0 \end{aligned}

对 N 进行取余，先得到最低位 a0a_0。余数拿走，然后在除以 n，得到：

N′=(N−a0)/n=aknk−1+ak−1nk−2+⋯+a1\begin{aligned} N' =&(N - a_0)/n \\ =&a_{k}n^{k-1}+a_{k-1}n^{k-2}+\dots+a_{1} \end{aligned}

重复取余除以基，就能依次拿到 a1,a2,...,aka_1, a_2, ..., a_k。

「整数部分取余除以基」的另一种理解方式。
image.png

再看「小数部分乘基取整」。观察：

D=b1n−1+b2n−2+...++bl−1n−(l−1)+bln−lD⋅n=b1+b2n−1+...++bl−1n−(l−2)+bln−(l−1)\begin{aligned} D=&b_{1}n^{-1}+b_{2}n^{-2}+...++b_{l-1}n^{-(l-1)}+b_{l}n^{-l} \\ D \cdot n =& b_{1}+b_{2}n^{-1}+...++b_{l-1}n^{-(l-2)}+b_{l}n^{-(l-1)} \end{aligned}

b2n−1+...+bl−1n−(l−2)+bln−(l−1)b_{2}n^{-1}+...+b_{l-1}n^{-(l-2)}+b_{l}n^{-(l-1)} 部分一定是小数，取整时得到 b1b_1。整数拿走，继续乘 n，有：

D′=(D⋅n−b1)⋅n=b2+...+bl−1n−(l−3)+bln−(l−2)\begin{aligned} D' =& (D\cdot n -b_1)\cdot n \\ =& b_{2}+...+b_{l-1}n^{-(l-3)}+b_{l}n^{-(l-2)} \end{aligned}

重复取整乘 n，就能依次拿到 b1,b2,...,blb_1,b_2,...,b_l。

两数交换

常用写法

中间变量法

1
2
3
4
// 记法：记住变量首尾相接，怎么写都不会错
int t = a;
a = b;
b = t;

这种方法可读性高，但是需要在内存中存放临时变量。

数学运算法

1
2
3
4
5
6
7
8
9
// 加减法
a = a + b;
b = a - b;
a = a - b;

// 异或法
a ^= b;
b ^= a;
a ^= b;

方法评价：

  • 加减法：两个数相加之后，可能其结果超出了变量类型能表达的最大范围，这个时候结果就会出数据溢出，不推荐使用。
  • 异或法：效率是最高的，但是可读性不是很好。

Java 中编写 swap 交换函数

Java 在有参函数调用时，如果参数传递的是基本类型，进行的是值传递，而不是 地址或引用传递。

因此，以下的写法是错误的：

1
2
public static void swap(int a, int b);
public static void swap(Integer a, Integer b);

正确的写法是传入一个数组，在数组的基础上进行交换：

1
2
3
4
5
public static void swap(int[] arr) {
	int temp = arr[0];
	arr[0] = arr[1];
	arr[1] = temp;
}

循环增减

1
2
3
// 循环增减
idx=(idx+1) % SIZE;
idx=(idx + SIZE - 1) % SIZE;

将比较关系整数化

得到 a 和 b 的大小关系，小于是 -1，等于是 0，大于是 1

1
2
// 布尔大小比较转为输出整数
(a>b)-(a<b)

四舍五入

1
2
3
// 四舍五入
double x;
x = (int)((x * 1000) + 0.5) / 1000.0)  // 保留3位小数就乘1000、除以1000.0

向上取整转变为向下取整

对于正整数 mm，有：

⌈nm⌉=⌊n+m−1m⌋=⌊n−1m⌋+1\lceil \frac{n}{m} \rceil = \lfloor \frac{n+m-1}{m} \rfloor= \lfloor \frac{n-1}{m} \rfloor +1

我们可以根据这个性质将一些向上取整操作处理为向下取整。

最大公约数 GCD

辗转相除法数学定理：gcd(a,b) = gcd(b,a mod b)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 迭代版本
public int gcd(int a, int b) {
	while (b != 0) {
		a %= b;
		swap(new int[]{a,b}); // 交换结束 b 是小的那一个
	}
	return a;
}

// 自己写的版本
public int gcd(int a,int b){
	while(a%b!=0){
		a%=b;
		swap(new int[]{a,b});
	}
	return b;
}

递归版本：

1
2
3
4
5
// 递归版本
public static int gcd(int a,int b){
	if (b == 0) return a;
	return gcd(b, a % b);
}

相关题目：

质数的判断

详看：站内文章【刷题日记】判断质数

本文参考