Hanoi二叉数算法

轩辕十四

贡献于2010-10-12

字数:0 关键词: C/C++开发

H anoi塔 问题 一种非递 归算法 的 c + + 实现 2006 年 文 章 编 号 :100 3 — 58 50 (20 0 6)0 4 — 00 54 — 0 3 H anoi 塔 问 题 一 种 非 递 归 算 法 的 C + + 实 现 Im plem entation of C + + to M ak e A N o n — recursive A lgorithm a b o u t T o w e r o f H an o i 贺存 薪 (北 京 交通 大学 北京 100 044 ) 【摘 要】通过对汉诺问题的递归算法及结果的分析 ,创造性地借助二叉树 的数据结构设计 出非递 归算法。给 出 了实现该 算 法的 C + + 语 言源 程序 。该 算 法并未 真正在 物理 上 生成 所谓 的二叉树 ,有 别于 常规 对 二叉树 结构 的使 用 。 . 【关键 词】汉诺 ,非递 归 ,二 叉树 ,中序遍 历 ,算 法 ,实现 中 圈 分 类 号 :T P 3 11.12 文 献 标 识 码 :A A B S T R A C T T h ro u gh a nalyzin g th e recursive algo rith m an d re sult o f H an o i p ro b lem ,th is p ape r d esig ns th e n o n — recu rsive a lgo rith m creative ly by dint o f the da ta stru cture of b in ary — tree ,an d p re sen ts th e so u rce pro gram o f C + + tO m ake the algo rith m . T h is algo rith m ha sn ’t rea lly cre ated th e sa m e b ina ry — tree ph y sica lly ,an d it is d iffe ren t fro m th e trad itio na l b in ary -- tree stru ctu re in ap plicatio n K E Y W O R D S H an oi,n o n — recu rsiv e , b in ary — tree , in o rd er trav ersa l, algo rith m , im p le m e n tatio n H anoi塔 问题 是 递 归 程 序 设 计 中 的 经 典 问题 之 一 , 大部 分讲 递 归程 序 (或 算 法 )设 计 的书 都 以 H anoi 塔 问题 为例 。递 归过程 结构 清晰 ,容易 理解 ,便 于设 计 算 法 、调 试程 序 。但 ,递 归过程 须使 用堆 栈技 术 ,要 比非 递归 程序 耗 费更 多 的时 间和 空 间 ,尤 其 是 H anoi塔 问 题 ,其 时 空复 杂 度是 随着 盘 子 个 数 的增 加 而 以几 何 级 数递增 的。 本 文借 助二 叉树 的数据 结构 设计 出 H anoi塔 问题 的一种非递归算法。该算法易于理解,实现简单,时间 略优 于递 归算法 ,且不 需额 外空 间 。因为该 算 法仅借 助 满二 叉树 的形式 组织期 望 的数据 结果 ,分 析规 律 ,实 现 算 法 时并 未真 正在物 理上 生成 所谓 的满 二叉树 。 1 H anoi(汉诺 )问题 的递归算法 H an oi(汉诺 )问题 是 这 样 的 :古 代 有 一个 梵 塔 ,其 中有 3 个塔 座 A 、B 、C 。开 始时 A 座 上有 N 个盘子 ,每 个 盘子 大 小不 等 ,大 的在 下 ,小 的在上 ;另两 个 塔 座 为 空 。一 个 和 尚想 把这 Ⅳ 个盘 子从 座 转移 到 C 座 。佛 经上 规 定 ,若要 移 动盘 子 ,每 次 只 能移 动 一 个 ,并且 每 个塔 座上 都必 须始 终保 持大 盘在 下 ,小 盘在 上 ,移动 过 程 中可 以借助 B 座 。请 帮和 尚设 计 出移动 步骤 。 其递归算法用 C + + 语言实现如下(参考文献 [1] 中的程 序写 成 ,有 关 C + + 语 法规 则 见 参 考 文 献 [3]、 参考 文献 [4]): # in clud e< iostream .h > in line vo id m o v e (ch ar g eto ne ,ch ar p u to ne ) { static int n一0 ;//n 用来表示移动盘 子步 骤的序号 co u t< < + + n < < : < < geto ne < < 一 < < p u to ne < < en dl ; ) vo id h ano i(in t n ,ch ar on e ,ch ar tW O ,cha r th ree ) { if(n = 一 1)m o ve (o n e ,three ) ; else { h an o i(n 一 1 ,o ne ,th ree ,tW O ) ; m ov e (o n e ,th ree ) ; h ano i(n 一 1 ,tW O ,o ne ,th ree ) ; ) ) v o id m a in () { in t m ; cout< < ”请输入盘子数 (0< N < 31):一; cin > > m : cout< < ”移动”< < m < < 个盘子的步骤 :一< < endl; h an oi(m ,’A ’,’B ’,’C ’) ; ) 观 察 v oid h an oi(in t n ,ch ar one ,ch ar tw o ,ch ar * 2 00 5 一l l 一30 收 到 ,20 06 — 0 3 — 0 1 改 回 * * 贺存薪 ,1979 年生 ,在读硕士 ,研究方 向:程序设计 与算 法优 化。 维普资讯 http://www.cqvip.com 第 19 卷 第 4 期 电 脑 开 发 与 应 用 three)函数 ,我们 发现其结构与中序遍历二叉树[2]的 递 归算 法 的函数结 构 一致 。 2 H an oi(汉诺 )问题 的非递 归算法 2.1 H an oi(汉 诺 )问题 的具体 结 果 1 个 盘子 的结 果是 :1 : — C 2 个 盘子 的结 果是 :1 : — B 2 : — C 3 :B — C 3 个 盘子 的结 果 是 :1 :A — C 2 :A — B 3 :C — B 4 : — C 5 :B — A 6 :B — C 7 : — C 4 个盘 子 的结果 是 :1 : — B 2 : — C 3 :B — C 4 : — B 5 :C — A 6 :C — B 7 :A — B 8 :A — C 9 :B — C 1 0 :B — A 1 1 :C — 1 2 :B — C 1 3 : — B 1 4 : — C 1 5 :B — C 5 个 盘子 的结 果是 :⋯ ⋯ 不 难 发 现 ,步 骤 总 数 是 盘 子 总数 A_ Ⅳ 的 确定 函 数 :S 一2Ⅳ一 1 ,与 满 二 炙 树 图1 1个盘子 的节点 总数 和树 高 的关 系一致 。于 是 ,不 的结果 妨把 上 面 的结果 当作 中 序遍 历 满 二叉 树 的结果 ,画 出 对应 的满二 叉树 ,如 图 1 、图 2、图 3 、图 4 所示 。 图 2 2个 盘 子 的 结 果 图3 3个 盘 子 的 结 果 图4 4个 盘 子 的结 果 2 .2 观察这 些满 二叉 树 ,发现 以下 结果 ① 盘子数 Ⅳ 确定 后 ,树高 H 是确 定 的 :H = N ; ② 倒 数 第 1 层 的 序 号 分 别 是 1 (即 2。)、3、5、 7、⋯ 、2 一 1(即 2 一 2o),顺 序 排 列 的 2 个 能 被 2。 整除 且 不 能被 2 整 除 的数 ;倒 数 第 2 层 的序 号 为 2 、 6、10、14、⋯ 2 一2 ,2,v-2个顺 序 排 列 的能被 2 整 除 且 不 能被 2 整 除 的数 ;倒 数第 3 层 的序号 为顺 序 排列 的 2N- 3个 能被 2 整 除且 不 能 被 2。整 除 的数 .-.·;最 上 层 的序号 为 2Ⅳ- ,只有 2N--N 一2。一1 个 ; ⑨ 每一层 的节点 数是 确 定 的 ,等 于 2卜 为从 上 往 下数 的层数 ,从 1 开 始数 ) ; ④若不看节点前 的序号,每幅图中相同层的结果 完全相 同(第 1 层全是 — c ;第 2 层全是 — B ,B — C ;等 ) ; ⑤ 若 只看字母 (实为盘子名),每一层都从 开 始 ,到 c 结 束 ,且除 首尾外 字母 都重 复一 次 ; ⑥ 移 盘 方 向,奇 数层 都 是 A — c 、c — B 、B — 、A — c 、C — B 、B — A 、⋯ 模 3 循 环 ,且 以 A — c 开 始 以 A — c 结 束 ,偶数层 都是 — B 、B — c 、C — 、 — B 、B — c 、c — 、⋯ 模 3 循 环 ,且 以 — B 开始 以 B — c 结束 。 2.3 综合 以上 分析 ,得 出以下 结论 ① 盘子 数 Ⅳ 确 定后 ,步骤 总数 是 确定 的 : 一2Ⅳ 一 1;任意 一步 的结果 也是 确定 的 ,可 由以下几条 确定 ; ② 第 M (0< M < 2Ⅳ)步 所 处 的层 数是 确定 的 ,当 M 能 被 2 整 除 且 不 能被 2卧 整 除 时 ,M 处 在 倒 数第 R + 1 层 ,即层数 t,一Ⅳ一R ; ⑨第 M (0< M < 2Ⅳ)步在 第 t,层 的顺 序号 (从 0 开 始 ) K 一(M ÷2 一1) -- 2 ; ④ 根 据 2.2 中⑥ 的结 论 ,由 t,和 K 得 出 结果 (即 移 盘方 向) 已是显然 。 这就 是非 递 归算法 的思想 。用 C + + 语言 实现 ,源 程 序如 下 : # in clu de < iostream .h > vo id s hu ch u (in t m ,in t n ) { fo r (int t— n ,y — t8L1 ,c — m ;y 一 1 ;t— t> > 1 ,y — t&1 ,c 一 一 );//定位 ,C 表示层号 sw itch ((c&1) * 3+ (t> > 1) 3 )//c& l 奇 偶 判 断 ,t> > 1 为层 中序 号 { case 0 :co ut< < n < < :A — B ~hreak ; case 1 :to u t< < n < < :B — C kn ;b reak ; case 2 :to u t< < n < < :C — A kn ;b reak ; case 3 :co u t< < n < < ;A — C kn ;b reak ; case 4 :co u t< < n < < :C — B kn ;b reak ; case 5 :co ut< < n < < :B — A kn ; } } vo id m ain () { int c一1,m ,n 一1;//n 表示移动盘子的步骤序号 COUt( ( ”请输入 盘子 数(0( N ( 31):一; cin > > m ; COUt( ( 移动 < < m < < 个盘 子的步骤 :一~ endl; for(c< < 一m ;n< c;n + + )l/c= 步骤总数 + l shuchu (m , );//输出每一步结果 本文程序在 V C 6.0 下运行通过 ,程序中步骤总数 维普资讯 http://www.cqvip.com H anoi塔 问题一种非递 归算法的 c + + 实现 2006 年 定义为 int 型 ,故输入盘子数应限制在 0< N < 31。若 按从 大 到小 的顺 序给 盘 子编 号 ,则 盘 子 的序 号 与 二 叉 树 的层数 对应 (第 J 层 为移 动第 |,个 盘 子的 结果 ) 。该 算 法不 仅 可 以给 出移 动 盘子 的方 向 ,也 可 以给 出被 移 动 的盘子 的序 号 (即标示 符 )。 3 结 论 H anoi塔 问题 的非递 归算 法 已有 一些 。有 的没 有 程 序 实 现 ,有 的程 序 不 完 整 ,有 的设 计 复 杂 .11], 有 的时 间复杂 度 比递 归算 法 高[1 ,有 的空 间上 需要 另 外 设栈 或数 组 ¨]。 本 算法 所用 结论 的证 明请参 看 文献 [5]。算 法 的实 质与文献[8]并无太大区别,只是文献[8]重在算法的 形式 推 导 ,算 法 不 易理 解 ,本 文 重在 算 法 的形 式 解 释 , 易于人 们接 受 。 参 考 文 献 [1] 谭浩强.C 程序设计[M ].北京 :清华大学出版社 ,1999. [23 宁正元.数据 结构一用 C 语言 描述[M ].北 京 :中国水利 水 电 出版 社 ,200 0 . [3] 吕凤 翥.C + + 语言 基础教 程 [M ].北京 :清 华大学 出版 社 ,19 99 . [43 马建 红 ,沈西 挺.V isual C + + 程 序设 计 与软件 技术 基础 [M ].北 京 :中国水利水 电出版社 ,2002. [53 王 明.梵 塔 问题 的两 个定 理 [J].应 用数 学 ,1999 ,12 (2) :112 — 1 14. [63 刘 振海 ,柬长宝.H anoi塔 问题的一种 非递归算 法 [J].电 脑开发 与应用 ,2002 ,15(11):33 — 34. [73 谢贤 飞,赵小勇.对 H anoi塔 问题非递 归算 法 的改进[J]. 电脑 开 发 与 应 用 ,200 3 ,16 (7 ) :47 — 4 8. [8] 宁爱兵 ,黄 明 和.H anoi塔 问题非 递 归算 法 的形 式 推导 [J].计算机工程 与科学 ,2003 ,2 5(3):66 — 68. [9] 李 忠 ,尹德辉 ,孟 林 .递 归算法 非递归化 的一般 规律 [J].四川师范大学学 报( 自然科学 版),2003 ,26(2):209 — 2 1 2 . [1O] 张世禄.H anoi塔 问题 的最佳解 法[J].四川师范学 院学 报 (自然科学 版),2001,22(4):364 — 367. [11] 李永新.汉诺 塔问题的非递 归算 法实现 [J].湖 州师范学 院学 报 ( 自然 科 学 ) ,20 00 ,2 2 (6 ) :4 3 — 4 7 . [12] 王 颖 ,王正 洲.汉 诺塔 问题迭代 算法实 现和分 析[J]. 合肥联合大学学报 ,1999,9(3):84 — 87. [13] 姚文 勇 ,李帮 正.H A N O I塔 问题求 解 [J].绵 阳师 范 高 等专科学校学报 ,1999 ,18(2):21 — 25. (上 接 第 5 3 页 ) 允 许迟 到包 率 。这种 方 法最适 合 包到 达 间隔变 化 大的 网络 ,如 IP 网络 。 3.2 IP 电话 的丢 包 由于 IP 网络不能保证服务,常常会意外地丢失语 音 包 。因此 ,丢包 的问题相 当严重 ,现在 的 IP 网络将 语 音帧都作为数据对待,在负载高峰和阻塞的情况下 ,语 音 帧会 和 数据 帧一 样被 丢失 。由 于数据 帧对 时 间不敏 感 ,丢包可通过重传处理来纠正 ,而语音包 的丢失却不 能这样处理,可采用插值法来补偿 ,即用 回放 已收到的 语 音包 来 替代 丢失 的语 音包 。这 是一 种 在非 相邻语 音 帧 间填 充 时 间的 简单 方 法 ,这 种 方 法对 偶 尔 丢包 的情 况较 适 用 ,而对 丢失 较 多包 和 丢 失 大包 的情 况 则 不适 用 。另一种丢包补偿法是发送冗余信息 ,即在发送第 ,z + 1 个 包 时 ,重 复发送 第 个 包 的语 音 信息 。这种 方 法 的优 点是 能精 确矫 正 丢包 ,但要 使 用更 大 的带宽 ,并 产 生更 大 的时延 。还 有 一种 混合 方法 就是 使用 非 常低 的 带宽语音编码器来提供冗余信息 ,这可降低额外的带 宽需 求 ,但不 能解 决 时延 问题 。 4 总 结 总 之 ,随着 IP 网络 技 术 的发 展 ,IP 电话在 不 久 的 将来 必 将成 为人 们 日常通 信 的工 具 。IP 网络 与电话 网 结合 ,特别是在 IP 电话 中 7 号信令技术的发展和与智 能 网 的结合 ,将 不断 丰 富 IP 电话 的业 务特 性 。同时 ,计 算 机 网 络是 计 算机 技 术 与通 信 技 术相 结 合 的产 物 ,是 信 息化 社会 的基 础设 施 。IP 网络 互连 技术 的发 展使 整 个 社会 实 现网 络化成 为 可能 ,形成 社会 网络 化 ,网络 社 会化的局面。IP 电话正是在这种趋势下 ,促进信息网 络 走 向融合 的 前奏 。 参 考 文 献 [1] 刘 轶.H .323 标 准及其在 Internet 上 的应 用.微型 电脑 与应 用 ,1 99 9 ,15 (10 ) :1 1 — 13. [2] 张智江.IP P hone 技术及其应用.电信科 学 ,1999(1):15 — 1 7 . [3] 赵 慧玲 ,梁 勇,吴 广颖。IP 电话技 术综述。广东通 信技 术 ,199 9 (6) :1 7 — 19. [43 刘章庆 .IP 电话 — — 新一代 的语音 服务手段.电信 科学 , 】9 98 ( 】O ) 12 9 — 3 】. 欢 迤 订 量 .《电脑开发与应厕》厕刊 Y 维普资讯 http://www.cqvip.com

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 20 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档

相关文档