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 程序


推荐相关:

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

巧用二进制数思想编程方法例谈_学科竞赛_高中教育_教育专区。信息学竞赛巧用二进制数思想编程方法例谈浙江慈溪实验中学 张利波 315300 二进制数在计算机中有着非常重...


巧用二进制编程

巧用二进制数思想编程方法例谈浙江慈溪实验中学 张利波 315300 二进制数在计算机中有着非常重要的意义,在信息学竞赛中,巧妙使用二进制数的特 点,可能使程序思路...


浅谈数形结合思想在信息学竞赛中的应用

编程、时间、空间复杂度 第 2 页共 12 页 浅谈数形结合思想在信息学竞赛中...如今信息时代中,计算机处理各类事物,最终无不是归结 于二进制数的基本运算,数...


浅谈编程语言

使用的工具是什么?发展如何?下面让我们 来简单的谈...字节码文件是与平台无关的二进制码文件,执行时由...《Java 编程思想》.机械工业出版社.2007 年 06 月...


使用通讯方式改变变频器参数方法浅谈

传统的控制方式一般是使用 PLC 的数 字输入输出端子...各通讯口的通讯功能如下: Port0(编程口) : 通讯...例: CR(0DH) 寄存器号(二进制) K 协议/CCM/...


浅谈数学之美

把千万分之一写成 10-7; 二进制在计算机领域的...用 2 、 3 等表示无限不循环的数, 虚数单位 ? ...产生新方法、 新思想、 新概念、 新理论的起点。 ...


数学系毕业论文《浅谈数学中的美》

数量,我们就可用按钮的组合来表示任何一个二进制数...夺天工的生活世 界,也才给我们带来丰富的自然美...统一性遭到破坏后, 产生新方法、新思想、新概念、...


浅谈数值逼近

以下我们通过实例证明一为体会二分逼近法的思想及...数 N 可以表示成一个二进制的数,在这个二进制的...运用二分 法逼近的方法求解.如用二分法逼近求方程 ...


浅谈量子信息技术

两个昆比特位能同时储存所有的 4 个 二进制数。...使用无线电频率脉冲编程,并使用类似 于医院中的核磁...其基本思想是:将原物的信息分成经典信息和量子信息...


单片机串口通信浅谈

按照二进制数的数位一位接一位 的传输,例 如要...在此对比一下并口的 传输方式,并就是并行的意思,...必须软件置零 二、PC 机端编程(使用 VB) Private...

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