第4章-第1讲-迭代法、蛮力法_2

1、 计算机科学学院 王小明 （博士博士/ /教授教授/ /博士生导师博士生导师） Email: 每节一经典每节一经典用算法的视觉处理问题：用算法的视觉处理问题：有穷性，确定性，可行性，输入输出有穷性，确定性，可行性，输入输出迭代算法迭代算法迭代法迭代法(iteration): (iteration): 用变量的旧值不断递推出新值的解决用变量的旧值不断递推出新值的解决 问题的方法。通常用于数值计算。问题的方法。通常用于数值计算。例例4.1 S=04.1 S=0 i=1 i=1 FOR (i100;i+1) FOR (i100;i+1) S=S+i; S=S+i; 第4讲 基本算法策略例例4.24.

2、2 设方程为设方程为f(x)=0f(x)=0，用某种数学方法导出等价，用某种数学方法导出等价 的形式的形式x=g(x)x=g(x)，然后按以下步骤执行：，然后按以下步骤执行：Step 1 Step 1 选一个方程的近似根，赋给变量选一个方程的近似根，赋给变量x0 x0；Step 2 Step 2 将将x0 x0的值保存于变量的值保存于变量x1x1，然后计算，然后计算g(x1)g(x1)， 并将结果存于变量并将结果存于变量x0 x0； Step 3 Step 3 当当x0 x0与与x1x1的差的绝对值不小于指定的精度的差的绝对值不小于指定的精度 要求时，重复步骤（要求时，重复步骤（2 2）的计算

3、。）的计算。 即当即当x1-x0 x1-x0Epsilon) while ( fabs(x0-x1)Epsilon)； printf(“printf(“方程的近似根是方程的近似根是%fn”%fn”，x0)x0)； 第4讲 基本算法策略具体使用迭代法求根时应注意以下两种可能发生的情况具体使用迭代法求根时应注意以下两种可能发生的情况:（1）如果方程无解，算法求出的近似根序列）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；并在程序

4、中对迭代的次数给予限制；（2）方程虽然有解，但迭代公式选择不当，或）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭迭代的初始近似根选择不合理，也会导致迭代失败。代失败。 第4讲 基本算法策略（1）递推法递推法迭代法迭代法 倒推法倒推法 第4讲 基本算法策略1 1）递推法）递推法 递推法是利用问题本身所具有的一种递推关系求问题解的一递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。种方法。 例如，求解规模为例如，求解规模为n n的问题，当的问题，当n=1n=1时，解或为已知，或能非时，解或为已知，或能非常方便地得到。能采用递推法构造算法的问题具有重要的递推常

5、方便地得到。能采用递推法构造算法的问题具有重要的递推性质，即当得到问题规模为性质，即当得到问题规模为i-1i-1的解后，由问题的递推性质，能的解后，由问题的递推性质，能从已求得的规模为从已求得的规模为1 1，2 2，i-1i-1的一系列解，构造出问题规模的一系列解，构造出问题规模为为i i的解。这样，程序可从的解。这样，程序可从i=0i=0或或i=1i=1出发，重复地，由已知至出发，重复地，由已知至i-i-1 1规模的解，通过递推，获得规模为规模的解，通过递推，获得规模为i i的解，直至得到规模为的解，直至得到规模为n n的的解。解。 第4讲 基本算法策略例例4.24.2 main() mai

6、n() int i,a=1,b=1;int i,a=1,b=1; print(a,b); print(a,b); for(i=1;i=5;i=i+1) for(i=1;i=1;i=i-1) for (i=9;i=1;i=i-1) a=2 a=2* *( (a a+1)+1) print(a); print(a); 第4讲 基本算法策略 课外习题：课外习题： p128,p128,例例5 5：穿越沙漠问题：穿越沙漠问题第4讲 基本算法策略 迭代法解方程：迭代法解方程： 阅读阅读p130-133,p130-133,例例6 6，例，例7 7，例，例8 8第4讲 基本算法策略 作业：作业： 预习预习p1

7、33-138: p133-138: 蛮力法蛮力法第4讲 基本算法策略Thats all for todayThats all for todaySee you next timeSee you next timeGood bye! Good bye! 计算机科学学院 王小明 （博士博士/ /教授教授/ /博士生导师博士生导师） Email: 每节一经典每节一经典用用9 9以内的实例理解问题：以内的实例理解问题：手工模拟计算过程手工模拟计算过程 蛮力法蛮力法：把问题的所有情况或所有过程交给计算：把问题的所有情况或所有过程交给计算 机去一一尝试，从中找出问题的解。机去一一尝试，从中找出问题的解。例

8、例4.4 4.4 顺序查找，选择排序，冒泡排序，插入排顺序查找，选择排序，冒泡排序，插入排序等等。序等等。 从序列从序列 2 2，5 5，8 8，9 9，1212，1717中查找中查找2323，需要从，需要从第一个数第一个数2 2开始，逐一向后查，直到末尾数开始，逐一向后查，直到末尾数1717，才断定此序列中没有这个数。才断定此序列中没有这个数。 第4讲 蛮力法 枚举法枚举法(enumerate)(enumerate)：蛮力策略的一种具体表现形式。根据问题：蛮力策略的一种具体表现形式。根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足中的条件将可能的情况一一列举出来，逐一尝试从中找

9、出满足问题条件的解。问题条件的解。 缺点：当问题情况数目太多时，太费时间。缺点：当问题情况数目太多时，太费时间。 改进策略：忽略一些明显不可能的情况，以减少列举的可能解改进策略：忽略一些明显不可能的情况，以减少列举的可能解数目。数目。 方法：方法：1 1）找出枚举范围：分析问题各种情况。）找出枚举范围：分析问题各种情况。 2 2）找出约束条件：分析问题的解需要满足的条件，并用）找出约束条件：分析问题的解需要满足的条件，并用 逻辑表达式表示。逻辑表达式表示。 第4讲 蛮力法 例例4.54.5 百钱百鸡问题。如何用百钱百鸡问题。如何用100100元买元买100100只鸡？只鸡？ 鸡翁鸡翁1 1，值

10、钱，值钱5 5，鸡母，鸡母1 1，值钱，值钱3 3，鸡仔，鸡仔3 3，值钱，值钱1 1。问题分析：问题分析：用用100100元恰好买元恰好买100100只鸡；设只鸡；设x,y,zx,y,z表示公鸡、母鸡、鸡表示公鸡、母鸡、鸡 仔数量。仔数量。数学模型：数学模型：1 1）枚举范围：）枚举范围：0 x100/5; 0 x100/5; 0y100/3; 0y100/3; 0z3 0z3* *100;100;2) 2) 约束条件：约束条件：x+y+z=100;x+y+z=100; 5x+3y+z/3=100 5x+3y+z/3=100 第4讲 蛮力法计算模型计算模型: : （试探法，即枚举法）（试探法

11、，即枚举法）0=x=100/5; 0=x=100/5; 0=y=100/3; 0=y=100/3; 0=z=3 0=z=3* *100;100; 如果如果 x+y+z=100 x+y+z=100并且并且 5x+3y+z/3=1005x+3y+z/3=100 那么那么 此时的此时的x,y,zx,y,z值正好是问题答案值正好是问题答案 否则否则 继续试探。继续试探。 第4讲 蛮力法 算法描述算法描述(3(3重循环重循环) )：main()main() int x,y,z; int x,y,z; for(x=0;x=20 for(x=0;x=20；x=x+1)x=x+1) for(y=0;y=33;

12、y=y+1) for(y=0;y=33;y=y+1) for(z=0;z=300;z=z+1) for(z=0;z=300;z=z+1) if x+y+z=100 and 5 if x+y+z=100 and 5* *x+3x+3* *y+z/3=100y+z/3=100 print(x,y,z) print(x,y,z) 第4讲 蛮力法 算法分析算法分析：上述算法共枚举尝试：上述算法共枚举尝试2020* *3333* *300=198000300=198000次次缺点：缺点：时间效率低时间效率低改进策略：改进策略：1 1）当公鸡和母鸡数量确定之后，小鸡数量为）当公鸡和母鸡数量确定之后，小鸡数

13、量为 100-x-y, 100-x-y,不需要对小鸡数量进行枚举。不需要对小鸡数量进行枚举。 2 2）只有当）只有当z z值被值被3 3整除时，解才可能有意义。整除时，解才可能有意义。 约束条件：约束条件：z z modmod 3=0; 5x+3y+z/3=100 3=0; 5x+3y+z/3=100 第4讲 蛮力法 优化算法（优化算法（3 3重循环变重循环变2 2重循环）重循环）：main()main() int x,y,z; int x,y,z; for(x=0;x=20 for(x=0;x=20；x=x+1)x=x+1) for(y=0;y=33;y=y+1) for(y=0;y=33;

14、y=y+1) if z if z modmod 3=0 and 5 3=0 and 5* *x+3x+3* *y+z/3=100y+z/3=100 print(x,y,z) print(x,y,z) 第4讲 蛮力法 算法分析：算法分析：上述算法共枚举尝试上述算法共枚举尝试2020* *33=66033=660次次 优点：优点：时间效率高（和第一个算法相比）时间效率高（和第一个算法相比）思考与实践验证问题：思考与实践验证问题：1 1）如果把上述算法中的循环顺序）如果把上述算法中的循环顺序 改变，结果一样吗？改变，结果一样吗？ 2 2）如果把上述算法中的循环顺序）如果把上述算法中的循环顺序 改变，

15、共枚举的次数是否相同？改变，共枚举的次数是否相同？课堂练习课堂练习：P134,P134,例例1010。 第4讲 蛮力法 例例1212 狱吏问题：谁能从监狱获得自由？狱吏问题：谁能从监狱获得自由？ 国王对囚犯进行大赦，游戏规则是：让一个狱吏国王对囚犯进行大赦，游戏规则是：让一个狱吏n n次通过一排锁次通过一排锁着的牢房，每通过一次，按规则转动着的牢房，每通过一次，按规则转动n n间牢房中某些门锁，每转间牢房中某些门锁，每转一次，原来锁着的被打开，原来开着的被锁上；通过一次，原来锁着的被打开，原来开着的被锁上；通过n n次后，门次后，门锁开着的牢房中的犯人获得释放。锁开着的牢房中的犯人获得释放。规

16、则：规则：1 1）第一次通过时：每间房门锁被打开；）第一次通过时：每间房门锁被打开； 2 2）第二次通过时：从第二间开始转动，每隔）第二次通过时：从第二间开始转动，每隔1 1间转动一次间转动一次 3) 3) 第三次通过时：从第三间开始转动，每隔第三次通过时：从第三间开始转动，每隔2 2间转动一次间转动一次 k) k) 第第k k次通过时：从第次通过时：从第k k间开始转动，每隔间开始转动，每隔k-1k-1间转动一次间转动一次 第4讲 蛮力法 在在“9”9”以内理解以内理解狱吏问题：以狱吏问题：以6 6个牢房为例。个牢房为例。145632牢房 Y Y Y Y Y Y Y X Y X Y X Y

17、X X X Y Y Y X X Y Y Y Y X X Y X Y Y X X Y Y X X X X X X X 问题分析：第问题分析：第1 1次转动门锁房号：次转动门锁房号：1 1，2 2，,n,n 第第2 2次转动门锁房号：次转动门锁房号：2 2，4,6,4,6, 第第3 3次转动门锁房号：次转动门锁房号：3 3，6,9,6,9, 第第i i次转动门锁房号：次转动门锁房号：i i，2i2i，3i,3i, 即：它们是起点为即：它们是起点为i,i,公差为公差为i i的等差数列。的等差数列。 最后一次只转动第最后一次只转动第n n号门锁一次。号门锁一次。算法设计思想：算法设计思想：1 1）数组

18、元素）数组元素ai(i=1,2,n)ai(i=1,2,n)的初值均的初值均 （计算模型）（计算模型） 为为1 1表示所有门锁着，门号与锁号相表示所有门锁着，门号与锁号相 同。同。ajaj为为0 0时表示锁号为时表示锁号为j j的锁锁着。的锁锁着。 2 2）当第）当第j j号门锁被转动时，号门锁被转动时，aj=1-ajaj=1-aj 3) 3) 每趟用每趟用i i表示，表示，1=i=n1=i=n 4) 4) 每趟从第每趟从第j j个（个（j=ij=i）锁开起，每隔）锁开起，每隔i i个个 锁转动一次，表示为锁转动一次，表示为j=j+i,i=j=nj=j+i,i=j=n例如例如，当，当aj=1aj

19、=1时，则时，则aj=1-aj=1-1=0aj=1-aj=1-1=0； 当当aj=0aj=0时，则时，则aj=1-aj=1-0=1aj=1-aj=1-0=1算法设计算法设计: : ( (共三个阶段：初始阶段，反复开共三个阶段：初始阶段，反复开- -关锁阶段，放人判定哪些锁开着关锁阶段，放人判定哪些锁开着) )Main()Main() int int * *a,I,j,n;a,I,j,n; input(n); input(n); a=calloc(n+1,sizeof (int); a=calloc(n+1,sizeof (int); for(i=1;i=n;i=i+1)for(i=1;i=n;

20、i=i+1) ai=1; ai=1; for(i=1;i=n;i=i+1)for(i=1;i=n;i=i+1) for(j=i;j=n;j=j+i) for(j=i;j=n;j=j+i) aj=1-aj; aj=1-aj; for(i=1;i=n;i=i+1)for(i=1;i=n;i=i+1) if (ai=0) if (ai=0) print(i,”is free”); print(i,”is free”); 初始化，给数组初始化，给数组a分分配配n+1个内存空间个内存空间使使n个门锁标志全为个门锁标志全为1，表示门都锁着表示门都锁着狱吏走狱吏走n趟，每趟用趟，每趟用i标记，标记，每趟转动

21、的门锁号用每趟转动的门锁号用j表示表示输出锁开着的牢房号（锁号）输出锁开着的牢房号（锁号）算法分析算法分析：1)1)仔细分析算法可以看出，模拟狱吏开锁的仔细分析算法可以看出，模拟狱吏开锁的 语句语句aj=1-ajaj=1-aj是关键语句，所以选择该是关键语句，所以选择该 语句执行的总次数衡量算法复杂度。语句执行的总次数衡量算法复杂度。 该语句执行的总次数为：该语句执行的总次数为： f(n)=n+n/2+n/3+1 f(n)=n+n/2+n/3+1 则时间复杂度为则时间复杂度为O(nlongO(nlongn n) ) 2)2)共用了共用了n+1n+1个数组空间，所以空间复杂度为个数组空间，所以空

22、间复杂度为 S(n)=S(n+1)=S(n), S(n)=S(n+1)=S(n),表示随着问题规模表示随着问题规模n n的增大，算法的增大，算法执行所需存储空间的增长率与执行所需存储空间的增长率与n n的增长率相同的增长率相同. .课堂练习课堂练习：阅读理解算法：阅读理解算法2 2和算法和算法3 3算法算法2 2关键点关键点：求一个数的不同的因数个数：求一个数的不同的因数个数算法思想算法思想：第：第1 1次被转动门锁的编号是次被转动门锁的编号是1 1的倍数；的倍数； 第第2 2次被转动门锁的编号是次被转动门锁的编号是2 2的倍数；的倍数； 第第3 3次被转动门锁的编号是次被转动门锁的编号是3

23、3的倍数；的倍数； 第第i i次被转动门锁的编号是次被转动门锁的编号是i i的倍数；的倍数；总结上述规律总结上述规律：狱吏问题转化为数的因子个数问题狱吏问题转化为数的因子个数问题用用n n表示数，用表示数，用d(n)d(n)表示表示n n的因子个数的因子个数例如：例如： n 1 2 3 4 5 6 n 1 2 3 4 5 6 因数因数 11 1,21,2 1,31,3 1,2,41,2,4 1,51,51,2,3,61,2,3,6 d(n) 1 2 2 3 2 4 d(n) 1 2 2 3 2 4 建立数学模型：由于牢房开始是关闭着的，所以如果建立数学模型：由于牢房开始是关闭着的，所以如果d(

24、i)d(i)是奇数，则编号为是奇数，则编号为i i的牢房最后是开着的。的牢房最后是开着的。看下页图来初步验证数学模型的正确性。看下页图来初步验证数学模型的正确性。 在在“9”9”以内理解以内理解狱吏问题：以狱吏问题：以6 6牢房为例。牢房为例。145632牢房 Y Y Y Y Y Y Y X Y X Y X Y X X X Y Y Y X X Y Y Y Y X X Y X Y Y X X Y Y X X X X X X X 算法算法2 2：Main2()Main2() int s,I,j,n;int s,I,j,n; input(n); input(n); for(i=1;i=n;i=i+1

25、) for(i=1;i=n;i=i+1) s=1; s=1; for(j=2;j=i;j=j+1) for(j=2;j=i;j=j+1) if(i mod j)=0; if(i mod j)=0; s=s+1; s=s+1; if(s mod 2=1) if(s mod 2=1) print(i,”is free”); print(i,”is free”); 用枚举法（蛮力法）用枚举法（蛮力法）求求i的因子个数的因子个数输出锁开着的牢房号（锁号）输出锁开着的牢房号（锁号）1是每个数的因子，因此每个数至少有一个因子，是每个数的因子，因此每个数至少有一个因子，s表示表示i的因子个数的因子个数算法算法2 2：Main2()Main2() int s,I,j,n;int s,I,j,n; input(n); input(n); for(i=1;i=n;i=i+1) for(i=1;i=n;i=i+1) s=1; s=1; for(j=2;j=i;j=j+1) for(j=2;j=i;j=j+1) if(i mod j)=0; if(i mod j)=0; s=s+1; s=s+1; if(s mod 2=1) if(s mod 2=1) print(i,”is free”); print(i,”is free”); 时间复杂度：执行频次最高的语句是时间复杂度：