编程之美

1.1 cpu使用问题

 

#include <iostream>
#include <ctime>
#include <cmath>
#include <Windows.h>
using namespace std;

//第一种方式
void main()
{
	INT64 start=0;
	int busy=10;
	int idle=busy;
	cout<<"CPU使用率问题";
	while(true)
	{
		start=GetTickCount();
		while((GetTickCount()-start)<=busy);
		Sleep(idle);
	}
}

//第二种方式
int main()
{
	for(;;)
	{
		for(int i = 0; i < 9600000; i++);
		//for(int i = 0; i < 21360000; i++);//2.67Ghz 4核
		Sleep(10);
	}
	return 0;
}

//正玄曲线
const double SPLIT=0.01;
const int COUNT=200;
const double PI=3.14159265;
const int INTERVAL = 300;
void main()
{
	DWORD busy[COUNT],idle[COUNT];
	int half=INTERVAL/2;
	double radian=0.0;
	for(int i=0;i<COUNT;i++)
	{
		busy[i]=DWORD(sin(PI*radian)*half+half);
		idle[i]=INTERVAL-busy[i];
		radian+=0.01;
	}
	DWORD start=0;
	int j=0;
	while(true)
	{
		start=GetTickCount();
		j=j%COUNT;
		while((GetTickCount()-start)<=busy[j]);
		Sleep(idle[j]);
		j++;
	}
}

CPU核心运行周期数

 

#include <iostream>
using namespace std;
inline __int64 GetCPUTickCount()  
{  
	__asm  
	{  
		rdtsc;  
	}  
}
void main()
{
	cout<<"CPU核心运行周期数"<<GetCPUTickCount()<<endl;
	system("pause");
}

 

1.2 将帅问题

 

 

#include <iostream>
using namespace std;

//第一种方式
struct {
	unsigned char a:4;
	unsigned char b:4;
} i;
void main()
{
	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);
	system("pause");
}

//第二种方式
#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));
	system("pause");
	return 0;
}

 

1.12 电梯调度

 

#include <iostream>
using namespace std;
#define N 6
void main()
{
	int nPerson[N]={55,66,77,88,99,44};
	int N1=0,N2=0,N3=0;
	int nTargetFloor=0,nMinFloor=0,i;

	for (i=1,N1=0,N2=nPerson[0],N3=0;i<N;i++)
	{
		N3+=nPerson[i];
		nMinFloor+=nPerson[i+1]*i;
	}
	for (i=1;i<N;i++)
	{
		if (N1+N2<N3)
		{
			nTargetFloor=i+1;
			nMinFloor+=(N1+N2-N3);
			N1+=N2;
			N2=nPerson[i];
			N3-=nPerson[i];
		}
		else
			break;
	}
	cout<<"nTargetFloor "<<nTargetFloor<<"\nnMinFloor "<<nMinFloor<<endl;
	system("pause");
}

 

1.13 NIM两堆石头

 

#include <iostream>
#include <cmath>
using namespace std;
#define swap(x,y) ((x)^=(y),(y)^=(x),(x)^=(y))
void main()
{
	double a,b;
	a=(1+sqrt(5.0))/2;
	b=(3+sqrt(5.0))/2;
	int m,n;
	bool nim=false;
	cout<<"输入两堆石头的书数目\n";
	cin>>m>>n;
	if (m==n)
		nim=true;
	if(n>m)
		swap(n,m);
	if (n-m==(long)floor(n*a))
		nim=false;
	else 
		nim=true;
	if(nim)
		cout<<"先取石头玩家先赢\n";
	else
		cout<<"后取石头玩家先赢\n";
	system("pause");
}

 

2.7 最大公约数最小公倍数求解

http://blog.csdn.net/aoxiangzhiguanjun/article/details/8755260

 

2.13 子数组最大乘积

 

#include <iostream>  
#include   <stdlib.h>   
#include   <stdio.h>   
using namespace  std;  

// 子数组的最大乘积  
int MaxProduct(int *a, int n)  
{  
	int maxProduct = 1; // max positive product at current position  
	int minProduct = 1; // min negative product at current position  
	int r = 1; // result, max multiplication totally  

	for (int i = 0; i < n; i++)  
	{  
		if (a[i] > 0)  
		{  
			maxProduct *= a[i];  
			minProduct = min(minProduct * a[i], 1);  
		}  
		else if (a[i] == 0)  
		{  
			maxProduct = 1;  
			minProduct = 1;  
		}  
		else // a[i] < 0  
		{  
			int temp = maxProduct;  
			maxProduct = max(minProduct * a[i], 1);  
			minProduct = temp * a[i];  
		}  

		r = max(r, maxProduct);  
	}  

	return r;  
}  

int main(int argc, char* argv[])  
{  
	int a[]={1, -2, -1,0,5};  
	int result = MaxProduct(a,5);  
	cout<<result<<endl;  
	system("pause");  
	return 0;  
}  

 

 

2.14 求子数组最大和

给一个数组，元素都是整数（有正数也有负数），寻找连续的元素相加之和为最大的序列。

http://blog.csdn.net/aoxiangzhiguanjun/article/details/8836702

 

3.2 电话号码对应英语单词并实现从数字字典中查询

 

#include <iostream>
using namespace std;
#define telLen 3

void match(char *words)
{
	char *word="YES YER";
	if(strstr(word,words))
	{
		printf("words %s\n",words);
	}
}
void main()
{
	char word[telLen+1]={0};//存储生成的每个单词
	char c[10][10]={"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};//0到9数字所表示的字母
	int total[10]={0,0,3,3,3,3,3,4,3,4};//每个数字里包含的字母个数
	int number[telLen]={9,3,7};//电话号码
	int answer[10]={0};//数组记录每个字母在它所在的数字键能代表的字符集中的偏移（索引）,初始化为0
	int i,j=0;
	while(true)
	{
		for (i=0;i<telLen;i++)
		{
			if(number[i]==1||number[i]==0)//忽略空格的影响
				break;
			else
			{
				printf("%c",c[number[i]][answer[i]]);
				word[i]=c[number[i]][answer[i]];
			}
		}
		word[telLen]='\0';
		match(word);//在数据字典中匹配
		printf("\n");
		int k=telLen-1;
		while(k>=0)
		{
			if (answer[k]<total[number[k]]-1)
			{
				answer[k]++;
				break;
			}
			else
			{
				answer[k]=0;
				k--;
			}
		}
		if (k<0)
			break;
	}
	system("pause");
}

 

 

3.6 编程判断两个链表是否相交

http://blog.csdn.net/aoxiangzhiguanjun/article/details/8804403

 

3.8 二叉树中的一些问题

http://blog.csdn.net/aoxiangzhiguanjun/article/details/8904794

 

3.9 重建二叉树

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node
{
	char    chValue;
	struct Node    *lChild;
	struct Node    *rChild;
}Node;


//重建二叉树
void Rebuild(char *pPreOrder , char *pInOrder , Node **pRoot , int nTreeLen)
{
	int  nLeftLen , nRightLen;
	char *pLeftEnd;
	Node *p;

	//边界条件检查
	if(!pPreOrder || !pInOrder || !pRoot)    return;   

	if(!(p = (Node *)malloc(sizeof(Node))))    return;
	p->chValue = *pPreOrder;    
	p->lChild = p->rChild = NULL;
	*pRoot = p;

	if(nTreeLen == 1)    return;

	//划分左右子数
	pLeftEnd = pInOrder;
	while(*pLeftEnd != *pPreOrder)    pLeftEnd++;
	nLeftLen = (int)(pLeftEnd - pInOrder);
	nRightLen = nTreeLen - nLeftLen - 1;

	if(nLeftLen)    Rebuild(pPreOrder + 1 , pInOrder , &(p->lChild) , nLeftLen);
	if(nRightLen)   Rebuild(pPreOrder + nLeftLen + 1, pInOrder + nLeftLen + 1 , &(p->rChild) , nRightLen);
}

//后序遍历
void PostOrder(Node *p)
{
	if(p)
	{
		PostOrder(p->lChild);
		PostOrder(p->rChild);
		printf("%c",p->chValue);
	}
}

int main(void)
{
	char PreOrder[32] , InOrder[32];
	Node *pTree;

	//输入先序和中序序列
	while(scanf("%s%s", PreOrder , InOrder) != EOF)//abdcef   dbaecf
	{
		Rebuild(PreOrder , InOrder , &pTree , strlen(PreOrder));
		PostOrder(pTree);
		printf("\n");
	}
	return 0;
}

 

 

4.9 数独的构造

 

#include <iostream>  
#include <cstdlib>  
using namespace std;  
/*问题：
构造一个9*9的方格矩阵，玩家要在每个方格中，分别填上1至9的任意一个数字，
让整个棋盘每一列、每一行以及每一个3*3的小矩阵中的数字都不重复。
首先我们通过一个深度优先搜索来生成一个可行解，然后随机删除一定数量的数字，
以生成一个数独。*/
#define LEN 9  
#define CLEAR(a) memset((a), 0, sizeof(a))  

int level[] = {30, 37, 45};  

int grid[LEN+1][LEN+1];  
int value[LEN+1];  

void next(int &x, int &y)  
{  
	x++;  
	if (x>9)  
	{  
		x = 1;  
		y++;  
	}  
}  

// 选择下一个有效状态  
int pickNextValidValue(int x, int y, int cur)  
{  
	CLEAR(value);  
	int i, j;  
	for (i=1; i<y; i++)  
		value[grid[i][x]] = 1;  
	for (j=1; j<x; j++)  
		value[grid[y][j]] = 1;  
	int u = (x-1)/3*3 + 1;  
	int v = (y-1)/3*3 + 1;  
	for (i=v; i<v+3; i++)  
		for (j=u; j<u+3; j++)  
		{  
			value[grid[i][j]] = 1;  
		}  
		for (i=cur+1; i<=LEN && value[i]; i++);  
		return i;  
}  

void pre(int &x, int &y)  
{  
	x--;  
	if (x<1)  
	{  
		x = 9;  
		y--;  
	}  
}  

int times = 0;  

int main()  
{  
	int x, y, i, j;  
	x = y = 1;  
	// 深度搜索的迭代算法  
	while (true)  
	{  
		times++;  
		// 满足成功结果  
		if (y==LEN && x==LEN)  
		{  
			for (i=1; i<=LEN; i++)  
			{  
				for (j=1; j<=LEN; j++)  
					cout << grid[i][j] << " ";  
				cout << endl;  
			}  
			cout << times << endl;  
			break;  
			//pre(x, y);  
			//times = 0;  
		}  
		// 满足失败结果  
		if (y==0)  
			break;  
		// 改变状态  
		grid[y][x] = pickNextValidValue(x, y, grid[y][x]);  
		if (grid[y][x] > LEN)  
		{  
			// 恢复状态  
			grid[y][x] = 0;  
			pre(x, y);  
		}  
		else  
			// 进一步搜索  
			next(x,y);  
	}  
	for (i=1; i<= level[2]; i++)  
	{  
		int ind = rand()%(LEN*LEN);  
		grid[ind/LEN+1][ind%LEN] = 0;  
	}  
	for (i=1; i<=LEN; i++)  
	{  
		for (j=1; j<=LEN; j++)  
			cout << grid[i][j] << " ";  
		cout << endl;  
	}  
	system("pause");
}  

 

 

4.10 数字哑谜和回文

 

#include<iostream>
#include<string>
using namespace std;
// 题目:人过大佛寺*我=寺佛大过人.   其中每个字母代表着一个不同的数字.
int main()
{
	bool flag;
	bool IsUsed[10];
	int number,revert_number,t,v;
	for(number=0;number<100000;number++)
	{
		flag=true;
		memset(IsUsed,0,sizeof(IsUsed));
		t=number;
		revert_number=0;
		for(int i=0;i<5;i++)
		{
			v=t%10;
			revert_number=revert_number*10+v;
			t/=10;
			if(IsUsed[v])
				flag=false;
			else
				IsUsed[v]=1;
		}
		if(flag&&(revert_number%number==0))
		{
			v=revert_number/number;
			if(v<10&&!IsUsed[v])
				cout<<number<<" "<<v<<" "<<revert_number<<endl;
		}
	}
	system("pause");
	return 0;
}

 

编程之美 完

以上有些代码参考《编程之美》还有一些是参考网络上的，剩下的是自己编写的。