《算法讲义：过程抽象》由会员分享，可在线阅读，更多相关《算法讲义：过程抽象（46页珍藏版）》请在金锄头文库上搜索。
1、问题求解与程序设计 第二讲,李文新 2005.2-6,课程网页及上机安排,http:/ 上机安排 周六？日 上午：8-10 10-12 ？ 分班,内容提要,1014题 一些观点和理念 递归过程 例题：采用牛顿法求平方根 练习：采用牛顿法求立方根 过程和它们所产生的计算 线性的递归和迭代 树形递归 练习：换零钱方式的统计 讨论：1163 讨论：1037,关于1014题,证明的总体思想 当某种价值k的珠宝的数目n足够多时，如果可分，一定可以找到一种分法，使得两边都有k，那么两边各去掉一个k，还是可分的。 即 如果其他价值的珠宝数目不变，如果价值为k的珠宝个数为n-2时可分，则为n时也可分；如果n-
2、2时不可分，则为n时也不可分； 如此 n-2 再 2，直到n不足够大，这些情况都是等价的。所以数目大时可以将其变小，结果不变。,关于1014题,需要注意的是，每次只能减少偶数个，所以简化以后，n的奇偶性不变。； 至于为什么一定可以找到两边都有价值k的分法，有定理帮我们找： 如果只有一边有价值k的珠宝，则一定可以找到另一边的某些珠宝的一种组合，其和十k的倍数m，此时就可以用另一边的组合换过m个k来，使得两边都有k， 为什么右边一定有足够多的珠宝能组合出mk来？因为我们在说n足够大的情况，如果它不足够大，我们就不要再把它缩小了，,关于1014题,足够大是如何丈量的？另一边有多于k块珠宝，就一定能组
3、合出k的倍数来，不论这些珠宝的价值如何。 如何组合？假设k块珠宝的价值分别为a1,ak，考虑序列：0,a1,a1+a2,a1+a2+a3,a1+ak,用这k+1个数模k,所的余数必定有两个相同，用后面一个减前面一个，得到的仍是a1,ak中某几个数的组合，而这个数模k等于0，这个组合就是我们要找的，与mk交换的珠宝。 这里a1,ak可以相同，也可以不同。,一些观点和理念,“计算机科学”并不是一种科学，而且其重要性也与计算机本身并无太大关系。计算机革命是有关我们如何去思考的方式，以及我们如何去表达自己的思考的一个革命。在这个变化里最基本的东西，就是出现了这样一种或许是最好是称为过程性认识论的现象
4、这就是如何从一种命令式的观点去研究知识的结构，这一观点是与经典数学领域中所采用的更具说明性的观点完全不同的。数学为精确处理“是什么”提供了一种框架，而计算则为精确处理“怎么做”的概念提供了一种框架。,一些观点和理念,心智的活动，除了尽力产生各种简单的认识之外，主要表现在如下三个方面：1）将若干简单认识组合为一个复合认识，由此产生出各种复杂的认识。2）将两个认识放在一起对照，不管它们如何简单或者复杂，在这样做时并不将它们合而为一。由此得到有关它们的相互关系的认识。3）将有关认识与那些在实际中和它们同在的所有其他认识隔离开，这就是抽象，所有具有普遍性的认识都是这样得到的。,一些观点和理念,一个强有
5、力的程序设计语言，不仅是一种指挥计算机执行任务的方式，它还应该成为一种框架，使我们能够在其中组织自己有关计算过程的思想。这样，当我们描述一个语言时，就需要将注意力特别放在这一语言所提供的，能够将简单的认识组合起来形成更复杂认识的方法方面。,一些观点和理念,每种强有力的语言都为此提供了三种机制： 基本表达形式，用于表示语言所关心的最简单的个体。 组合的方法，通过它们可以从较简单的东西出发构造出复合的元素。 抽象的方法，通过它们可以为复合对象命名，并将它们当作单元去操作。,一些观点和理念,在程序设计中，我们需要处理两类要素：过程和数据（二者不是严格区分的）。非形式地说，数据是一种我们希望去操作的“
6、东西”，而过程就是有关操作这些数据的规则的描述。这样，任何强有力的程序设计语言都必须能表述基本的数据和基本的过程，还需要提供对过程和数据进行组合和抽象的方法。,例题：采用牛顿法求平方根,给定一个正数x，如何计算x的平方根呢？ 牛顿的逐步逼近法 对于x的平方根，给定一个猜测值y，则y与x/y的平均值是比y更好的一个猜测值，继续这一过程，会得到越来越好的猜测值。,例题：采用牛顿法求平方根,如何用过程语言表述这一计算过程？ 初始条件：给定 x 和 猜测值 guess sqrt(guess,x) if(goodEnough(guess,x) return guess; return sqrt(impr
7、ove(guess,x),x); goodEnough(guess,x) if(abs(guess*guess-x) n) fact-iter(1,2,6) return product; fact-iter(2,3,6) fact-iter(product*counter, fact-iter(6,4,6) counter+,n); fact-iter(24,5,6) fact-iter(120,6,6) fact-iter(720,7,6),线性的递归和迭代,计算步骤与n成正比 线性 递归计算 保留计算链 迭代计算 无需保留计算链，保留有限状态,树形递归,Fibonacci数列 0，1，1
8、，f(n-1)+f(n-2),f(n)if(n=0 | n=1) return n;return f(n-1)+f(n-2);,树形递归,f(5),f(3),f(2),f(1),f(2),f(4),f(0),f(1),f(0),f(3),f(2),f(1),f(1),f(0),f(1),1,1,0,0,1,0,1,0,冗余计算,迭代,fib(n) fib-iter(1,0,n); /n=1实际求第3项 fib-iter(a,b,count)if(count = 0) return b;return fib-iter(a+b,a,count-); ,练习：换零钱方式的统计,给了半美元、四分之一美
9、元、10美分、5美分和1美分的硬币，将1美元换成零钱一共有多少种不同的方式？更一般的问题是，给定任意数量的现金，我们能写出一个程序，计算出所有换零钱方式的总数吗？,练习：换零钱方式的统计,count-change(amount)cc(amount,5); cc(amount,kinds-of-coins)if(amount = 0) return 1;if(amount0 | kinds-of-coins=0) return 0;return cc(amount, kinds-of-coins 1)+ cc(amount first-denomination(kinds-of- coins),
10、 kinds-of-coins); ,练习：换零钱方式的统计,first-denomination(kinds-of-coins)swicth(kinds-of-coins)1: return 1;2: return 5;3: return 10;4: return 25;5: return 50; ,讨论 1163,求三角形从顶到底的最大和，每次向下或右下累加 Sample Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30,讨论 1037,问题,A decorative fence 1037,问题的出处,中欧信息学奥林匹克竞赛200
11、2年6月30日-7月6日 第一天: fence A decorative fence 时限: 1 s 内存: 1 MB,问题描述,漂亮的篱笆定义如下： 篱笆由宽度相同，高度互不相同的木条组成 组成篱笆的木条高低相间，错落有致 篱笆的长度定义为组成篱笆的木条数目N，其中木条的高度取值（不按排列顺序）分别为1，2，N。 把篱笆按其木条高度顺序记为：a1a2aN，则可以对篱笆进行字典排序，例如：,问题描述,长度为 4 的漂亮篱笆排序为：,1 2 3 4 5 6 7 8 9 10,问题描述,给定篱笆长度N和在该长度下的序号C，要求给出第C种漂亮篱笆的形状。,问题描述,样例输入： 2 2 1 3 3 样
12、例输出： 1 2 2 3 1,样例解释,1,2,1,2,1,3,2,1,3,2,1,3,2,1,3,2,问题解答,问题分析 对于长度为N的漂亮篱笆，其序列为： 以高度为1的木条开始的上升序列 以高度为2的木条开始的下降序列 以高度为2的木条开始的上升序列 以高度为3的木条开始的下降序列 以高度为3的木条开始的上升序列 ,问题解答,问题分析 如果能够确定上述每一种序列的个数，就可以确定数字C落在哪个区间，从而确定其第一个木条的高度；则此时问题简化成N-1规模的问题，依照同样的方法可以确定第2个木条的高度，以此类推，可以确定所有木条的高度。,问题解答,递推公式 令 表示长度为N的漂亮篱笆中以高度为
13、i的木条开始，呈下降趋势的篱笆的个数； 令 表示长度为N的漂亮篱笆中以高度为i的木条开始，呈上升趋势的篱笆的个数； 则有公式：,问题解答,（1）（2）（3）,公式解释,公式（1）：以1开始的下降序列为0个 公式（2）：可以由下降序列的个数推出上升序列的个数，如下图：,公式解释,i,x1,x2,x3,x4,x5,x6,x7,N+1,N-i+1,i,i,i,i,i,i,i,N-i+1,公式解释,公式（3）：在以j+1开始的下降序列中，第2个木条的可能取值是1,j;以它开始的序列是上升序列，如下图：,公式解释,j+1,1,2,j,going down,going up,问题解答,根据递推公式可以生成两个数组up和down数组，如下：,up,down,N=1 N=2 N=3 N=4 N=1 N=2 N=3 N=4,
