1.1 让CPU占用率曲线听你指挥

Note:对于不懂的东西，先了解概念或定义，再考虑操纵它。

Definition:

CPU占用率（CPU Usage），在任务管理器的一个刷新周期内，CPU忙的时间和刷新周期总时间的比率，＝BusyTime/TotalTime

Trial:

文中使用的是Windows系统，由于自己的电脑是Mac，便想试试Mac下的效果。要获得图中的两个小窗口，点击上方菜单栏中“窗口->CPU使用率”和“窗口->CPU历史记录”。在Mac中编译C++文件要用到g++，系统自带，编译后生成一个a.out的文件。

$ g++ 50%CPU.cpp
$ ./a.out

Trial-1:死循环

活动监视器里a.out的CPU占用率确实达到了100%，但是下边显示的每个核（还是每个CPU）的利用率并未达到100%，而是两个柱形各达到了约50%。

Trial-2:50%占用率

CPU配置是2.5GHz Intel Core i7，按照书中每秒执行两条汇编的估算方式，循环次数应为1＊10^9，然后休息1000ms。实际编写为1＊10^7，休息10ms。结果CPU占用率为0～1%。设定循环次数为5＊10^8，休息1ms，a.out的CPU占用率总算达到了50%，但是一直在40%～60%之间波动，不知道这是什么原因，难道是系统缘故？每秒执行汇编的速度会变动？监视器更新频率设定为1s/2s/5s都差不多。

Trial-3:指定CPU

Windows中的函数都用不了，如GetProcessorInfo()、SetThreadAffinityMask()等。Google了Mac下CPU调度的相关函数也是寥寥，不过最终还是找到了thread_policy_set()这个官方API。代码如下：

int core = 1;
thread_port_t mach_thread = pthread_mach_thread_np(pthread_self());
thread_affinity_policy_data_t policy = { core };
thread_policy_set(mach_thread1, THREAD_AFFINITY_POLICY,
                    (thread_policy_t)&policy, 1);

但是并没有效果，即使是死循环也是分配到多个CPU上……猜测是函数的参数不对或者不是用这个函数。对系统调度的知识匮乏，只能等大牛解答或者以后再试了。

1.2 中国象棋将帅问题

Note:感觉在面试的时候，要把“一个变量”的要求问清楚，数组算一个变量嘛？结构体算一个变量嘛？字符串算一个变量嘛？输出的形式问清楚，用数字坐标表示？用象棋坐标表示？

自己思考后看了第一个解答不敢相信竟然要这么复杂。直到看到后面，才知道给的第一个解过于复杂了倒像是在炫技，其实简洁最美，高手只用简单的BYTE类型（自己试了下，Mac上报错BYTE显示未定义，使用整型也可以）和寥寥数行代码搞定了，列出来欣赏下：

BYTE i = 81;
while(i--){
    if (i / 9 % 3 == i % 9 % 3)
        continue;
    printf("A = %d, B = %d\n", i / 9 + 1, i % 9 + 1);
}

C/C++原生的变量只有void, int, short, long, float, double和char。猜测作者详细介绍第一种方法即是为了介绍知识也是为了铺垫后面简洁的答案吧。第三个解法的效率高在减少了81次取模和81次除的运算？

1.3 一摞烙饼的排序

搜索剪枝问题，如果要发Paper估计就是如何计算更小／更大的上下界，或者其他的剪枝方法（盖茨大牛唯一一篇论文）。

扩展问题:

感觉有点像二分之后各自排序，待仔细研究吧。
翻到最上面后，根据情况不翻或多翻一次吧，但是这样是最优的吗……
概率问题1/2，不是很懂为什么要问这个问题。
把翻转数替换为翻转烙饼的总个数，然后计算上下边界＋剪枝
……为难菜鸡这种问题真的合适吗？那我只能找规律猜是16了。

编程之美笔记 1