《算法》世界二

一.算法要素

1.数据对象的运算和操作：计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类：

1.算术运算：加减乘除等运算

2.逻辑运算：或、且、非等运算

3.关系运算：大于、小于、等于、不等于等运算

4.数据传输：输入、输出、赋值等运算

2.算法的控制结构：一个算法的功能结构不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。

二.爆炸函数

国王赏不起的小麦

在古代印度有一个国王,他拥有至高无上的权力和难以计数的财富。但是权力和财富最终使他对生活感到厌倦，渴望着有新鲜的刺激。

某天，一位老人带着自己发明的国际象棋来朝见。国王对这新奇的玩意非常喜欢，非常迷恋，并感到非常满足。

对老人说:"你给了我无穷的乐趣。为了奖赏你，你可以从我这儿得到你所要的任何东西"。

老人的要求是:请您在棋盘上的第一个格子上放 1 粒麦子，第二个格子上放 2 粒，第三个格子上放 4 粒，第四个格子上放 8 粒……

即每一个次序在后的格子中放的麦粒都必须是前一个格子麦粒数目的倍数，直到最后一个格子放满为止。

国王哈哈大笑，慷慨地答应了老人这个卑微的请求。然而，国王最终发现，按照与老人的约定，全印度的麦子竟然连棋盘一小半格子数目都不够。

老人索要的麦粒数目实际上是天文数字，总数将是一个 20 位数，折算重量约为 2000 多亿吨，即使现代，全球小麦的年产量也不够。

简单算一下，假设把第一个格子的一粒米写成 2 的 0 次方，第二个格子写成 2 的 1 次方，第三个格子写成 2 的 2 次方，那么第 N 个格子就可以写成 2 的 N-1 次方。国际象棋一共 64 个格子，到了第 64 个格子的时候，需要放的米粒数就是 2 的 63 次方，即 9，223，372，036，854，780，000 粒，这还只是这一个格子的容量，如果全部累计，则为 18，446，744，073，709，600，000 粒。如果 1000 粒米有一克重，那么折算一下，第 64 格就需要放 9，223，372，036 吨米。

由指数函数图象来看，简直可以说是直线增长的(实际上远比直线增长快)，比爆炸的威力还要大，所以指数函数也称为爆炸函数。

1.什么是爆炸函数

爆炸函数也就是指数函数。数学领域词汇，特点是增长速度特别快。

​

​

三.方法介绍

递推法

递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

递归法

程序调用自身的编程技巧称为递归（recursion）。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

穷举法

穷举法，或称为暴力破解法，其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。它也常用于对于密码的破译，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有 10000 种组合，因此最多尝试 10000 次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。

贪心算法

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。

分治法

分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

动态规划法

动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

迭代法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

分支界限法

分枝界限法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。

回溯法

回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

四.兔子数列

1.兔子算法

题目：古典问题：3 个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

分析：首先我们要明白题目的意思指的是每个月的兔子总对数；假设将兔子分为小中大三种，兔子从出生后三个月后每个月就会生出一对兔子，

那么我们假定第一个月的兔子为小兔子，第二个月为中兔子，第三个月之后就为大兔子，那么第一个月分别有 1、0、0，第二个月分别为 0、1、0，

第三个月分别为 1、0、1，第四个月分别为,1、1、1，第五个月分别为 2、1、2，第六个月分别为 3、2、3，第七个月分别为 5、3、5……

兔子总数分别为：1、1、2、3、5、8、13……

于是得出了一个规律，从第三个月起，后面的兔子总数都等于前面两个月的兔子总数之和，即为斐波那契数列。

2.什么是兔子数列

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368[1]

正在上传…重新上传取消斐波那契数列特别指出：第 0 项是 0，第 1 项是第一个 1。

这个数列从第 3 项开始，每一项都等于前两项之和。

斐波那契数列的提出者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci），生于公元 1170 年，卒于 1250 年，籍贯是比萨。他被人称作“比萨的列昂纳多”。1202 年，他撰写了《算盘全书》（Liber Abacci）一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。