当前课程知识点:程序设计基础 > 第五章 分治思想与递归 > 5.1 阶乘 > 5.1.1 阶乘问题
同学们 我们今天要讲一个新的内容
在讲新内容之前
大家先看一个课前的思考题
这上面列出了三个公式
那我问大家 这三个公式有没有区别
第一个写的是n的阶乘等于
1乘上2乘上3一直乘到n
那么第二个式子写的呢是
n的阶乘等于n-1的阶乘的结果去乘上n
那第三个式子写的是
n的阶乘等于n乘上n-1的阶乘
有同学说这个问题看上去三个公式没区别呀
他们都在完成一个n的阶乘的运算
只不过它写的表达式有所不同
我们下面就要求大家把三个
数学的式子用我们以前讲过的知识
把它转化成为程序的代码
那这里头我们提出一个特殊的要求
那上一讲大家学过了函数
所以这里头要求大家
用上一讲学过的函数的知识
把阶乘用一个函数来定义它
因为大家回头查书会发现
在C++的库函数里头
是没有阶乘这样一个函数的
那我们现在来看看自己编写
这样的函数该怎么写呢
首先我们知道在第一个式子里头
它告诉我们n的阶乘的求解
是1乘上2乘上3一直乘到n
那这很显然是一个一个的把1到n的数拿过来
然后去进行累乘
那这样的一个式子很明显的告诉我们
我们只需要用一个循环就可以搞定
这个函数的实现
所以大家可以看到我们代码里头
通过函数 通过循环把这个阶乘
给它求解出来了
那也就是for循环 然后呢
从1到n依次去做一个枚举
依次去做一个枚举
然后把它累乘起来
这里头有一个小小的一个技巧
当我们做累乘的这样的操作的时候
这个初始的那个值 应该设成1
第二个要注意的是这个初始值
一定得在循环之前完成
这个次序不能错
所以这样的问题初学者很容易去犯错误
不知道该放哪个地方也不知道该设成什么值
那么对于阶乘而言 它的初始值应该是1
因为你乘上去之后它才能够保持那个乘积的结果
所以这个循环体就比较容易实现
m=m*i 依次去枚举那个i
利用循环这个语句的特性
让计算机去一次一次的把1到n的数拿过来
然后按照你写的公式去算它
这个就看上去没有什么复杂的
那么是不是只有这一种实现方式呢
很显然不是
我们刚才在课前的问题里头让你去看到了
我这个阶乘的式子是有三种写法的
你现在实现的只是其中的第一个
那好 我们照着类似的思路
按照第二个式子去写这个阶乘的函数
我们该怎么做呢
那我们第二个式子大家可以看到
它是说n的阶乘等于n-1的阶乘去乘上n
那换言之我们认为n-1的阶乘已经有了
然后用它 以它为基础去乘上n
就得到n的阶乘了
那这是一个在高中数学里头很常见的一种技巧
就是你把前一项的结果算出来
那去算后一项怎么算呢
在前一项的基础上再去乘上那个变化的量
就能得到它
所以按照以前我们学循环的一个思路
我们可以给n-1的阶乘给它定义一个
在它最开始的时候那一项有一个初值
那这个初值是什么呢
实际上这就是1的阶乘
1的阶乘大家都知道它是1
所以我们这个时候 假定
比方说我们求10以内的十个数的阶乘的话
那我们可以先利用上一节课
所学到的数组的知识
定义一个十个整数的数组
然后把1的阶乘 第一项嘛
把它存放到m[1]这个元素里去
大家学数组虽然知道下标是从0开始的
为了看代码比较自然一点呢
我们把1的阶乘放到m[1]这个元素里头去
所以把这个值直接人算出来
这里头也再一次提醒大家
虽然我们是希望尽可能的发挥计算机的
它的能力去帮助人类来解题
但并不意味着我们编写任何一个程序
所有的一切都让计算机去算
这个没有必要 所以这个里头
我们结合人的知识 我们知道1的阶乘是1
所以我们让m[1]等于1
这样子就得到了一个初值
那根据我们前面讲到的那个公式
n的阶乘等于n-1的阶乘 这个结果去乘上n
那现在1的阶乘有啦
那就意味着我可以去得到2的阶乘
同理 2的阶乘有了之后
根据这个公式 我可以去得到3的阶乘
以此类推 于是我们就可以看出来
通过一个for循环
可以得到后面的每一项它的阶乘值
所以我们只要用从小到大这样的一个顺序
从前项到后项这样一个过程
依次就可以求出来每一项的阶乘
这个里头之所以能够这么去实现
就是因为数学上的确是存在后项和前项
之间有这样一种对应关系
大家的高中数学里头学到了这样一个知识
所以我们代码写出来就是很简单
一个for循环 m[i]从2开始
然后呢一直到你要求的这个n
当然这里头我们为了简化
代码里头假定这个n是10以内的
然后我们这个int m这个数组才存放的下
然后在循环体里头就是每一项等于它的前一项
以前已经算过了嘛 m[i-1]去乘上i
这样就得到了一个新的实现阶乘的算法
很显然 这个算法它看上去真的是
是跟我们在前面问题里头所提的
n的阶乘等于n-1的阶乘乘上n
这样的一个式子是对应的
有了前面的n-1的阶乘的这个项
然后呢 用它做基础做一个被乘数
再去乘上一个n
就得到了当前的n的阶乘这一项的值
那跟它的公式也是一个翻译过程
这是我们的第二种实现方法
那我想大家通过这两个不同的函数的实现
应该已经体会到俩公式确实是有区别
-1.1 基础知识
-1.2 买菜问题
-1.3 数学运算
-1.4 补充说明
-1.5 总结
--1.5 总结
-程设论道
--程设论道
-师生问答
-第一章 编程初步--语法自测
-2.1 关于超级计算器的几点思考
-2.2 电子秤模拟 — 背景介绍及需求分析
-2.3 电子秤模拟 — 代码实现
-2.4 变量定义与变量类型
-2.5 猜数游戏与数据表示
-2.6 关于变量的讨论
--公告
-2.7 变量体现的计算思维
-程设论道
--程设论道
-师生问答
--师生问答
-第二章 变量与代数思维--语法自测
-3.1 谁做的好事——语义表示
-3.2 谁做的好事——真假检查
-3.3 谁做的好事——循环枚举
-3.4 谁是嫌疑犯——多重循环枚举
-3.5 谁是嫌疑犯——破案线索表示
-3.6 谁是嫌疑犯——用二进制枚举
-程设论道
--程设论道一
--程设论道二
--程设论道三
-师生问答
-第三章 逻辑推理与枚举解题--语法自测
-4.1 插花游戏
-4.2 筛法
-4.3 线性查找
-4.4 折半查找
--4.4.1 提问
-4.5 排序问题
-4.6 总结
--4.6.1 总结
-程设论道
--程设论道二:筛法
-师生问答
-第四章 筛法与查找--语法自测
-5.1 阶乘
-5.2 排序
-5.3 矩阵填充
-5.4 分书与八皇后
-5.5 青蛙过河
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答一
--师生问答二
-第五章 分治思想与递归--语法自测
-6.1 兔子数列问题
-6.2 分鱼问题
-6.3 橱窗的插花问题
-6.4 最长公共子序列问题
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第六章 递推与动态规划--语法自测
-7.1 统计记录总数
-7.2 统计活跃用户数
-7.3 统计在线时长
--7.3.2 结构
-7.4 总结
--7.4.1 总结
-程设论道
--程设论道
-师生问答
--师生问答
-第七章 文本数据处理--语法自测
-8.1 将数据组织成链表
-8.2 提高链表访问效率 —— 哈希链表
-8.3 以二进制文件存储链表
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第八章 非文本数据处理--语法自测
-9.1 自动售卖程序
-9.2 配制水果信息
-9.3 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测