從演算法到實現

A. 演算法工程師要學什麼

所謂演算法工程師，首先需要是一名工程師，那麼就要掌握所有開發工程師都需要掌握的一些能力。有些新手對於這一點存在一些誤解，認為所謂演算法工程師就只需要思考和設計演算法，不用在乎這些演算法如何實現，而且會有人幫你來實現你想出來的演算法方案。這種思想是錯誤的，在大多數企業的大多數職位中，演算法工程師需要負責從演算法設計到演算法實現再到演算法上線這一個全流程的工作。所以作為一個演算法工程師，首先要會編程，你的編程語言一定要熟練掌握。當你熟練掌握編程語言以後，還要認真研究機器學習理論以及概率與數理統計方面的知識。慢慢進階到架構設計以後，你才向演算法工程師邁出了堅實的一步。

B. CRC演算法，從原理到實現

CRC，一種基於有限域GF(2)的多項式環的Hash演算法。在GF(2)中，多項式系數只有0、1，加減運算等同於異或(XOR)運算，乘除運算與一般多項式運算一致（合並同類項時需要注意為XOR運算）

在GF(2)中，多項式系數只有0、1，加減運算等同於異或(XOR)運算，乘除運算與一般多項式運算一致（合並同類項時需要注意為XOR運算）。在CRC-n演算法中，有M(x)·x ⁿ =Q(x)·G(x)+R(x)，M(x)為m位的數據，G(x)為一個GF(2)的n+1項的生成多項式(Poly)，M(x)·x ⁿ 則是通過在數據M(x)後添加n個0形成的對應的m+n位多項式，而R(x)即為M(x)·x ⁿ 除以G(x)的n位余數——即CRC校驗碼，Q(x)為商，直接丟棄。通過比較兩次計算產生的Signature是否一致判斷故障的發生

假定M(x)=11100110，G(x)=x ³ + x + 1，其中n=3，則M(x)·x ⁿ =11100110000，將G(x)多項式中的各項系數取出，按降冪排列所對應的數據Poly=1011，然後對其進行除法運算：

所得n位余數即為CRC——100

根據定義可以建立一個簡單的CRC實現演算法，模型如下圖所示：
1)建立一個長度為r的CRC Register，並初始化為0
2)在M(x)後添加r個0形成M(x)·x ⁿ
3)將CRC Register左移一位，將M(x)·x ⁿ 的MSB移入CRC Register的Bit 0
4)第3步中的從CRC Register移出的數，如果是1，則計算，CRC Register=Poly XOR CRC Register
5)重復第3步，直到M(x)·x ⁿ 全部移入CRC Register
6)CRC Register即為CRC校驗值

根據定義所建立的演算法模型存在明顯缺陷，按位移動處理效率低下，為此我們探索如何實現更大處理單元的演算法。這次我們以CRC-32為例，按照前面的演算法思路構建的模型如下圖所示：

設CRC Register中的Byte 3依次為：t7 t6 t5 t4 t3 t2 t1 t0，Poly中的Bit31-Bit24依次為：g7 g6 g5 g4 g3 g2 g1 g0，根據1.3.2可知，在第1次迭代中，CRC Register的MSB:t7將會決定Poly與CRC Register的異或，如果t7=1，這就會發生，反之就不會發生;在第2次迭代中，CRC Register的MSB:t6 XOR (t7*g7) 將會決定本次Poly與CRC Register的異或是否發生，即t7、t6控制第2XOR操作；同理，在第3次迭代中，CRC Register的MSB也是通過t7、t6、t5決定，即t7、t6、t5控制第3次XOR操作。故我們可以得出下述結論：k次以後的迭代的最高位的值，可以由寄存器的前k位計算得到。根據這個結論，我們可以一次性取出CRC Register的Byte 3，提前計算出8次迭代後的寄存器余式，因為高位終將會在迭代中被移出，我們只需要關心餘式即可。同時XOR運算滿足結合律：A XOR B XOR C = A XOR (B XOR C)

上圖即為Byte 3全部迭代移出的示意圖，根據結合律可以看出，我們可以依據Byte 3直接確定8次異或的與否及Poly的偏移量，從而提前計算出不同偏移量的Poly間XOR的值，令其為A，易知A的高8位和Byte 3一定相等，Reg向左移出btye3，從M(x)·x ⁿ 讀取一個byte放在byte 0，最後將A的低32位與Reg完成XOR操作。為避免與位元組邊界發生沖突，我們採用位元組的整數倍——位元組（1 byte）、字（2 byte）、雙字（4 byte），故一般不採用4bit作為處理單元。由於一個位元組的取值是有限的——256種，我們只要提前計算一個位元組全部的A值保存到表中。運行時以byte值為索引，直接從表裡取出即可

至此我們完成基於1 byte為處理單元的Table Driven，演算法模型如下圖所示：
1)建立一個長度為r的CRC Register，並初始化為0
2)在M(x)後添加r個0形成M(x)·x ⁿ
3)將CRC Register左移一個byte，從M(x)·x ⁿ 讀入一個byte至CRC Register的byte 0中
4)以第3步中的從CRC Register移出的byte為index，從表中取出對應的n位寬的值，將該值與CRC Register進行XOR
5)重復第3步，直到M(x)·x ⁿ 全部移入CRC Register6) CRC Register即為CRC校驗值

在上述的兩種演算法中，我們每次都需要在M(x)後添加n個0，其並不參與運算，目的只是為了將M(x)的全部推入CRC Register而已，並且在有些情境下在M(x)後添0操作並不總是能夠實現的，故通過改進計算步驟有了直接表法，避免了對原始數據的添0操作
演算法流程，演算法模型如下圖所示：
1)建立一個長度為r的CRC Register，按照Init值對其初始化
2)將CRC Register左移一個byte，從M(x)左移一個byte，兩者進行XOR
3)第2步中XOR後的值作為index，從表中取出對應的n位寬的值，將該值與CRC Register進行XOR
4)重復第2步，直到M(x)全部取出
5)CRC Register即為CRC校驗值

在Direct Table演算法中，當RefIn、RefOut為True，每次都需要對數據做顛倒操作，很麻煩。為此產生了Reflected Direct Table演算法，該演算法改變了CRC Register的移動方向，而不需要對M(x)做任何處理，按位元組順序讀取即可，演算法模型如下圖所示

演算法流程如下：
1)建立一個長度為r的CRC Register，按照Init值對其初始化
2)將CRC Register右移一個byte，從M(x)左移一個byte，兩者進行XOR
3)第2步中XOR後的值作為index，從表中取出對應的n位寬的值，將該值與CRC Register進行XOR
4)重復第2步，直到M(x)全部取出
5)CRC Register即為CRC校驗值

Name: CRC標准

Width: 生成的CRC的位寬

Poly: 生成多項式，一般採用十六進制簡記，長度為width+1，由於其最高位恆為1，故記法中不體現出來（例如：x ¹⁶ +x ¹² +x ⁵ +1記為0x1021）

Init: 初始值，如果數據前添加了若干個前導零，在前述演算法中，一般是檢測不到的，故通過改變CRC Register中的預設值，以實現對該類型錯誤的檢測。在Direct Table演算法中用Init初始化CRC Register即可，在Table Driven演算法中，不可以直接用Init初始化CRC Register，因為其等同於在原始數據前插入了Init，必須要先把CRC Register設為0，等M(x)·x ⁿ 移動n/8次後，即CRC Register的預設值0全部移出時，再將Init值異或進CRC Register。完成Init操作

Xorout: 結果異或值，所有計算完成後將CRC Register與Xorout進行異或作，作為最後的校驗值

RefIn: 輸入反轉，這是一個布爾值，如果為False，則每個位元組內的位順序保持不變，即Bit 7為MSB，Bit0為LSB。如果為True，則將需要每個位元組內的位順序顛倒，即Bit 7為LSB，Bit0為MSB。這個約定在硬體CRC中是合理的，因為在串口通訊中硬體一般默認先發送位元組的Bit 0，最後發送Bit 7

RefOut: 輸出反轉，這是一個布爾值，如果為False，則在計算結束後，直接進入Xorout環節，如果為True，則在計算結束後，將CRC Register進行顛倒後，再進入Xorout環節。注意，和RefIn顛倒位元組內的位順序不同的是，這個是將CRC Register的值作為一個整體顛倒，即Bit n到Bit0進行顛倒

針對常見常用的下述CRC給出了實現方法，以供參考

C. 哲學家進餐問題的演算法與實現

1．哲學家進餐問題：
(1) 在什麼情況下5 個哲學家全部吃不上飯考慮兩種實現的方式，如下：
A. 演算法描述： void philosopher(int i) /*i：哲學家編號，從0 到4*/ {while (TRUE) { think( ); /*哲學家正在思考*/ take_fork(i); /*取左側的筷子*/ take_fork((i+1) % N); /*取左側筷子；％為取模運算*/eat( ); /*吃飯*/put_fork(i); /*把左側筷子放回桌子*/ put_fork((i+1) % N); /*把右側筷子放回桌子*/ } } 分析：假如所有的哲學家都同時拿起左側筷子，看到右側筷子不可用，又都放下左側筷子，等一會兒，又同時拿起左側筷子，如此這般，永遠重復。對於這種情況，即所有的程序都在無限期地運行，但是都無法取得任何進展，即出現飢餓，所有哲學家都吃不上飯。
B．演算法描述：規定在拿到左側的筷子後，先檢查右面的筷子是否可用。如果不可用，則先放下左側筷子，等一段時間再重復整個過程。分析：當出現以下情形，在某一個瞬間，所有的哲學家都同時啟動這個演算法，拿起左側的筷子，而看到右側筷子不可用，又都放下左側筷子，等一會兒，又同時拿起左側筷子……如此這樣永遠重復下去。對於這種情況，所有的程序都在運行，但卻無法取得進展，即出現飢餓，所有的哲學家都吃不上飯。
(2) 描述一種沒有人餓死（永遠拿不到筷子）演算法。考慮了四種實現的方式（A、B、C、D）：
A．原理：至多隻允許四個哲學家同時進餐,以保證至少有一個哲學家能夠進餐,最終總會釋放出他所使用過的兩支筷子,從而可使更多的哲學家進餐。以下將room 作為信號量，只允許4 個哲學家同時進入餐廳就餐，這樣就能保證至少有一個哲學家可以就餐，而申請進入餐廳的哲學家進入room 的等待隊列，根據FIFO 的原則，總會進入到餐廳就餐，因此不會出現餓死和死鎖的現象。
偽碼： semaphore chopstick[5]={1，1，1，1，1}; semaphore room=4; void philosopher(int i) { while(true) {think(); wait(room); //請求進入房間進餐 wait(chopstick[i]); //請求左手邊的筷子 wait(chopstick[(i+1)%5]); //請求右手邊的筷子 eat(); signal(chopstick[(i+1)%5]); //釋放右手邊的筷子 signal(chopstick[i]); //釋放左手邊的筷子 signal(room); //退出房間釋放信號量room } }
B．原理：僅當哲學家的左右兩支筷子都可用時,才允許他拿起筷子進餐。
方法1：利用AND 型信號量機制實現：根據課程講述，在一個原語中，將一段代碼同時需要的多個臨界資源，要麼全部分配給它，要麼一個都不分配，因此不會出現死鎖的情形。當某些資源不夠時阻塞調用進程;由於等待隊列的存在，使得對資源的請求滿足FIFO 的要求，因此不會出現飢餓的情形。
偽碼： semaphore chopstick[5]={1，1，1，1，1}; void philosopher(int I) { while(true) { think();Swait(chopstick[(I+1)]%5,chopstick[I]); eat(); Ssignal(chopstick[(I+1)]%5,chopstick[I]);} } 方法2：利用信號量的保護機制實現。通過信號量mutex對eat（）之前的取左側和右側筷子的操作進行保護，使之成為一個原子操作，這樣可以防止死鎖的出現。偽碼： semaphore mutex = 1 ; semaphorechopstick[5]={1，1，1，1，1};void philosopher(int I) { while(true) { think(); wait(mutex);wait(chopstick[(I+1)]%5); wait(chopstick[I]); signal(mutex); eat();signal(chopstick[(I+1)]%5); signal(chopstick[I]); } }
C．原理：規定奇數號的哲學家先拿起他左邊的筷子,然後再去拿他右邊的筷子;而偶數號的哲學家則相反.按此規定,將是1,2號哲學家競爭1號筷子,3,4號哲學家競爭3號筷子.即五個哲學家都競爭奇數號筷子,獲得後,再去競爭偶數號筷子,最後總會有一個哲學家能獲得兩支筷子而進餐。而申請不到的哲學家進入阻塞等待隊列，根FIFO原則，則先申請的哲學家會較先可以吃飯，因此不會出現餓死的哲學家。
偽碼： semaphore chopstick[5]={1，1，1，1，1}; void philosopher(int i) { while(true) { think(); if(i%2== 0) //偶數哲學家，先右後左。 { wait (chopstick[ i + 1 ] mod 5) ; wait (chopstick[ i]) ;eat(); signal (chopstick[ i + 1 ] mod 5) ; signal (chopstick[ i]) ; } Else //奇數哲學家，先左後右。 { wait (chopstick[ i]) ; wait (chopstick[ i +1 ] mod 5) ; eat(); signal (chopstick[ i]) ; signal (chopstick[ i + 1 ] mod 5); } }
D．利用管程機制實現（最終該實現是失敗的，見以下分析）：原理：不是對每隻筷子設置信號量，而是對每個哲學家設置信號量。test()函數有以下作用：
a. 如果當前處理的哲學家處於飢餓狀態且兩側哲學家不在吃飯狀態，則當前哲學家通過 test()函數試圖進入吃飯狀態。
b. 如果通過test()進入吃飯狀態不成功，那麼當前哲學家就在該信號量阻塞等待，直到其他的哲學家進程通過test()將該哲學家的狀態設置為EATING。
c. 當一個哲學家進程調用put_forks()放下筷子的時候，會通過test()測試它的鄰居，如果鄰居處於飢餓狀態，且該鄰居的鄰居不在吃飯狀態，則該鄰居進入吃飯狀態。由上所述,該演算法不會出現死鎖，因為一個哲學家只有在兩個鄰座都不在進餐時，才允許轉換到進餐狀態。該演算法會出現某個哲學家適終無法吃飯的情況，即當該哲學家的左右兩個哲學家交替處在吃飯的狀態的時候，則該哲學家始終無法進入吃飯的狀態，因此不滿足題目的要求。但是該演算法能夠實現對於任意多位哲學家的情況都能獲得最大的並行度，因此具有重要的意義。
偽碼：#define N 5 /* 哲學家人數*/#define LEFT (i-1+N)%N /* i的左鄰號碼 */ #define RIGHT (i+1)%N /* i的右鄰號碼 */ typedef enum { THINKING, HUNGRY, EATING } phil_state; /*哲學家狀態*/ monitor dp /*管程*/ { phil_state state[N]; semaphore mutex =1; semaphore s[N];/*每個哲學家一個信號量，初始值為0*/void test(int i) { if ( state[i] == HUNGRY &&state[LEFT(i)] != EATING&& state[RIGHT(i)] != EATING ) { state[i] = EATING; V(s[i]); } } void get_forks(inti) { P(mutex); state[i] = HUNGRY; test(i); /*試圖得到兩支筷子*/ V(mutex); P(s[i]); /*得不到筷子則阻塞*/ } void put_forks(int i) { P(mutex); state[i]= THINKING;test(LEFT(i)); /*看左鄰是否進餐*/ test(RIGHT(i)); /*看右鄰是否進餐*/ V(mutex); } } 哲學家進程如下： void philosopher(int process) { while(true) { think();get_forks(process); eat(); put_forks(process); } }
2.理發師問題：一個理發店有一個入口和一個出口。理發店內有一個可站5 位顧客的站席區、4 個單人沙發、3 個理發師及其專用理發工具、一個收銀台。新來的顧客坐在沙發上等待；沒有空沙發時，可在站席區等待；站席區滿時，只能在入口外等待。理發師可從事理發、收銀和休息三種活動。
理發店的活動滿足下列條件：
1）休息的理發師是坐地自己專用的理發椅上，不會佔用顧客的沙發；
2）處理休息狀態的理發師可為在沙發上等待時間最長的顧客理發；
3）理發時間長短由理發師決定；
4）在站席區等待時間最長的顧客可坐到空閑的理發上；
5）任何時刻最多隻能有一個理發師在收銀。試用信號量機制或管程機制實現理發師進程和顧客進程。
原理：
(1) customer 進程：首先檢查站席區是否已滿（stand_capacity）,若滿選擇離開，否則進入站席區，即進入理發店。在站席區等待沙發的空位（信號量sofa），如果沙發已滿，則進入阻塞等待隊列，直到出現空位，在站席區中等待時間最長的顧客離開站席區（stand_capacity）。坐到沙發上，等待理發椅(barber_chair)，如果理發椅已滿，則進入阻塞等待隊列，直到出現空位，在沙發上等待時間最長的顧客離開沙發（釋放信號量sofa）。坐到理發椅上，釋放准備好的信號（customer_ready），獲得該理發師的編號（0~1 的數字）。等待理發師理發結束（finished[barber_number]）。在離開理發椅之前付款（payment），等待收據 (receipt)，離開理發椅（leave_barberchair）。最後離開理發店。
這里需要注意幾點：
a) 首先是幾個需要進行互斥處理的地方，主要包括:進入站席區、進入沙發、進入理發椅和付款幾個地方。
b) 通過barber_chair保證一個理發椅上最多隻有一名顧客。但這也不夠，因為單憑 baber_chair 無法保證一名顧客離開理發椅之前，另一位顧客不會坐到該理發椅上，因此增加信號量leave_barberchair，讓顧客離開理發椅後，釋放該信號，而理發師接收到該信號後才釋放barber_chair 等待下一位顧客。
c) 在理發的過程中，需要保證是自己理發完畢，才能夠進行下面的付款、離開理發椅的活動。這個機制是通過customer 進程獲得給他理發的理發師編號來實現的，這樣，當該編號的理發師釋放對應的finished[i]信號的時候，該顧客才理發完畢。
d) 理發師是通過mutex 信號量保證他們每個人同時只進行一項操作（理發或者收款）。
e) 為了保證該顧客理發完畢後馬上可以付款離開，就應該保證給該顧客理發的理發師在理發完畢後馬上到收銀台進入收款操作而不是給下一位顧客服務。在偽碼中由以下機制實現：即顧客在釋放離開理發椅的信號前，發出付款的信號。這樣該理發師得不到顧客的離開理發椅的信號，不能進入下一個循環為下一名顧客服務，而只能進入收款台的收款操作。直到顧客接到收據後，才釋放離開理發椅的信號，離開理發椅，讓理發師釋放該理發椅的信號，讓下一位等待的顧客坐到理發椅上。
(2)barber 進程首先將該理發師的編號壓入隊列，供顧客提取。等待顧客坐到理發椅坐好(信號量 customer_ready)，開始理發，理發結束後釋放結束信號（finished[i]）。等待顧客離開理發椅（leave_barberchair）（期間去收銀台進行收款活動），釋放理發椅空閑信號(barber_chair)，等待下一位顧客坐上來。
(3)cash（收銀台）進程等待顧客付款(payment),執行收款操作，收款操作結束，給付收據（receipt）。信號量總表：信號量 waitsignal stand_capacity 顧客等待進入理發店顧客離開站席區 sofa 顧客等待坐到沙發顧客離開沙發 barber_chair 顧客等待空理發椅理發師釋放空理發椅 customer_ready 理發師等待，直到一個顧客坐到理發椅顧客坐到理發椅上，給理發師發出信號 mutex 等待理發師空閑，執行理發或收款操作理發師執行理發或收款結束，進入空閑狀態 mutex1執行入隊或出隊等待入隊或出隊結束，釋放信號 finished[i] 顧客等待對應編號理發師理發結束理發師理發結束，釋放信號 leave_barberchair 理發師等待顧客離開理發椅顧客付款完畢得到收據，離開理發椅釋放信號 payment 收銀員等待顧客付款顧客付款，發出信號 receipt 顧客等待收銀員收、開具收據收銀員收款結束、開具收據，釋放信號
偽碼： semaphore stand_capacity=5; semaphore sofa=4; semaphorebarber_chair=3; semaphore customer_ready=0; semaphore mutex=3; semaphoremutex1=1; semaphore finished[3]={0,0,0}; semaphore leave_barberchair=0;semaphore payment=0; semaphore receipt=0; void customer() { int barber_number;wait(stand_capacity); //等待進入理發店 enter_room(); //進入理發店 wait(sofa); //等待沙發 leave_stand_section(); //離開站席區 signal(stand_capacity); sit_on_sofa(); //坐在沙發上 wait(barber_chair); //等待理發椅 get_up_sofa(); //離開沙發 signal(sofa); wait(mutex1);sit_on_barberchair(); //坐到理發椅上 signal(customer_ready); barber_number=dequeue(); //得到理發師編號 signal(mutex1); wait(finished[barber_number]);//等待理發結束 pay(); //付款 signal(payment); //付款 wait(receipt); //等待收據 get_up_barberchair(); //離開理發椅 signal(leave_barberchair); //發出離開理發椅信號 exit_shop(); //了離開理發店 } void barber(int i) { while(true) { wait(mutex1);enqueue(i); //將該理發師的編號加入隊列 signal(mutex1); wait(customer_ready); //等待顧客准備好 wait(mutex); cut_hair(); //理發 signal(mutex); signal(finished[i]); //理發結束 wait(leave_barberchair); //等待顧客離開理發椅信號 signal(barber_chair); //釋放barber_chair 信號 } } void cash() //收銀 { while(true) { wait(payment); //等待顧客付款 wait(mutex); //原子操作 get_pay(); //接受付款 give_receipt(); //給顧客收據 signal(mutex); signal(receipt); //收銀完畢，釋放信號 } }
分析：在分析該問題過程中，出現若干問題，是參閱相關資料後才認識到這些問題的隱蔽性和嚴重性的,主要包括：
（1）在顧客進程，如果是在釋放leave_barberchair 信號之後進行付款動作的話，很容易造成沒有收銀員為其收款的情形，原因是：為該顧客理發的理發師收到 leave_barberchair 信號後，釋放barber_chair 信號，另外一名顧客坐到理發椅上，該理發師有可能為這另外一名顧客理發，而沒有為剛理完發的顧客收款。為解決這個問題，就是採取在釋放leave_barberchair 信號之前，完成付款操作。這樣該理發師無法進入下一輪循環為另外顧客服務，只能到收銀台收款。
（2）本演算法是通過給理發師編號的方式，當顧客坐到某理發椅上也同時獲得理發師的編號，如此，當該理發師理發結束，釋放信號，顧客只有接收到為其理發的理發師的理發結束信號才會進行付款等操作。這樣實現，是為避免這樣的錯誤，即：如果僅用一個finished 信號量的話，很容易出現別的理發師理發完畢釋放了finished 信號，把正在理發的這位顧客趕去付款,而已經理完發的顧客卻被阻塞在理發椅上的情形。當然也可以為顧客進行編號，讓理發師獲取他理發的顧客的編號，但這樣就會限制顧客的數量，因為finished[] 數組不能是無限的。而為理發師編號，則只需要三個元素即可。

D. 演算法設計與程序實現:java,100元的具體劃分方案,可選面值有1元,10元,20元,50元,100元.

for( int a=0,loopCountA=100/100; a<=loopCountA; a++ )
for( int b=0,loopCountB=(100-a*100)/50; b<=loopCountB; b++ )
for( int c=0,loopCountC=(100-a*100-b*50)/20; c<=loopCountC; c++ )
for( int d=0,loopCountD=(100-a*100-b*50-c*20)/10; d<=loopCountD; d++ )
for( int e=0,loopCountE=(100-a*100-b*50-c*20-d*10)/1; e<=loopCountE; e+=10 )
if( (a*100+b*50+c*20+d*10+e)==100 )
System.out.println("1元："+e+"張；10元："+d+"張；20元："+c+"張；50元："+b+"張；100元："+a+"張。");

改進了下，速度快了一些。

E. 普里姆演算法的普里姆演算法的實現

為了便於在兩個頂點集U和V-U之間選擇權最小的邊，建立了兩個輔助數組closest和lowcost，它們記錄從U到V-U具有最小權值的邊，對於某個j∈V-U，closest[j]存儲該邊依附的在U中的頂點編號，lowcost[j]存儲該邊的權值。
為了方便，假設圖G採用鄰接矩陣g存儲，對應的Prim(g,v)演算法如下：
void Prim(MatGraph g,int v) //輸出求得的最小生樹的所有邊
{ int lowcost[MAXVEX]; //建立數組lowcost
int closest[MAXVEX]; //建立數組closest
int min,i,j,k;
for (i=0;i<g.n;i++) //給lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //構造n-1條邊
{ min=INF; k=-1;
for (j=0;j<g.n;j++) //在(V-U)中找出離U最近的頂點k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j];
k=j; //k為最近頂點的編號
}
printf( 邊(%d,%d),權值為%d ,closest[k],k,min);
lowcost[k]=0; //標記k已經加入U
for (j=0;j<g.n;j++) //修正數組lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{ lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
普里姆演算法中有兩重for循環，所以時間復雜度為O(n2)，其中n為圖的頂點個數。由於與e無關，所以普里姆演算法特別適合於稠密圖求最小生成樹。

F. 最優化原理的演算法實現

動態規劃的主要難點在於理論上的設計，也就是上面4個步驟的確定，一旦設計完成，實現部分就會非常簡單。使用動態規劃求解問題，最重要的就是確定動態規劃三要素：問題的階段,每個階段的狀態以及從前一個階段轉化到後一個階段之間的遞推關系。遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對於大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃演算法的核心之處。確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表示一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最後根據整個表格的數據通過簡單的取捨或者運算求得問題的最優解。下面分別以求解最大化投資回報問題和最長公共子序列問題為例闡述用動態規劃演算法求解問題的一般思路。
實例：
最大化投資回報問題
某人有一定的資金用來購買不同面額的債卷，不同面額債卷的年收益是不同的，求給定資金，年限以及債卷面額、收益的情況下怎樣購買才能使此人獲得最大投資回報。
程序輸入約定：第一行第一列表示資金（1000的倍數）總量，第二列表示投資年限；第二行表示債卷面額總數；從第三行開始每行表示一種債卷，佔用兩列，前一列表示債卷面額，後一列表示其年收益，如下輸入實例，
10000 1
2
4000 400
3000 250
程序實現如下，注釋幾乎說明了一切，所以不再另外分析。
/// 此數組是演算法的關鍵存儲結構，用來存儲不同階段各種債卷
/// 組合下對應可獲取的最大利息。
int saifa[80005];
/// 此函數用於計算當前債卷在不同購買額下的最優利息情況，
/// 注意此時的利息情況是基於上一次債卷的情況下計算得到的，
/// 也就是說當前利息最優是基於上一次利息最優的基礎上計算出來的，
/// 這也正好體現了動態規劃中「最優化原則」：不管前面的策略如何，
/// 此後的決策必須是基於當前狀態（由上一次決策產生）的最優決策。
/*
動態規劃的求解過程一般都可以用一個最優決策表來描述，
對於本程序，以示例輸入為例，對於第一年，其最優決策表如下：
0 1 2 3 4 5 6 7 8 9 10(*1000) -- (1)
0 0 0 0 400 400 400 400 800 800 800 -- (2)
0 0 0 250 400 400 500 650 800 900900 -- (3)
(1) -- 表示首先選利息為400的債卷在對應資金下的最優利息。
(2) -- 表示可用來購買債卷的資金。
(3) -- 表示在已有狀態下再選擇利息為300的債卷在對應資金下的最優利息。
注意上面表格，在求購買利息為300的債卷獲得的最優收益的時候，
參考了以前的最優狀態，以3行8列的650為例，7(*1000)可以
在以前購買了0張4000的債卷的基礎上再2張3000的，也可以在以前購
買了1張4000的基礎上再買1張3000，經比較取其收益大的，這就是典
型的動態規劃中的當前最優狀態計算。
本程序中把上面的最優決策二維表用一個一維數組表示，值得借鑒。
*/
void add(int a,int b)
{
cout << a << << b << endl; // for debug
for(int i=0;i<=80000;i++)
{
if(i+a > 80000)
{
break;
}
if(saifa[i]+b > saifa[i+a]) // 累計同時購買多種債卷時的利息
{
saifa[i+a] = saifa[i] + b;
}
if(i<200) // for debug
cout << i << -<< saifa[i] << ;
}
cout << endl; // for debug
}
int main(void)
{
int n,d,money,year,pay,bond;
int ii,i;
scanf(%d,&n);
for(ii=0;ii<n;ii++)
{
memset(saifa,0,sizeof(saifa));
scanf(%d%d,&money,&year);
scanf(%d,&d);
for(i=0;i<d;i++)
{
scanf(%d%d,&pay,&bond);
add(pay/1000,bond);
}
// 計算指定年限內最優組合的本金利息總額
for(i=0;i<year;i++)
{
cout << saifa[money/1000]<< ; // for debug
money += saifa[money/1000];
}
cout << endl; // for debug
printf(%d ,money);
}
return 0;
}
上述程序實現方法同樣適合於背包問題，最優庫存問題等，只是針對具體情況，最優決策表的表示和生成會有所不同。

G. 「演算法時代」到來，為何演算法服務人類並未被實現

一開始演算法只是服務於人類的，但隨著網路的發達以及智能地推廣，人們驚訝的發現自己正在慢慢依賴演算法乃至無法失去它。

好像在上世紀90年代當計算機深藍贏了大師之後，當時就有人提出智能電腦也許終究有一天將主導人類。而它的初衷只是發明出來，幫助人們生活在一個更加便利的環境下，人是主導它，或者說控制它的，它被發明出來也只是服務於人類的，但是隨著時間的推移會逐漸發現當它被賦予了的各種演算法以及不斷更新之後，開始會學習了，它產生的某種意義上的主導性，而這一點可能會將人類擺在一個尷尬的位置，因為人類將無法完全操控它。

久而久之的這種演算法讓人們變得越來越懶惰了，人們不願去自主思考，因為智能設備會推送給人類精準的信息，這些信息就是人類所需要的，它們已經自動排除了人類所不感興趣的無用信息了。

H. crc演算法在單片機上的實現

CRC演算法原理及C語言實現

摘 要 本文從理論上推導出CRC演算法實現原理,給出三種分別適應不同計算機或微控制器硬體環境的C語言程序。讀者更能根據本演算法原理,用不同的語言編寫出獨特風格更加實用的CRC計算程序。
關鍵詞 CRC 演算法 C語言
1 引言
循環冗餘碼CRC檢驗技術廣泛應用於測控及通信領域。CRC計算可以靠專用的硬體來實現,但是對於低成本的微控制器系統,在沒有硬體支持下實現CRC檢驗,關鍵的問題就是如何通過軟體來完成CRC計算,也就是CRC演算法的問題。
這里將提供三種演算法,它們稍有不同,一種適用於程序空間十分苛刻但CRC計算速度要求不高的微控制器系統,另一種適用於程序空間較大且CRC計算速度要求較高的計算機或微控制器系統,最後一種是適用於程序空間不太大,且CRC計算速度又不可以太慢的微控制器系統。
2 CRC簡介
CRC校驗的基本思想是利用線性編碼理論,在發送端根據要傳送的k位二進制碼序列,以一定的規則產生一個校驗用的監督碼（既CRC碼）r位,並附在信息後邊,構成一個新的二進制碼序列數共(k+r)位,最後發送出去。在接收端,則根據信息碼和CRC碼之間所遵循的規則進行檢驗,以確定傳送中是否出錯。
16位的CRC碼產生的規則是先將要發送的二進制序列數左移16位（既乘以 ）後,再除以一個多項式,最後所得到的余數既是CRC碼,如式（2-1）式所示,其中B(X)表示n位的二進制序列數,G(X)為多項式,Q(X)為整數,R(X)是余數（既CRC碼）。
（2-1）
求CRC碼所採用模2加減運演算法則,既是不帶進位和借位的按位加減,這種加減運算實際上就是邏輯上的異或運算,加法和減法等價,乘法和除法運算與普通代數式的乘除法運算是一樣,符合同樣的規律。生成CRC碼的多項式如下,其中CRC-16和CRC-CCITT產生16位的CRC碼,而CRC-32則產生的是32位的CRC碼。本文不討論32位的CRC演算法,有興趣的朋友可以根據本文的思路自己去推導計算方法。
CRC-16：（美國二進制同步系統中採用）
CRC-CCITT：（由歐洲CCITT推薦）
CRC-32：

接收方將接收到的二進制序列數（包括信息碼和CRC碼）除以多項式,如果余數為0,則說明傳輸中無錯誤發生,否則說明傳輸有誤,關於其原理這里不再多述。用軟體計算CRC碼時,接收方可以將接收到的信息碼求CRC碼,比較結果和接收到的CRC碼是否相同。

3 按位計算CRC
對於一個二進制序列數可以表示為式(3-1):
(3-1)
求此二進制序列數的CRC碼時,先乘以 後（既左移16位）,再除以多項式G(X),所得的余數既是所要求的CRC碼。如式(3-2)所示：
(3-2)
可以設： (3-3)
其中 為整數, 為16位二進制余數。將式(3-3)代入式(3-2)得：

(3-4)
再設： (3-5)
其中 為整數, 為16位二進制余數,將式(3-5)代入式(3-4),如上類推,最後得到：
(3-6)
根據CRC的定義,很顯然,十六位二進制數 既是我們要求的CRC碼。
式(3-5)是編程計算CRC的關鍵,它說明計算本位後的CRC碼等於上一位CRC碼乘以2後除以多項式,所得的余數再加上本位值除以多項式所得的余數。由此不難理解下面求CRC碼的C語言程序。*ptr指向發送緩沖區的首位元組,len是要發送的總位元組數,0x1021與多項式有關。
unsigned int cal_crc(unsigned char *ptr, unsigned char len) {
unsigned char i;
unsigned int crc=0;
while(len--!=0) {
for(i=0x80; i!=0; i/=2) {
if((crc&;0x8000)!=0) {crc*=2; crc^=0x1021;} /* 余式CRC乘以2再求CRC */
else crc*=2;
if((*ptr&;i)!=0) crc^=0x1021; /* 再加上本位的CRC */
}
ptr++;
}
return(crc);
}
按位計算CRC雖然代碼簡單,所佔用的內存比較少,但其最大的缺點就是一位一位地計算會佔用很多的處理器處理時間,尤其在高速通訊的場合,這個缺點更是不可容忍。因此下面再介紹一種按位元組查錶快速計算CRC的方法。
4 按位元組計算CRC
不難理解,對於一個二進制序列數可以按位元組表示為式(4-1),其中 為一個位元組(共8位)。
(4-1)
求此二進制序列數的CRC碼時,先乘以 後（既左移16位）,再除以多項式G(X),所得的余數既是所要求的CRC碼。如式(4-2)所示：
（4-2）
可以設： (4-3)
其中 為整數, 為16位二進制余數。將式(4-3)代入式(4-2)得：
（4-4）
因為：
（4-5）
其中 是 的高八位, 是 的低八位。將式（4-5）代入式（4-4）,經整理後得：
（4-6）
再設： (4-7)
其中 為整數, 為16位二進制余數。將式(4-7)代入式(4-6),如上類推,最後得：
(4-8)
很顯然,十六位二進制數 既是我們要求的CRC碼。
式(4-7)是編寫按位元組計算CRC程序的關鍵,它說明計算本位元組後的CRC碼等於上一位元組余式CRC碼的低8位左移8位後,再加上上一位元組CRC右移8位（也既取高8位）和本位元組之和後所求得的CRC碼,如果我們把8位二進制序列數的CRC全部計算出來,放如一個表裡,採用查表法,可以大大提高計算速度。由此不難理解下面按位元組求CRC碼的C語言程序。*ptr指向發送緩沖區的首位元組,len是要發送的總位元組數,CRC余式表是按0x11021多項式求出的。
unsigned int cal_crc(unsigned char *ptr, unsigned char len) {
unsigned int crc;
unsigned char da;
unsigned int crc_ta[256]={ /* CRC余式表 */
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
0x 1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,
0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,
0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,
0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,
0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,
0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,
0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,
0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,
0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,
0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,
0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,
0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,
0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,
0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,
0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,
0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,
0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,
0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,
0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,
0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,
0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
};

crc=0;
while(len--!=0) {
da=(uchar) (crc/256); /* 以8位二進制數的形式暫存CRC的高8位 */
crc<<=8; /* 左移8位,相當於CRC的低8位乘以 */
crc^=crc_ta[da^*ptr]; /* 高8位和當前位元組相加後再查表求CRC ,再加上以前的CRC */
ptr++;
}
return(crc);
}
很顯然,按位元組求CRC時,由於採用了查表法,大大提高了計算速度。但對於廣泛運用的8位微處理器,代碼空間有限,對於要求256個CRC余式表（共512位元組的內存）已經顯得捉襟見肘了,但CRC的計算速度又不可以太慢,因此再介紹下面一種按半位元組求CRC的演算法。
5 按半位元組計算CRC
同樣道理,對於一個二進制序列數可以按位元組表示為式(5-1),其中 為半個位元組(共4位)。
(5-1)
求此二進制序列數的CRC碼時,先乘以 後（既左移16位）,再除以多項式G(X),所得的余數既是所要求的CRC碼。如式(4-2)所示：
（5-2）
可以設： (5-3)
其中 為整數, 為16位二進制余數。將式(5-3)代入式(5-2)得：
（5-4）
因為：
（5-5）
其中 是 的高4位, 是 的低12位。將式（5-5）代入式（5-4）,經整理後得：
（5-6）
再設： (5-7)
其中 為整數, 為16位二進制余數。將式(5-7)代入式(5-6),如上類推,最後得：
(5-8)
很顯然,十六位二進制數 既是我們要求的CRC碼。
式(5-7)是編寫按位元組計算CRC程序的關鍵,它說明計算本位元組後的CRC碼等於上一位元組CRC碼的低12位左移4位後,再加上上一位元組余式CRC右移4位（也既取高4位）和本位元組之和後所求得的CRC碼,如果我們把4位二進制序列數的CRC全部計算出來,放在一個表裡,採用查表法,每個位元組算兩次（半位元組算一次）,可以在速度和內存空間取得均衡。由此不難理解下面按半位元組求CRC碼的C語言程序。*ptr指向發送緩沖區的首位元組,len是要發送的總位元組數,CRC余式表是按0x11021多項式求出的。
unsigned cal_crc(unsigned char *ptr, unsigned char len) {
unsigned int crc;
unsigned char da;
unsigned int crc_ta[16]={ /* CRC余式表 */
0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,
0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
}

crc=0;
while(len--!=0) {
da=((uchar)(crc/256))/16; /* 暫存CRC的高四位 */
crc<<=4; /* CRC右移4位,相當於取CRC的低12位）*/
crc^=crc_ta[da^(*ptr/16)]; /* CRC的高4位和本位元組的前半位元組相加後查表計算CRC,
然後加上上一次CRC的余數 */
da=((uchar)(crc/256))/16; /* 暫存CRC的高4位 */
crc<<=4; /* CRC右移4位, 相當於CRC的低12位） */
crc^=crc_ta[da^(*ptr&;0x0f)]; /* CRC的高4位和本位元組的後半位元組相加後查表計算CRC,
然後再加上上一次CRC的余數 */
ptr++;
}
return(crc);
}

I. 1+1=2在計算機中是怎麼實現的額，從演算法一直追溯到硬體，整個運算過程是如何實現的

貌似我記得是 0001+0001=0010這是電路板的信號模擬。1是有電子0是沒電子。然後模擬出來的結果就是0010也就是2.因為計算機用的是2進制。大概就這樣了。

J. 如何成為一名合格的演算法工程師

BAT企業的演算法工程師是這樣工作的：問題抽象、數據採集和處理、特徵工程、建模訓練調優、模型評估、上線部署。（具體操作可以看阿里演算法專家chris老師的演算法工作流視頻演算法工作流是怎樣的？）而一個演算法工程師真正值錢的地方在於問題抽象和上線部署這兩個。