每年一到要找工作的时候，我就能收到很多人给我发来的邮件，总是问我怎么选择他们的offer，去腾讯还是去豆瓣，去外企还是去国内的企业，去创业还是去考研，来北京还是回老家，该不该去创新工场？该不该去thoughtworks？……等等，等等。今年从7月份到现在，我收到并回复了60多封这样的邮件。我更多帮他们整理思路，帮他们明白自己最想要的是什么。（注：我以后不再回复类似的邮件了）。

我深深地发现，对于我国这样从小被父母和老师安排各种事情长大的人，当有一天，父母和老师都跟不上的时候，我们几乎完全不知道怎么去做选择。而我最近也离开了亚马逊，换了一个工作。又正值年底，就像去年的那篇《三个故事和三个问题》一样，让我想到写一篇这样的文章。

几个例子

当我们在面对各种对选择的影响因子的时候，如：城市，公司规模，公司性质，薪水，项目，户口，技术，方向，眼界…… 你总会发现，你会在几个公司中纠结一些东西，举几个例子：

某网友和我说，他们去上海腾讯，因为腾讯的规模很大，但却发现薪水待遇没有豆瓣高（低的还不是一点），如果以后要换工作的话，起薪点直接关系到了以后的高工资。我说那就去豆瓣吧，他说豆瓣在北京，污染那么严重，又没有户口，生存环境不好。我说去腾讯吧，他说腾讯最近组织调整，不稳定。我说那就去豆瓣吧，慢公司，发展很稳当。他说，豆瓣的盈利不清楚，而且用Python，自己不喜欢。我说，那就去腾讯吧，……
还有一网友和我说，他想回老家，因为老家的人脉关系比较好，能混得好。但又想留在大城市，因为大城市可以开眼界。
另一网友和我说，他想进外企，练练英语，开开眼界，但是又怕在外企里当个螺丝钉，想法得不到实施。朋友拉他去创业，觉得创业挺好的，锻炼大，但是朋友做的那个不知道能不能做好。
还有一网友在创新工场的某团队和考研之间抉择，不知道去创新工场行不行，觉得那个项目一般，但是感觉那个团队挺有激情的，另一方面觉得自己的学历还不够，读个研应该能找到更好的工作。
还有一些朋友问题我应该学什么技术？不应该学什么技术？或是怎么学会学得最快，技术的路径应该是什么？有的说只做后端不做前端，有的说，只做算法研究，不做工程，等等，等等。因为他们觉得人生有限，术业有专攻。
等等，等等……

我个人觉得，如果是非计算机科班出生的人不会做选择，不知道怎么走也罢了，但是我们计算机科班出生的人是学过算法的，懂算法的人应该是知道怎么做选择的。

排序算法

你不可能要所有的东西，所以你只能要你最重要的东西，你要知道什么东西最重要，你就需要对你心内的那些欲望和抱负有清楚的认识，不然，你就会在纠结中度过。

所以，在选择中纠结的人有必要参考一下排序算法。

首先，你最需要参考的就是“冒泡排序”——这种算法的思路就是每次冒泡出一个最大的数。所以，你有必要问问你自己，面对那些影响你选择的因子，如果你只能要一个的话，你会要哪个？而剩下的都可以放弃。于是，当你把最大的数，一个一个冒泡出来的时候，并用这个决策因子来过滤选项的时候，你就能比较容易地知道知道你应该选什么了。这个算法告诉我们，人的杂念越少，就越容易做出选择。
好吧，可能你已茫然到了怎么比较两个决策因子的大小，比如：你分不清楚，工资>业务前景吗？业务前景>能力提升吗？所以你完全没有办法进行冒泡法。那你，你不妨参考一个“快速排序”的思路——这个算法告诉我们，我们一开始并不需要找到最大的数，我们只需要把你价值观中的某个标准拿出来，然后，把可以满足这个价值的放到右边，不能的放到左边去。比如，你的标准是：工资大于5000元&&业务前景长于3年的公司，你可以用这个标准来过滤你的选项。然后，你可以再调整这个标准再继续递归下去。这个算法告诉我们，我们的选择标准越清晰，我们就越容易做出选择。

这是排序算法中最经典的两个算法了，面试必考。相信你已烂熟于心中了。所以，我觉得你把这个算法应用于你的人生选择也应该不是什么问题。关于在于，你是否知道自己想要的是什么？

排序算法的核心思想就是，让你帮助你认清自己最需要的是什么，认清自己最想要的是什么，然后根据这个去做选择。

贪婪算法

所谓贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择（注意：是当前状态下），从而希望导致结果是最好或最优的算法。贪婪算法最经典的一个例子就是哈夫曼编码。

对于人类来说，一般人在行为处事的时候都会使用到贪婪算法，

比如在找零钱的时候，如果要找补36元，我们一般会按这样的顺序找钱：20元，10元，5元，1元。
或者我们在过十字路口的时候，要从到对角线的那个街区时，我们也会使用贪婪算法——哪边的绿灯先亮了我们就先过到那边去，然后再转身90度等红灯再过街。

这样的例子有很多。对于选择中，大多数人都会选用贪婪算法，因为这是一个比较简单的算法，未来太复杂了，只能走一步看一步，在当前的状况下做出最利于自己的判断和选择即可。

有的人会贪婪薪水，有的人会贪婪做的项目，有的人会贪婪业务，有的人会贪婪职位，有的人会贪婪自己的兴趣……这些都没什么问题。贪婪算法并没有错，虽然不是全局最优解，但其可以让你找到局部最优解或是次优解。其实，有次优解也不错了。贪婪算法基本上是一种急功近利的算法，但是并不代表这种算法不好，如果贪婪的是一种长远和持续，又未尝不可呢？。

动态规划

但是我们知道，对于大部分的问题，贪婪法通常都不能找出最优解，因为他们一般没有测试所有可能的解。因为贪婪算法是一种短视的行为，只会跟据当前的形式做判断，也就是过早做决定，因而没法达到最佳解。

动态规划和贪婪算法的最大不同是，贪婪算法做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

动态规划算法至少告诉我们两个事：

1）**承前启后非常重要，**当你准备去做遍历的时候，你的上次的经历不但能开启你以后的经历，而且还能为后面的经历所用。你的每一步都没有浪费。

2）是否可以回退也很重要。这意思是——如果你面前有两个选择，一个是A公司一个是B公司，如果今天你错失了B公司，那到你明天还能不能找回来？

比如说：你有两个offer，一个是Yahoo，一个是Baidu，上述的第一点会让我们思考，Yahoo和Baidu谁能给我们开启更大的平台？上述的第二点告诉我们，是进入Yahoo后如果没有选好，是否还能回退到Baidu公司？还是进入Baidu公司后能容易回退到Yahoo公司？

Dijkstra最短路径

最短路径是一个Greedy + DP的算法。相当经典。这个算法的大意如下：

1）在初始化的时候，所有的结点都和我是无穷大，默认是达不到的。

2）从离自己最近的结点开始贪婪。

3）走过去，看看又能到达什么样的结点，计算并更新到所有目标点的距离。

4）再贪婪与原点最短的结点，如此反复。

这个算法给我们带来了一些这样的启示：

有朋友和我说过他想成为一个架构师，或是某技术领域的专家，并会踏踏实实的向这个目标前进，永不放弃。我还是鼓励了他，但我也告诉他了这个著名的算法，我说，这个算法告诉你，架构师或某领域的专家对你来说目前的距离是无穷大，他们放在心中，先看看你能够得着的东西。**所谓踏实，并不是踏踏实实追求你的目标，而是踏踏实实把你够得着看得见的就在身边的东西干好。**我还记得我刚参加工作，从老家出来的时候，从来没有想过要成为一个技术牛人，也从来没有想过我的博客会那么的有影响力，在做自己力所能及，看得见摸得着的事情，我就看见什么技术就学什么，学着学着就知道怎么学更轻松，怎么学更扎实，这也许就是我的最短路径。
有很多朋友问我要不要学C++，或是问我学Python还是学Ruby，是不是不用学前端，等等。这些朋友告诉我，他们不可能学习多个语言，学了不用也就忘了，而且术业有专攻。这并没有什么不对的，只是我个人觉得，学习一个东西没有必要只有两种状态，一种是不学，另一种是精通。了解一个技术其实花不了多少时间，我学C++的目的其实是为了更懂Java，学TCP/IP协议其实是为了更懂Socket编程，很多东西都是连通和相辅相成的，学好了C/C++/Unix/TCP等这些基础技术后，我发现到达别的技术路径一下缩短了（这就是为什么我用两天时间就可以了解Go语言的原因）。这就好像这个算法一样，算法效率不高，也许达到你的目标，你在一开始花了很长时间，遍历了很多地方，但是，这也许这就是你的最短路径。

算法就是Trade-Off

你根本没有办法能得到所有你想得到的东西，任何的选择都意味着放弃——当你要去获得一个东西的时候，你总是需要放弃一些东西。人生本来就是一个跷跷板，一头上，另一头必然下。这和我们做软件设计或算法设计一样，用时间换空间，用空间换时间，还有CAP理论，总是有很多的Trade-Off，正如这个短语的原意一样——你总是要用某种东西去交易某种东西。

我们都在用某种东西在交易我们的未来，有的人用自己的努力，有的人用自己的思考，有的人用自己的年轻，有的人用自己的自由，有的人用自己的价值观，有的人用自己的道德…… …… 有的人在交换金钱，有的人在交换眼界，有的人在交换经历，有的人在交换地位，有的人在交换能力，有的人在交换自由，有的人在交换兴趣，有的人在交换虚荣心，在交换安逸享乐…… ……

每个人有每个人的算法，每个算法都有每个算法的purpose，就算大家在用同样的算法，但是每个人算法中的那些变量、开关和条件都不一样，得到的结果也不一样。我们就是生活在Matrix里的一段程序，我们每个人的算法决定着我们每个人的选择，我们的选择决定了我们的人生。

2012年就要过去了，祝大家新年快乐！

插图来自电影 Life of Pi

（全文完）

（转载本站文章请注明作者和出处酷壳 – CoolShell.cn ，请勿用于任何商业用途）

——=== 访问酷壳404页面以支持公益事业 ===——

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/9294305

2013/03/31

posted in OJ题解

HDU OJ 4505 小Q系列故事——电梯里的爱情

#include <stdio.h>

int max(int a[100], int n)	//求最高层数
{
	int highest;
	int i;

	highest = a[0];

	for (i = 1; i < n; i++)
	{
		if (a[i] > highest)
			highest = a[i];
	}

	return highest;
}

int count_time(int n, int a[100], int highest)//计算每组测试需要的总时间
{
	int i, j;
	int flag;		//标记每层是否有人下
	int time;

	time = 0;
	for (i = 0; i <= highest; i++)	//计算每层花费时间
	{
		time += 6;
		flag = 0;
		for (j = 0; j < n; j++)		//计算每层每个人花费的时间
		{
			if (a[j] == i)
			{
				time += 1;
				flag = 1;
			}
		}
		if (flag)					//每层的开门时间
			time += 5;		
	}

	time += highest * 4;			//电梯下楼花费时间

	return time;
}

int main()
{
	int c, n, a[100], time;
	int i;
	int highest;	//要到的最高层

	scanf("%d", &c);

	while (c != 0)
	{
		time = 0;

		scanf("%d", &n);
		for (i = 0; i < n; i++)		//记录每个人要到的层数到a[i]
		{
			scanf("%d", &a[i]);
		}

		highest = max(a, n);

		time = count_time(n, a, highest);	//计算每组测试需要的总时间
		
		printf("%d\n", time-6);

		c--;
	}

	return 0;
}

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/8743678

2013/03/29

posted in OJ题解

HDU OF 4509 湫湫系列故事——减肥记II

/*
2013年3月23日16:54:09
HDU OJ 4509
也是 腾讯马拉松 2月21日 第5题
*/
#include <stdio.h>

bool is_later(int h1, int m1, int h, int m)	//判断某时间点是否在开始时间点后
{
	if ((h>h1) || ((h==h1)&&(m>=m1)))
		return true;
	else
		return false;
}

bool is_former(int h2, int m2, int h, int m)	//判断某时间点是否在结束时间点前
{
	if ((h<h2) || ((h==h2)&&(m<m2)))
		return true;
	else 
		return false;
}

bool is_invade(int h1, int m1, int h2, int m2, int h, int m) //判断改时间点是否被这件事占用
{
	if (is_later(h1, m1, h, m) && is_former(h2, m2, h, m))
		return true;
	else
		return false;
}

int main()
{
	int n, i, j;
	int h1, m1, h2, m2, h, m;
	int time[24][60];
	int free_time;

	while (scanf("%d", &n) != EOF)
	{
		for (i = 0; i < 24; i++)	//标志量初始化，表示每个时间点未被占用
		{
			for (j = 0; j < 60; j++)
			{
				time[i][j] = 0;
			}
		}

		for (i = 0; i < n; i++)		//对每件事进行分析，看它占用了哪些时间点
		{
			scanf("%d:%d %d:%d", &h1, &m1, &h2, &m2);
			for (h = 0; h < 24; h++)
			{
				for (m = 0; m < 60; m++)
				{
					if (time[h][m] == 0)
					{
						if (is_invade(h1, m1, h2, m2, h, m))
							time[h][m] = 1;
					}
				}
			}
		}

		free_time = 0; 
		for (h = 0; h < 24; h++)	//统计空余时间
		{
			for (m = 0; m < 60; m++)
			{
				if (!time[h][m])
					free_time++;
			}
		}

		printf("%d\n", free_time);
	}


	return 0;
}

/*
思路：
	该题采用了 标记量 的方式，来标记哪些时间被占用，哪些未被占用。

总结：
	1. 确定了 内联函数 确实能用，但是发现 是否是内联函数 运行时间一样长!
	2. 确定了 bool类型 确实能用。
	3. 当初没有做出来的原因：
		① 审题错误，导致第一回思路错误
		② 想采用更好算法，导致 逻辑过于复杂，程序出现了错误。
	4. 这回 花了一个小时 才做出来， 原因：
		程序出了错误，调试了半天。
	错误原因：
		① 把 == 写成了 =
		② bool 变量 默认返回 true，因此需要考虑返回 false情况。
*/

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/8738478

2012/10/12

posted in OJ题解

『转』求N内的所有素数

转自梦醒潇湘 http://blog.chinaunix.net/uid-26548237-id-3364131.html

先收藏起来，往后慢慢研究。。

*****************************************以下为正文******************************************************

今天，关于素数问题纠结了好久好久，倍感知识缺乏啊。因此，通过自己的了解和网上查阅资料，加上自己的啰嗦，在这里整理一下，日后可以翻阅。

首先，感谢网上的前辈，如果没有您们，我不会获得关于素数的比较全面的知识。非常感谢。

1、素数及相关

素数，又称质数，在一个大于1的自然数中，除了1和此整数自身之外，不能被其他自然数整除的数。

比1大但不是素数的数称为合数。

1和0既不是素数，也不是合数。

算术基本定理证明每个大于1的正整数都可以写成素数的乘积，并且这种乘积的形式是唯一的。

2、试除法求素数

算法描述：根据素数的定义可知，不能被1和自身外的整数整除的数为素数。所以，我们可以得知，判断一个素数是否为素数只要看它是否能被2~sqrt(i)间的数整数即可。而求N内所有素数则是循环重复上述过程。

C语言实现如下所示。

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <malloc.h>
//试除法
#define NUM 10000
int Test_prime(int n)
{
int count = 0;
int i, j;
int *num= (int*)malloc(sizeof(int)* n);
num[count++]= 2;
for(i = 3; i <= n; i++)
{
for(j= 2; j <= sqrt(i); j++)
{
if(i% j == 0)
{
break;
}
}
if(j> sqrt(i))
{
num[count++]= i;
}
}
free(num);
return count;
}
int main()
{
int count;
clock_t start,end;
start = clock();
count = Test_prime(NUM);
end = clock();
printf("%d 内的素数个数为：%d, 总共耗时为：%d 毫秒\n", NUM, count,end - start);
return 0;
}

测试结果如下所示（测试在VC6.0下进行）。

从上面可以看出，当数据很大时，时间消耗增长的比较快。

3、试除法的优化方案

仔细研究试除法，可以发现以下几个问题：

1> 在循环条件中重复调用了sqrt(i)，这显然是比较浪费时间的；

2> 判断素数，真的需要拿2-sqrt(i)间的所有整数去除吗？我们知道，合数都可以分解成若干质数，所以，只要2-sqrt(i)间的质数不能整除i即可；

C语言实现如下所示。

点击(此处)折叠或打开

//求N内的所有素数
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <malloc.h>
//试除法
#define NUM 1000000
int Test_prime(int n)
{
int count = 0;
int i, j, k, stop;
//分配空间
int *num= (int*)malloc(sizeof(int)* n);
//2肯定是素数
num[count++]= 2;
stop = 0;
for(i = 3; i <= n; i++)
{
//在循环中重复调用sqrt是低效做法，故引入k
k = (int)sqrt(i);
//stop的作用是：统计小于当前k值的质数的数目
while(num[stop]<= k && stop < count)
{
stop++;
}
for(j= 0; j < stop; j++)
{
if( i% num[j]== 0)
{
//i不能被2-sqrt(i)间的素数整除，自然不能被其他整数整除，所以为素数
break;
}
}
if(j== stop)
{
num[count++]= i;
}
}
free(num);
return count;
}
int main()
{
int count;
clock_t start,end;
start = clock();
count = Test_prime(NUM);
end = clock();
printf("%d 内的素数个数为：%d, 总共耗时为：%d 毫秒\n", NUM, count,end - start);
return 0;
}

测试结果如下所示。

相对于优化前的算法，时间提供了很多。特别是在时间增长曲线的幅度变小了，N值越大，优化后的算法比优化后的算法效率更高。

4、合数过滤筛选法

算法描述：由质数的定义可以知道，质数N不能被2-（N-1）间的任何整数整除；反过来看，只要能被2-（N-1)间的任何整数整除的N，都不是素数。所以，我们采用排除法：就是对N以内的所有数，只要逐个去除值为2-（N-1)的倍数的数，剩下的就是素数。

C语言实现如下所示。

//合并筛选法
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <malloc.h>
//试除法
#define NUM 10000
int Test_prime(int n)
{
int count = 0;
int i, j;
//分配空间，之所以是n+1，是因为浪费了一个num[0]
char *num =(char *)malloc(sizeof(char)* (n + 1));
//初始化素数标记
for(i = 2; i<= n; i++)
{
num[i]= 1;
}
//以2-(N-1)为因子过滤合数
for(i = 2; i <= n-1; i++)
{
for(j= 2; j * i <= n; j++)
{
//i*j是由两整数相乘而得，显然不是素数
num[i*j]= 0;
}
}
//统计素数个数
for( i = 2; i<= n; i++)
{
if( 1== num[i])
{
count++;
}
}
free(num);
return count;
}
int main()
{
int count;
clock_t start,end;
start = clock();
count = Test_prime(NUM);
end = clock();
printf("%d 内的素数个数为：%d, 总共耗时为：%d 毫秒\n", NUM, count,end - start);
return 0;
}

测试结果如下所示。

上述程序好多地方采用了比较低效的做法，为了与后文的优化作比较，这也是像我一样的初学者通常采用的版本，因此，要学会优化。

5、合并筛选法优化方案

上述算法存在的问题是：

1> 在外层循环，需要一直执行到n-1嘛？不要，因为n/2-（n-1）之间的数显然不能整除出n；

2> 在内层循环中重复使用i*j显然是低效的，考虑到计算机中加减运算速度比乘除快，可以考虑变乘法为加法；

3> 在循环修改flag的过程中，其实有很多数被重复计算若干次，比如6 = 2*3 = 3*2,被重复置零，所以，可以进行避免；

C语言实现如下所示。

点击(此处)折叠或打开

//合并筛选法的优化方案
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <malloc.h>
#define NUM 300000
int Test_prime(int n)
{
int count = 0;
int i, j;
//分配空间
char *num =(char *)malloc(sizeof(char)* (n + 1));
//初始化素数标记
num[2] = 1;
//注意此处是i<n，上例中的i<=n
for(i = 3; i< n; i++)
{
num[i++]= 1;
num[i]= 0;//偶数自然不是素数
}
//如果n为奇数
if(n % 2 != 0)
{
num[n]= 1;
}
//从3开始过滤，因为，2的倍数在初始化中去掉了
for(i = 3; i <= n/2; i++)
** {**
** if(0 == num[i] )**
** {**
** continue;**
** }**
** //从i的2倍开始过滤**
** for(j = i + i; j <= n;j+=i)**
** {**
** num[j] = 0;**
** }**
** }**
//统计素数个数
for( i = 2; i<= n; i++)
{
if( 1== num[i])
{
count++;
}
}
free(num);
return count;
}
int main()
{
int count;
clock_t start,end;
start = clock();
count = Test_prime(NUM);
end = clock();
printf("%d 内的素数个数为：%d, 总共耗时为：%d 毫秒\n", NUM, count,end - start);
return 0;
}

测试如下所示。

确实比先前快了很多，优化真的可以带来时间的提高，这样我很是欣喜。

后来想到进行添加补充：

如果我对上述红色部分代码进行优化，如下所示。

点击(此处)折叠或打开

//从3开始过滤，因为，2的倍数在初始化中去掉了
for(i = 3; i <= n/2;i = i + 2)
{
//在这里进行判断，就已经具有剔除了偶数的功能
if(0== num[i])
{
continue;
}
//从i的2倍开始过滤
for(j= i + i; j<= n;j+=i)
{
//是直接进行赋值快呢？还是在此处加上判断快呢？？不晓得啊？求解。。
if( j % 2 == 0)
{
continue;
}
else
{
num[j]= 0;
}
}
}

第一部分红色，我将原来的奇数和偶数进行判断，变为了只对奇数进行判断；

第二部分红色，我将奇数的倍数为偶数的直接剔除，变成只对倍数为奇数的进行赋值；

以上两者改变，都基于开始时，已经将偶数剔除。

对NUM = 300000测试如下所示。

时间仅为7毫秒，比优化前NUM = 300000时，时间更快。

6、继续优化

C语言实现代码如下所示。

点击(此处)折叠或打开

//合并筛选法的优化方案
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <malloc.h>
#include <string.h>
#define NUM 10000
int Test_prime(int n)
{
int i, j;
// 素数数量统计
int count = 0;
// 分配素数标记空间，明白+1原因了吧，因为浪费了一个num[0]
char *num =(char*)malloc( n+1);
// 干嘛用的，请仔细研究下文
int mpLen = 2*3*5*7*11*13;
char magicPattern[2*3*5*7*11*13];
// 奇怪的代码，想！
for (i=0; i<mpLen; i++)
{
magicPattern[i++]= 1;
magicPattern[i++]= 0;
magicPattern[i++]= 0;
magicPattern[i++]= 0;
magicPattern[i++]= 1;
magicPattern[i]= 0;
}
for (i=4; i<=mpLen; i+=5)
{
magicPattern[i]= 0;
}
for (i=6; i<=mpLen; i+=7)
{
magicPattern[i]= 0;
}
for (i=10; i<=mpLen; i+=11)
{
magicPattern[i]= 0;
}
for (i=12; i<=mpLen; i+=13)
{
magicPattern[i]= 0;
}
// 新的初始化方法,将2,3,5,7,11,13的倍数全干掉
// 而且采用memcpy以mpLen长的magicPattern来批量处理
int remainder = n%mpLen;
char* p = num+1;
char* pstop = p+n-remainder;
while (p< pstop)
{
memcpy(p, magicPattern, mpLen);
p += mpLen;
}
if (remainder> 0)
{
memcpy(p, magicPattern, remainder);
}
num[2] = 1;
num[3] = 1;
num[5] = 1;
num[7] = 1;
num[11]= 1;
num[13]= 1;
// 从17开始过滤，因为2,3,5,7,11,13的倍数早被去掉了
// 到n/13止的
int stop = n/13;
for (i=17; i<= stop; i++)
{
// i是合数
if (0== num[i])
{
continue;
}
// 从i的17倍开始过滤
int step= i*2;
for (j=i*17; j<= n; j+=step)
{
num[j]= 0;
}
}
// 统计素数个数
for (i=2; i<=n; i++)
{
if (num[i])
{
count++;
}
}
// 释放内存
free(num);
return count;
}
int main()
{
int count;
clock_t start,end;
start = clock();
count = Test_prime(NUM);
end = clock();
printf("%d 内的素数个数为：%d, 总共耗时为：%d 毫秒\n", NUM, count,end - start);
return 0;
}

测试结果如下所示。

** ** 说实话，这种思想真的很赞，现在的我是无法想到的，感谢作者，让我有了更广泛的见识。

7、其他

除了以上几种算法外，如拉宾米勒素数测试算法，感觉这个算法比较难，先好好看看，等弄懂了，然后补上。

通过今天的纠结，对于求素数有了更加深刻的了解和认识，感觉自己还差很多，需要更加的努力。

另外，感谢来自百度空间的作者 doforfun_net，给我了很大的启发，学到了很多。

梦醒潇湘

2012-10-3 20:15

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/8066111

2012/06/09

posted in OJ题解

杭电 Identity Card

Identity Card

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1969 Accepted Submission(s): 627

Problem Description

Do you own an ID card?You must have a identity card number in your family's Household Register. From the ID card you can get specific personal information of everyone. The number has 18 bits,the first 17 bits contain special specially meanings:the first 6 bits represent the region you come from,then comes the next 8 bits which stand for your birthday.What do other 4 bits represent?You can Baidu or Google it.
Here is the codes which represent the region you are in.

However,in your card,maybe only 33 appears,0000 is replaced by other numbers.
Here is Samuel's ID number 331004198910120036 can you tell where he is from?The first 2 numbers tell that he is from Zhengjiang Province,number 19891012 is his birthday date (yy/mm/dd).

Input

Input will contain 2 parts:
A number n in the first line,n here means there is n test cases. For each of the test cases,there is a string of the ID card number.

Output

Based on the table output where he is from and when is his birthday. The format you can refer to the Sample Output.

Sample Input

1
330000198910120036

Sample Output

He/She is from Zhejiang,and his/her birthday is on 10,12,1989 based on the table.

Author

Samuel

Source

灰色橙子专场

Recommend

zty

代码：

#include <iostream>
#include <string>
using namespace std;

int main()
{
int n;
double temp;
string place;
char st[18];

cin >> n;
getchar();                                 //getchar()来吃掉enter，要不然enter会被gets函数读入
while (n--)
{
  gets(st);
  cout << "He/She is from ";
  if (st[0] == '3' && st[1] == '3')     //3要用''括起来，因为st是字符数组
   cout << "Zhejiang";
  else if (st[0] == '1' && st[1] == '1')
   cout << "Beijing";
  else if (st[0] == '7' && st[1] == '1')
   cout << "Taiwan";
  else if (st[0] == '8' && st[1] == '1')
   cout << "Hong Kong";
  else if (st[0] == '8' && st[1] == '2')
   cout << "Macao";
  else if (st[0] == '5' && st[1] == '4')
   cout << "Tibet";
  else if (st[0] == '2' && st[1] == '1')
   cout << "Liaoning";
  else if (st[0] == '3' && st[1] == '1')
   cout << "Shanghai";

  cout << ",and his/her birthday is on "
    << st[10] << st[11] << ','
    << st[12] << st[13] << ','
    << st[6] << st[7] << st[8] << st[9];
  cout << " based on the table."
    << endl;
}

return 0;
}

总结：

一开始想用 int temp来存放ID Card Number，运用'/'和'%'来提取号码，但是没那么大的整形变量，
而用double的话，不能用'%'，而且会发生溢出错误。
所以运用了字符数组。

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/7648866

2012/06/09

posted in OJ题解

杭电 IBM Minus One

IBM Minus One

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1467 Accepted Submission(s): 627

Problem Description

You may have heard of the book '2001 - A Space Odyssey' by Arthur C. Clarke, or the film of the same name by Stanley Kubrick. In it a spaceship is sent from Earth to Saturn. The crew is put into stasis for the long flight, only two men are awake, and the ship is controlled by the intelligent computer HAL. But during the flight HAL is acting more and more strangely, and even starts to kill the crew on board. We don't tell you how the story ends, in case you want to read the book for yourself :-)

After the movie was released and became very popular, there was some discussion as to what the name 'HAL' actually meant. Some thought that it might be an abbreviation for 'Heuristic ALgorithm'. But the most popular explanation is the following: if you replace every letter in the word HAL by its successor in the alphabet, you get ... IBM.

Perhaps there are even more acronyms related in this strange way! You are to write a program that may help to find this out.

Input

The input starts with the integer n on a line by itself - this is the number of strings to follow. The following n lines each contain one string of at most 50 upper-case letters.

Output

For each string in the input, first output the number of the string, as shown in the sample output. The print the string start is derived from the input string by replacing every time by the following letter in the alphabet, and replacing 'Z' by 'A'.

Print a blank line after each test case.

Sample Input

2
HAL
SWERC

Sample Output

String #1 IBM

String #2
TXFSD

Source

Southwestern Europe 1997, Practice

我的代码：

#include <iostream>
using namespace std;

int main()
{
int n, i, k, len;
char st[100];

cin >> n;
getchar();
for (i = 1; i <= n; i++)
{
cout << "String #" << i << endl;

  gets(st);
  len = strlen(st);
  for (k = 0; k < len; k++)
  {
   st[k] ++;
   if (st[k] == 'Z' + 1)
    st[k] = 'A';
  }
  puts(st);
  cout << endl;
}

return 0;
}

总结：

一开始范2了，把第二个循环变量想成i了，导致半天没AC。。反省反省。。。

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/7647879