当前课程知识点:程序设计基础 > 第四章 筛法与查找 > 4.1 插花游戏 > 4.1.1 问题提出(求素数)
好 同学们 我们继续来学习
第四章的内容
首先呢 我想跟大家想象这样一个场景
一群清华幼儿园的小朋友做游戏
老师为了让小朋友熟悉倍数的概念
设计了这样一个游戏
买了很多花瓶
然后把花瓶进行了一个编号
从2开始往后编号 2,3,4这样
然后呢要求小朋友向这些花瓶当中去插花
规则是这样的
第一位小朋友呢
他先走过去向大于2
而且是带2的倍数的这些花瓶中插一朵花
第二位小朋友上去
向大于3而且是3的倍数的这些花瓶中插一朵花
以此类推
问题是最后有哪些花瓶当中是没有被插过花的
根据我们的数学知识
我们都知道像这样一个问题
实际上是相当于我们在找素数
最后没有插花的那些瓶子的编号就是一个素数
所以我们今天就不要让小朋友们费劲去插花了
我们尝试用计算机写一个程序来告诉他们
到底哪些花瓶当中最后没有插花
比如说我们这个问题
找出100以内的所有的素数
然后由小到大的进行输出
这样一个题根据我们上一章学习的知识
我们有枚举法
所以根据枚举法我们就形成了这样一个思路
枚举一下2到100当的中所有的自然数N
然后判断一下这个N是不是素数
如果是呢就直接把它输出
因为枚举的顺序就是从小到大的
所以输出的顺序也会是从小到大进行输出
这样一个思路当中我把我们熟悉的关键字
比如枚举如果和输出给它标上了蓝色
说明这句话我们其实很容易的
把它翻译成计算机语言的代码
那中间有一句判断N是否是素数
还记得我们第一章学的数学函数吧
这个显然判断一个数是不是素数
应该是一个数学问题
跟我们的sin,sqrt开根号这种函数应该是类似的
那我们只需要去找一个这样的数学函数
然后就把它依次的翻译过来就行了
那下面我们就试着把这个程序
刚才的思路翻译成程序
第一句枚举从2到100的所有的自然数N
其实就可以翻译成一个for循环
N从2一直到100
第二句判断N是不是素数
那我们去调一个数学函数
这个函数叫什么我们还不知道
没有去查 所以我们这里打了一个问号问号
把它运行的计算结果存在一个布尔类型的变量里
比如true就代表它是一个素数
false就代表它不是素数
咱们假设有这么一个函数
那第三句如果N是素数
实际上就是判断刚才计算的结果
刚才这个变量到底是true还是false这样一个过程
最后输出N咱们很熟悉了
这个cout 把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 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测