單元演算法基本構建

① 實現演算法所存儲的單元多少和演算法的工作量大小分別稱為演算法的什麼

這需要進行位操作,必較麻煩的,
在學習程序語言和進行程序設計的時候，交換兩個變數的值是經常要使用的。通常我們的做法是（尤其是在學習階段）：定義一個新的變數，藉助它完成交換。代碼如下：
int a,b;
a=10; b=15;
int t;
t=a; a=b; b=t;
這種演算法易於理解，特別適合幫助初學者了解計算機程序的特點，是賦值語句的經典應用。在實際軟體開發當中，此演算法簡單明了，不會產生歧義，便於程序員之間的交流，一般情況下碰到交換變數值的問題，都應採用此演算法（以下稱為標准演算法）。

上面的演算法最大的缺點就是需要藉助一個臨時變數。那麼不藉助臨時變數可以實現交換嗎？答案是肯定的！這里我們可以用三種演算法來實現：1）算術運算；2）指針地址操作；3）位運算。

1） 算術運算
簡單來說，就是通過普通的+和-運算來實現。代碼如下：
int a,b;
a=10;b=12;
a=b-a; //a=2;b=12
b=b-a; //a=2;b=10
a=b+a; //a=10;b=10
通過以上運算，a和b中的值就進行了交換。表面上看起來很簡單，但是不容易想到，尤其是在習慣標准演算法之後。
它的原理是：把a、b看做數軸上的點，圍繞兩點間的距離來進行計算。
具體過程：第一句「a=b-a」求出ab兩點的距離，並且將其保存在a中；第二句「b=b-a」求出a到原點的距離（b到原點的距離與ab兩點距離之差），並且將其保存在b中；第三句「a=b+a」求出b到原點的距離（a到原點距離與ab兩點距離之和），並且將其保存在a中。完成交換。
此演算法與標准演算法相比，多了三個計算的過程，但是沒有藉助臨時變數。（以下稱為算術演算法）

2） 指針地址操作
因為對地址的操作實際上進行的是整數運算，比如：兩個地址相減得到一個整數，表示兩個變數在內存中的儲存位置隔了多少個位元組；地址和一個整數相加即「a+10」表示以a為基地址的在a後10個a類數據單元的地址。所以理論上可以通過和算術演算法類似的運算來完成地址的交換，從而達到交換變數的目的。即：
int *a,*b; //假設
*a=new int(10);
*b=new int(20); //&a=0x00001000h,&b=0x00001200h
a=(int*)(b-a); //&a=0x00000200h,&b=0x00001200h
b=(int*)(b-a); //&a=0x00000200h,&b=0x00001000h
a=(int*)(b+int(a)); //&a=0x00001200h,&b=0x00001000h
通過以上運算a、b的地址真的已經完成了交換，且a指向了原先b指向的值，b指向原先a指向的值了嗎？上面的代碼可以通過編譯，但是執行結果卻令人匪夷所思！原因何在？
首先必須了解，操作系統把內存分為幾個區域：系統代碼/數據區、應用程序代碼/數據區、堆棧區、全局數據區等等。在編譯源程序時，常量、全局變數等都放入全局數據區，局部變數、動態變數則放入堆棧區。這樣當演算法執行到「a=(int*)(b-a)」時，a的值並不是0x00000200h，而是要加上變數a所在內存區的基地址，實際的結果是：0x008f0200h，其中0x008f即為基地址，0200即為a在該內存區的位移。它是由編譯器自動添加的。因此導致以後的地址計算均不正確，使得a,b指向所在區的其他內存單元。再次，地址運算不能出現負數，即當a的地址大於b的地址時，b-a<0，系統自動採用補碼的形式表示負的位移，由此會產生錯誤，導致與前面同樣的結果。
有辦法解決嗎？當然！以下是改進的演算法：
if(a<b)
{
a=(int*)(b-a);
b=(int*)(b-(int(a)&0x0000ffff));
a=(int*)(b+(int(a)&0x0000ffff));
}
else
{
b=(int*)(a-b);
a=(int*)(a-(int(b)&0x0000ffff));
b=(int*)(a+(int(b)&0x0000ffff));
}
演算法做的最大改進就是採用位運算中的與運算「int(a)&0x0000ffff」，因為地址中高16位為段地址，後16位為位移地址，將它和0x0000ffff進行與運算後，段地址被屏蔽，只保留位移地址。這樣就原始演算法吻合，從而得到正確的結果。
此演算法同樣沒有使用第三變數就完成了值的交換，與算術演算法比較它顯得不好理解，但是它有它的優點即在交換很大的數據類型時，它的執行速度比算術演算法快。因為它交換的時地址，而變數值在內存中是沒有移動過的。（以下稱為地址演算法）

3） 位運算
通過異或運算也能實現變數的交換，這也許是最為神奇的，請看以下代碼：
int a=10,b=12; //a=1010^b=1100;
a=a^b; //a=0110^b=1100;
b=a^b; //a=0110^b=1010;
a=a^b; //a=1100=12;b=1010;
此演算法能夠實現是由異或運算的特點決定的，通過異或運算能夠使數據中的某些位翻轉，其他位不變。這就意味著任意一個數與任意一個給定的值連續異或兩次，值不變。
即：a^b^b=a。將a=a^b代入b=a^b則得b=a^b^b=a;同理可以得到a=b^a^a=b;輕松完成交換。

以上三個演算法均實現了不藉助其他變數來完成兩個變數值的交換，相比較而言算術演算法和位演算法計算量相當，地址演算法中計算較復雜，卻可以很輕松的實現大類型（比如自定義的類或結構）的交換，而前兩種只能進行整形數據的交換（理論上重載「^」運算符，也可以實現任意結構的交換）。

介紹這三種演算法並不是要應用到實踐當中，而是為了探討技術，展示程序設計的魅力。從中可以看出，數學中的小技巧對程序設計而言具有相當的影響力，運用得當會有意想不到的神奇效果。而從實際的軟體開發看，標准演算法無疑是最好的，能夠解決任意類型的交換問題。

② 怎麼證明由三種基本結構所構成的演算法可以解決任何復雜問題

三種基本結構化結構：順序、選擇、循環。證明如下：

一、很多書籍確確實實的說明指出，這三種結構可以解決一切復雜的演算法問題是已經證明了的。

二、演算法過程就是一個步驟一個步驟、一條指令一條指令按照程序執行的過程，所以順序結構很自然的就是演算法的一個最基本的特性。

三、我們在解決問題時，由於對一些事實情況把握不太確定（邏輯學告訴我們思維必須確定才能進行正確的思維，否則會發生前後矛盾的情況，這也是一個良好演算法的要求），所以如果不進行正確的判斷的話，就不能輕易進入下一步驟。

由此當演算法執行到某一步驟時，如果要對某些情況進行判斷，才能進入下一步的執行，那麼選擇結構就是必須的了。它正是判斷了之後，再確定該執行哪些步驟。

四、循環結構是非必需的，它可有前兩種結構構成。

所以，總結起來：任何演算法它都是機械的一系列步驟，並且要求每一步都是確定的，當執行完這一步驟後，它就要確定下一步驟，如果根據演算法對象已經知道下一步該執行什麼了，就不需要再判斷直接進入下一步。

但是當對這些演算法對象的情況不確定時，我們就要判斷並選擇一些已經確定好操作對象的步驟。這也是問題的一個最根本的特性，就是我們提出問題的原因。因為思維遇到阻礙，就需要判斷，只有確定後才能繼續正確思維，才能解決問題。