计算理论与算法分析设计：倒推法

倒推法

11/6/20221例楼梯上有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编写算法计算共有多少种不同的上楼梯方法。只有两种情况：

1）

从第n-1阶到第n阶；

2）

从第n-2阶到第n阶。记n阶台阶的走法数为f(n)，则

f(n)=1n=1

f(n)=2

n=2

f(n)=f(n-1)+f(n-2)n>211/6/20222main(){intn:;print('n=');input(n);print('f(',n,')=',f(n));}f(intx){if(x=1)

return(1);if(x=2)return(2);else

return(f(x-1)+f(x-2));}11/6/20223例：有两条完全相同的蚊香，每个可以点一个小时，问怎样量出45分钟？11/6/20224有一位探险家用5天的时间徒步横穿A、B两村，两村间是荒无人烟的沙漠，如果一个人只能担负3天的食物和水，那么这个探险家至少雇几个人才能顺利通过沙漠。

11/6/20225

A城雇用一人与探险家同带3天食物同行一天，然后被雇人带一天食物返回，并留一天食物给探险家，这样探险家正好有3天的食物继续前行，并于第三天打电话雇B城人带3天食物出发，第四天会面他们会面，探险家得到一天的食物赴B城。

11/6/20226随机化算法11/6/20227定义：在算法中引入随机因素,即通过随机数选择算法的下一步操作。特点：简单、快速一种平衡：随机算法可以理解为在时间、空间和随机三大计算资源中的平衡11/6/20228计算机产生随机数的方法d0=d

dn=bdn-1+c

an=dn%6553611/6/20229计算机产生随机数的方法unsignedintseed;

scanf("%d",&seed);

srand(seed);

for(i=0;i<MAX;i++){

printf("%d",rand()%10+1);}11/6/202210计算机产生随机数的方法srand((unsigned)time(0));

for(inti=0;i<MAX;i++){

printf("%d",rand()%10+1);}11/6/2022111、数值概率算法：用于数值问题的求解2、Sherwood算法一定能得到问题的正确解常见的四类随机算法：11/6/2022123、LasVegas算法或者得到正确的解，或者得不到解。4、MonteCarlo算法一定能得到解，但是得到的解可能不正确，然而这种概率是小的且有界的。常见的四类随机算法：11/6/202213数值概率算法11/6/202214用随机投点法计算值设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为。所以当n足够大时，k与n之比就逼近这一概率。从而。publicstaticdoubledarts(intn){//用随机投点法计算值

intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if((x*x+y*y)<=1)k++;}return4*k/(double)n;}11/6/202215举例:QuickSort传统的快排序算法

-总是取第一个元素作为划分元；

-算法的最坏运行时间是O(n2)，平均时间是O(nlogn)；-因此存在一些输入实例，使得算法达到最长运行时间，如：降序的序列；随机快排序算法

-随机选择一个元素作为划分元；

-任何一个输入的期望时间是O(nlogn)；-是一个舍伍德算法；11/6/202216举例:八后问题对于大部分解，八后的位置并不具有系统性-因此可以随机地把它们放在连续的行上，只要注意不要互相威胁。但是可能会失败。解决方案：随机+回溯11/6/202217主元素问题设T[1…n]是一个含有n个元素的数组。当|{i|{T[i]=x}}|>n/2时，称元素x为数组T的主元素。

majority(int

t[],intn){

随机产生整数i；

intx=t[i];

intk=0;

for(intj=1;j<=n;j++)

if(t[j]==x)k++;

return(k>n/2);}

11/6/202218主元素问题majority2返回true的概率是p+(1-p)p=1-(1-p)2>3/4

majority2(intt[],intn){if(majority(t,n))returntrue; elsereturnmajority(t,n);}

11/6/202219主元素问题11/6/202220主元素问题设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|>n/2时，称元素x是数组T的主元素。publicstaticboolean

majority(int[]t,intn){//判定主元素的蒙特卡罗算法

rnd=newRandom();

inti=rnd.random(n)+1;

intx=t[i];//随机选择数组元素

intk=0;for(intj=1;j<=n;j++)if(t[j]==x)k++;return(k>n/2);//k>n/2时t含有主元素

}publicstaticboolean

majorityMC(int[]t,intn,doublee){//重复éù次调用算法majority

intk=(int)Math.ceil(Math.log(1/e)/Math.log(2));for(inti=1;i<=k;i++)if(majority(t,n))returntrue;returnfalse;}对于任何给定的>0，算法majorityMC重复调用log(1/)

次算法majority。它是一个偏真蒙特卡罗算法，且其错误概率小于。算法majorityMC所需的计算时间显然是O(nlog(1/))。11/6/202221素数测试Wilson定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!-1(modn)。费尔马小定理：如果p是一个素数，且0<a<p，则ap-1(modp)。二次探测定理：如果p是一个素数，且0<x<p，则方程x21(modp)的解为x=1，p-1。privatestaticint

power(inta,intp,intn){//计算apmodn，并实施对n的二次探测

intx,result;if(p==0)result=1;else{x=power(a,p/2,n);//递归计算

result=(x*x)%n;//二次探测

if((result==1)&&(x!=1)&&(x!=n-1))composite=true;if((p%2)==1)//p是奇数

result=(result*a)%n;}returnresult;}publicstaticboolean

prime(intn){//素数测试的蒙特卡罗算法

rnd=newRandom();

inta,result;composite=false;a=rnd.random(n-3)+2;result=power(a,n-1,n);if(composite||(result!=1))returnfalse;elsereturntrue;}算法prime是一个偏假3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过(1/4)k。这是一个很保守的估计，实际使用的效果要好得多。11/6/202222算法导论11/6/202223RSA公钥加密系统

11/6/202224反复平方法求数的幂11/6/202225RSA1.Selectatrandomtwolargeprimenumberspandqsuchthatp≠

q.2.Computenbytheequationn=pq.3.Selectasmalloddintegerethatisrelativelyprimetoφ(n),equals(p-1)(q-1).4.Computedas