電腦程式的演算法小記

什麼是電腦程式設計？

　　簡單的說，它就是告訴電腦要做什麼。電腦可以做很多事情，但是不太擅長自主思考，程式設計師需要像給小孩子吃東西一樣告訴它具體的細節，並且使電腦能夠理解的語言——演算法。

　　演算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對某一規範的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合某個問題，執行這個演算法就不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間複雜度與時間複雜度來衡量。
　　演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。
　　形式化演算法的概念部分源自於嘗試解決希爾伯特提出的判定問題，並在其後嘗試定義有效計算性或有效方法中成形。這些嘗試包括庫爾特·哥德爾、Jacques Herbrand和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算， 1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，仍然常有直覺想法難以定義為形式化演算法的情況。

特徵

　　一個演算法應該要有以下五個重要的特徵：
　　1、有窮性（Finiteness）
　　　　特質必須有窮性是指演算法必須能在執行有限個步驟之後終止；
　　2、確切性(Definiteness)
　　　　演算法的每一步必須有確切的定義；
　　3、輸入項(Input)
　　　　　3、輸入項(Input)
　　　　　3、輸入項(Input)##　　　　　一個演算法有個或多個演算法有個演算法有個或多個演算法有個演算法有個或多個演算法有個演算法有個問題個輸入，以刻畫運算物件的初始情況，所謂0個輸入是指演算法本身定出了初始條件；
　　4、輸出項(Output)
　　　　一個演算法有一個或多個輸出，以反映對輸入資料加工後的結果。沒有輸出的演算法是毫無意義的；
　　5、可行性(Effectiveness)

　　　　演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性）。

要素

　　一，資料物件的運算與操作：電腦可以執行的基本操作是以指令的形式描述的。一個電腦系統能執​​行的所有指令的集合，成為該電腦系統的指令系統。一個計算機的基本運算與運算有以下四類：
　　　　1，算術運算：加減乘除等運算
　　　　2，邏輯運算：或、且、非等運算
　　　　　小於、等於、不等於等運算
　　　　4，資料傳輸：輸入、輸出、賦值等運算[1]

　　二，演算法的控制結構：一個演算法的功能結構不僅取決於所選用的操作，而且取決於所選用的操作，而且取決於所選用的操作也與各操作之間的執行順序有關。

分類

　　演算法可大致分為基本演算法、資料結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、平行演算法，厄米變形模型，隨機森林演算法。
　　演算法可以宏泛的分為三類：
　　　　一，有限的，確定性演算法 這類演算法在有限的一段時間內終止。他們可能要花很長時間來執行指定的任務，但仍將在一定的時間內終止。這類演算法所得的結果常取決於輸入值。
　　　　二，有限的，非確定演算法 這類演算法在有限的時間內終止。然而，對於一個（或一些）給定的數值，演算法的結果並不是唯一的或確定的。

　　　　三，無限的演算法 是那些由於沒有定義終止定義條件，或定義的條件無法由輸入的資料滿足而不終止運行的演算法。通常，無限演算法的產生是由於未能確定的定義終止條件。

基礎數論儲備

二次剩餘###

先來看一個式x2≡n(modp),我們現在給出n，要求求得x的值。如果可以求得，n為mod p的二次剩餘，其實就是n在mod p意義下開的盡方。 Cipolla就是一個用來求得上式的x的一個演算法。

勒讓德符號

勒讓德符號是判斷一個數是否為p的二次剩餘的一個有力工具，p一定要為奇質數。 （n,p）表示n為關於p的勒讓德符號。其實就是判斷n是否為p的二次剩餘。

(np)=⎧⎩⎨1——p不是n的倍數,n是p的二次剩餘−1——p不是n的倍數，n是p的二次非剩餘（不是二次剩餘就是非剩餘）0——p是n的倍數

#看起來好像是一大段廢話，勒讓德只是站在巨人的肩膀上總結了一下而已。 
其實勒讓德也總結了一些性質，不過一般只用得到歐拉判別準則，不夠勒讓德符號是個積性函數可能還有點用。
但還是不知道如何判斷n是否為p的二次剩餘，往下看歐拉判別準則

ll Legendre(ll a, ll p)  
 {  
#       return qsm( a, (p-1)/2, p);  
 } 12341234

歐拉判別準則

先回顧歐拉定理xφ(p)≡1 (modp) 
因為這裡的p是奇質數，所以xp−1≡1(modp) 
對xp−1進行開方操作，在虛數域中xp−12≡±1(modp)，如果等於1就肯定開的了方，為-1一定開不了。所以x是否為n的二次剩餘就用這個歐拉判別準則。

if(qsm(n,(p-1)/2)==p-1){    printf("No root\n");
   continue;  
}12341234

#-1在mod p意義下為p-1。

演算法流程

給出n和p 
就算我們n關於p的勒讓德符號為1，那麼要怎麼取開n的方呢？ 
現在是腦洞大開的時候。

找一個數a

我們隨機一個數a，然後對a2−n進行開方操作（就是計算他勒讓德符號的值），直到他們的勒讓德符號為-1為止（就是開不了方為止）。 
就是找到一個a滿足(a2−n)p−12=−1 
先不要管為什麼，後面會講，我們現在就默默的去膜拜Cipolla的腦洞很大。

while(1){
   a=rand()%p;
   w=(a*a-n+p)%p;    if(qsm(w,(p-1) /2)==p-1)break;
}1234512345

因為是隨機找a，那麼會不會要找很久。 
答案：不會！
∙定理1：x2≡n(modp)中有p−12個n能使方程式有解 
⇒證明定理1：x2≡n(modp)，如果有不同的數u,v，使他們帶入x後可以使方程式有解，那麼很顯然滿足u2−v2|p，所以滿足(u+v)(u−v)|p，因為 
u2−v2|p所以p不可能是(u-v)的倍數，所以(u+v)|p，那麼這樣的數對在p中存在的數量為p−12 
根據定理1，隨機找a的期望為2。

建立一個複數域

說是建立，其實根本不用程式去打，說是建立複數域只是跟方便理解。 
在平常學的複數域中，有一個i，滿足i2=−1。 
我們也建立一個類似的域，因為我們要對a2−n開方，而a2−n有不是p的二次剩餘，所以我們定義ω=a2−n−−−−−√。那麼現在的ω也像i一樣，滿足ω2=a2−n，這樣我們就定義了一個新的域。

struct CN{
   ll x,y;
   CN friend operator *(CN x,CN y){
       CN z;
       z.x=x.x x.y*y.y%p*w%p)%p;
       z.y=(x.x*y.y%p+x.y*y.x%p)%p;        return z; 691


像正常打複數運算一樣我們定義一下運算子。可以發現z.x那個地方後面是*w而不是*1，因為現在的域單位複數為ω，滿足ω2=a2−n，而不像正常複數的i2=−1。在這個域中的表示方式類似正常的複數：a+bω

得出答案

我們要求的是x2≡n(modp)，x的值 

我們現在知道了a和ω之後，就能得到答案了。 

答案=(a+ω)p+12 
真的嗎？真的！但是這個答案不是由實數和虛數組成的嗎？ 
根據拉格朗日定理，可以得到虛數處的係數一定為0。

CN Cqsm(CN x,ll y){\\複數的快速冪   CN z;z.x=1,z.y=0;\\注意初始化   while(y){        if(y&1)z=z*x;
       x=x*x;
         x=x*x;
       y/=2;
   }    return z;
}1234567891234567899296789999(>doo a,u.y=1;//為什麼u.y是1－在複數的統計學中只用統計係數就好了
   u=Cqsm(u,(p+1)/2);
   ll yi= u.x,er=p-u.x;    if(yi>er)swap(yi,er);    if(yi==er){        printf("%lld\n", ); %lld %lld\n",yi,er);
   }12345678910111234567891011


為什麼會有兩個答案，例如4√=±2，x2≡(p−x

為什麼會有兩個答案，例如4√=±2，x2≡(p−x)2( modp)很顯然，因為把後面拆開x2≡x2−2px+p2(modp)，把p都約去，所以x2≡(p−x)2(modp)。

證明原理

再搞出一些定理方便說明。

定理

∙定理2：(a+b)p≡ap+bp(modp) 
⇒證明定理2：根據二項式定理: 
(a+ b)p≡∑pi=0Cipap−ibi(modp) 
≡∑pi=0p!(p−i)!i!ap−ibi(modp) 
可以發現，只有當i=0或i= p的時候式子沒有p的因子，所以中間有p的因子的都可以省略，所以(a+b)p≡ap+bp(modp) 
∙定理3：ωp≡−ω(modp) 
⇒證明定理3：ωp 
=ωp−1∗ω 
=(ω2)p−12∗ω 
=(a2−n)p−12∗ω－因為ω2=a2− n 
=−ω－因為滿足(a2−n)p−12=−1 
∙定理4：ap≡a(modp) 
⇒證明定理3：ap根據費馬小定理 
≡ap−1≡1(modp) 
所以ap≡a∗ap−1≡a(modp)

推導

問題：x2≡n(modp)求解x
Cipolla：x≡(a+ω)p+12(modp)的實數 
#直接把式子轉換： 
(a+ω)p+12(modp) 
≡((a +ω)p+1)12(modp) 
≡((a+ω)p(a+ω))12(modp) 
≡((ap+ωp)(a+ω))12( modp)依據定理2 
≡((a−ω)(a+ω))12(modp)依定理3與定理4 
≡(a2−ω2)12(modp)依定理3與定理4
≡(a2−(a2−n))12(modp)滿足ω2=a2−n 
≡n12(modp) 
所以(a+ω)p+12≡n12≡n√(modp ) 
這腦洞太大了！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！

以上是電腦程式的演算法小記的詳細內容。更多資訊請關注PHP中文網其他相關文章！