编程之美-学习笔记.doc

编程之美学习笔记

游戏之乐

让CPU占有率曲线听你指挥

解析：此题的运行环境在是单核单线程的P4CPU下，如果是多核多线程的情况下，此题的答案需要进一步探讨。关键概念：CPU的占有率，是每个刷新周期内CPU占有率的统计平均值，通过在刷新周期内调节忙/闲的比例来控制这个。

解法一：利用上述概念，通过设定相应的忙/闲的时间，来到达50%，这里忙的时候，可以用个计算CPU的每个时间周期以及每个时钟周期可以执行的代码，闲的时候，可以通过Sleep(10)。这样能简单地满足条件。

解法二：解法一是通过计算，但是不同电脑的话，要有不同的计算。为了克服这个问题，利用GetTickCount()这个windows的API可以得到“系统启动到现在”的时间，具体原理跟解法一样。但这个更加准确。

解法三，如果要使CPU利用率曲线呈现正弦曲线，那么就要设定忙的时间为正弦函数，可以设定一个数组，存放一个周期内的这些满足条件的值，闲的时候为一个取样时间减忙时间，即可。

中国象棋的将帅问题

解析：要输出将帅不能碰面的所有可能情况，要求在代码中只能使用一个字节存储变量。可以构造一个3*3的逻辑坐标，用1到9来标示位置。将问题通过画图来表达，这样有利于拓展思路，让交流更流畅。让将和帅不在同一条直线上，那么根据一列数字的特点来构思。

解法一：将一个字节的变量的高4位标示A，低4位标示B，然后通过两层循环使A与B不断变化〔移位等〕，通过判断A%3与B%3的关系，把符合的值输出。

解法二：显然解法一的思路很严谨，但是相对来说比拟复杂，尤其是A与B的操作方面，如果能构造一个struct，有两个unsignedchar的4位的变量，控制起来非常简单。

structAB

{

unsignedchara:4;

unsignedcharb:4;

}i;

for(i.a=1;i.a=9;i.a++)

for(i.b=1;i.b=9;i.b++)

if(i.a%3!=i.b%3)

coutA:(int)i.aB:(int)i.bendl;

解法三：不再构造上述的结构体等，直接利用数字的性质，非常的巧妙。

chari=81;

while(i--)

{

if(i/9%3==i%9%3)continue;

coutA:i/9+1B:i%9+1endl;

}

一摞烙饼的排序

解析：显然无法用根本的排序方法对其排序，那么最直接的方法是找出N个数种最大者，将这通过两次翻转放置到最底部，然后处理N-1，N-2等，直到全部排序完，显然一共需要交换2*〔N-1〕次。具体代码如下：

voidreverse(intcakes[],intbeg,intend)

{

inttemp;

while(begend){

temp=cakes[beg];

cakes[beg++]=cakes[end];

cakes[end--]=temp;

}

}

voidcake_sort(intcakes[],intn)

{

intith,max_idx,cur_max,idx;

//find(ith+1)biggestcake

for(ith=n-1;ith=1;--ith)

{

cur_max=cakes[0];

max_idx=0;

for(idx=1;idx=ith;++idx)

{

if(cakes[idx]cur_max){

cur_max=cakes[idx];

max_idx=idx;

}

}

if(max_idx!=ith){

reverse(cakes,0,max_idx);

reverse(cakes,0,ith);

}

}

}

书上的例子是穷举所有的翻转可能，通过评估对每一个递归都做了检查，肯定能找出一个，虽然时间复杂度外表上比拟高，但是递归的开销其实比拟大，还有空间开销很大。

买书问题

解析：此题的关键是无法证明贪心算法是有效的，如果能证明有效，那么用贪心算法的效率将非常高，此题主要告诉了我们思考问题的方法，先贪心，不行的话就动态规划法，如果不存在5+3的价格高于4+