倒推法

2024/7/12

of158例樓梯上有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>22024/7/13

of158main(){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));}2024/7/14

of158例：有兩條完全相同的蚊香，每個可以點一個小時，問怎樣量出45分鐘？2024/7/15

of158有一位探險家用5天的時間徒步橫穿A、B兩村，兩村間是荒無人煙的沙漠，如果一個人只能擔負3天的食物和水，那么這個探險家至少雇幾個人才能順利通過沙漠。

2024/7/16

of158

A城雇用一人與探險家同帶3天食物同行一天，然后被雇人帶一天食物返回，并留一天食物給探險家，這樣探險家正好有3天的食物繼續前行，并于第三天打電話雇B城人帶3天食物出發，第四天會面他們會面，探險家得到一天的食物赴B城。

隨機化算法2024/7/18

of158定義：在算法中引入隨機因素,即通過隨機數選擇算法的下一步操作。特點：簡單、快速一種平衡：隨機算法可以理解為在時間、空間和隨機三大計算資源中的平衡2024/7/19

of158計算機產生隨機數的方法d0=d

dn=bdn-1+can=dn%655362024/7/110

of158計算機產生隨機數的方法unsignedintseed;

scanf("%d",&seed);

srand(seed);

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

printf("%d",rand()%10+1);}2024/7/111

of158計算機產生隨機數的方法srand((unsigned)time(0));

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

printf("%d",rand()%10+1);}2024/7/112

of1581、數值概率算法：用于數值問題的求解2、Sherwood算法一定能得到問題的正確解常見的四類隨機算法：2024/7/113

of1583、LasVegas算法或者得到正確的解，或者得不到解。4、MonteCarlo算法一定能得到解，但是得到的解可能不正確，然而這種概率是小的且有界的。常見的四類隨機算法：數值概率算法2024/7/115

of158用隨機投點法計算

值設有一半徑為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;}2024/7/116

of158舉例:QuickSort傳統的快排序算法

-總是取第一個元素作為劃分元；

-算法的最壞運行時間是O(n2)，平均時間是O(nlogn)；-因此存在一些輸入實例，使得算法達到最長運行時間，如：降序的序列；隨機快排序算法

-隨機選擇一個元素作為劃分元；

-任何一個輸入的期望時間是O(nlogn)；-是一個舍伍德算法；2024/7/117

of158舉例:八后問題對于大部分解，八后的位置并不具有系統性-因此可以隨機地把它們放在連續的行上，只要注意不要互相威脅。但是可能會失敗。解決方案：隨機+回溯2024/7/118

of158主元素問題設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);}

2024/7/119

of158主元素問題majority2返回true的概率是p+(1-p)p=1-(1-p)2>3/4majority2(intt[],intn){if(majority(t,n))returntrue; elsereturnmajority(t,n);}

2024/7/120

of158主元素問題2024/7/121

of158主元素問題設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/))。2024/7/122

of158素數測試Wilson定理：對于給定的正整數n，判定n是一個素數的充要條件是(n-1)!

-1(modn)。費爾馬小定理：如果p是一個素數，且0<a<p，則ap-1(modp)。二次探測定理：如果p是一個素數，且0<x<p，則方程x2

1(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。這是一個很保守的估計，實際使用的效果要好得多。2024/7/123

of158算法導論RSA公鑰加密系統

2024/7/125

of158反復平方法求數的冪2024/7/126

of158RSA1.Selectatrandomtwolargeprimenumberspandqsuchthatp≠

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