趣味算法一棋盘的麦子

1.《趣味算法》原文章节内容_一棋盘的麦子

👍原文章节：

如果说数学是皇冠上的一颗明珠,那么算法就是这颗明珠上的光芒,算法让这颗明珠更加熠熠生辉,为科技

进步和社会发展照亮了前进的路。数学是美学，算法是艺术。 走进算法的人,才能体会它的无穷魅力。

多年来，我有一个梦想,希望每-位提到算法的人,不再立即紧皱眉头,脑海里闪现枯燥的公式、冗长的代

码;我希望每一位阅读和使用算法的人,体会到算法之美，就像躺在法国普罗旺斯小镇的长椅上,呷一口红

酒，闭上眼睛，体会舌尖上的美味,感受鼻腔中满溢的薰衣草的芳香…

🤎以上这一段内容很棒

很多人提到算法会感觉很深奥，算法本身就具有一定的复杂性。也许算法这个名词听上去很抽象，让人联想不到任何具体的物体。也许你会觉得算法与自己的生活并无太多关系，它只不过存在于那些闲得无聊的数学家或计算机专业人士的脑海中.，但这本《趣味算法》很有趣书哈中所有的示例都与生活息息相关，淋漓尽致地展现了算法解决问题的本质，让你爱上算法，乐在其中。

👍原文例子：

有一个古老的传说,一位国王的女儿不幸落水,水中有很多鳄鱼， 国王情急之下下令:“谁能把公主救上
来，就把女儿嫁给他。"很多 人纷纷退让,一个勇敢的小伙子挺身而出,冒着生命危险把公主救了上来,国王
一看是个穷小子,想要反悔，说:“除了女儿，你要什么都可以。”小伙子说:“好吧,我只要一棋盘的麦子。
您在第1个格子里放1粒麦子,在第2个格子里放2粒,在第3个格子里放4粒，在第4个格子里放8粒，以此类
推，每一个格子里麦子的粒数都是前一格子里麦子粒数的两倍。把这64个格子放满了就行,我就要这么多。
国王听后哈哈大笑,觉得小伙子的要求很容易满足,满口答应。结果发现,把全国的麦子都拿来,也填不完
这64个格.....国王无奈，只好把女儿嫁给了这个小伙子。

原文解析:

棋盘上的64个格子究竟需要放多少粒麦子?

注意:宕机就是死机,指计算机无法正常工作,包括一切原因导致的死机。计算机主机出现意外故障而死机，-些服务器(如数据库服务器)死锁,服务器的某些服务停止运行等,都可以称为宕机。

常见的算法时间复杂度有以下几类。

(1)常数阶。

常数阶算法的运行次数是一个常数 ,如5、20、 100。 常数阶算法的时间复杂度通常用0(1)表示。

(2)多项式阶。

很多算法的时间复杂度是多项式,通常用O(n)、O(n2 ^22)、 O(n3 ^33)等表示。

(3)指数阶。

指数阶算法的运行效率极差, 程序员往往像躲“恶魔”一样避开这种算法。指数阶算法的时间复杂度通常

用0(2n ^nn)、O(n!)、 O(nn ^nn)等表示。

(4 )对数阶。

对数阶算法的运行效率较高,通常用O(logn)、O(nlogn)等表示。

指数阶增量随着x的增加而急剧增加,而对数阶增长缓慢。它们之间的关系如下:

0(1)< O(logn)< O(n)< O(nlogn) < O(n2 ^22)< O(n3 ^33)< 0(2n ^nn) < O(n!)< O(nn ^nn)

在设计算法时,我们要注意算法复杂度增量的问题,尽量避免爆炸级增量。

2.什么是算法

算法就是计算的办法或法则。这里的计算指的当然不只是加、减、乘、除等算术运算，而是广义的做任何事情的计算，而办法和法则意味着使用它就可以解决需要的问题。

由上面提到的定义可推知，算法作为解决问题的方法，它必须具备以下特点:

●确定性，即无歧义，能让人照着执行。

●可行性，算法中的运算都是基本的，理论上能够由人用纸和笔完成。

●有限性，在有限输入下，算法必须能在有限步骤内实现有限输出。

此外，算法必须有输出、计算的结果，通常还有至少-一个输入量。这是因为算法用以解

决的问题的描述均包括输入和输出。例如，排序问题可以描述如下:

此外，算法必须有输出、计算的结果，通常还有至少-一个输入量。这是因为算法用以解

决的问题的描述均包括输入和输出。例如，排序问题可以描述如下:

输入:

数列: a₁,a₂,…a_n

输出:

排列: a’₁,a’₂,…a’_n, 其中 a’₁≤a’₂≤…≤a’_n

举例:

输入序列:824936

输出序列:234689

3.算法的表示

由于算法由一系列步骤组成，那么任何一个步骤序列从广义上看，都可以当做是一个算法。例如，下面的步骤就可以看做是一个算法:

1)起床

2)吃早点

3)上早自习

4)上课

5)吃午饭

6)上课

7)吃晚饭

8)上晚自习

9)睡觉

这是用自然语言表示的一个学生每天运行的通用算法。下面是一个将末端递归转换为循

环的算法，除了自然语言，我们也可用计算机语言(即程序设计语言)来表示算法。实际上，由于

计算机程序给出的是-一个-一个步骤的执行序列，因此计算机程序都是算法，或者说都是算法

的-种表示。例如，下面的计算机程序片段就表示的是一个计算阶乘的算法:

int factorial (int n)
{
if(n==0) return 1;
else return n* factorial(n-1) ;
}