当前课程知识点:程序设计基础 >  第五章 分治思想与递归 >  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 总结

--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.1 提问

--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 总结

--4.6.1 总结

-程设论道

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

--程设论道二:筛法

-师生问答

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

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

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

第五章 分治思想与递归

-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.2 结构

--7.3.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

--7.4.1 总结

-程设论道

--程设论道

-师生问答

--师生问答

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

第八章 非文本数据处理

-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 阶乘问题笔记与讨论

也许你还感兴趣的课程:

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