当前课程知识点:程序设计基础 > 第二章 变量与代数思维 > 2.5 猜数游戏与数据表示 > 2.5.1 猜数游戏与数据表示
刚才我们在讲变量
的定义的时候
提到了类型这样一个概念
然后大家也发现
不同类型的变量
它的存储空间是不一样的
这个变量表达的
意义也不同
有的是表达整数的
有的是表达浮点数的
那很显然小数跟整数
是不一样的东西
那我们就要思考一个问题
这些不同的数
在计算机里面
它到底怎么存储的呢
这个事情其实
是一个很神奇的东西
涉及到很深刻的思想
但是我们不妨从
一个简单的游戏开始
大家来看这样
一个猜数的游戏
你现在心里面默想
一个小于50的
这样的一个数
那下面我会给你几个卡片
问在这六张卡片里面
你所想好的那个数到底
是在哪个卡片里面有
那么当你回答我
依次回答我每个卡片里面
有没有你想的
那个数的时候
那我就能感应到
你想的那个数是什么
第零号卡片
大家看
事先想好你要什么数啊
0-50之间的数
看看在这个里面有没有呢
有或者没有你记下一个答案
好吗 好
我们接着看一号卡片
这一号卡片里面
也是一些数字
那么你去看看你的
这些数在不在这个里面
二号卡片 另外的一些数
和没卡片的值不一样
你去看看你自己
脑袋想的数
在里面有没有出现
三号卡片
那么看看这些值有没有
四号
那么五号
好 一共是六张卡片
给大家呈现完了
想想你要的那些数
你猜的那些数
在不在这里面呢
我们有同学说我想到呢
有这样一个数
这个数它在零号
卡片里面出现了
它在二号卡片里面出现了
它在五号卡片里面出现了
当你回答这样的
三句话的时候
我立刻就能算出来
你想的那个数是37
那刚才那个37到底
我是怎么算出来的呢
我当然没有费吹灰之力
但计算机它其实是
用一个程序来算的
我们来看看这段代码
跟以前一样这个代码
是分成几个部分的
最开始有一个include
这是要求的大家
已经越来越熟悉了
事实上我们这门课程里面
绝大多数的代码
这前面的几行都是一样的
所以大家写程序上来
就可以把这几行输进去
然后下面是main函数
最后是在main函数里面的语句
我们可以看到在这个代码里面
在main函数里面
代码是通过空行
分成好几段的
第一段大家可以看到
是一些变量的定义
这个里面变量定义的过程
它是把六个变量
在一行里面写出来
用逗号把它分隔开
int d0,d1一直到d5
定义了六个变量
代码的第二段
大家看它歧视用户
你猜的那个数到底
在哪个卡片里面呢
请你回答出来
所以下面是
c in d0d1d2d3d4d5
要求用户依次回答
零号卡片一直到五号卡片
到底哪个里面有这个数
如果有就输入1
如果没有就输入0
所以输入六个数
第三段大家看到cout
你的那个数是什么呢
cout一个提示信息
然后就是一个计算结果
把结果输出来
37就在这个地方输出的
那他怎么算出来的呢
我们看到这个里面
用用户回答的六个答案
我们把它写成了一个公式
去计算那个结果
d0加上d1乘上2
加上d2乘上4
加上d3乘上8
加上d4乘上16
加上d5乘上32
很奇怪这个里面每一个数
每一个变量它
所乘的这个结果
乘的这个倍数
是在不断变化的
也就是1 2 4 8 16 32
这里面其实是
有一定的道理在里面
后面我们会提到
它到底是什么道理
我们在这个代码里面
通过这样一个计算
那你可以试着
看一看你的这个数
用你的回答的六个答案
按照这样一个计算的公式
你去算一算
看看是不是你想要的这个数
至少我们的37
通过这样的公式
可以算出来
那这里面是个
什么样的原理呢
也就说这样一个
代数的表达式
它是根据什么样的思路
写出来的呢
这个很关键
这个其实是我们用计算机
解决问题的思考过程
你现在看到的代码
是思考的结果
我怎么想到这个呢
我们画一个示意图
你可以看到你的零号卡片
到五号卡片
当我们依次去回答零号卡片
二号卡片五号卡片上
有这个值的时候
我们把它写到纸上
你就可以看到分别是101001
这几个值
按照刚才我们的计算的公式
我们可以写出来这个总的结果
就是二的五次方
加上二的二次方
加上二的零次方
就是那个1
这么一加
就变成了32加上4加上1
正好就是37
那大家看着这个示意图啊
其实告诉我们了一个很大的秘密
就是数到底在
计算机里面怎么表示的
我们可以看到
这个图的格子上面
依次写了二的五次方
二的四次方等等等
二的零次方
然后下面写了100101
这几个值
然后再下面写了
37的计算过程
这样的一个图示告诉我们
计算机表示整数的时候
它是用类似这样的一个形式
来定义的
也就是每一个二进制位
二进制要么是0要么是1
只有两种可能性
那么每一个二进制位
根据它在上面的位置不同
其实代表了不同的数值
比方说这个零一二d2这一位
它代表的是二的平方是4
也就是这一位如果是一的话
就代表这个数是4
那如果我这有好几个1呢
那就得把它加起来
也就是大家在下面看到的
这样一个∑一个求和的形式
所以一个八进位的整数
它去表示的时候
就是用八个0101的这种序列
通过下面的这个∑
的式子来计算的
那么这是你计算的过程
对我们数的表示来讲的话
就是任何一个数都要
把它拆成一个用八个二进字位
表示的这样一种形式
这是一个字节来
表示的情况下
是这样子的
所以刚才37就被表示成为
100101这样的一个结果
以前我们在讲到整
数的类型的时候说
整数占四个字节
那么它四个字节
在计算机里面
又是怎么来表示的呢
其实道理是一样的
你无非是把
这个拉长一点而已
把八个八个拼在一起
拼成了32和二进制位
那这里每一个二进字位
用同样的准则
去把它表示出来
也就是这个图
里面大家看到的
第0位它对应的是2的0次方
第32位它对应的是2的31次方
所以不同的位如果是0
那么这一位的值就没有了
如果是1就把
这对应的值加上去
所以它任然是按照
前面的∑这样一个式子
去计算这个32个二进制位
到底能表示多少的整数
如果所有的位都是1
很显然这是一个最大的整数
如果是无符号情况下
那他是一个最大的整数
这个时候你加起来
就是一个超级大的数
那么大家在这里面
已经对数的表示
至少是整数有一个概念
可能刨根问底的同学就会问
老师那个浮点数怎么办呀
很显然浮点数的表示 它的规律
肯定跟整数的表示不一样
如果一样的话我们
计算机怎么来分别它呢
但是这个不一样里面
有一个东西是一样的
那就是对于浮点数来讲
他的二进制位
也只能取0或者1
而不可能是其他的
那区别在什么地方呢
那只能是这些数的
解释发生了变化
细节东西我们后面
讨论的时候再跟大家一起来探讨
下面我们来回答
刚才的猜数的游戏里面
既然已经了解了
它计算的原理
可是我们没有回答
不知道
那个卡片是怎么做出来的呢
也就是我要去玩这个游戏
假如某一天我要去
玩100个数让你去猜
很显然六个卡片不够了
所以下面我们简单地
跟同学探讨一下
这六张卡片我们是
怎样把他们设计出来的
大家先看这个一个表格
这个表格大家看上去似乎很复杂
我们来简单的解释一下
这个卡片的点上一行
是二的七次方二的六次方
到二的零次方
这样的一个式子
然后下面依次写了
第七到第零这样一个结果
那我们可以看到在
最左边的一列写上了1234567
其实是7个数
我们发现这每一个数
它所对应的8个二进制位
是各不相同的
比如我们随便挑一个
5 它的二进制位000101
那么我们可以看到它在第零列
是一个1第二列下标是一个2是1
其他的都是0
根据这样一个拆分的过程
当然这个拆分的过程
其实就是5这个数
计算机里面表示
成二进制的时候
它的表示的结果
所以换言之就是5这个数
表示成二进制位的
一种二进制的表达形式
最后的三位是101
根据这个结果我们就知道
5这个数要出现在
零号卡片和二号卡片
这两个位置恰好
就是5的二进制表达
它等于1的那两个位的序号
你看 零号 二号
根据这样一个规律我们把
1-50的每一个数
都用二进制的表达
看看他们各自的1
出现在什么位置
然后再对应的卡片
上去写上这个数字
六张卡片就做出来了
至于这样的六张卡片
它上面的值能不能通过
程序自动的生成出来呢
那我们还要用到后面的
章节学到的知识
才能解决
那现在给大家
布置一个思考题
假定有n个整数
这个思考题有n个整数
我需要你去玩上面的游戏
需要制作多少张卡片
拿程序算不要拿手算
那么每张卡片上
应该分别写哪些数字
如果你暂时没办法自动
去完成这些卡片上的
这些数字的自动输出的话
你可以不妨呢把这个
设定成一个固定的数就是100
这个你事先可以
知道有多少张卡片
然后你就可以用
我们现在讲到的知识
去完成这个工作
这个留给大家课下去思考
-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 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测