砝码称重问题的多种算法分析与探究.docVIP

许之民 ( 安徽师范大学 教育科学学院，安徽 芜湖 241000) 摘 要: 针对算法设计中的砝码称重问题，提出了四种不同的算法，重点从时间复杂度方面对各种算法进行了深 入的效率分析，并给出了各种算法的 pascal 主程序，对其他算法问题的分析解决具有重要的指导意义和实用价值． 关键词: 算法分析; 称重问题; 时间复杂度 中图分类号: 文献标识码: A 文章编号: 1673 － 162X( 2011) 01 － 0044 － 05 TP301 Analysis and Exploration of Various Algorithms of The Weight Problem XU Zhi-min ( College of Education Science，Anhui Normal University，Wuhu，Anhui 241000，China) Abstract: For the weight problem in algorithm design，the paper proposes four different algorithms which are analyzed in depth from the time complexity aspect，the pascal programs for each algorithm are also given． The paper has important guiding significance and practical value for other algorithmic problems． Key words: algorithm analysis; the weight problem; time complexity 计算机资源最重要的是运算所需的时间和存储程序及数据所需的空间资源． 对一个问题，一般存在多 种求解算法，可以根据算法所需要的时空资源来确定出其中有效的算法． ［1］随着计算机硬件技术的发展， 现在计算机的内存和硬盘空间基本上能满足问题的需要，即空间资源已经不是问题，因此，现在分析一个 算法主要考虑算法的计算时间． 本文主要从时间资源方面对砝码称重问题进行探究，涉及的算法有枚举 法、深度有哪些信誉好的足球投注网站、宽度有哪些信誉好的足球投注网站和动态规划等，通过多角度的分析和横向纵向的比较，对其他算法问题的求解具有 重要的指导意义和实用价值． 1 砝码称重问题的描述 对砝码称重问题模型的一般性研究有助于解决其他各种拓展出的问题，对算法设计、信息学奥赛和实 际生活中问题的解决都具有现实的意义． 例如，在信息学奥赛中，由砝码称重问题的简单模型往往可以拓 展出许多相关的问题模型，包括装箱问题、采药、开心的金明、货币系统、竞赛总分等． 砝码称重问题基本模 型描述如下: 设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚( 其总重≤1 000) ． 要求如下所述， 输入方式: a1 输出方式: N a6( 表示 1g 砝码有 a1 个，2g 砝码有 a2 个，…，20g 砝码有 a6 个) a2 a3 a4 a5 ( N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况) 0 0 0 0 如输入: 1 1 输出: 3( 表示可以称出 1g、2g、3g 三种不同的重量) 收稿日期: 2010 － 10 － 18 修回日期: 2011 － 01 － 10 2 砝码称重问题的算法解析 2． 1 枚举法 直接枚举 本题最直接的做法是枚举每一种砝码的个数，其主程序: 2． 1． 1 readln( a1，a2，a3，a4，a5，a6) ; fillchar( g，sizeof( g) ，0) ; for i: = 0 to a1 do for j: = 0 to a2 do for k: = 0 to a3 do for m: = 0 to a4 do for n: = 0 to a5 do for h: = 0 to a6 do begin sum: = i* 1 + j* 2 + k* 3 + m* 5 + n* 10 + h* 20; g［sum］: = g［sum］+ 1; end; / / 用数组计数 total: = 0; for i: = 1 to 1000 do if g［i］＜ ＞ 0 then total: = total + 1; writeln( total) ; 上述方法的缺点是循环的变量和循环的次数必须是确定的，当两者不确定的时候便不能用上述方法 求解，比如这题是 n 种砝码，要从键盘输入 n． 有没有其他方法呢? 优化枚举 先把题目改一下: 这 6 种砝码的个数都是