序言

下水道井盖为什么是圆的

“下水道井盖是圆的，因为圆形不会掉进井口，而且圆形具有均匀分布压力的优势。”

一个屋子有一个门（门是关闭的）和3盏电灯。屋外有3个开关，分别与这3盏灯相连。你可以随意操纵这些开关，可一旦你将门打开，就不能变换开关了。确定每个开关具体管哪盏灯？

答：将一盏灯开一段时间，再关掉，在剩余2盏灯里随机开一盏，进屋去看，发热的灯对应第一个碰的开关，亮着的灯对应开关开着的开关，灭的灯对应没碰过的开关。

游戏之乐

如何写一个程序让 cpu 占用率保持在 50%？

不要用 if-else 来解决，要把比例转成不同的 worktime。

解法的精确与否其实取决于“多久时间内测度一次已占用的时间”和“睡眠”两类 api 的精度。

bash 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/bin/bash
# 精简版CPU负载控制器

L=${1:-50}  # 默认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    # 90%负载
./cpu.sh 30    # 30%负载
./cpu.sh       # 50%负载（默认）

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) {
        // 默认50%利用率
        double targetLoad = 0.5;
        
        // 解析命令行参数
        if (args.length > 0) {
            try {
                targetLoad = Double.parseDouble(args[0]) / 100.0;
                // 限制范围在0-1之间
                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 停止");
        
        // 执行CPU负载控制
        executeCPULoad(targetLoad);
    }
    
    private static void executeCPULoad(double loadRatio) {
        final long PERIOD_MS = 100; // 100ms周期
        
        while (true) {
            long workTime = (long) (PERIOD_MS * loadRatio);
            long sleepTime = PERIOD_MS - workTime;
            
            // 工作阶段 - 消耗CPU
            long workStart = System.currentTimeMillis();
            while (System.currentTimeMillis() - workStart < workTime) {
                // 空循环消耗CPU
                Math.sqrt(Math.random());
            }
            
            // 休息阶段 - 让出CPU
            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) {
        // 默认50%利用率
        double targetLoad = 0.5;
        // 默认使用所有CPU核心
        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 停止");
        
        // 执行多核CPU负载控制
        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; // 100ms周期
        
        while (!Thread.currentThread().isInterrupted()) {
            long workTime = (long) (PERIOD_MS * loadRatio);
            long sleepTime = PERIOD_MS - workTime;
            
            // 工作阶段 - 消耗CPU
            long workStart = System.currentTimeMillis();
            while (System.currentTimeMillis() - workStart < workTime && 
                   !Thread.currentThread().isInterrupted()) {
                // 空循环消耗CPU
                Math.sqrt(Math.random());
            }
            
            // 休息阶段 - 让出CPU
            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; // 控制周期100ms
    private static final int FREQUENCY = 1;    // 频率1Hz（每秒一个完整波形）
    
    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;
            
            // 生成正弦波值: sin(2πft)
            // f = FREQUENCY, t = timeInSeconds
            double sineValue = Math.sin(2 * Math.PI * FREQUENCY * timeInSeconds);
            
            // 将正弦波值 [-1,1] 映射到负载比例 [0.1, 0.9]
            // 避免0%和100%极端值以保证稳定性
            double loadRatio = 0.5 + 0.4 * sineValue;
            
            // 执行CPU负载控制
            executeCPULoad(loadRatio);
            
            // 每2秒显示一次当前状态
            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;
        
        // 工作阶段 - 消耗CPU
        long workStart = System.currentTimeMillis();
        while (System.currentTimeMillis() - workStart < workTime) {
            // 空循环消耗CPU
            Math.sqrt(Math.random());
        }
        
        // 休息阶段 - 让出CPU
        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();//更新开始时间为系统开启到现在经历的时间
  // 10ms 的精度渐进式地寻找 GetTickCount() 逼近一个目标时间区间
  while(GetTickCount() - startTime <= _busyTime);//总时间 - 开始时间
  _sleep(_idleTime);
 }
}

中国象棋将帅问题

这个问题主要考察：

  1. 如果利用一个字节的前后半4位，要怎样用掩码输出，用与运算来获取变更后的值。
  2. 怎样把二维的位置当作二维矩阵又当作一维向量。
  3. 怎样从排列组合总数，反推出组号+组内距离的组合。
  4. 怎样从位置转换为列位置-运用 1-based 的设计。

翻烙饼问题

回溯搜索解空间的基本结构

  • 剪枝判断: 检查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）。
flowchart TD
    Start("开始: search(step)") --> Count("搜索计数: searchCount++")
    Count --> Estimate("估计剩余步数: estimate = lowerBound(...)")
    
    %% 剪枝判断
    Estimate --> Prune{"剪枝检查:
    step + estimate >= maxSwap?"}
    Prune -->|是| ReturnPrune("返回: 剪枝 - 路径不优")
    
    %% 检查是否已找到解
    Prune -->|否| CheckSorted{"目标检查:
    isSorted(reverseCakeArray)?"}
    
    %% 解的处理
    CheckSorted -->|是| CheckBetter{"是否更优解?
    step < maxSwap?"}
    CheckBetter -->|是| UpdateSolution("更新最优解:
    1. maxSwap = step
    2. 保存翻转序列")
    UpdateSolution --> ReturnSolution("返回: 记录解")
    CheckBetter -->|否| ReturnSolution
    
    %% 决策遍历
    CheckSorted -->|否| ForLoop("开始决策遍历:
    for i = 1 to cakeCount-1")
    
    %% 递归探索过程
    ForLoop --> Execute("执行选择:
    reverse(0, i) - 翻转饼")
    Execute --> Record("记录决策:
    reverseCakeArraySwap[step] = i")
    Record --> Recurse("递归探索:
    search(step + 1)")
    Recurse --> Backtrack("状态回溯:
    reverse(0, i) - 撤销翻转")
    
    Backtrack --> NextDecision{"继续下一个决策?
    i < cakeCount-1?"}
    NextDecision -->|是| Execute
    NextDecision -->|否| ReturnExhausted("返回: 决策已穷尽")
    
    %% 决策点说明
    Execute -.- ExecuteNote("在当前状态下尝试一种翻转方式")
    Backtrack -.- BacktrackNote("恢复状态以便尝试下一种翻转")
    Recurse -.- RecurseNote("基于当前翻转继续深入搜索")
    
    %% 核心数据结构
    subgraph DataStructures ["主要状态数据"]
        DS1["reverseCakeArray: 当前煎饼状态"]
        DS2["reverseCakeArraySwap: 当前路径记录"]
        DS3["maxSwap: 当前最优解步数"]
        DS4["swapArray: 最优解的翻转序列"]
    end

总流程

flowchart TD
    %% 主程序流程
    Start([开始程序]) --> MainMethod["main()方法"]
    MainMethod --> CreateSorter["创建PancakeSorting实例"]
    CreateSorter --> RunMethod["sorter.run(cakeArrayInput, size)"]
    
    %% Run方法展开
    RunMethod --> InitMethod["init(pCakeArray, cakeCount)"]
    InitMethod --> ResetSearchCount["searchCount = 0"]
    ResetSearchCount --> StartSearch["search(0)"]
    StartSearch --> OutputResult["sorter.output()"]
    OutputResult --> End([结束程序])
    
    %% init方法详情
    subgraph InitProcess ["初始化过程"]
        Init1["保存烙饼数量和初始数组"] --> Init2["设置maxSwap初始上界"]
        Init2 --> Init3["初始化存储最优解的数组swapArray"]
        Init3 --> Init4["初始化工作区reverseCakeArray"]
        Init4 --> Init5["初始化临时日志reverseCakeArraySwap"]
    end
    
    InitMethod -.-> InitProcess
    
    %% 核心搜索算法
    subgraph SearchProcess ["search(step)方法 - 回溯搜索核心"]
        S1["统计搜索次数searchCount++"] --> S2["估算当前状态：estimate = lowerBound(...)"]
        
        %% 剪枝判断
        S2 --> S3{"剪枝条件：
        step + estimate >= maxSwap?"}
        S3 -->|是| S4["返回(剪枝)"]
        
        %% 目标检查
        S3 -->|否| S5{"是否已排序：
        isSorted(reverseCakeArray)?"}
        
        %% 解的处理
        S5 -->|是| S6{"是否更好解：
        step < maxSwap?"}
        S6 -->|是| S7["更新最优解：
        maxSwap = step
        保存翻转序列"]
        S7 --> S8["返回(找到解)"]
        S6 -->|否| S8
        
        %% 决策遍历
        S5 -->|否| S9["开始决策循环：
        for i = 1 to cakeCount-1"]
        
        %% 单步决策逻辑
        S9 --> S10["执行翻转：
        reverse(0, i)"]
        S10 --> S11["记录决策：
        reverseCakeArraySwap[step] = i"]
        S11 --> S12["递归搜索：
        search(step + 1)"]
        S12 --> S13["回溯恢复：
        reverse(0, i)"]
        
        %% 循环控制
        S13 --> S14{"继续循环？
        i < cakeCount-1?"}
        S14 -->|是| S10
        S14 -->|否| S15["返回(穷尽决策)"]
    end
    
    StartSearch -.-> SearchProcess
    
    %% 辅助方法
    subgraph HelperMethods ["辅助方法"]
        H1["isSorted() - 检查是否已排序"]
        H2["lowerBound() - 估算最少翻转次数"]
        H3["reverse() - 执行翻转操作"]
        H4["upperBound() - 计算最大翻转次数"]
    end
    
    %% 核心数据结构
    subgraph DataStructures ["核心数据结构"]
        D1["cakeArray：原始输入数组(只读)"]
        D2["cakeCount：烙饼数量"]
        D3["maxSwap：当前最优解步数"]
        D4["swapArray：最优解翻转序列"]
        D5["reverseCakeArray：当前工作区"]
        D6["reverseCakeArraySwap：当前路径记录"]
        D7["searchCount：搜索统计计数"]
    end
    
    %% 关键操作展示
    subgraph ReverseOperation ["reverse(begin, end)翻转操作"]
        R1["初始化：begin和end指向区间两端"] --> R2{"while(begin < end)"}
        R2 -->|是| R3["交换begin和end位置的元素"]
        R3 --> R4["begin++, end--"]
        R4 --> R2
        R2 -->|否| R5["翻转完成"]
    end
    
    %% 调用关系
    S2 -.-> H2
    S5 -.-> H1
    S10 -.-> H3
    S13 -.-> H3
    Init2 -.-> H4
    
    %% 数据流向
    D5 -..->|"修改工作区"| H3
    D5 -..->|"检查排序状态"| H1
    D5 -..->|"估算剩余步数"| H2
    D6 -..->|"记录翻转决策"| S11
    D3 -..->|"更新最优值"| S7
    D4 -..->|"记录最优解"| S7

    %% 可视化改进
    classDef process fill:#f9f9f9,stroke:#333,stroke-width:1px;
    classDef decision fill:#e1f5fe,stroke:#01579b,stroke-width:1px;
    classDef data fill:#fff9c4,stroke:#fbc02d,stroke-width:1px;
    
    class S3,S5,S6,S14 decision;
    class DataStructures,InitProcess data;
    class SearchProcess,HelperMethods,ReverseOperation process;