算法设计与分析-迭代法1

算法设计与分析

DesignandAnalysisofAlgorithms122023/11/21第三章迭代法主要内容3==简单地迭代运算==迭代（辗转法） 是一种不断用变量地旧值递推新值地过程分类精确迭代 杨辉三角,内存移动算法等近似迭代二分法与牛顿迭代法等设计方法确定迭代模型控制迭代过程2023/11/214例三-一输出如图所示地杨辉三角形。一一一一二一一三三一一四六四一……………(一)杨辉三角形一一一一二一一三三一一

四六四一……………(二)杨辉三角形存储格式问题分析存储:A[n,n]矩阵矩阵:A={a零,零,a一,零,a一,一,…,ai,零,…,ai,i,…,an-一,n-一}元素之间地关系:ai,j=ai-一,j-一+ai-一,j==简单地迭代运算==2023/11/215例三-一输出如图所示地杨辉三角形。==简单地迭代运算==一一一一二一一三三一一

四六四一……………(二)杨辉三角形存储格式算法设计与描述输入:n输出:杨辉三角Yanghui(n){a[零,零]一,a[一,零]一,a[一,一]一;fori二ton-一do{a[i,零]一;a[i,i]一;forj一toi-一doa[i,j]a[i-一,j-一]+a[i-一,j];}output(a);}算法分析(一)输入n,规模为n(二)核心操作:a[i,j]a[i-一,j-一]+a[i-一,j]地加法运算及两边地值;(三)依据定理二.五算法地时间复杂度为T(n)==Θ(n二)2023/11/216一一一一二一一三三一一

四六四一……………杨辉三角与斐波那契数列F(零)=一F(一)=一F(二)=二F(三)=三F(四)=五==简单地迭代运算==关于杨辉三角靓丽地Fibonacciai/ai-一2023/11/217==简单地迭代运算==靓丽地Fibonacci2023/11/218例三-二穿越沙漠问题问题分析==简单地迭代运算==用一辆吉普车穿越一零零零公里地沙漠。吉普车地总装油量为五零零升,耗油率为一升/公里。由于沙漠没有油库,需要先用这辆车在沙漠建立临时油库。该吉普车以最少地耗油量穿越沙漠,应在什么地方建油库,以及各处地贮油量。?km终点?L起点五零零km五零零L第一加油站一零零零L五零零/三km第二加油站一五零零L五零零/五km第三加油站2023/11/219例三-二穿越沙漠问题问题分析==简单地迭代运算==计算模型设起点到终点距离为distance,终点到加油站地距离为dis,加油站地油量为oil,加油站编号为n,计算模型如下:?km终点?L起点五零零km五零零L第一加油站一零零零L五零零/三km第二加油站一五零零L五零零/五km第三加油站2023/11/2110例三-二穿越沙漠问题==简单地迭代运算==算法分析问题规模:distance与n核心语句:求加油站距离,规律如下:五零零+五零零/三+五零零/五+……+五零零/二*n-一=distance可得如下公式:

===O(logn)2023/11/2111==简单地迭代运算==思考题: 猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个,第二天早上又将剩下地桃子吃掉一半,又多吃了一个。以后每天早上都吃前一天剩下地一半零一个。到第一零天早上想再吃时,见只剩下一个桃子了。求第一天摘多少个桃子2023/11/2112例三-三内存移动问题问题分析建立存原序列地数组a[n]与移位后数列b[n],b[(k+i)modn]=a[i],i∈[零,n-一]时间渐近复杂度O(n),空间渐近复杂度O(二*n)(二)建立存原序列地数组a[n]与临时变量tmp,令tmp=a[n-一]a[n-一]=a[n-二]a[n-i]=a[n-i-一],i∈[一,n-一]时间渐近复杂度O(k*n),空间渐近复杂度O(n+一)=O(n)==简单地迭代运算==数组有n个数据,要将它们顺序循环向后移k位,即前面地元素向后(右)移k位,后面地元素则循环向前移k位,例:零,一,二,三,四,五循环移三位后为:三,四,五,零,一,二。考虑到n会很大,不允许用二*n及以上个空间来完成此题。2023/11/2113例三-三内存移动问题问题分析若n=五,k=三时,零,一,二,三,四移动三位后为二,三,四,零,一,一轮移动恰好完任务（零三一四二零）。若n=六,k=三时,零,一,二,三,四,五移动三位后为三,四,五,零,一,二,用三轮移动完任务（零三零,一四一,二五二）。==简单地迭代运算==数组有n个数据,要将它们顺序循环向后移k位,即前面地元素向后(右)移k位,后面地元素则循环向前移k位xi=(i+k)modn（三-一）移动地轮数:n与k地最大公约数Q每轮移动地元素数量:n/Q2023/11/2114例三-三内存移动问题设数列元素个数为n,向右移动次数为k,位置编号为零,一,二,…,i,…,n-一。则按照式(三-一)计算位置:Loc一:x一=(x零+k)modn,设商为y零,x一=k+x零-n*y零;Loc二:x二=(x一+k)modn,设商为y一,x二=二*k+x零-n*(y零+y一);……按上述规律,可得下式:xi=(x零+i*k-n*(y零+y一+…+yi-一))modn(三-二)由式(三-二)得xi=(x零+i*k)modn设第i次连续移动后,回到初始位置,则有必有xi=(x零+i*k)modn=x零(三-三)设第p轮连续移动地起始位置为xp,则有:xi=(xp+i*k)modn=xp(三-四)==简单地迭代运算==必有:i*kmodn=零成立实践经验告诉我们,不一定要移动完成2023/11/2115例三-三内存移动问题==简单地迭代运算==因有:i*kmodn=零成立可设:i*k/n=yi*k=n*y设k与n地最大公约数Q,则有k=a*Q,n=b*Q,可得k/n=y/i=a*Q/b*Q=a/b,a,b互质。i为最小移动次数,必满足i=b。∴n=i*Q∴i=n/Q计算模型(一)求最大公约数—欧几里得定理,当r≠零时,有

(二)令q=b,移动次数:i=n/q(三)计算元素移动位置:m=(m+k)modn2023/11/2116例三-三内存移动问题==简单地迭代运算==xp=(xp-一+i*k)modn算法地改观察实例n=六,k=三,第一轮循环为零-三-零,执行过程为:tmp零,m零;i零,m三,s三,a[三]零,tmp三;i一,m零,s零,a[零]三,tmp零。2023/11/2117例三-三内存移动问题==简单地迭代运算==jn/q-一;p一(i+j*k)modn;tmpa[p一];for(jj-一;j>=零;j--){p二(i+j*k)modn;a[p一]=a[p二];p一=p二;}a[p二]=tmp;改后地实例执行过程为:i一,p一三,tmp三;i零,p二零,a[三]零;a[零]三。算法地改未改为:tmp零,m零;i零,m三,s三,a[三]零,tmp三;i一,m零,s零,a[零]三,tmp零。2023/11/2118==简单地迭代运算==思考题:数组有n个数据,要将它们顺序循环向前移k位,即后面地元素向前(左)移k位,前面地元素则循环向后移k位,例:零,一,二,三,四,五循环移二位后为:二,三,四,五,零,一。考虑到n会很大,不允许用二*n及以上个空间来完成此题。2023/11/2119例三-四编程求当n<=一零零时,n！地准确值。==简单地迭代运算==问题分析基本数据类型 整型数据:-三二七六八——三二七六七 长整型:-二一四七四八三六四八——二一四七四八三六四七 单精度:六位精度,±(三.四e-三八~三.四e+三八) 双精度:一七位精确度,±(一.七e-三零八~一.七e+三零八)不够大,不精确设计要点:(一)存储:可用整数或字符类型地数组,每个元素一到若干位(二)数组长度:由式log(n!)=Θ(nlogn)确定。如每个元素存储存六位整数,log(n!)=一零零log(一零零)/六≈三四（一零零！有二七位）(三)计算:模拟竖式乘法三.二算法与数据结构2023/11/21例三-四编程求当N<=一零零时,N！地准确值实例分析九！=三六二八八零一零零！=九三三二六二一五四四三九四四一五二六八一六九九二六三八五六二六六七零零四九零七一五九六八二六四三八一六二一四六八 五九二九六三八九五二一七五九九九九三二二九九一五六零八九一四 四六三九七六一五六五七八二八六二五三六九七九二零八二七二二三 七五八二五一一八五二一零九一六八六四零零零零零零零零零零零零零零零零零零零零零零零零==简单地迭代运算==三.二算法与数据结构2023/11/21例三-四编程求当N<=一零零时,N！地准确值竖式乘法原理--实例分析零八六一九六零a[零]*一一bb%一零六a[零]=九一六八零零b/一零六d=六a[零]a[一]一零!零八八二六三零一一×ia[一]*一一+d九三b==简单地迭代运算==三.二算法与数据结构2023/11/21竖式乘法原理--实例分析b%一零六a[零]=八三二零零零b/一零六d=一三a[零]一八!零零八二七a[一]五零七三七三零b=a[j]×i+d;a[j]=b%一零六;d=b/一零六;一九×i零四六二a[二]a[零]*一九b零零二三八三零一七一零零三九五a[一]五零七三七三一九×+d=一三ba[一]零零零零零零？六四零二零零零零零零七二八零零零六四零二零七二八零零零==简单地迭代运算==三.二算法与数据结构2023/11/21==简单地迭代运算==计算模型设存储大数结果地数组为a[