tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

巧用二进制数思想编程方法例谈


巧用二进制数思想编程方法例谈
浙江慈溪实验中学 张利波 315300

二进制数在计算机中有着非常重要的意义, 在信息学竞赛中, 巧妙使用二进制数的特点, 可能使程序思路更加简洁明了,解题也变得相当简单,下面列举几个程序来说明。 例 1、如图所示为一个城市街道简图,小明从 A 点出发到达 B 点。如 果在每一个路口只能向右或向上走, 问小明可有多少条行走路线?并输出 每条路线。 问题分析: 该题一般的方法可以用深度优先遍历或广度优先遍历求解 所有的行走路线。那么如何套用二进制数思想编程呢?根据题意,可以通 过以下几个方面进行分析: ①行走方向只有两种向右走或向上走,那么我们不妨用 0 表示向上走,1 表示向左走; ②根据路径从 A 点到 B 点,不论走哪条路径,走的步数总是固定的,如图中就是 7 步,因 此,我们可以确定二进制数的位数是 7 位;③根据行走方向,用“1”表示向右走,据图向 右走的步数为 4, 用二进制数表示又产生一个约束条件, 7 位二进制数中的 “1” 的个数为 4, 同理, “0”的个数为 3。 根据以上分析, 原题即转换成对 7 位二进制数的筛选, 范围在(0001111)2——(1111000)2 之间,且分离各位数字,相加为 4,符合上述条件的,即为可以行走的一条路线,要统计所 有可行走路线, 只要对每个符合条件的线路数量累加即可。 参考程序中避免了十进制数转换 成二进制数的操作,采用穷举所有 7 位的二进制数并对此进行筛选完成。参考程序如下。 program AllPath(input,output);(在 FreePascal 下通过) const n=4;m=3;{向走的步数、向上走的步数} var i,total:integer; a:array[1..(m+n)] of 0..1; begin total:=0;{累加器} for a[1]:=0 to 1 do{逐位枚举} for a[2]:=0 to 1 do for a[3]:=0 to 1 do for a[4]:=0 to 1 do A B

for a[5]:=0 to 1 do for a[6]:=0 to 1 do for a[7]:=0 to 1 do if a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]=n then{条件筛选} begin total:=total+1; write('No:',total,'---> '); for i:=1 to 7 do write(a[i]:2); writeln;{符合条件,输出线路} end; end. 例 2、如下图,有一个无穷大的栈 S,在栈的 右边排列着 1,2,3,4,5 共五个车厢。其中每个 车厢可以向左行走, 也可以先进栈 S 让后面的车厢 通过。现已知第一个到达出口的是 3 号车厢,请写 出所有可能的到达出口的车厢排列总数,并输出每种排列。(源自第八届信息学初赛普及组 问题求解) 问题分析: 这是一例典型的栈应用题,主要考察栈“先进后出” 特点, 如果用常规办法, 如递归,也可能造成遗漏,用非递归办法则更为复杂。根据题意,我们可以通过以下几个方 面进行分析: ①栈的操作只有两类:进栈和出栈,那么就可以用二进制数 0、1 表示,用“1”表示 进栈, “0”表示出栈;②每个车厢经过栈操作(进栈出栈),如果车厢直接向左行走,可以理 解成进栈后马上出栈,这样就可以把 5 个车厢的操作化解成 10 个动作,用 10 个二进制位 数来表示;③根据栈操作,出栈必在进栈之后,则对应二进制数“1”的个数必不小于“0” 个数;④题意中要求第一个到达出口的是 3 号车厢,可以确定二进制数的高 4 位数字为 “1110” ,表示 1,2,3 车厢进栈后,首个出栈车厢为第 3 个车厢,这样数据范围由原来 10 位缩小至低 6 位;⑤此外由题意不难发现,该 6 位上的二进制数字,含“1”的个数为 2 个,因此可以进一步框定数据范围在(001010)2——(110000)2,⑥最后一次操作不可能是进 栈操作,因此数据最低位不能为 1,即只能为偶数。参考程序如下。 Program AutoStack(input,output);(在 FreePascal 下通过) Const TotalBus=5;FirstBus=3;{总车辆,首个到达车辆} 出口← ← S↓ 1 2 3 4 5

Var Yushu,Shang,OneNum:integer;{十进制转化成二进制数用到的变量} i,j,p,k,total,max:integer; a:array[1..(2*TotalBus)] of 0..1;{存放二进制数} b:array[0..TotalBus] of integer;{输出时进栈、出栈操作对应数据暂存} begin total:=0; for i:=1 to FirstBus do a[i]:=1;a[FirstBus+1]:=0;{确定高位上的数据} writeln('-Id- ---erjinzhi-- ---serial---'); for i:=10 to 48 do{确定查找范围,在该范围进行筛选} if not odd(i) then{选择偶数} begin Shang:=i; OneNum:=0;k:=0; while Shang<>0 do{把十进制数转换成二进制数} begin k:=k+1; Yushu:=Shang mod 2;{取余数} Shang:=trunc(Shang div 2);{取商} OneNum:= OneNum+Yushu;{对“1”进行统计} if OneNum>trunc(k div 2) then break; {去除不合法数据,马上退出} a[2*TotalBus+1-k]:=Yushu; end; if (OneNum=TotalBus-FirstBus) and (Shang=0) then{经过一次检验后全部完成二 进制转换,对“1”个数进行判定} begin{检验后合格,输出序列} total:=total+1;write('No.',total,': '); for j:=1 to 2*TotalBus do write(a[j]); write(' ('); p:=0; k:=1; max:=0; for j:=1 to 2*TotalBus do{对进栈、出栈操作进行出栈输出}

if a[j]=1 then begin p:=p+1;b[p]:=max+1; max:=b[p]; end else begin write(b[p]:2);p:=p-1; end; writeln(')'); end; end; end. 通过以上两个程序,我们大致了解用二进制数编程的方法,那么适用该方法时,程序描 述有哪些明显特点呢?下面是笔者归纳的一些特点: 具体例举 序号 一般规律 例 1 程序 关键处理动作只有两种:可 ① 以用 0、1 表示 关键动作数量固定:可以确 ② 定二进制数的数值范围 动作序列可化解成二进制 ③ 数:便于输出动作过程 可以用若干个二进制数对应 ④ 模拟若干个正确的操作序列 约束条件可以转化成该二进 ⑤ 制数的某些特点,方便筛选 “1”的个数为 4 量为 5 当然用二进制数的思想巧妙进行程序编写, 其基本方法还是穷举, 如果单纯地列举每一 位的情况,对于二进制位较多的情况,估计时间肯定得超时,这里只是给予方法上的启迪, 在实际编程中, 在运用二进制数思想编程时, 要充分搜索题意信息, 缩小二进制数搜索范围, 或者结合排列组合知识的运用,程序效率会更高。 注:本文发表于《Noi 专刊》2007 年第 10 期 向上,向右走 (1111000)2 (1110010)2 等 向右走为 4 步: 的个数;进栈为 5, “1”的数 作 (111011000)2 (111001010)2 等 先进栈, 后出栈: 1 个数必<=0 101 可表示向右, 101 表示进栈、出栈、进栈操 走7步 经过 10 次操作 向右走,向左走 进栈,出栈 例 2 程序


推荐相关:

数据的存储以及二进制思想

数据存储以及二进制思想_计算机软件及应用_IT/计算机_专业资料。数据存储以及...法 : 1=0 八进制和十六进制 除了二进制,编程中也经常使用八进制和十六进制。...


10—十进制和二进制的转换_图文

或者用下面这种方法: 把二进制数首先写成加权系数展开式,然后按十进制加法规则 ...下面我们开讲原理,举个十进制整数转换为二进制整数的例 子, 假设十进制整数 A...


二进制小数

“退一还二”. 十进制小数化为二进制小数,主要通过分数作中间媒介. 例将(0....一是要学习推理中的思想方法,二是最好归纳成一个易用 易记的公式. 十进制...


基于二进制的歌德巴赫猜想的证明

通过 Java 编程,利用计算机最为基础的二进制(0-1)...的它,先后 被挪威数学家布朗用一种古老的筛选法将...可能这种论证似 乎很简单,思想也不太成熟,可是却难...


编程题12_八进制转换为二进制

编程题12_八进制转换为二进制_电脑基础知识_IT/计算机_专业资料。名称 编程题 12:八进制转换为二进制 备注 描述 12.用函数实现将一个八进制数转换为一个二进制...


《二进制数 信息编码》说课稿

二进制数 信息编码》说课稿_其它课程_初中教育_...实际问题的思想方法,促使学生主动学习从而培养学生...结合我的教学实践, 谈谈我的几点反思: 1、自我评价...


小学奥数系列:第十四讲 从数的二进制谈起

小学奥数系列:第十四讲 从数的二进制谈起_学科竞赛_小学教育_教育专区。小学...的是怎样较快地把一个十进制数化为二进制数.还以 1993 为例, 前面的方法是...


小学奥数系列:第十四讲 从数的二进制谈起

小学奥数系列:第十四讲 从数的二进制谈起_学科竞赛_小学教育_教育专区。小学...的是怎样较快地把一个十进制数化为二进制数.还以 1993 为例, 前面的方法是...


四位二进制数的可控加法实验报告

3. 使用编译器将设计实现 四位二进制数的可控加法实验报告 一、实验目的。 1. 了解四位二进制数运算的基本原理,制定设计方案。 2. 利用 ISE 软件进行可编程...


七年级教学渗透数学思想方法例谈

七年级教学渗透数学思想方法例谈_教学案例/设计_教学研究_教育专区。七年级教学渗透数学思想方法例谈湖北 熊志新 向其智 表示函数常见方法有三种:表格、图形和...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com