当前课程知识点:C++语言程序设计基础 >  第3章 函数 >  嵌套与递归 >  例3-9

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

例3-9在线视频

例3-9

下一节:例3-10

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

例3-9课程教案、知识点、字幕

大家好

欢迎继续学习C++语言程序设计

这一节呢

我要给大家介绍一个

典型的递归的例题

这个例题要求我们

从n个人里面

选择k个人组成一个委员会

这是一个典型的组合问题

这个问题本身

我相信大家都见过

那么用计算机程序

怎么去实现这个问题呢

那我们就要看看组合的公式本身

大家想想这个问题

要用组合来解决吧

那么组合的公式描述

是不是本身就是递归的呢

好 现在我们来看

这个从n个人里面

选k个人组成委员会的这个例题

它的公式实际上是这样的

这是一个大家学过的

在数学中学过的组合的公式

也就是由n个人里

选k个人的组合数

等于由n-1个人里

选k个人的组合数

加上由n-1个人里面

选k-1个人的组合数

那也就是说

我们看到它又是一个递归的问题

在解释什么是组合的时候

又用到了组合

所以后面给出的这个条件

非常重要

必须有这个递归终结条件

就是当n等于k

或者k等于0的时候

组合数为1

如果没有这个递归终结条件的话

这个递归将无穷无尽

这个公式就不可计算了

下面我们来看

这个代码的实现

这个函数也是一个递归函数

我们来看

这个函数里面

它有两个深入递归点

由于组合的公式

又用到了组合

所以我们来看

从n个人里面

选k个人组成委员会的这个函数

如果n大于k 那么方案为0

所以return 0没有选法

如果说n等于k

或者k等于0

那只有一种选法

所以结论是1

不要小看这个结论1

恰恰这个是递归的终结点

好 那么如果都不是这两种情况

那就进到最后一个else分支里面

要调用自身去求

从n-1个人里面选k个人

和从n-1个人里面选k-1个人

把它们两个加起来

所以解决组合问题的时候呢

又用到了这个组合函数

那么这个函数它比较复杂

因为它有两个递归深入点

在第一个递归深入点

深入递归

再回退回原来的位置以后

又要进到第二个递归深入点

再深入递归进去

再回退回来

这个呢

我希望大家用单步跟踪的方式

跟踪这个递归过程

看一看这个结果

数不要选的太大

递归的层不要太多

重点是要体会一下

这个深入递归

和逐级回退的这个过程

那么主函数的逻辑

当然是比较简单

直接调用这个组合函数就可以了

只是在执行组合函数的过程中

它的过程是一个递归的过程

好 这个例题就是这些内容

C++语言程序设计基础课程列表:

第1章 绪论

-导学

--第1章导学

-计算机系统简介

--计算机系统简介

--计算机系统简介 测试题

-计算机语言和程序设计方法的发展

--计算机语言和程序设计方法的发展

--计算机语言和程序设计方法的发展 测试题

-面向对象的基本概念

--面向对象的基本概念

--面向对象的基本概念 测试题

-程序的开发过程

--程序的开发过程

--程序的开发过程 测试题

-信息的表示和储存

--计算机中的信息与存储单位

--计算机的数字系统

--数据的编码表示

--信息的表示和储存 测试题

-实验指导

--实验一:VS开发环境介绍

第2章 C++简单程序设计(一)

-导学

--第二章导学

-C++语言概述

--C++的特点和程序实例

--C++字符集和词法记号

--C++语言概述 测试题

-基本数据类型、常量、变量

--基本数据类型、常量、变量

--程序举例

--基本数据类型、常量、变量 测试题

-运算与表达式

--算术运算与赋值运算

--逗号运算、关系运算、逻辑运算和条件运算

--Sizeof运算、位运算

--运算优先级、类型转换

--运算与表达式 测试题

-实验二:简单程序设计(上)

--实验二:简单程序设计(上)

第2章 C++简单程序设计(二)

-数据的输入和输出

--数据的输入和输出

--数据的输入和输出 测试题

-选择结构

--if语句

--switch语句

--选择结构 测试题

-循环结构

--循环结构——while语句

--do-while语句

--for语句

--嵌套的控制结构、其他控制语句

--循环结构 测试题

-自定义类型

--自定义类型

--自定义类型

-第2章小结

--第二章小结

-实验二:C++简单程序设计(下)

--实验二C++简单程序设计(下)

第3章 函数

-导学

--导学

-函数定义

--函数定义

--函数定义 测试题

-函数调用

--函数调用(例3-1)

--例3-2

--例3-3

--例3-4

--例3-5

--例3-6

--函数调用 测试题

-嵌套与递归

--函数的嵌套调用(例3-7)

--函数的递归调用(例3-8)

--例3-9

--例3-10

--嵌套与递归 测试题

-函数的参数传递

--函数的参数传递

--函数的参数传递 测试题

-引用类型

--引用类型(例3-11)

--引用类型 测试题

-含有可变参数的函数

--含有可变参数的函数

--含有可变参数的函数 测试题

-内联函数

--内联函数(例3-14)

--内联函数 测试题

-constexpr函数

--constexpr函数

--CONSTEXPR函数课后习题

-带默认参数值的函数

--带默认参数值的函数

--默认参数值例(3-15)

--带默认参数值的函数 测试题

-函数重载

--函数重载(例3-16)

--函数重载 测试题

-C++系统函数

--C++系统函数(例3-17)

--C++系统函数习题

-第3章小结

--第三章小结

-实验三(上)函数的应用

--实验三(上)函数的应用

-实验三(下)函数的应用

--实验三(下)函数的应用

第4章 类与对象

-导学

--导学

-面向对象程序的基本特点

--面向对象程序的基本特点

--面向对象程序的基本特点 测试题

-类和对象

--类和对象的定义

--类和对象的程序举例

--类和对象 测试题

-构造函数

--构造函数基本概念

--构造函数例题(1)——例4-1

--构造函数例题(2)——例4-2

--委托构造函数

--复制构造函数

--复制构造函数调用举例

--构造函数 测试题

-析构函数

--析构函数

--析构函数 测试题

-类的组合

--类的组合

--类的组合程序举例

--前向引用声明

--类的组合 测试题

-UML简介

--UML简介

--UML简介课后习题

-结构体与联合体

--结构体(例4-7)

--联合体(例4-8)

--结构体与联合体 测试题

-枚举类

--枚举类

--枚举类 测试题

-第4章小结

--第四章小结

-实验四(上)

--实验四(上)

-实验四(下)

--实验四(下)

第5章 数据的共享与保护

-导学

--导学

-标识符的作用域与可见性

--标识符的作用域与可见性

--标识符的作用域与可见性 测试题

-对象的生存期

--对象的生存期

--对象的生存期 测试题

-类的静态成员

--静态数据成员(例5-4)

--静态函数成员(例5-5)

--类的静态成员 测试题

-类的友元

--类的友元(例5-6)

--类的友元 测试题

-共享数据的保护

--共享数据的保护(例5-7)

--共享数据的保护 测试题

-多文件结构和预编译命令

--多文件结构和预编译命令(例5-10)

--多文件结构和预编译命令 测试题

-第5章小结

--小结

-实验五

--实验五

第6章 数组、指针与字符串(一)

-导学

--导学

-数组的定义与初始化

--数组的定义与使用

--数组的储存与初始化

--一维数组应用举例

--数组的定义与初始化 测试题

-数组作为函数的参数

--数组作为函数参数(例6-2)

--数组作为函数的参数 测试题

-对象数组

--对象数组

--对象数组 测试题

-基于范围的for循环

--基于范围的for循环

-指针的定义和运算

--指针的概念、定义和指针运算

--指针的初始化和赋值

--指针的算术运算、关系运算

--指针的定义和运算 测试题

-综合实例

--综合实例

-实验六(上)

--实验六上

第6章 数组、指针与字符串(二)

-指针与数组

--用指针访问数组元素

--指针数组

--指针与数组 测试题

-指针与函数

--以指针作为函数参数

--指针类型的函数

--指向函数的指针

--指针与函数 测试题

-对象指针

--对象指针

--对象指针 测试题

-动态内存分配

--动态分配与释放内存

--申请和释放动态数组(一)

--申请和释放动态数组(二)

--动态内存分配 测试题

-智能指针

--智能指针

-vector对象

--vector对象

--vector对象 测试题

-对象复制与移动

--深层复制与浅层复制

--移动构造

--对象复制与移动 测试题

-字符串

--C风格字符串

--string类

--字符串 测试题

-第6章小结

--第六章小结

-综合实例

--综合实例

-实验六(下)

--实验六(下)

例3-9笔记与讨论

也许你还感兴趣的课程:

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