当前课程知识点：C语言程序设计（上） > 循环结构的程序设计（二） > 4.7 循环的综合应用 > 4.7.1 数的排列组合问题

返回《C语言程序设计（上）》慕课在线视频课程列表

4.7.1 数的排列组合问题在线视频

4.7.1 数的排列组合问题

下一节:4.7.2 循环综合应用——穷举算法

返回《C语言程序设计（上）》慕课在线视频列表

4.7.1 数的排列组合问题课程教案、知识点、字幕

接下来我们

看几道综合应用的题目

我们给出来的第一道题是

怎么讲呢

取1到9

这九个数字里边

四个互不相同的数

然后让它们的和是12

这是一个条件

和是12是一个条件

第二个条件是

刚才说完了

互不相同

这两个约束

四个四个数排列

互不相同并且和是12

用什么方法比较合适呢

最直接的

不动脑子的方法就是

穷举

因为计算机

不怕烦

它是

可以给你从头到尾遍历一遍

比如说像这样的数

这也算互不相同

因为6和3

对调了

那么它加起来的和呢

正好是12

所有这样的数

都满足条件

那么1到9里边可以有多少种

这样的组合呢

那我们

看一下

我们想想

一定是要受这个约束

那我们考虑

这个程序怎么做呢

我们来把这程序写一下

我们看一下

刚才我们说的

有四个数

任意数组成

数列

这里边按我们刚才说的

四个数位上的数分别用

i　j　k　l来表示

那么这四个数

每个数都从

1到9

遍历了一遍

i从1到9

j也是从1到9

把所有的可能都遍历了一遍

那在队内循环里边

做两件事

就是这个题目给的要求

第一个要求是

四个数互不相等

我们用或运算

来做这个

选择

或运算

i和j相等吗

或者i和k相等吗

有任意一个相等

我们就会

执行了continue

就是说

下边的事情不用做了

因为你这个条件不满足了

就continue

当前的这一轮的循环

那么

下一个条件是用谁来做呢

这四个东西相加

四个数相加

它的和

不等于12吗

如果不等于12

出局

也让它中断

所以我们这里边用两个表达式

一个是或运算

一个是

关系运算

来看是不是满足

四个数相加等于12

或者四个数不相等

那么我们把

这两个判断的

这个东西都放在了最内循环的里边

那大家可以想想

这个内循环被执行了多少次

我们可以

统计一下看

我们先把程序运行一下

看一下

我们现在看见的是

所有这里边

可能出现的

这种组合

等等

这到底是多少个呢

我们给它计个数看一下

这里边的n

是用来做什么呢

n是用来计数的

这是计的数

这个数我们是说

看它是不是被5整除是

控制格式的

我们把这个数输出一下试试看

然后

我们输出一个

printf

printf里边要的是

什么东西呢

要这个

后边要的是这个n

看一下它运行了多少次呢

这个n

不是循环多少次

是说

你找到了多少组这样的数

就是如果它们都没有出局

就是说都没有

执行这两个continue

那就说明

你这个组合找到了

一共有多少个这样的组合呢

是在n里边的

这块我们拿

n和5去求余

那是说

每一行我们打算排五个这样的组合

每一行排了五个这样的组合

2　3　4　5

一共有多少个呢

48个

我们让它

48搁在下一行上

怎么做呢

斜杠n

48搁在下一行上

好　这48

放在了这

明确区间我们可以再一个斜杠n

让它

隔开一些

一上来有48个这样的数据

那我们刚才是想说

这个内循环的这件事情

判断

以及下边的这几个执行的这件事情

被执行了多少次呢

我们进入这个内循环

可以统计一下

咱这一块设一个计数器

m

那给它赋初值是0

那我们只要在这个内循环里边

做一个

m加加

就可以了

咱在输出的这块

再给一个输出

百分号d

计的内循环到底循环了多少次呢

把这个m拿出来看一下

运行

6561次

内循环被执行了

6561次

可不可以

把这个事情做得

再简化一些

有没有更好一些的算法呢

我们回过头来看

这是刚才咱们的程序

我们看一下这个程序

实际上

大家稍微

考虑一下

就可以

想到

比如说

i等于j吗

这件事情

搁在这个内循环里边

其实是没有道理的

为什么呢

是　i是最外层的循环

j是第二层的循环

i等于j吗

这件事情

完全可以放在这判断

就可以啦

那大家想

我放在这判断的话

你只循环了

9的两个

外循环是9次

内循环9次

那就是9的平方81次

就是说这个判断

这个语句

关系运算

被执行了81次

而不是执行了六千五百多次

那还有没有别的可能呢

我们注意到这里边

有这么几种

情况

大家可以考虑的算法选取的不同

四个

数

加起来的和是

12

那么我们说

互不相同的四个数

一定是小于6的数

而不是说

而不用你把它运行

循环到9

就是

四个数都小于6的话

我们是不是把循环

循环

从

1

到6

就可以了

而且是

小于或等于6

那就是到6就可以了

下边还有第二个问题是

我们刚才说的

你把相应的循环控制变量的

判断

放在与它相关的里边

不要放在最内层

那么这个相差的次数

就是很多的

是9的四次方还是9的二次方

还有一个是说

我们四个数加起来是12

那其中

第四个数

还用去循环吗

第四个数不就是减掉

前三个数吗

所以我们第四个数的l

那循环不就只有三次了吗

三重循环了

不用四重循环

考虑到这三个因素

这个是循环的终值

可以到6

而这个是说

把它判断放在相应的位置

而这个是让

直接减少一重循环

考虑这样的算法

大家看一下

是不是有

程序呢

我们看一下

程序这样写

可不可以

外循环

i到小于7

j也是到小于7

这三重循环都是

小于7

而l呢

不用去循环了

12减掉它们三个就可以了

12减掉它们三个

这一重循环

就去掉了

而我们把这个判断

这种判断

可以放在哪里呢

i和j的判断

放在这里

加了一个if

如果它俩相等

大家看

在第二重的循环里边

如果i等于j的话

我直接就出局

不做了

下边这一块的事情

整个下面的这一重循环

以及这些判断

就不做了

因为已经有一个数

不符合条件了

所以呢

这个算法

要和刚才我们直接做的那个算法

相比的话

它的运行效率应该是高了很多

我们

来看一下

能感觉到它的运行效率高了吗

似乎没有感觉到啊

大家都是

瞬间就出来的

这是因为计算机太快了

那我们把这个

跟刚才的方法一样

稍微统计一下它的循环次数

看一下

同样

我们给这块设一个m

我们看一下这个内循环

被执行了多少次呢

m加加

只要我进内循环

我就加加一次

然后呢

在这块

我把

这个m也给输出来

然后呢

我们刚才说

让它

下来两行

在别的行上

不跟那几个数搁在一起

运行一下看

我们刚才是

加了一个计数器

清零

然后计数器在哪里

这

计数器在内循环里边计数

我们现在是看内循环

一共被执行了多少次

大家看

这个内循环被执行了180次

然后呢

产生的这些数还是48个数

没有变

而刚才我们看到的

那个内循环被执行了

五千多次

是六千多次还是五千多次

而这个执行了180次

所以呢

考虑这个程序

我们稍微的

考虑了一下它这里边的一些

因素

就使得这个程序的

算法就要好得多

所以我们通过这个例子

是想告诉大家

实际上对于同一个问题

你的解决

解决问题的思路

是有不同的

而稍微加一些

对算法的优化考虑

就会使

大家这个程序获得一个

非常好的一个效果

这个程序其实还有

不同的一些方法

大家自己下去可以再试一下

C语言程序设计（上）课程列表：

从问题到C语言程序设计

-1.1 计算机的问题求解方法

--1.1.1--程序设计面向的问题

--1.1.2--关于计算

--1.1.3-1关于算法-算法的特征

--1.1.3-2关于算法——算法的表示

--1.1.3-3关于算法——算法的优化

--1.1.4-1-程序设计方法

--1.1.4-2-程序设计方法

--讨论题：数学模型

-1.1 计算机的问题求解方法--作业

-1.2 C语言与C程序

--1.2.1-1-C概述

--1.2.1-2-C概述

--1.2.2-C初步

--讨论题：运算符

-1.3 C语言处理系统与程序调试运行

--1.3.1C程序如何调试运行

--1.3.2常用C语言处理系统

--1.3.3DEVC++的使用-v1

--1.3.4C语言概貌小程序

-1.4 程序中的人机交互

--1.4 printf用法

--1.4.2 scanf的用法

--作业讨论区

数据计算实现与顺序结构程序设计（一）

-2.1 算术运算的C程序实现

--2.1.1 第二章

--2.1.2 C语言算术表达式概念

--2.1.3 算术运算的实现

--2.1.4 整数相除

--2.1.5 输入格式造成的计算错误

--2.1.6 求余运算

--2.1.7 自增自减运算

--2.1.8 复合运算

--fangcheng-1.c

--fangcheng-2.c

--fangcheng-3.c

--fangcheng-4.c

--算术混合运算.c

--讨论题：自增自减符

--讨论题：程序输出结果

--讨论题：程序运行结果

-2.1 算术运算的C程序实现--作业

-2.2 关系运算的C程序实现

--2.2.1 关系比较问题

--2.2.2 C语言关系表达式

--2.2.3关系运算优先级

--2.2.4 用关系运算做判断条件

--2.2.5 程序实例

--2.2.6 字符比较

--pingshifen-1.c

--panduanzhengshu.c

--pingshifen-2.c

--字符比较.c

--讨论题：比较大小

--讨论题：程序的运行

-2.2 关系运算的C程序实现--作业

-第二周作业--作业

数据计算实现与顺序结构程序设计（二）

-2.3 逻辑运算的C程序实现

--2.3.1 逻辑运算问题~1

--2.3.2 逻辑运算表达式

--2.3.3 如何判断闰年

--2.3.4 逻辑运算优先级

--2.3.5 条件运算符

--计算结合性

--2.3.7 一个简单实例

--自动购票问题.c

--讨论题：逻辑表达式

-2.3 逻辑运算的C程序实现--作业

-2.4 位运算的C程序实现

--2.4.1 什么是位运算

--2.4.2 位运算有哪些

--2.4.3 位运算怎么用

--讨论题：位运算

-2.5 几种很个别的运算

--2.5 几个很个别的运算

-2.5 几种很个别的运算--作业

-2.6 混合运算及数据类型转换

--2.6 混合运算及数据类型转换

--讨论题：数据类型

-2.7 顺序结构程序实例

--2.7.1 第一个程序：三角形

--三角形面积.c

--讨论题：工业产值

--讨论题：程序无效结果

-2.7 顺序结构程序实例--作业

选择结构的程序设计

-3.1 程序中的路径选择实现

--3.1.1_1 第三章

--3.1.1_2 神奇的if_else

--打印学生成绩.c

--一元二次方程.c

-3.1 程序中的路径选择实现--作业

-3.2 路径中的再选择——嵌套判断

--3.2.1_1 if语句的嵌套

--3.2.1_2三个数排序1029

--3.2.2 用户登录检查

--三个数排序_未优化.c

--三个数排序_优化.c

--讨论题：程序改错

-3.2 路径中的再选择——嵌套判断--作业

-3.3 复杂判断问题的C程序设计

--3.3 多级选择

--银行存款.c

--讨论题：多级选择

-3.4 多分支问题的C程序设计

--3.4.1 switch语句表达式

--3.4.2 加减乘除计算

--3.4.3 几类说明

--加减乘除运算.c

--讨论题：关于switch

-3.4 多分支问题的C程序设计--作业

-3.5 GOTO的适当使用

--3.5 GOTO的适当使用

-3.6 选择结构的程序实例

--3.6 程序展示

--计算第几天.c

--存款利息__switch实现.c

--讨论题：输出奇数

--讨论题：计算税金

-3.6 选择结构的程序实例--作业

-第四周作业--作业

循环结构的程序设计（一）

-4.1 需要重复执行的程序

--4.1.1----第四章~1

--4.1.2---while实现先判断后循环~1

--4.1.3----while循环的应用-录入速度~1

--打印学生成绩.c

--统计录入速度.c

--求平均数.c

-4.1 需要重复执行的程序--作业

-4.2 至少要执行一次的循环

--4.2.1至少要执行一次的循环

--4.2.2-do-while循环应用

--成绩录入_do while实现.c

--字符分类统计.c

--讨论题：关于while

-4.2 至少要执行一次的循环--作业

-4.3 已知循环次数用for语句

--4.3.1--用for语句控制循环次数

--4.3.2--循环的应用-求和

--求和问题.c

--斐波那契数列问题.c

--数列求和.c

--讨论题：循环语句的不同

--讨论题：循环语句

-4.3 已知循环次数用for语句--作业

-4.4 循环控制——简单循环应用

--4.4.1-循环的应用-找数-水仙花数

--4.4.2--循环的应用-求素数

--水仙花数.c

--讨论题：死循环

--讨论题：continue和break

--讨论题：猜数字

-循环结构的程序设计（一）--4.4 循环控制——简单循环应用

循环结构的程序设计（二）

-4.5 循环的嵌套

--4.5.1 循环的嵌套——九九乘法表

--4.5.2 循环的嵌套——打印三角形

--打印九九乘法表.c

--打印实心三角图案.c

--打印空心三角图案.c

--讨论题：程序运行

-4.5 循环的嵌套--作业

-4.6 break与continue

--4.6 循环中断与继续循环——break再讨论

--最大素数.c

--求正数个数及平均数.c

-4.6 break与continue--作业

-4.7 循环的综合应用

--4.7.1 数的排列组合问题

--4.7.2 循环综合应用——穷举算法

--4.7.3 循环综合应用——满足条件的数

--4.7.4 循环综合应用——求最后三位数

--4.7.5 循环综合应用——打印空心图案

--数的排列组合.c

--数的排列组合优化.c

--鸡兔同笼.c

--找满足条件的数.c

--输出14的13次方的最后三位数.c

--打印空心字符.c

--讨论题：打印图形

--讨论题：打印空心图形

--讨论题：计算闰年

-第六周作业

--虚拟实验：循环程序设计实验

-第六周作业--作业

数组（一）

-5.1 同类有序数据处理问题

--5.1.0 数组开篇

--5.1.1 同类有序数据存储问题

--讨论题：下标变量与下标

-5.2 一维数组的定义和引用

--5.2.1_1 数组的定义~1

--5.2.1_2 数组的初始化

--5.2.2 一维数组的输入输出

--5.2.3 一维数组的应用1--成绩排序(选择法)~2

--5.2.4 一维数组的应用2--Fibonacci数列

--数组定义.c

--数组初始化.c

--输出大于平均值的数.c

--反向输出.c

--选择法_成绩排序.c

--求斐波那契数列前n项.c

--讨论题：对称数

--讨论题：关于'\0'

-5.2 一维数组的定义和引用--作业

-5.3 一维字符串数组

--5.3 一维字符串数组11.24~1

--用函数测试字符串长度.c

--讨论题：编程

-5.4 字符串处理函数

--5.4 字符数组的输入与输出

--字符串反向.c

--字符串函数

--讨论题：程序如何运行

--讨论题：黑色星期五

数组（二）

-5.5 二维数组的定义与使用

--5.5 二维数组定义

--二维数组的定义与初始化.c

-5.6 二维数组的输入输出

--5.6 二维数组的输入与输出

--二位数组输出_矩阵输出.c

--讨论题：随机数据存储

-5.6 二维数组的输入输出--作业

-5.7 二维数组的应用‍

--5.7.1二维数组的应用-转置矩阵

--5.7.2 用一维数组方式引用二维数组元素

--转置矩阵.c

--找二维数组最大数.c

--讨论题：修改程序

--讨论题：关于随机数函数 rand()

-5.8 二维字符数组

--5.8 单词排序

--单词排序.c

--讨论题：回文字符串

-5.8 二维字符数组--作业

-5.9 数组综合应用

--5.9.1 应用1——学生成绩统计

--统计成绩.c

--5.9.2 应用2——删除重复字符

--删除串中的重复字符串

--5.9.3 应用3——统计字符

--5.9_4数组的应用4--矩阵相乘

--统计字符次数.c

--讨论题：洗牌

-本期课程结束语

-第八周编程作业

--虚拟实验：冒泡排序算法程序设计实验

期末复习

-《C语言程序设计（上）》期末复习参考

期末复习答案

-《C语言程序设计（上）》期末复习参考答案

4.7.1 数的排列组合问题笔记与讨论

也许你还感兴趣的课程:

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