序言
下水道井盖为什么是圆的
“下水道井盖是圆的，因为圆形不会掉进井口，而且圆形具有均匀分布压力的优势。”
一个屋子有一个门（门是关闭的）和3盏电灯。屋外有3个开关，分别与这3盏灯相连。你可以随意操纵这些开关，可一旦你将门打开，就不能变换开关了。确定每个开关具体管哪盏灯？
答：将一盏灯开一段时间，再关掉，在剩余2盏灯里随机开一盏，进屋去看，发热的灯对应第一个碰的开关，亮着的灯对应开关开着的开关，灭的灯对应没碰过的开关。
游戏之乐
如何写一个程序让 cpu 占用率保持在 50%？
不要用 if-else 来解决，要把比例转成不同的 worktime。
解法的精确与否其实取决于“多久时间内测度一次已占用的时间”和“睡眠”两类 api 的精度。
基本思路：
- 先计算一下某个周期内的目标时间：
- 假设我们使用 1s 为一个完整周期，则这个周期的 50% 为0.5s。
- 我们就用当前时间 + 0.5s 得到一个真正目标时间，比如当前时间在 15:06秒，目标时间就是15:06.5。如果有毫秒偏差，以此类推。
- 找一个无限 while 循环，内部只做两件事：
- 进行一个稍微复杂的数学计算，如开平方或者写入数字到文件，或者生成随机数打印-要避免死代码优化。
- 一计算完就校验当前时间是否到达目标时间，如果到达目标时间，则休眠。
- 醒来，进入下一周期。
bash 版本
1
2
3
4
5
6
7
8
9
10
11
12
13
| #!/bin/bash
L=${1:-50}
[ $L -lt 0 ] || [ $L -gt 100 ] && { echo "用法: $0 [0-100]"; exit 1; }
echo "CPU负载${L}%，Ctrl+C停止"
trap 'echo -e "\n停止"' INT
while true; do
for i in $(seq $L); do : > /dev/null; done
[ $((100-L)) -gt 0 ] && sleep 0.0$((100-L))
done
|
用法：
1
2
3
4
| chmod +x cpu.sh
./cpu.sh 90
./cpu.sh 30
./cpu.sh
|
java 版本
单核
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| public class SimpleCPULoader {
public static void main(String[] args) {
double targetLoad = 0.5;
if (args.length > 0) {
try {
targetLoad = Double.parseDouble(args[0]) / 100.0;
targetLoad = Math.max(0.0, Math.min(1.0, targetLoad));
} catch (NumberFormatException e) {
System.err.println("参数格式错误，使用默认50%负载");
}
}
System.out.println("开始CPU负载测试，目标利用率: " + (targetLoad * 100) + "%");
System.out.println("按 Ctrl+C 停止");
executeCPULoad(targetLoad);
}
private static void executeCPULoad(double loadRatio) {
final long PERIOD_MS = 100;
while (true) {
long workTime = (long) (PERIOD_MS * loadRatio);
long sleepTime = PERIOD_MS - workTime;
long workStart = System.currentTimeMillis();
while (System.currentTimeMillis() - workStart < workTime) {
Math.sqrt(Math.random());
}
try {
if (sleepTime > 0) {
Thread.sleep(sleepTime);
}
} catch (InterruptedException e) {
System.out.println("\n程序被中断");
return;
}
}
}
}
|
多核
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
public class MultiCoreCPULoader {
public static void main(String[] args) {
double targetLoad = 0.5;
int cores = Runtime.getRuntime().availableProcessors();
for (int i = 0; i < args.length; i++) {
try {
if (args[i].equals("-load") && i + 1 < args.length) {
targetLoad = Double.parseDouble(args[++i]) / 100.0;
targetLoad = Math.max(0.0, Math.min(1.0, targetLoad));
} else if (args[i].equals("-cores") && i + 1 < args.length) {
cores = Integer.parseInt(args[++i]);
cores = Math.max(1, Math.min(cores, Runtime.getRuntime().availableProcessors()));
}
} catch (NumberFormatException e) {
System.err.println("参数格式错误");
printUsage();
return;
}
}
System.out.println("开始CPU负载测试");
System.out.println("目标利用率: " + (targetLoad * 100) + "%");
System.out.println("使用核心数: " + cores);
System.out.println("按 Ctrl+C 停止");
executeMultiCoreCPULoad(targetLoad, cores);
}
private static void executeMultiCoreCPULoad(double loadRatio, int cores) {
ExecutorService executor = Executors.newFixedThreadPool(cores);
for (int i = 0; i < cores; i++) {
final int coreId = i;
executor.submit(() -> {
System.out.println("核心 " + coreId + " 开始工作");
executeSingleCoreCPULoad(loadRatio);
});
}
try {
Runtime.getRuntime().addShutdownHook(new Thread(() -> {
System.out.println("\n正在停止所有核心...");
executor.shutdown();
try {
if (!executor.awaitTermination(5, TimeUnit.SECONDS)) {
executor.shutdownNow();
}
} catch (InterruptedException e) {
executor.shutdownNow();
}
}));
executor.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);
} catch (InterruptedException e) {
System.out.println("\n程序被中断");
executor.shutdownNow();
}
}
private static void executeSingleCoreCPULoad(double loadRatio) {
final long PERIOD_MS = 100;
while (!Thread.currentThread().isInterrupted()) {
long workTime = (long) (PERIOD_MS * loadRatio);
long sleepTime = PERIOD_MS - workTime;
long workStart = System.currentTimeMillis();
while (System.currentTimeMillis() - workStart < workTime &&
!Thread.currentThread().isInterrupted()) {
Math.sqrt(Math.random());
}
try {
if (sleepTime > 0) {
Thread.sleep(sleepTime);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
break;
}
}
}
private static void printUsage() {
System.out.println("用法: java MultiCoreCPULoader [选项]");
System.out.println("选项:");
System.out.println(" -load <百分比> 设置CPU负载 (0-100)，默认50");
System.out.println(" -cores <数量> 指定使用的核心数，默认使用所有核心");
System.out.println("示例:");
System.out.println(" java MultiCoreCPULoader -load 90 # 90%负载，所有核心");
System.out.println(" java MultiCoreCPULoader -load 70 -cores 2 # 70%负载，2个核心");
System.out.println(" java MultiCoreCPULoader # 50%负载，所有核心");
}
}
|
多核和单核的差别是每个核用一个单独线程来处理 load，但是核心思路还是在 workTime 里面用一个 sqrt 的方法来对随机数开平方，其余时间睡眠。
正弦函数版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| public class SineWaveCPULoader {
private static final long PERIOD_MS = 100;
private static final int FREQUENCY = 1;
public static void main(String[] args) {
System.out.println("开始生成正弦波CPU负载...");
System.out.println("波形频率: " + FREQUENCY + "Hz");
System.out.println("按 Ctrl+C 停止");
generateSineWave();
}
private static void generateSineWave() {
long startTime = System.currentTimeMillis();
while (true) {
long currentTime = System.currentTimeMillis();
double timeInSeconds = (currentTime - startTime) / 1000.0;
double sineValue = Math.sin(2 * Math.PI * FREQUENCY * timeInSeconds);
double loadRatio = 0.5 + 0.4 * sineValue;
executeCPULoad(loadRatio);
if ((currentTime / 2000) % 1 == 0) {
System.out.printf("\r时间: %.1fs, 正弦值: %.2f, CPU负载: %.1f%%",
timeInSeconds, sineValue, loadRatio * 100);
System.out.flush();
}
}
}
private static void executeCPULoad(double loadRatio) {
long workTime = (long) (PERIOD_MS * loadRatio);
long sleepTime = PERIOD_MS - workTime;
long workStart = System.currentTimeMillis();
while (System.currentTimeMillis() - workStart < workTime) {
Math.sqrt(Math.random());
}
try {
if (sleepTime > 0) {
Thread.sleep(sleepTime);
}
} catch (InterruptedException e) {
System.out.println("\n程序被中断");
System.exit(0);
}
}
}
|
这个算法的核心是计算距离起点的距离，然后推算出这个阶段的点在正弦曲线上的的纵轴多高，然后再用 executeCPULoad 函数来操纵 CPU。
利用系统 cpu 的解
如果能够获取当前的 cpu 利用率，sleep一个最小循环，然后进到下个 while 里再获取一次。
利用 cpu 的理论执行时间
1
2
3
4
5
6
7
8
9
10
11
12
13
| const DWORD _busyTime = 10;
const DWORD _idleTime = _busyTime;
_int64 _startTime = 0;
void letCpuControl_GetTickCount()
{
while(true)
{
DWORD startTime = GetTickCount();
while(GetTickCount() - startTime <= _busyTime);
_sleep(_idleTime);
}
}
|
中国象棋将帅问题
这个问题主要考察：
- 如果利用一个字节的前后半4位，要怎样用掩码输出，用与运算来获取变更后的值。
- 怎样把二维的位置当作二维矩阵又当作一维向量。
- 怎样从排列组合总数，反推出组号+组内距离的组合。
- 怎样从位置转换为列位置-运用 1-based 的设计。
翻烙饼问题
回溯搜索解空间的基本结构
回溯本质上是深度优先（前中后序遍历二叉树都是深度优先） + 剪枝。
启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径。
1
2
3
4
5
6
7
8
9
10
11
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择本层集合中元素（画成树，就是树节点孩子的大小）){
处理节点;
backtracking();
回溯，撤销处理结果;
}
}
|
回溯=递归+局部枚举+放下前任
P(n,k)=(n−k)!n!C(n,k)=k!(n−k)!n!
===P(n,k) nP(n−1,k−1) P(n−1,k)+kP(n−1,k−1) (n−k)!n!
- 递归函数一般是没有返回值的
- 先写终止条件，一般符合终止条件之后就是要收集结果的时候
- 单层搜索。是一个for循环，一般来说这个循环遍历的就是集合中的所有元素。在这个for循环里处理元素
- 递归（放递归函数）
- 回溯操作（手动撤销）
- 剪枝判断: 检查
if (step + lowerBound(reverseCakeArray, cakeCount) >= maxSwap)是否满足，若满足则直接return;。
- 解的处理: 检查
if (isSorted(reverseCakeArray, cakeCount))是否满足，若是则：
- 更新最优解：
if (step < maxSwap) { maxSwap = step; ... }
- 记录解：将
reverseCakeArraySwap中记录的当前路径复制到swapArray。
- 然后
return;。
- 决策遍历:
for (int i = 1; i < cakeCount; ++i)循环，遍历所有可能的翻转位置i：
- 执行选择: 调用
reverse(0, i);修改工作区reverseCakeArray的状态。
- 记录决策: 执行
reverseCakeArraySwap[step] = i; 将当前决策（翻转位置 i）记录到路径数组reverseCakeArraySwap。
- 递归探索: 调用
search(step + 1);基于修改后的reverseCakeArray状态深入搜索。
- 状态回溯: 递归
search(step + 1)返回后，再次调用reverse(0, i);撤销之前翻转对reverseCakeArray的影响，恢复状态，准备下一次循环（尝试下一个 i）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
backtrack(nums);
return res;
}
void backtrack(int[] nums) {
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
track.addLast(nums[i]);
backtrack(nums);
track.removeLast();
used[i] = false;
}
}
}
|
这里的答案都是使用盒视角（result）来选元素（nums[i]）的。
总流程
