算法设计题集-read.pdf

法 设 计 题 集 第一章 算法初步 第一节 程序设计与算法 ．时间复杂度：在运行算法时所耗费的时 一、算法 间为f(n)(即 n 的函数)。 法是解决问题方法的精确描述，但是并 ．空间复杂度：实现算法所占用的空间为 不是所有问题都有 法，有些问题经研究可行， g(n) （也为n 的函数）。 则相应有 法，但这并不是说问题就有结果。 称O(f(n))和O (g(n))为该 法的复杂度。 上述的“可行”，是指对算法的研究。 １．待解问题的描述 二、程序设计 待解问题表述应精确、简练、清楚，使用 １．程序 形式化模型刻划问题是最恰当的。例如，使用 程序是对所要解决的问题的各个对象和处 数学模型刻划问题是最简明、严格的，一旦问 理规则的描述，或者说是数据结构和算法的描 题形式化了，就可依据相应严格的模型对问题 述，因此有人说，数据结构＋算法＝程序。 求解。 ２．程序设计 ２．算法设计 程序设计就是设计、编制和调试程序的过 法设计的任务是对各类具体问题设计良 程。 好的算法及研究设计 法的规律和方法。常用 ３．结构化程序设计 的算法有：穷举有哪些信誉好的足球投注网站法、递 法、回溯法、贪 结构化程序设计是利用逐步求精的方法， 心法、分治法等。 按一套程式化的设计准则进行程序的设计。由 ３．算法分析 这种方法产生的程序是结构良好的。所谓 “结 算法分析的任务是对设计出的每一个具体 构良好”是指： 的算法，利用数学工具，讨论各种复杂度，以 （１）易于保证和验证其正确性； 探讨某种具体算法适用于哪类问题，或某类问 （２）易于阅读、易于理解和易于维护。 题宜采用哪种算法。 按照这种方法或准则设计出来的程序称为 法的复杂度分时间复杂度和空间复杂 结构化的程序。 度。 “逐步求精”是对一个复杂问题，不是一步 就编成一个可执行的程序，而是分步进行。 数)、g （两数的最大公约数）。 ．第一步编出的程序最为抽象； 处理步骤：对m 从２到333 检查l 与g 的商 ．第二步编出的程序是 第一步所编的程 为120,且余数为0 时,打印m 与667-m 。 序（如过程、函数等）细化，较为抽象； 第一层抽象程序： ．…… Program TwoNum; ．第i 步编出的程序比第i-1 步抽象级要 Var m,l,g:integer; 低； Begin for m:=2 to 333 do ．…… begin l:=lcm(m,667-m); ｛求最小 ．直到最后，第n 步编出的程序即为可执 公倍数｝ 行的程序。