编程之美随书源代码-中文注释.doc

55

第1章
游戏之乐
——游戏中碰到的题目
代码清单1-1
1.
int main()
{
for(; ;
{
for(int i = 0; i < 9600000; i++)
;
Sleep(10);
}
return 0;
}
代码清单1-2

int busyTime = 10; // 10 ms
int idleTime = busyTime; // same ratio will lead to 50% cpu usage

Int64 startTime = 0;
while(true)
{
startTime = GetTickCount();
// busy loop
while((GetTickCount() - startTime) <= busyTime)
;

// idle loop
Sleep(idleTime);
}
代码清单1-3
2.
// C# code
static void MakeUsage(float level)
{
PerformanceCounter p = new PerformanceCounter("Processor",
"%Processor Time", "_Total");

if(p==NULL)
{
return
}

while(true)
{
if(p.NextValue() > level)
System.Threading.Thread.Sleep(10);
}
}
代码清单1-4

// C++ code to make task manager generate sine graph
#include "Windows.h"
#include "stdlib.h"
#include "math.h"

const double SPLIT = 0.01;
const int COUNT = 200;
const double PI = 3.14159265;
const int INTERVAL = 300;

int _tmain(int argc, _TCHAR* argv[])
{
DWORD busySpan[COUNT]; // array of busy times
DWORD idleSpan[COUNT]; // array of idle times
int half = INTERVAL / 2;
double radian = 0.0;
for(int i = 0; i < COUNT; i++)
{
busySpan[i] = (DWORD)(half + (sin(PI * radian) * half));
idleSpan[i] = INTERVAL - busySpan[i];
radian += SPLIT;
}

DWORD startTime = 0;
int j = 0;
while(true)
{
j = j % COUNT;
startTime = GetTickCount();
while((GetTickCount() - startTime) <= busySpan[j])
;
Sleep(idleSpan[j]);
j++;
}
return 0;
}
代码清单1-5

_PROCESSOR_POWER_INFORMATION info;

CallNTPowerInformation(11, // query processor power information
NULL, // no input buffer
0, // input buffer size is zero
&info, // output buffer
Sizeof(info)); // outbuf size

__int64 t_begin = GetCPUTickCount();

// do something

__int64 t_end = GetCPUTickCount();
double millisec = ((double)t_end –(double)t_begin)
/(double)info.CurrentMhz;
代码清单1-6

#define HALF_BITS_LENGTH 4
// 这个值是记忆存储单元长度的一半，在这道题里是4bit
#define FULLMASK 255
// 这个数字表示一个全部bit的mask，在二进制表示中，它是11111111。
#define LMASK (FULLMASK << HALF_BITS_LENGTH)
// 这个宏表示左bits的mask，在二进制表示中，它是11110000。
#define RMASK (FULLMASK >> HALF_BITS_LENGTH)
// 这个数字表示右bits的mask，在二进制表示中，它表示00001111。
#define RSET(b, n) (b = ((LMASK & b) ^ n))
// 这个宏，将b的右边设置成n
#define LSET(b, n) (b = ((RMASK & b) ^ (n << HALF_BITS_LENGTH)))
// 这个宏，将b的左边设置成n
#define RGET(b) (RMASK & b)
// 这个宏得到b的右边的值
#define LGET(b) ((LMASK & b) >> HALF_BITS_LENGTH)
// 这个宏得到b的左边的值
#define GRIDW 3
// 这个数字表示将帅移动范围的行宽度。
#include <stdio.h>
#define HALF_BITS_LENGTH 4
#define FULLMASK 255
#define LMASK (FULLMASK << HALF_BITS_LENGTH)
#define RMASK (FULLMASK >> HALF_BITS_LENGTH)
#define RSET(b, n) (b = ((LMASK & b) ^ n))
#define LSET(b, n) (b = ((RMASK & b) ^ (n << HALF_BITS_LENGTH)))
#define RGET(b) (RMASK & b)
#define LGET(b) ((LMASK & b) >> HALF_BITS_LENGTH)
#define GRIDW 3

int main()
{
unsigned char b;
for(LSET(b, 1); LGET(b) <= GRIDW * GRIDW; LSET(b, (LGET(b) + 1)))
for(RSET(b, 1); RGET(b) <= GRIDW * GRIDW; RSET(b, (RGET(b) + 1)))
if(LGET(b) % GRIDW != RGET(b) % GRIDW)
printf("A = %d, B = %d\n", LGET(b), RGET(b));

return 0;
}
代码清单1-7

struct {
unsigned char a:4;
unsigned char b: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)
printf(“A = %d, B = %d\n”, i.a, i.b);
代码清单1-8

/****************************************************************/
//
// 烙饼排序实现
//
/****************************************************************/
class CPrefixSorting
{
public:

CPrefixSorting()
{
m_nCakeCnt = 0;
m_nMaxSwap = 0;
}

~CPrefixSorting()
{
if( m_CakeArray != NULL )
{
delete m_CakeArray; 
}
if( m_SwapArray != NULL )
{
delete m_SwapArray; 
}
if( m_ReverseCakeArray != NULL )
{
delete m_ReverseCakeArray; 
}
if( m_ReverseCakeArraySwap != NULL )
{
delete m_ReverseCakeArraySwap; 
}
}

//
// 计算烙饼翻转信息
// @param
// pCakeArray 存储烙饼索引数组
// nCakeCnt 烙饼个数
//
void Run(int* pCakeArray, int nCakeCnt)
{
Init(pCakeArray, nCakeCnt);

m_nSearch = 0;
Search(0);
}

//
// 输出烙饼具体翻转的次数
//
void Output()
{
for(int i = 0; i < m_nMaxSwap; i++)
{
printf("%d ", m_arrSwap[i]);
}

printf("\n |Search Times| : %d\n", m_nSearch);
printf("Total Swap times = %d\n", m_nMaxSwap);
}

private:

//
// 初始化数组信息
// @param
// pCakeArray 存储烙饼索引数组
// nCakeCnt 烙饼个数
//
void Init(int* pCakeArray, int nCakeCnt)
{
Assert(pCakeArray != NULL);
Assert(nCakeCnt > 0);

m_nCakeCnt = nCakeCnt;

// 初始化烙饼数组
m_CakeArray = new int[m_nCakeCnt];
Assert(m_CakeArray != NULL);
for(int i = 0; i < m_nCakeCnt; i++)
{
m_CakeArray[i] = pCakeArray[i];
}

// 设置最多交换次数信息
m_nMaxSwap = UpBound(m_nCakeCnt);

// 初始化交换结果数组
m_SwapArray = new int[m_nMaxSwap + 1];
Assert(m_SwapArray != NULL);

// 初始化中间交换结果信息
m_ReverseCakeArray = new int[m_nCakeCnt];
for(i = 0; i < m_nCakeCnt; i++)
{
m_ReverseCakeArray[i] = m_CakeArray[i];
}
m_ReverseCakeArraySwap = new int[m_nMaxSwap];
}

//
// 寻找当前翻转的上界
//
//
int UpBound(int nCakeCnt)
{
return nCakeCnt*2;
}

//
// 寻找当前翻转的下界
//
//
int LowerBound(int* pCakeArray, int nCakeCnt)
{
int t, ret = 0;

// 根据当前数组的排序信息情况来判断最少需要交换多少次
for(int i = 1; i < nCakeCnt; i++)
{
// 判断位置相邻的两个烙饼，是否为尺寸排序上相邻的
t = pCakeArray[i] - pCakeArray[i-1];
if((t == 1) || (t == -1))
{
}
else
{
ret++;
}
}
return ret;
}

// 排序的主函数
void Search(int step)
{
int i, nEstimate;

m_nSearch++;

// 估算这次搜索所需要的最小交换次数
nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt);
if(step + nEstimate > m_nMaxSwap)
return;

// 如果已经排好序，即翻转完成，输出结果
if(IsSorted(m_ReverseCakeArray, m_nCakeCnt))
{
if(step < m_nMaxSwap)
{
m_nMaxSwap = step;
for(i = 0; i < m_nMaxSwap; i++)
m_arrSwap[i] = m_ReverseCakeArraySwap[i];
}
return;
}

// 递归进行翻转
for(i = 1; i < m_nCakeCnt; i++)
{
Revert(0, i);
m_ReverseCakeArraySwap[step] = i;
Search(step + 1);
Revert(0, i);
}
}
//
// true : 已经排好序
// false : 未排序
//
bool IsSorted(int* pCakeArray, int nCakeCnt)
{
for(int i = 1; i < nCakeCnt; i++)
{
if(pCakeArray[i-1] > pCakeArray[i])
{
return false;
}
}
return true;
}

//
// 翻转烙饼信息
//
void Revert(int nBegin, int nEnd)
{
Assert(nEnd > nBegin);
int i, j, t;

// 翻转烙饼信息
for(i = nBegin, j = nEnd; i < j; i++, j--)
{
t = m_ReverseCakeArray[i];
m_ReverseCakeArray[i] = m_ReverseCakeArray[j];
m_ReverseCakeArray[j] = t;
}
}

private:

int* m_CakeArray; // 烙饼信息数组
int m_nCakeCnt; // 烙饼个数
int m_nMaxSwap; // 最多交换次数。根据前面的推断，这里最多为
// m_nCakeCnt * 2
int* m_SwapArray; // 交换结果数组

int* m_ReverseCakeArray; // 当前翻转烙饼信息数组
int* m_ReverseCakeArraySwap; // 当前翻转烙饼交换结果数组
int m_nSearch; // 当前搜索次数信息
};
代码清单1-9

int Cal(int V, int T)
{
opt[0][T] = 0; // 边界条件，T为所有饮料种类
for(int i = 1; i <= V; i++) // 边界条件
{
opt[i][T] = -INF;
}
for(int j = T - 1; j >= 0; j--)
{
for(int i = 0; i <= V; i++)
{
opt[i][j] = -INF;
for(int k = 0; k <= C[j]; k++) // 遍历第j种饮料选取数量k
{
if(i < k * V[j])
{
break;
}
int x = opt[i - k * V[j]][j + 1];
if(x != -INF)
{
x += H[j] * k;
if(x > opt[i][j])
{
opt[i][j] = x;
}
}
}
}
}
return opt[V][0];
}
代码清单1-10

int[V + 1][T + 1] opt; // 子问题的记录项表，假设从i到T种饮料中，
// 找出容量总和为V'的一个方案，满意度最多能够达到
// opt（V'，i，T-1），存储于opt[V'][i]，
// 初始化时opt中存储值为-1，表示该子问题尚未求解。
int Cal(int V, int type)
{
if(type == T)
{
if(V == 0)
return 0;
else
return -INF;
}
if(V < 0)
return -INF;
else if(V == 0)
return 0;
else if(opt[V][type] != -1)
return opt[V][type]; // 该子问题已求解，则直接返回子问题的解；
// 子问题尚未求解，则求解该子问题
int ret = -INF;
for(int i = 0; i <= C[type]; i++)
{
int temp = Cal(V – i * C[type], type + 1);
if(temp != -INF)
{
temp += H[type] * i;
if(temp > ret)
ret = temp;
}

}
return opt[V][type] = ret;
}
代码清单1-11

int nPerson[]; // nPerson[i]表示到第i层的乘客数目
int nFloor, nMinFloor, nTargetFloor;
nTargetFloor = -1;
for(i = 1; i <= N; i++)
{
nFloor = 0;
for(j = 1; j < i; j++)
nFloor += nPerson[j] * (i - j);
for(j = i + 1; j <= N; j++)
nFloor += nPerson[j] *(j - i);
if(nTargetFloor == -1 || nMinFloor > nFloor)
{
nMinFloor = nFloor;
nTargetFloor = i;
}
}
return(nTargetFloor, nMinFloor);
代码清单1-12

int nPerson[]; // nPerson[i]表示到第i层的乘客数目
int nMinFloor, nTargetFloor;
int N1, N2, N3;

nTargetFloor = 1;
nMinFloor = 0;
for(N1 = 0, N2 = nPerson[1], N3 = 0, i = 2; i <= N; i++)
{
N3 += nPerson[i];
nMinFloor += nPerson[i] * (i - 1);
}
for(i = 2; i <= N; i++)
{
if(N1 + N2 < N3)
{
nTargetFloor = i;
nMinFloor += (N1 + N2 - N3);
N1 += N2;
N2 = nPerson[i];
N3 -= nPerson[i];
}
else
break;
}

return(nTargetFloor, nMinFloor);
代码清单1-13

int nMaxColors = 0, i, k, j;
for(i = 0; i < N; i++)
{
for(k = 0; k < nMaxColors; k++)
isForbidden[k] = false;
for(j = 0; j < i; j++)
if(Overlap(b[j], e[j], b[i], e[i]))
isForbidden[color[j]] = true;
for(k = 0; k < nMaxColors; k++)
if(!isForbidden[k])
break;
if(k<nMaxColors)
color[i] = k;
else
color[i] = nMaxColors++;
}
return nMaxColors；
代码清单1-14

/*TimePoints数组就是将所有的B[i],E[i]按大小排序的结果。
这个数组的元素有两个成员，一个是val,表示这个元素代表的时间点的数值，另一个是type,表示这个元素代表的时间点是一个时间段的开始（B[i]），还是结束(E[i])。*/
int nColorUsing = 0, MaxColor = 0;
for(int i = 0; i < 2 * N; i++)
{
if(TimePoints[i].type == “Begin”)
{
nColorUsing++;
if(nColorUsing > MaxColor)
MaxColor = nColorUsing;
}
else
nColorUsing--;
}
代码清单1-15

while(true)
{
bool isDownloadCompleted;
isDownloadCompleted = GetBlockFromNet(g_buffer);
WriteBlockToDisk(g_buffer);
if(isDownloadCompleted)
break;
}
代码清单1-16

class Thread
{
public:
// initialize a thread and set the work function
Thread(void (*work_func)());
// once the object is destructed, the thread will be aborted
~Thread();
// start the thread
void Start();
// stop the thread
void Abort();
};

class Semaphore
{
public:
// initialize semaphore counts
Semaphore(int count, int max_count);
~Semaphore();
// consume a signal (count--), block current thread if count == 0
void Unsignal();
// raise a signal (count++)
void Signal();
};

class Mutex
{
public:
// block thread until other threads release the mutex
WaitMutex();
// release mutex to let other thread wait for it
ReleaseMutex();
};
代码清单1-17

#define BUFFER_COUNT 100
Block g_buffer[BUFFER_COUNT];

Thread g_threadA(ProcA);
Thread g_threadB(ProcB);
Semaphore g_seFull(0, BUFFER_COUNT);
Semaphore g_seEmpty(BUFFER_COUNT, BUFFER_COUNT);
bool g_downloadComplete;
int in_index = 0;
int out_index = 0;

void main()
{
g_downloadComplete = false;
threadA.Start();
threadB.Start();
// wait here till threads finished
}
void ProcA()
{
while(true)
{
g_seEmpty.Unsignal();
g_downloadComplete = GetBlockFromNet(g_buffer + in_index);
in_index = (in_index + 1) % BUFFER_COUNT;
g_seFull.Signal();
if(g_downloadComplete)
break;
}
}

void ProcB()
{
while(true)
{
g_seFull.Unsignal();
WriteBlockToDisk(g_buffer + out_index);
out_index = (out_index + 1) % BUFFER_COUNT;
g_seEmpty.Signal();
if(g_downloadComplete && out_index == in_index)
break;
}
}
代码清单1-18：C#自底向上的解法

static bool nim(int x, int y)
{
// speical case
if(x == y)
{
return true; // I win
}

// swap the number
if(x > y)
{
int t = x; x = y; y = t;
}

// basic cases
if(x == 1 && y == 2)
{
return false; // I l