当前课程知识点：程序设计基础 > 第五章分治思想与递归 > 5.1 阶乘 > 5.1.1 阶乘问题

返回《程序设计基础》慕课在线视频课程列表

5.1.1 阶乘问题在线视频

5.1.1 阶乘问题

下一节:5.1.2 递归解法

返回《程序设计基础》慕课在线视频列表

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.1.1 什么是程序？什么是语言？

--1.1.2 什么是程序设计？

--1.1.3 计算机发展史

-1.2 买菜问题

--1.2.1 问题描述

--1.2.2 程序的基本结构

-1.3 数学运算

--1.3.1 数学运算符

--1.3.2 数学函数

-1.4 补充说明

--1.4.1 编程环境的下载与安装

--1.4.2 程序基本结构中的含义

--1.4.3 格式与风格

-1.5 总结

-程设论道

-师生问答

--师生问答一：怎样学好程序设计

--师生问答二：语言选择

--师生问答三：关于函数

-第一章编程初步--语法自测

第二章变量与代数思维

-2.1 关于超级计算器的几点思考

--2.1.1 关于超级计算器的几点思考

-2.2 电子秤模拟 — 背景介绍及需求分析

--2.2.1 电子秤模拟 — 背景介绍及需求分析

-2.3 电子秤模拟 — 代码实现

--2.3.1 电子秤模拟 — 代码实现

-2.4 变量定义与变量类型

--2.4.1 变量定义与变量类型

-2.5 猜数游戏与数据表示

--2.5.1 猜数游戏与数据表示

-2.6 关于变量的讨论

--2.6.1 变量的初始值

--2.6.2 变量类型

--2.6.3 变量内存单元地址

--2.6.4 存“变量地址”的变量——指针

--2.6.5 指针的读/写操作

--2.6.6 指针的加/减操作

-2.7 变量体现的计算思维

--2.7.1 变量体现的计算思维

-程设论道

-师生问答

-第二章变量与代数思维--语法自测

第三章逻辑推理与枚举解题

-3.1 谁做的好事——语义表示

--3.1.1 谁做的好事——语义表示

-3.2 谁做的好事——真假检查

--3.2.1 谁做的好事——真假检查

-3.3 谁做的好事——循环枚举

--3.3.1 谁做的好事——循环枚举

-3.4 谁是嫌疑犯——多重循环枚举

--3.4.1 谁是嫌疑犯——多重循环枚举

-3.5 谁是嫌疑犯——破案线索表示

--3.5.1 谁是嫌疑犯——破案线索表示

-3.6 谁是嫌疑犯——用二进制枚举

--3.6.1 谁是嫌疑犯——用二进制枚举

-程设论道

--程设论道一

--程设论道二

--程设论道三

-师生问答

--师生问答一：字符与ASCII码表

--师生问答二：其他循环语句、运算符优先级与变量作用域

-第三章逻辑推理与枚举解题--语法自测

第四章筛法与查找

-4.1 插花游戏

--4.1.1 问题提出（求素数）

--4.1.2 函数初探

--4.1.3 运行演示

-4.2 筛法

--4.2.1 筛法思路

--4.2.2 数组的定义

--4.2.3 代码翻译

--4.2.4 运行演示

--4.2.5 小朋友数人数

--4.2.6 运行演示

--4.2.7 韩信点兵

-4.3 线性查找

--4.3.1 扑克查找问题

--4.3.2 扑克查找问题代码翻译

--4.3.3 最小值问题

--4.3.4 最小值问题代码翻译

-4.4 折半查找

--4.4.2 折半查找思路

--4.4.3 折半查找代码翻译

--4.4.4 折半查找运行演示

-4.5 排序问题

--4.5.1 插入排序

--4.5.2 选择排序

--4.5.3 函数写法

--4.5.4 运行演示

-4.6 总结

-程设论道

--程设论道一：数组与编码思维

--程设论道二：筛法

-师生问答

--师生问答一：函数与面向过程编程

--师生问答二：数组的下标越界

-第四章筛法与查找--语法自测

第五章分治思想与递归

-5.1 阶乘

--5.1.1 阶乘问题

--5.1.2 递归解法

--5.1.3 递归小结

-5.2 排序

--5.2.1 归并排序——总体思路

--5.2.2 归并排序——思路分解

--5.2.3 归并排序——代码解说

--5.2.4 快速排序——总体思路

--5.2.5 快速排序——代码解说

--5.2.6 排序总结

-5.3 矩阵填充

--5.3.1 矩阵填充问题

--5.3.2 代码解说

-5.4 分书与八皇后

--5.4.1 问题描述

--5.4.2 问题分析——共性

--5.4.3 问题分析——区别

--5.4.4 解题准备——二维数组

--5.4.5 解题准备——递归设计

--5.4.6 代码解说——分书问题

--5.4.7 代码解说——八皇后问题

-5.5 青蛙过河

--5.5.1 问题描述

--5.5.2 问题分析——简单情况

--5.5.3 问题分析——复杂情况

--5.5.4 问题分析——一般情况

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答一

--师生问答二

-第五章分治思想与递归--语法自测

第六章递推与动态规划

-6.1 兔子数列问题

--6.1.1 问题描述

--6.1.2 按大小兔子分别递推

--6.1.3 按总数递推

--6.1.4 不用数组递推

-6.2 分鱼问题

--6.2.1 问题描述

--6.2.2 从A到E递推

--6.2.3 从E到A递推

-6.3 橱窗的插花问题

--6.3.1 问题描述

--6.3.2 题意理解与分析

--6.3.3 用枚举思想解题

--6.3.4 采用递推的优化算法

--6.3.5.1 采用动态规划算法—优化分析

--6.3.5.2 采用动态规划算法—递推代码

--6.3.5.3 采用动态规划算法—计算过程

--6.3.5.4 采用动态规划算法—输出方案

--6.3.6 动态规划总结

-6.4 最长公共子序列问题

--6.4.1 问题描述与理解

--6.4.2 问题分析

--6.4.3.1 动态规划解题(1)

--6.4.3.2 动态规划解题(2)

--6.4.3.3 动态规划代码

-程设论道

--程设论道一

--程设论道二

-师生问答

-第六章递推与动态规划--语法自测

第七章文本数据处理

-7.1 统计记录总数

--7.1.1 问题分析

--7.1.2 读文件操作

-7.2 统计活跃用户数

--7.2.1 问题分析

--7.2.2 字符串

--7.2.3 程序翻译与演示

-7.3 统计在线时长

--7.3.1 问题分析

--7.3.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

-程设论道

-师生问答

-第七章文本数据处理--语法自测

第八章非文本数据处理

-8.1 将数据组织成链表

--8.1.1 链表的基本概念

--8.1.2 代码讲解

--8.1.3 链表遍历与释放

-8.2 提高链表访问效率 —— 哈希链表

--8.2.1 简单的哈希算法

--8.2.2 算法实现

-8.3 以二进制文件存储链表

--8.3.1 二进制文件的操作方法

--8.3.2 代码讲解

-程设论道

--程设论道一

--程设论道二

-师生问答

-第八章非文本数据处理--语法自测

第九章可配置的程序设计

-9.1 自动售卖程序

--9.1.1 提出问题与初步设计

--9.1.2 细化实现订单处理

--9.1.3 使程序更健壮

-9.2 配制水果信息

--9.2.1 提出问题与设计文件格式

--9.2.2 实现订单处理功能

-9.3 指定界面语言

--9.3.1 提出问题与命令行参数

--9.3.2 实现程序功能

-程设论道

-师生问答

-第九章可配置的程序设计--语法自测

5.1.1 阶乘问题笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。