算法（Algorithm）：計算機(jī)解題的基本思想方法和步驟。

算法的描述：是對要解決一個問題或要完成一項(xiàng)任務(wù)所采取的方法和步驟的描述，包括需要什么數(shù)據(jù)（輸入什么數(shù)據(jù)、輸出什么結(jié)果）、采用什么結(jié)構(gòu)、使用什么語句以及如何安排這些語句等。通常使用自然語言、結(jié)構(gòu)化流程圖、偽代碼等來描述算法。

一、計數(shù)、求和、求階乘等簡單算法?

此類問題都要使用循環(huán)，要注意根據(jù)問題確定循環(huán)變量的初值、終值或結(jié)束條件，更要注意用來表示計數(shù)、和、階乘的變量的初值。?

例：用隨機(jī)函數(shù)產(chǎn)生100個[0，99]范圍內(nèi)的隨機(jī)整數(shù)，統(tǒng)計個位上的數(shù)字分別為1，2，3，4，5，6，7，8，9，0的數(shù)的個數(shù)并打印出來。?

本題使用數(shù)組來處理，用數(shù)組a[100]存放產(chǎn)生的確100個隨機(jī)整數(shù)，數(shù)組x[10]來存放個位上的數(shù)字分別為1，2，3，4，5，6，7，8，9，0的數(shù)的個數(shù)。即個位是1的個數(shù)存放在x[1]中，個位是2的個數(shù)存放在x[2]中，……個位是0的個數(shù)存放在x[10]。?

?

void main() { int a[101],x[11],i,p; for(i=0;i<=11;i++) x=0; for(i=1;i<=100;i++) { a=rand() % 100; printf("%4d",a); if(i%10==0)printf("
"); } for(i=1;i<=100;i++) { p="a"%10; if(p==0) p="10"; x[p]=x[p]+1; } for(i=1;i<=10;i++) { p="i"; if(i==10) p="0"; printf("%d,%d
",p,x); } printf("
"); }

?

二、求兩個整數(shù)的最大公約數(shù)、最小公倍數(shù)?

分析：求最大公約數(shù)的算法思想：(最小公倍數(shù)=兩個整數(shù)之積/最大公約數(shù))?

(1) 對于已知兩數(shù)m，n，使得m>n；?
(2) m除以n得余數(shù)r；?
(3) 若r=0，則n為求得的最大公約數(shù)，算法結(jié)束；否則執(zhí)行(4)；?
(4) m←n，n←r，再重復(fù)執(zhí)行(2)。?

例如: 求 m="14" ,n=6 的最大公約數(shù). m n r

?

void main() { int nm,r,n,m,t; printf("please input two numbers:
"); scanf("%d,%d",&m,&n); nm=n*m; if (m

	?

	三、判斷素數(shù)?

	只能被1或本身整除的數(shù)稱為素數(shù) 基本思想：把m作為被除數(shù)，將2—INT（ ）作為除數(shù)，如果都除不盡，m就是素數(shù)，否則就不是。（可用以下程序段實(shí)現(xiàn)）?

	?
void main() { int m,i,k; printf("please input a number:
"); scanf("%d",&m); k=sqrt(m); for(i=2;i=k) printf("該數(shù)是素數(shù)"); else printf("該數(shù)不是素數(shù)"); }

	?

	將其寫成一函數(shù),若為素數(shù)返回1，不是則返回0?

	?
int?prime(?m%)?{int i,k; k=sqrt(m); for(i=2;i

	?

	

	四、驗(yàn)證哥德巴赫猜想?

	（任意一個大于等于6的偶數(shù)都可以分解為兩個素數(shù)之和）?

	基本思想：n為大于等于6的任一偶數(shù)，可分解為n1和n2兩個數(shù)，分別檢查n1和n2是否為素數(shù)，如都是，則為一組解。如n1不是素數(shù)，就不必再檢查n2是否素數(shù)。先從n1=3開始，檢驗(yàn)n1和n2（n2=N-n1）是否素數(shù)。然后使n1+2 再檢驗(yàn)n1、n2是否素數(shù)，… 直到n1=n/2為止。?

	利用上面的prime函數(shù)，驗(yàn)證哥德巴赫猜想的程序代碼如下：

	?
#include "math.h" int prime(int m) { int i,k; k=sqrt(m); for(i=2;i=k) return 1; else return 0; } main() { int x,i; printf("please input a even number(>=6):
"); scanf("%d",&x); if (x<6||x%2!=0) printf("data error!
"); else for(i=2;i<=x/2;i++) if (prime(i)&&prime(x-i)) { printf("%d+%d
",i,x-i); printf("驗(yàn)證成功!"); break; } }

	?

	
五、排序問題?

	1．選擇法排序（升序）?

	基本思想：?

	1）對有n個數(shù)的序列（存放在數(shù)組a(n)中），從中選出最小的數(shù)，與第1個數(shù)交換位置；?

	2）除第1 個數(shù)外，其余n-1個數(shù)中選最小的數(shù)，與第2個數(shù)交換位置；?

	3）依次類推，選擇了n-1次后，這個數(shù)列已按升序排列。?

	程序代碼如下：?

	?
void main() { int i,j,imin,s,a[10]; printf("
 input 10 numbers:
"); for(i=0;i<10;i++) scanf("%d",&a); for(i=0;i<9;i++) { imin="i"; for(j=i+1;j<10;j++) if(a[imin]>a[j]) imin="j"; if(i!=imin) {s=a; a=a[imin]; a[imin]=s; } printf("%d
",a); } }

	?

	2．冒泡法排序（升序）?

	基本思想：(將相鄰兩個數(shù)比較，小的調(diào)到前頭)?

	1）有n個數(shù)（存放在數(shù)組a(n)中），第一趟將每相鄰兩個數(shù)比較，小的調(diào)到前頭，經(jīng)n-1次兩兩相鄰比較后，最大的數(shù)已“沉底”，放在最后一個位置，小數(shù)上升“浮起”；?

	2）第二趟對余下的n-1個數(shù)（最大的數(shù)已“沉底”）按上法比較，經(jīng)n-2次兩兩相鄰比較后得次大的數(shù)；?

	3）依次類推，n個數(shù)共進(jìn)行n-1趟比較，在第j趟中要進(jìn)行n-j次兩兩比較。?

	程序段如下

	?
void main() { int a[10]; int i,j,t; printf("input 10 numbers
"); for(i=0;i<10;i++) scanf("%d",&a); printf("
"); for(j=0;j<=8;j++) for(i=0;i<9-j;i++) if(a>a[i+1]) {t=a;a=a[i+1];a[i+1]=t;} printf("the sorted numbers:
"); for(i=0;i<10;i++) printf("%d
",a); }

	?

	

	3．合并法排序（將兩個有序數(shù)組A、B合并成另一個有序的數(shù)組C，升序）?

	基本思想：?

	1）先在A、B數(shù)組中各取第一個元素進(jìn)行比較，將小的元素放入C數(shù)組；?

	2）取小的元素所在數(shù)組的下一個元素與另一數(shù)組中上次比較后較大的元素比較，重復(fù)上述比較過程，直到某個數(shù)組被先排完；?

	3）將另一個數(shù)組剩余元素抄入C數(shù)組，合并排序完成。?

	程序段如下：?

	?
void main() { int a[10],b[10],c[20],i,ia,ib,ic; printf("please input the first array:
"); for(i=0;i<10;i++) scanf("%d",&a); for(i=0;i<10;i++) scanf("%d",&b); printf("
"); ia=0;ib=0;ic=0; while(ia<10&&ib<10) { if(a[ia]

	?

	
六、查找問題?

	順序查找法（在一列數(shù)中查找某數(shù)x）?

	基本思想：一列數(shù)放在數(shù)組a[1]---a[n]中，待查找的數(shù)放在x 中，把x與a數(shù)組中的元素從頭到尾一一進(jìn)行比較查找。用變量p表示a數(shù)組元素下標(biāo)，p初值為1，使x與a[p]比較，如果x不等于a[p]，則使p=p+1，不斷重復(fù)這個過程；一旦x等于a[p]則退出循環(huán)；另外，如果p大于數(shù)組長度，循環(huán)也應(yīng)該停止。（這個過程可由下語句實(shí)現(xiàn)）

	?
void main() { int a[10],p,x,i; printf("please input the array:
"); for(i=0;i<10;i++) scanf("%d",&a); printf("please input the number you want find:
"); scanf("%d",&x); printf("
"); p=0; while(x!=a[p]&&p<10) p++; if(p>=10) printf("the number is not found!
"); else printf("the number is found the no%d!
",p); }

	?

	思考：將上面程序改寫一查找函數(shù)Find，若找到則返回下標(biāo)值，找不到返回-1

	②基本思想：一列數(shù)放在數(shù)組a[1]---a[n]中，待查找的關(guān)鍵值為key，把key與a數(shù)組中的元素從頭到尾一一進(jìn)行比較查找，若相同，查找成功，若找不到，則查找失敗。(查找子過程如下。index：存放找到元素的下標(biāo)。)?

	?
void main() { int a[10],index,x,i; printf("please input the array:
"); for(i=0;i<10;i++) scanf("%d",&a); printf("please input the number you want find:
"); scanf("%d",&x); printf("
"); index=-1; for(i=0;i<10;i++) if(x==a) { index="i"; break; } if(index==-1) printf("the number is not found!
"); else printf("the number is found the no%d!
",index); }

	?

	
七、二分法

	在一個數(shù)組中，知道一個數(shù)值，想確定他在數(shù)組中的位置下標(biāo)，如數(shù)組：A[5] = {1，2，6，7，9};我知道其中的值為6，那么他的下標(biāo)位置就是3。

	?
int Dichotomy(int *ucData, int long, int num){   int iDataLow  = 0 ;   int iDataHigh = num - 1;   int iDataMIDDLE;   while (iDataLow <= iDataHigh)   {     iDataMIDDLE = (iDataHigh + iDataLow)/2;     i f (ucData[iDataMIDDLE] > long)     {       iDataHigh = iDataMIDDLE - 1 ;     }          else if (ucData[iDataMIDDLE] < long)   {   iDataLow = iDataMIDDLE + 1 ;  }  else{   return iDataMIDDLE ;  }}}

	?

	
八、限幅濾波法

	對于隨機(jī)干擾 , 限幅濾波是一種有效的方法；

	基本方法：比較相鄰n 和 n - 1時刻的兩個采樣值y(n)和 y(n – 1)，根據(jù)經(jīng)驗(yàn)確定兩次采樣允許的最大偏差。如果兩次采樣值的差值超過最大偏差范圍 ,認(rèn)為發(fā)生可隨機(jī)干擾 ,并認(rèn)為后一次采樣值y(n)為非法值 ,應(yīng)予刪除 ,刪除y(n)后 ,可用y(n – 1) 代替y(n)；若未超過所允許的最大偏差范圍 ,則認(rèn)為本次采樣值有效。

	下面是限幅濾波程序：( A 值可根據(jù)實(shí)際情況調(diào)整，value 為有效值 ,new_value 為當(dāng)前采樣值濾波程序返回有效的實(shí)際值 )

	?
#define A 10char value;char filter(){   char new_value;    new_value = get_ad();    if ( ( new_value - value > A ) || ( value - new_value > A ))  return value;    return new_value;}

	?

	
九、中位值濾波法

	中位值濾波法能有效克服偶然因素引起的波動或采樣不穩(wěn)定引起的誤碼等脈沖干擾；

	對溫度 液位等緩慢變化的被測參數(shù)用此法能收到良好的濾波效果 ,但是對于流量壓力等快速變化的參數(shù)一般不宜采用中位值濾波法；

	基本方法：對某一被測參數(shù)連續(xù)采樣 n次(一般 n 取奇數(shù)) ,然后再把采樣值按大小排列 ,取中間值為本次采樣值。

	下面是中位值濾波程序：

	?
#define N   11char filter(){  char value_buf[N]， count,i,j,temp;    for ( count=0;countvalue_buf[i+1] )             {temp = value_buf; value_buf = value_buf[i+1]; value_buf[i+1] = temp;  }         }    }    return value_buf[(N-1)/2];}

	?

	
十.算術(shù)平均濾波法

	算術(shù)平均濾波法適用于對一般的具有隨機(jī)干擾的信號進(jìn)行濾波。這種信號的特點(diǎn)是信號本身在某一數(shù)值范圍附近上下波動 ,如測量流量、 液位；

	基本方法：按輸入的N 個采樣數(shù)據(jù) ,尋找這樣一個 Y ,使得 Y 與各個采樣值之間的偏差的平方和最小。

	編寫算術(shù)平均濾波法程序時嚴(yán)格注意:

	一.為了加快數(shù)據(jù)測量的速度 ,可采用先測量數(shù)據(jù) 存放在存儲器中 ,測完 N 點(diǎn)后 ,再對 N 個數(shù)據(jù)進(jìn)行平均值計算;

	二.選取適當(dāng)?shù)臄?shù)據(jù)格式 ,也就是說采用定點(diǎn)數(shù)還是采用浮點(diǎn)數(shù)。其程序如下所示：

	?
#define N 12char filter(){int   sum = 0，count;      for ( count=0;count

	?

	
十一、遞推平均濾波法

	基本方法：采用隊列作為測量數(shù)據(jù)存儲器 , ? 設(shè)隊列的長度為 N ,每進(jìn)行一次測量 ,把測量結(jié)果放于隊尾 ,而扔掉原來隊首的一個數(shù)據(jù) ,這樣在隊列中始終就有 N 個 “最新” 的數(shù)據(jù)。當(dāng)計算平均值時 ,只要把隊列中的 N 個數(shù)據(jù)進(jìn)行算數(shù)平均 ,就可得到新的算數(shù)平均值。這樣每進(jìn)行一次測量 ,就可得到一個新的算術(shù)平均值。

	?
#define N 12char value_buf[N]，i=0;char filter(){ char count; int   sum=0;  value_buf[i++] = get_ad();if ( i == N )    i = 0;for ( count=0;count

	?

	
十二、一階滯后濾波法

	優(yōu)點(diǎn)：對周期性干擾具有良好的抑制作用,適用于波動頻率較高的場合；

	缺點(diǎn)：相位滯后，靈敏度低.滯后程度取決于a值大小.不能消除濾波頻率高于采樣頻率的1/2的干擾信號。程序如下：

	?
#define a 50char value;char filter(){ char   new_value;   new_value = get_ad();   return (100-a)*value + a*new_value;}

	?

	
十三、PID控制算法

	在過程控制中，按偏差的比例（P）、積分（I）和微分（D）進(jìn)行控制的PID控制器（亦稱PID調(diào)節(jié)器）是應(yīng)用最為廣泛的一種自動控制器;

	對于過程控制的典型對象──“一階滯后＋純滯后”與“二階滯后＋純滯后”的控制對象，PID控制器是一種最優(yōu)控制;

	PID調(diào)節(jié)規(guī)律是連續(xù)系統(tǒng)動態(tài)品質(zhì)校正的一種有效方法，它的參數(shù)整定方式簡便，結(jié)構(gòu)改變靈活（PI、PD、…）。

	一? 模擬PID調(diào)節(jié)器

	

	模擬PID控制系統(tǒng)原理框圖


	PID調(diào)節(jié)器各校正環(huán)節(jié)的作用：

	比例環(huán)節(jié)：即時成比例地反應(yīng)控制系統(tǒng)的偏差信號e(t)，偏差一旦產(chǎn)生，調(diào)節(jié)器立即產(chǎn)生控制作用以減小偏差；

	積分環(huán)節(jié)：主要用于消除靜差，提高系統(tǒng)的無差度。積分時間常數(shù)TI越大，積分作用越弱，反之則越強(qiáng)；

	微分環(huán)節(jié)：能反應(yīng)偏差信號的變化趨勢(變化速率)，并能在偏差信號的值變得太大之前，在系統(tǒng)中引入一個有效的早期修正信號，從而加快系統(tǒng)的動作速度，減小調(diào)節(jié)時間。

	PID調(diào)節(jié)器是一種線性調(diào)節(jié)器，它將給定值r(t)與實(shí)際輸出值c(t)的偏差的比例(P)、積分(I)、微分(D)通過線性組合構(gòu)成控制量，對控制對象進(jìn)行控制。

	?

	

	

	數(shù)字PID控制器的差分方程：

	

	

	程序片段如下：

	?
#include #include              typedef struct PID { double SetPoint;     // 設(shè)定目標(biāo)Desired value double Proportion;    // 比例常數(shù)Proportional Const double Integral;      // 積分常數(shù)Integral Const double Derivative;    // 微分常數(shù)Derivative Const double LastError;    // Error[-1] 
double PrevError;    // Error[-2] double SumError;   // Sums of Errors } PID; 
主程序：double sensor (void) { return 100.0; } void actuator(double rDelta) {} void main(void) { PID sPID; double rOut; double rIn; PIDInit ( &sPID ); sPID.Proportion = 0.5；sPID.Derivative = 0.0; sPID.SetPoint = 100.0; 
for (;;) { rIn = sensor (); rOut = PIDCalc ( &sPID,rIn ); actuator ( rOut ); }}

	?

	
十四、開根號算法

	單片機(jī)開平方的快速算法

	因?yàn)楣ぷ鞯男枰?，要在單片機(jī)上實(shí)現(xiàn)開根號的操作。目前開平方的方法大部分是用牛頓迭代法。我在查了一些資料以后找到了一個比牛頓迭代法更加快速的方法。不敢獨(dú)享，介紹給大家，希望會有些幫助。


	1.原理

	因?yàn)榕虐娴脑?，用pow(X,Y)表示X的Y次冪，用B[0]，B[1]，...，B[m-1]表示一個序列，其中[x]為下標(biāo)。


	假設(shè)：

	B[x],b[x]都是二進(jìn)制序列,取值0或1。

	M = B[m-1]*pow(2,m-1) + B[m-2]*pow(2,m-2) + ... + B[1]*pow(2,1) + B[0]*pow(2,0)

	N = b[n-1]*pow(2,n-1) + b[n-2]*pow(2,n-2) + ... + b[1]*pow(2,1) + n[0]*pow(2,0)

	pow(N,2) = M


	?(1) N的最高位b[n-1]可以根據(jù)M的最高位B[m-1]直接求得。

	設(shè) m 已知,因?yàn)?pow(2, m-1) <= M <= pow(2, m)，所以 pow(2, (m-1)/2) <= N <= pow(2, m/2)

	如果 m 是奇數(shù)，設(shè)m=2*k+1,

	那么 pow(2,k) <= N < pow(2, 1/2+k) < pow(2, k+1),

	n-1=k, n=k+1=(m+1)/2

	如果 m 是偶數(shù)，設(shè)m=2k,

	那么 pow(2,k) > N >= pow(2, k-1/2) > pow(2, k-1),

	n-1=k-1,n=k=m/2

	所以b[n-1]完全由B[m-1]決定。

	余數(shù) M[1] = M - b[n-1]*pow(2, 2*n-2)


	?(2) N的次高位b[n-2]可以采用試探法來確定。

	因?yàn)閎[n-1]=1，假設(shè)b[n-2]=1，則 pow(b[n-1]*pow(2,n-1) + b[n-1]*pow(2,n-2), 2) = b[n-1]*pow(2,2*n-2) + (b[n-1]*pow(2,2*n-2) + b[n-2]*pow(2,2*n-4)),

	然后比較余數(shù)M[1]是否大于等于 (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4)。這種比較只須根據(jù)B[m-1]、B[m-2]、...、B[2*n-4]便可做出判斷，其余低位不做比較。

	若 M[1] >= (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4), 則假設(shè)有效，b[n-2] = 1；

	余數(shù) M[2] = M[1] - pow(pow(2,n-1)*b[n-1] + pow(2,n-2)*b[n-2], 2) = M[1] - (pow(2,2)+1)*pow(2,2*n-4)；

	若 M[1] < (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4), 則假設(shè)無效，b[n-2] = 0；余數(shù) M[2] = M[1]。


	?(3) 同理，可以從高位到低位逐位求出M的平方根N的各位。


	使用這種算法計算32位數(shù)的平方根時最多只須比較16次，而且每次比較時不必把M的各位逐一比較，尤其是開始時比較的位數(shù)很少，所以消耗的時間遠(yuǎn)低于牛頓迭代法。


	3. 實(shí)現(xiàn)代碼

	這里給出實(shí)現(xiàn)32位無符號整數(shù)開方得到16位無符號整數(shù)的C語言代碼。

	?
/****************************************//*Function: 開根號處理                  *//*入口參數(shù)：被開方數(shù)，長整型            *//*出口參數(shù)：開方結(jié)果，整型              *//****************************************/unsigned int sqrt_16(unsigned long M){     unsigned int N, i;    unsigned long tmp, ttp;   // 結(jié)果、循環(huán)計數(shù)    if (M == 0)               // 被開方數(shù)，開方結(jié)果也為0        return 0;
    N = 0;
    tmp = (M >> 30);          // 獲取最高位：B[m-1]    M <<= 2;    if (tmp > 1)              // 最高位為1    {        N ++;                 // 結(jié)果當(dāng)前位為1，否則為默認(rèn)的0        tmp -= N;    }
    for (i=15; i>0; i--)      // 求剩余的15位    {        N <<= 1;              // 左移一位
        tmp <<= 2;        tmp += (M >> 30);     // 假設(shè)
        ttp = N;        ttp = (ttp<<1)+1;
        M <<= 2;        if (tmp >= ttp)       // 假設(shè)成立        {            tmp -= ttp;            N ++;????????}????????    }
    return N;}　　

	? ? ? 審核編輯：彭靜