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

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

一、計數、求和、求階乘等簡單算法?

此類問題都要使用循環，要注意根據問題確定循環變量的初值、終值或結束條件，更要注意用來表示計數、和、階乘的變量的初值。

例：用隨機函數產生100個[0，99]范圍內的隨機整數，統計個位上的數字分別為1，2，3，4，5，6，7，8，9，0的數的個數并打印出來。

本題使用數組來處理，用數組a[100]存放產生的確100個隨機整數，數組x[10]來存放個位上的數字分別為1，2，3，4，5，6，7，8，9，0的數的個數。即個位是1的個數存放在x[1]中，個位是2的個數存放在x[2]中，……個位是0的個數存放在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("
");
}

二、求兩個整數的最大公約數、最小公倍數?

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

(1) 對于已知兩數m，n，使得m>n；

(2) m除以n得余數r；

(3) 若r=0，則n為求得的最大公約數，算法結束；否則執行(4)；

(4) m←n，n←r，再重復執行(2)。

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

14 6 2

6 2 0
?

?

void main()
{ int nm,r,n,m,t;
printf("please input two numbers:
");
scanf("%d,%d",&m,&n);
nm=n*m;
if (m
{ t="n"; n="m"; m="t"; }
r=m%n;
while (r!=0)
{ m="n"; n="r"; r="m"%n; }
printf("最大公約數:%d
",n);
printf("最小公倍數:%d
",nm/n);
}

三、判斷素數

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

?

void main()
{ int m,i,k;
printf("please input a number:
");
scanf("%d",&m);
k=sqrt(m);
for(i=2;i
if(m%i==0) break;
if(i>=k)
printf("該數是素數");
else
printf("該數不是素數");
}
將其寫成一函數,若為素數返回1，不是則返回0
int prime( m%)
{int i,k;
k=sqrt(m);
for(i=2;i
if(m%i==0) return 0;
return 1;
}

?

四、驗證哥德巴赫猜想?

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

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

利用上面的prime函數，驗證哥德巴赫猜想的程序代碼如下：

?

#include "math.h"
int prime(int m)
{ int i,k;
k=sqrt(m);
for(i=2;i
if(m%i==0) break;
if(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("驗證成功!");
break;
}
}

?

五、排序問題?

1．選擇法排序（升序）

基本思想：

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

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

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

程序代碼如下：

?

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．冒泡法排序（升序）?

基本思想：(將相鄰兩個數比較，小的調到前頭)

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

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

3）依次類推，n個數共進行n-1趟比較，在第j趟中要進行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．合并法排序（將兩個有序數組A、B合并成另一個有序的數組C，升序）?

基本思想：

1）先在A、B數組中各取第一個元素進行比較，將小的元素放入C數組；

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

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

程序段如下：

?

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]
{ c[ic]=a[ia];ia++;}
else
{ c[ic]=b[ib];ib++;}
ic++;
}
while(ia<=9)
{ c[ic]=a[ia];
ia++;ic++;
}
while(ib<=9)
{ c[ic]=b[ib];
b++;ic++;
}
for(i=0;i<20;i++)
printf("%d
",c);
}

?

六、查找問題?

① 順序查找法（在一列數中查找某數x）?

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

?

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);
}

?

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

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

?

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);
}

?

七、二分法

在一個數組中，知道一個數值，想確定他在數組中的位置下標，如數組：A[5] = {1，2，6，7，9};我知道其中的值為6，那么他的下標位置就是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 ;
}
}
}

?

八、限幅濾波法

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

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

下面是限幅濾波程序：( A 值可根據實際情況調整，value 為有效值 ,new_value 為當前采樣值濾波程序返回有效的實際值 )

?

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

?

九、中位值濾波法

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

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

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

下面是中位值濾波程序：

?

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

?

十.算術平均濾波法

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

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

編寫算術平均濾波法程序時嚴格注意:

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

二.選取適當的數據格式 ,也就是說采用定點數還是采用浮點數。其程序如下所示：

?

#define N 12
char filter()
{int   sum = 0，count;
for ( count=0;count
{  sum+=get_ad();    delay();}
return (char)(sum/N);
}

?

十一、遞推平均濾波法

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

?

#define N 12
char 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
sum = value_buf[count];
return (char)(sum/N);
}

?

十二、一階滯后濾波法

優點：對周期性干擾具有良好的抑制作用,適用于波動頻率較高的場合；

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

?

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

?

十三、PID控制算法

在過程控制中，按偏差的比例（P）、積分（I）和微分（D）進行控制的PID控制器（亦稱PID調節器）是應用最為廣泛的一種自動控制器;

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

PID調節規律是連續系統動態品質校正的一種有效方法，它的參數整定方式簡便，結構改變靈活（PI、PD、…）。

一? 模擬PID調節器

PID調節器各校正環節的作用：

比例環節：即時成比例地反應控制系統的偏差信號e(t)，偏差一旦產生，調節器立即產生控制作用以減小偏差；

積分環節：主要用于消除靜差，提高系統的無差度。積分時間常數TI越大，積分作用越弱，反之則越強；

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

PID調節器是一種線性調節器，它將給定值r(t)與實際輸出值c(t)的偏差的比例(P)、積分(I)、微分(D)通過線性組合構成控制量，對控制對象進行控制。

程序片段如下：

?

#include
#include
typedef struct PID {
double SetPoint;     // 設定目標Desired value
double Proportion;    // 比例常數Proportional Const
double Integral;      // 積分常數Integral Const
double Derivative;    // 微分常數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 );
}
}

?

十四、開根號算法

單片機開平方的快速算法

因為工作的需要，要在單片機上實現開根號的操作。目前開平方的方法大部分是用牛頓迭代法。我在查了一些資料以后找到了一個比牛頓迭代法更加快速的方法。不敢獨享，介紹給大家，希望會有些幫助。

1.原理

因為排版的原因，用pow(X,Y)表示X的Y次冪，用B[0]，B[1]，...，B[m-1]表示一個序列，其中[x]為下標。

假設：

B[x],b[x]都是二進制序列,取值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]可以根據M的最高位B[m-1]直接求得。

設 m 已知,因為 pow(2, m-1) <= M <= pow(2, m)，所以 pow(2, (m-1)/2) <= N <= pow(2, m/2)

如果 m 是奇數，設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 是偶數，設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]決定。

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

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

因為b[n-1]=1，假設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)),

然后比較余數M[1]是否大于等于 (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4)。這種比較只須根據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), 則假設有效，b[n-2] = 1；

余數 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), 則假設無效，b[n-2] = 0；余數 M[2] = M[1]。

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

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

3. 實現代碼

這里給出實現32位無符號整數開方得到16位無符號整數的C語言代碼。
?

?

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

?

審核編輯：劉清