单片机 算法_单片机算法 - CSDN
  • 单片机常用算法

    2018-03-22 08:53:13
    算法的描述:是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述,包括需要什么数据(输入什么数据、输出什么结果)、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程.....

    本文转载自:http://home.eeworld.com.cn/my/space-uid-554974-blogid-255035.html

    算法(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("\n");
    }
    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\n",p,x);
    }
    printf("\n");
    }

    二、求两个整数的最大公约数、最小公倍数
      分析:求最大公约数的算法思想:(最小公倍数=两个整数之积/最大公约数)
    (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:\n");
    scanf("%d,%d",&m,&n);
    nm=n*m;
    if (m<n)
    { t="n"; n="m"; m="t"; }
    r=m%n;
    while (r!=0)
    { m="n"; n="r"; r="m"%n; }
    printf("最大公约数:%d\n",n);
    printf("最小公倍数:%d\n",nm/n);
    }

    三、判断素数
      只能被1或本身整除的数称为素数 基本思想:把m作为被除数,将2—INT( )作为除数,如果都除不尽,m就是素数,否则就不是。(可用以下程序段实现)
    void main()
    { int m,i,k;
    printf("please input a number:\n");
    scanf("%d",&m);
    k=sqrt(m);
    for(i=2;i<k;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<k;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<k;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):\n");
    scanf("%d",&x);
    if (x<6||x%2!=0)
    printf("data error!\n");
    else
    for(i=2;i<=x/2;i++)
    if (prime(i)&&prime(x-i))
    {
    printf("%d+%d\n",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("\n input 10 numbers:\n");
    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\n",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\n");
    for(i=0;i<10;i++)
    scanf("%d",&a);
    printf("\n");
    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:\n");
    for(i=0;i<10;i++)
    printf("%d\n",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:\n");
    for(i=0;i<10;i++)
    scanf("%d",&a);
    for(i=0;i<10;i++)
    scanf("%d",&b);
    printf("\n");
    ia=0;ib=0;ic=0;
    while(ia<10&&ib<10)
    { if(a[ia]<b[ib])
    { 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\n",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:\n");
    for(i=0;i<10;i++)
    scanf("%d",&a);
    printf("please input the number you want find:\n");
    scanf("%d",&x);
    printf("\n");
    p=0;
    while(x!=a[p]&&p<10)
    p++;
    if(p>=10)
    printf("the number is not found!\n");
    else
    printf("the number is found the no%d!\n",p);
    }
    思考:将上面程序改写一查找函数Find,若找到则返回下标值,找不到返回-1
    ②基本思想:一列数放在数组a[1]---a[n]中,待查找的关键值为key,把key与a数组中的元素从头到尾一一进行比较查找,若相同,查找成功,若找不到,则查找失败。(查找子过程如下。index:存放找到元素的下标。)
    void main()
    { int a[10],index,x,i;
    printf("please input the array:\n");
    for(i=0;i<10;i++)
    scanf("%d",&a);
    printf("please input the number you want find:\n");
    scanf("%d",&x);
    printf("\n");
    index=-1;
    for(i=0;i<10;i++)
    if(x==a)
    { index="i"; break;
    }
    if(index==-1)
    printf("the number is not found!\n");
    else
    printf("the number is found the no%d!\n",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<N;count++)
        {  value_buf[count] = get_ad();    delay();   }
        for (j=0;j<N-1;j++)
        {  for (i=0;i<N-j;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<N;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<N;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控制系统原理框图


    PID调节器各校正环节的作用:
    比例环节:即时成比例地反应控制系统的偏差信号e(t),偏差一旦产生,调节器立即产生控制作用以减小偏差;
    积分环节:主要用于消除静差,提高系统的无差度。积分时间常数TI越大,积分作用越弱,反之则越强;
    微分环节:能反应偏差信号的变化趋势(变化速率),并能在偏差信号的值变得太大之前,在系统中引入一个有效的早期修正信号,从而加快系统的动作速度,减小调节时间。
           PID调节器是一种线性调节器,它将给定值r(t)与实际输出值c(t)的偏差的比例(P)、积分(I)、微分(D)通过线性组合构成控制量,对控制对象进行控制。











    程序片段如下:
    #include <reg52.h>
    #include <string.h>            
    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;
    }


    展开全文
  • 连接:http://bbs.21ic.com/icview-170880-1-1.html -------------------------------------------------以下为原文 ------------------- 连接:...单片机大多资源小,算法占用

    连接:http://bbs.21ic.com/icview-170880-1-1.html

    -------------------------------------------------以下为原文 -------------------

    连接:http://bbs.21ic.com/icview-170880-1-1.html

     

    单片机大多资源小,算法占用的资源越小越好,现在介绍就是一个占用很小资源的算法,这个算法是本人在进行扫描仪设计,实现灰度转二值时实现动态阈值,当时为了跟踪灰度等级的变化,需要一个灰度积分跟踪电路,开始使用一个电容积分电路,用灰度信号对电容充电,放电时以该电容电压的比例进行,实现对输入信号的跟踪,但用电容的电路设计比较复杂。过后发现这种比例放电的思想用软件实现非常简单,且具有积分、微分的作用。
    具体公式如下:
           SUM=SUM-SUM/n+S 
           其中:S为采样值,SUM为保存值,n是放电比例、最好选2的幂次数,单片机移位即可,不需要做除法,跟随后得到的值为SUM/nSUM注意不溢出,预留的容量为采样数最大值的n倍,初始化时如果是跟踪一段时间后使用,可以是任何值,否则可以用采样值乘n初始化。使用值为SUM/n(下文中SA),实现SUM/nS的跟踪。还有一个关键是计算周期T,即多长时间进行一次。
    一、积分作用:
    1.平滑滤波(滑动平均滤波)
    由公式中可以看出,每次采样、计算后,当前采样的影响对SUM/n只有1/n,而且采到的值随次数的增加影响越来越小直至没有,相关性逐渐减弱,而且是连续相关。如果计算周期与采样周期相同,使用计算后的值对干扰有n倍的抑制,即积分的平滑滤波作用,如1ms采样一次,同时运算一次,
    则使用值SA=SUM/n为抑制干扰的结果,且同样是1ms给出一个结果,使用两个变量实现平滑滤波,并且是即时使用的,与采样几次平均的平滑不同。



     

     

    2.动态阈值
    在很多应用中需要动态阈值,比如触摸按键的键阈值门限,血压计的心率检出,前面提到的灰度转二值黑白图像等(灰度转二值因为扫描速度2.5Mbyte/S,不能使用软件运算,但可以使用可编程逻辑实现)。动态阈值是对信号积分后得到的低频变化再与基本门限相加在触摸按键中增加动态阈值可以提高其适应性和可靠性。关键是根据按键反应时间和按键间隔确定按键积分参数,跟踪速度,n、T越大跟踪的越慢,积分效果越好。
     

    3.锁相作用:把上边的积分运算,用于对时间上周期的信号,例如根据过零触发信号锁定交流电源周期,使用两次T时间不同,其它相同的运算,由于T不同,跟踪速度不同,当两次运算的结果相等时可以确认为锁定,这时得到的是准确的电源周期值,而相位偏差也很小。

    二、微分作用:
    公式中的SA趋近采样值S,如果S是线性的,SA的值是可控滞后于S,那么运算的间隔时间T不同,得到的跟踪曲线的滞后特性不同,这种滞后特性的差和间隔时间就是微分特性,表示曲线的变化规律。如电热水壶,温度的变化相当于采样时间是还相当慢的,局部可以作为线性变化来处理。下边以设计电热水壶的过程来说明微分作用。
    电热水壶出口一直使用蒸汽开关这种需要交专利费的方式。不使用蒸汽开关检测压力只能使用热敏器件检测温度。
    温度检测的环境要求:
    1.        海拔高度不同的地区水开的温度不同。
    2.        热敏器件的误差较大,必须克服,否则可生产性不足。
    3.        环境温度不同,电源电压不同,装水量不同。
    由要求1、2决定检测温度不能判别水开与否,需要检测温度的变化率,但温度变化率的判别又和要求3相关,下边曲线图为热水器的加热曲线。蓝线为即时温度,橙色为一次运算后的曲线。

    图中加热过程中间添加了冷水,曲线有一段下降,过后的加热过程两个曲线有个差异滞后,同一个时间的两个曲线差表示了加热效率的变化,其中最大的加热效率体现了环境温度不同,电源电压不同,装水量不同的综合效果。由于滞后的时间可以通过计算周期T来调整,知道滞后时间又有相减的差,这就是微分效应,加热过程整个就是效率的变化过程。我们可以通过1秒钟计算一次,2秒钟计算一次,加上原始数据得到三个曲线,效率的变化一目了然。
            第一次的水开检测使用效率的方法,同时也会得到水开时的温度检测值,微分特性本身是可以预知变化趋势的,如果1秒钟计算一次,用当前检测值减去这次计算的结果,这个差与当前值相加,就可以做为当前1秒后的结果,也就是预知1秒后加热的检测值,结合第一次得到的水开温度检测值,以后的水开检测就有两个判断条件。

     

    ---------------------------------------------- 以下为匠人的分析-----------------------------

    拨开迷雾看真相,作者的这个算法,本质上,就是一阶滤波(低通滤波)。

    引用作者原来的公式

    SUM=SUM-SUM/n+S
    首先点破一下,等号前面的SUM代表的是本次运算结果,而等号后面的SUM代表的是上次运算结果。

    且看匠人如何推导: 
    设:
    SUM=A
    SUM/n=B=本次滤波结果
    1/n=a (一阶滤波系数)
    S=本次新采样值

    则:
    A=nB
    B=A/n


    另外:
    A代表本次值
    A’B’ 代表上次值

    作者原公式逐步推导:
    原始:SUM=SUM-SUM/n+S
    1步:A=A’ – A’/n +S
    2步:nB=nB’ – B’ +S
    3步:B= (nB’ – B’ +S)/n
    4步:B=B’ –B’/n +S/n
    5步:B=1- 1/nB’ + 1/n*S
    6步:B= 1-aB’+ a *S

    推导到最后一步,是不是很眼熟啦?
    呵呵,这就是经典的一阶滤波(低通滤波)的标准公式了

    展开全文
  • 单片机算法FFT

    2015-09-02 19:28:42
    FFT算法的解释
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    作 者:韩 昊
    知 乎:Heinrich
    微 博:@花生油工人
    知乎专栏:与时间无关的故事
     
    谨以此文献给大连海事大学的吴楠老师,柳晓鸣老师,王新年老师以及张晶泊老师。
     
    转载的同学请保留上面这句话,谢谢。如果还能保留文章来源就更感激不尽了。
     
    ——更新于2014.6.6,想直接看更新的同学可以直接跳到第四章————

    我保证这篇文章和你以前看过的所有文章都不同,这是 2012 年还在果壳的时候写的,但是当时没有来得及写完就出国了……于是拖了两年,嗯,我是拖延症患者……

    这篇文章的核心思想就是:

    要让读者在不看任何数学公式的情况下理解傅里叶分析。

    傅里叶分析不仅仅是一个数学工具,更是一种可以彻底颠覆一个人以前世界观的思维模式。但不幸的是,傅里叶分析的公式看起来太复杂了,所以很多大一新生上来就懵圈并从此对它深恶痛绝。老实说,这么有意思的东西居然成了大学里的杀手课程,不得不归咎于编教材的人实在是太严肃了。(您把教材写得好玩一点会死吗?会死吗?)所以我一直想写一个有意思的文章来解释傅里叶分析,有可能的话高中生都能看懂的那种。所以,不管读到这里的您从事何种工作,我保证您都能看懂,并且一定将体会到通过傅里叶分析看到世界另一个样子时的快感。至于对于已经有一定基础的朋友,也希望不要看到会的地方就急忙往后翻,仔细读一定会有新的发现。

    ————以上是定场诗————

    下面进入正题:

    抱歉,还是要啰嗦一句:其实学习本来就不是易事,我写这篇文章的初衷也是希望大家学习起来更加轻松,充满乐趣。但是千万!千万不要把这篇文章收藏起来,或是存下地址,心里想着:以后有时间再看。这样的例子太多了,也许几年后你都没有再打开这个页面。无论如何,耐下心,读下去。这篇文章要比读课本要轻松、开心得多……

    一、什么是频域

    从我们出生,我们看到的世界都以时间贯穿,股票的走势、人的身高、汽车的轨迹都会随着时间发生改变。这种以时间作为参照来观察动态世界的方法我们称其为时域分析。而我们也想当然的认为,世间万物都在随着时间不停的改变,并且永远不会静止下来。但如果我告诉你,用另一种方法来观察世界的话,你会发现世界是永恒不变的,你会不会觉得我疯了?我没有疯,这个静止的世界就叫做频域。

    先举一个公式上并非很恰当,但意义上再贴切不过的例子:

    在你的理解中,一段音乐是什么呢?

    这是我们对音乐最普遍的理解,一个随着时间变化的震动。但我相信对于乐器小能手们来说,音乐更直观的理解是这样的:


    好的!下课,同学们再见。

    是的,其实这一段写到这里已经可以结束了。上图是音乐在时域的样子,而下图则是音乐在频域的样子。所以频域这一概念对大家都从不陌生,只是从来没意识到而已。

    现在我们可以回过头来重新看看一开始那句痴人说梦般的话:世界是永恒的。

    将以上两图简化:

    时域:


    频域:

    在时域,我们观察到钢琴的琴弦一会上一会下的摆动,就如同一支股票的走势;而在频域,只有那一个永恒的音符。

    所以

    你眼中看似落叶纷飞变化无常的世界,实际只是躺在上帝怀中一份早已谱好的乐章。

    抱歉,这不是一句鸡汤文,而是黑板上确凿的公式:傅里叶同学告诉我们,任何周期函数,都可以看作是不同振幅,不同相位正弦波的叠加。在第一个例子里我们可以理解为,利用对不同琴键不同力度,不同时间点的敲击,可以组合出任何一首乐曲。

    而贯穿时域与频域的方法之一,就是传中说的傅里叶分析。傅里叶分析可分为傅里叶级数(Fourier Serie)和傅里叶变换(Fourier Transformation),我们从简单的开始谈起。

     

    二、傅里叶级数(Fourier Series)的频谱

    还是举个栗子并且有图有真相才好理解。

    如果我说我能用前面说的正弦曲线波叠加出一个带 90 度角的矩形波来,你会相信吗?你不会,就像当年的我一样。但是看看下图:

    第一幅图是一个郁闷的正弦波 cos(x)

    第二幅图是 2 个卖萌的正弦波的叠加 cos (x) +a.cos (3x)

    第三幅图是 4 个发春的正弦波的叠加

    第四幅图是 10 个便秘的正弦波的叠加

    随着正弦波数量逐渐的增长,他们最终会叠加成一个标准的矩形,大家从中体会到了什么道理?

    (只要努力,弯的都能掰直!)

    随着叠加的递增,所有正弦波中上升的部分逐渐让原本缓慢增加的曲线不断变陡,而所有正弦波中下降的部分又抵消了上升到最高处时继续上升的部分使其变为水平线。一个矩形就这么叠加而成了。但是要多少个正弦波叠加起来才能形成一个标准 90 度角的矩形波呢?不幸的告诉大家,答案是无穷多个。(上帝:我能让你们猜着我?)

    不仅仅是矩形,你能想到的任何波形都是可以如此方法用正弦波叠加起来的。这是没有接触过傅里叶分析的人在直觉上的第一个难点,但是一旦接受了这样的设定,游戏就开始有意思起来了。

    还是上图的正弦波累加成矩形波,我们换一个角度来看看:

    在这几幅图中,最前面黑色的线就是所有正弦波叠加而成的总和,也就是越来越接近矩形波的那个图形。而后面依不同颜色排列而成的正弦波就是组合为矩形波的各个分量。这些正弦波按照频率从低到高从前向后排列开来,而每一个波的振幅都是不同的。一定有细心的读者发现了,每两个正弦波之间都还有一条直线,那并不是分割线,而是振幅为 0 的正弦波!也就是说,为了组成特殊的曲线,有些正弦波成分是不需要的。

    这里,不同频率的正弦波我们成为频率分量。

    好了,关键的地方来了!!

    如果我们把第一个频率最低的频率分量看作“1”,我们就有了构建频域的最基本单元。

    对于我们最常见的有理数轴,数字“1”就是有理数轴的基本单元。

    (好吧,数学称法为——基。在那个年代,这个字还没有其他奇怪的解释,后面还有正交基这样的词汇我会说吗?)

    时域的基本单元就是“1 秒”,如果我们将一个角频率为\omega_{0}的正弦波 cos(\omega_{0}t)看作基础,那么频域的基本单元就是\omega_{0}

    有了“1”,还要有“0”才能构成世界,那么频域的“0”是什么呢?cos(0t)就是一个周期无限长的正弦波,也就是一条直线!所以在频域,0 频率也被称为直流分量,在傅里叶级数的叠加中,它仅仅影响全部波形相对于数轴整体向上或是向下而不改变波的形状。

    接下来,让我们回到初中,回忆一下已经死去的八戒,啊不,已经死去的老师是怎么定义正弦波的吧。

    正弦波就是一个圆周运动在一条直线上的投影。所以频域的基本单元也可以理解为一个始终在旋转的圆

    想看动图的同学请戳这里:

    File:Fourier series square wave circles animation.gif

    File:Fourier series sawtooth wave circles animation.gif

    以及这里:

    File:Fourier series sawtooth wave circles animation.gif

    点出去的朋友不要被 wiki 拐跑了,wiki 写的哪有这里的文章这么没节操是不是。

    介绍完了频域的基本组成单元,我们就可以看一看一个矩形波,在频域里的另一个模样了:


    这是什么奇怪的东西?

    这就是矩形波在频域的样子,是不是完全认不出来了?教科书一般就给到这里然后留给了读者无穷的遐想,以及无穷的吐槽,其实教科书只要补一张图就足够了:频域图像,也就是俗称的频谱,就是——

    再清楚一点:

    可以发现,在频谱中,偶数项的振幅都是0,也就对应了图中的彩色直线。振幅为 0 的正弦波。

    File:Fourier series and transform.gif

    动图请戳:

    File:Fourier series and transform.gif

    老实说,在我学傅里叶变换时,维基的这个图还没有出现,那时我就想到了这种表达方法,而且,后面还会加入维基没有表示出来的另一个谱——相位谱。

    但是在讲相位谱之前,我们先回顾一下刚刚的这个例子究竟意味着什么。记得前面说过的那句“世界是静止的”吗?估计好多人对这句话都已经吐槽半天了。想象一下,世界上每一个看似混乱的表象,实际都是一条时间轴上不规则的曲线,但实际这些曲线都是由这些无穷无尽的正弦波组成。我们看似不规律的事情反而是规律的正弦波在时域上的投影,而正弦波又是一个旋转的圆在直线上的投影。那么你的脑海中会产生一个什么画面呢?

    我们眼中的世界就像皮影戏的大幕布,幕布的后面有无数的齿轮,大齿轮带动小齿轮,小齿轮再带动更小的。在最外面的小齿轮上有一个小人——那就是我们自己。我们只看到这个小人毫无规律的在幕布前表演,却无法预测他下一步会去哪。而幕布后面的齿轮却永远一直那样不停的旋转,永不停歇。这样说来有些宿命论的感觉。说实话,这种对人生的描绘是我一个朋友在我们都是高中生的时候感叹的,当时想想似懂非懂,直到有一天我学到了傅里叶级数……

    三、傅里叶级数(Fourier Series)的相位谱

    上一章的关键词是:从侧面看。这一章的关键词是:从下面看。

    在这一章最开始,我想先回答很多人的一个问题:傅里叶分析究竟是干什么用的?这段相对比较枯燥,已经知道了的同学可以直接跳到下一个分割线。

    先说一个最直接的用途。无论听广播还是看电视,我们一定对一个词不陌生——频道。频道频道,就是频率的通道,不同的频道就是将不同的频率作为一个通道来进行信息传输。下面大家尝试一件事:

    先在纸上画一个sin(x),不一定标准,意思差不多就行。不是很难吧。

    好,接下去画一个sin(3x)+sin(5x)的图形。

    别说标准不标准了,曲线什么时候上升什么时候下降你都不一定画的对吧?

    好,画不出来不要紧,我把sin(3x)+sin(5x)的曲线给你,但是前提是你不知道这个曲线的方程式,现在需要你把sin(5x)给我从图里拿出去,看看剩下的是什么。这基本是不可能做到的。

    但是在频域呢?则简单的很,无非就是几条竖线而已。

    所以很多在时域看似不可能做到的数学操作,在频域相反很容易。这就是需要傅里叶变换的地方。尤其是从某条曲线中去除一些特定的频率成分,这在工程上称为滤波,是信号处理最重要的概念之一,只有在频域才能轻松的做到。

    再说一个更重要,但是稍微复杂一点的用途——求解微分方程。(这段有点难度,看不懂的可以直接跳过这段)微分方程的重要性不用我过多介绍了。各行各业都用的到。但是求解微分方程却是一件相当麻烦的事情。因为除了要计算加减乘除,还要计算微分积分。而傅里叶变换则可以让微分和积分在频域中变为乘法和除法,大学数学瞬间变小学算术有没有。

    傅里叶分析当然还有其他更重要的用途,我们随着讲随着提。

    ————————————————————————————————————

    下面我们继续说相位谱:

    通过时域到频域的变换,我们得到了一个从侧面看的频谱,但是这个频谱并没有包含时域中全部的信息。因为频谱只代表每一个对应的正弦波的振幅是多少,而没有提到相位。基础的正弦波A.sin(wt+θ)中,振幅,频率,相位缺一不可,不同相位决定了波的位置,所以对于频域分析,仅仅有频谱(振幅谱)是不够的,我们还需要一个相位谱。那么这个相位谱在哪呢?我们看下图,这次为了避免图片太混论,我们用7个波叠加的图。

    鉴于正弦波是周期的,我们需要设定一个用来标记正弦波位置的东西。在图中就是那些小红点。小红点是距离频率轴最近的波峰,而这个波峰所处的位置离频率轴有多远呢?为了看的更清楚,我们将红色的点投影到下平面,投影点我们用粉色点来表示。当然,这些粉色的点只标注了波峰距离频率轴的距离,并不是相位。


    这里需要纠正一个概念:时间差并不是相位差。如果将全部周期看作2Pi或者360度的话,相位差则是时间差在一个周期中所占的比例。我们将时间差除周期再乘2Pi,就得到了相位差。

    在完整的立体图中,我们将投影得到的时间差依次除以所在频率的周期,就得到了最下面的相位谱。所以,频谱是从侧面看,相位谱是从下面看。下次偷看女生裙底被发现的话,可以告诉她:“对不起,我只是想看看你的相位谱。”

    注意到,相位谱中的相位除了0,就是Pi。因为cos(t+Pi)=-cos(t),所以实际上相位为Pi的波只是上下翻转了而已。对于周期方波的傅里叶级数,这样的相位谱已经是很简单的了。另外值得注意的是,由于cos(t+2Pi)=cos(t),所以相位差是周期的,pi和3pi,5pi,7pi都是相同的相位。人为定义相位谱的值域为(-pi,pi],所以图中的相位差均为Pi。

    最后来一张大集合:

    四、傅里叶变换(Fourier Tranformation)

    相信通过前面三章,大家对频域以及傅里叶级数都有了一个全新的认识。但是文章在一开始关于钢琴琴谱的例子我曾说过,这个栗子是一个公式错误,但是概念典型的例子。所谓的公式错误在哪里呢?

    傅里叶级数的本质是将一个周期的信号分解成无限多分开的(离散的)正弦波,但是宇宙似乎并不是周期的。曾经在学数字信号处理的时候写过一首打油诗:

    往昔连续非周期,

    回忆周期不连续,

    任你ZT、DFT,

    还原不回去。

    (请无视我渣一样的文学水平……)

    在这个世界上,有的事情一期一会,永不再来,并且时间始终不曾停息地将那些刻骨铭心的往昔连续的标记在时间点上。但是这些事情往往又成为了我们格外宝贵的回忆,在我们大脑里隔一段时间就会周期性的蹦出来一下,可惜这些回忆都是零散的片段,往往只有最幸福的回忆,而平淡的回忆则逐渐被我们忘却。因为,往昔是一个连续的非周期信号,而回忆是一个周期离散信号。

    是否有一种数学工具将连续非周期信号变换为周期离散信号呢?抱歉,真没有。

    比如傅里叶级数,在时域是一个周期且连续的函数,而在频域是一个非周期离散的函数。这句话比较绕嘴,实在看着费事可以干脆回忆第一章的图片。

    而在我们接下去要讲的傅里叶变换,则是将一个时域非周期的连续信号,转换为一个在频域非周期的连续信号。

    算了,还是上一张图方便大家理解吧:

    或者我们也可以换一个角度理解:傅里叶变换实际上是对一个周期无限大的函数进行傅里叶变换。

    所以说,钢琴谱其实并非一个连续的频谱,而是很多在时间上离散的频率,但是这样的一个贴切的比喻真的是很难找出第二个来了。

    因此在傅里叶变换在频域上就从离散谱变成了连续谱。那么连续谱是什么样子呢?

    你见过大海么?

    为了方便大家对比,我们这次从另一个角度来看频谱,还是傅里叶级数中用到最多的那幅图,我们从频率较高的方向看。

    以上是离散谱,那么连续谱是什么样子呢?

    尽情的发挥你的想象,想象这些离散的正弦波离得越来越近,逐渐变得连续……

    直到变得像波涛起伏的大海:

    很抱歉,为了能让这些波浪更清晰的看到,我没有选用正确的计算参数,而是选择了一些让图片更美观的参数,不然这图看起来就像屎一样了。

    不过通过这样两幅图去比较,大家应该可以理解如何从离散谱变成了连续谱的了吧?原来离散谱的叠加,变成了连续谱的累积。所以在计算上也从求和符号变成了积分符号。

    不过,这个故事还没有讲完,接下去,我保证让你看到一幅比上图更美丽壮观的图片,但是这里需要介绍到一个数学工具才能然故事继续,这个工具就是——

     

    五、宇宙耍帅第一公式:欧拉公式

    虚数i这个概念大家在高中就接触过,但那时我们只知道它是-1 的平方根,可是它真正的意义是什么呢?


    这里有一条数轴,在数轴上有一个红色的线段,它的长度是1。当它乘以 3 的时候,它的长度发生了变化,变成了蓝色的线段,而当它乘以-1 的时候,就变成了绿色的线段,或者说线段在数轴上围绕原点旋转了 180 度。

    我们知道乘-1 其实就是乘了两次 i 使线段旋转了 180 度,那么乘一次 i 呢——答案很简单——旋转了 90 度。

    同时,我们获得了一个垂直的虚数轴。实数轴与虚数轴共同构成了一个复数的平面,也称复平面。这样我们就了解到,乘虚数i的一个功能——旋转。

    现在,就有请宇宙第一耍帅公式欧拉公式隆重登场——


    这个公式在数学领域的意义要远大于傅里叶分析,但是乘它为宇宙第一耍帅公式是因为它的特殊形式——当x等于 Pi 的时候。


    经常有理工科的学生为了跟妹子表现自己的学术功底,用这个公式来给妹子解释数学之美:”石榴姐你看,这个公式里既有自然底数e,自然数 1 和0,虚数i还有圆周率 pi,它是这么简洁,这么美丽啊!“但是姑娘们心里往往只有一句话:”臭屌丝……“

    这个公式关键的作用,是将正弦波统一成了简单的指数形式。我们来看看图像上的涵义:

    欧拉公式所描绘的,是一个随着时间变化,在复平面上做圆周运动的点,随着时间的改变,在时间轴上就成了一条螺旋线。如果只看它的实数部分,也就是螺旋线在左侧的投影,就是一个最基础的余弦函数。而右侧的投影则是一个正弦函数。

    关于复数更深的理解,大家可以参考:

    复数的物理意义是什么?

    这里不需要讲的太复杂,足够让大家理解后面的内容就可以了。

     

    六、指数形式的傅里叶变换

    有了欧拉公式的帮助,我们便知道:正弦波的叠加,也可以理解为螺旋线的叠加在实数空间的投影。而螺旋线的叠加如果用一个形象的栗子来理解是什么呢?

      光波

    高中时我们就学过,自然光是由不同颜色的光叠加而成的,而最著名的实验就是牛顿师傅的三棱镜实验:

    所以其实我们在很早就接触到了光的频谱,只是并没有了解频谱更重要的意义。

    但不同的是,傅里叶变换出来的频谱不仅仅是可见光这样频率范围有限的叠加,而是频率从 0 到无穷所有频率的组合。

    这里,我们可以用两种方法来理解正弦波:

    第一种前面已经讲过了,就是螺旋线在实轴的投影。

    另一种需要借助欧拉公式的另一种形式去理解:

    e^{it}=cos (t) +i.sin (t)
    e^{-it}=cos (t)-i.sin (t)

    将以上两式相加再除2,得到:

    这个式子可以怎么理解呢?

    我们刚才讲过,e^(it)可以理解为一条逆时针旋转的螺旋线,那么e^(-it)则可以理解为一条顺时针旋转的螺旋线。而 cos (t)则是这两条旋转方向不同的螺旋线叠加的一半,因为这两条螺旋线的虚数部分相互抵消掉了!

    举个例子的话,就是极化方向不同的两束光波,磁场抵消,电场加倍。

    这里,逆时针旋转的我们称为正频率,而顺时针旋转的我们称为负频率(注意不是复频率)。

    好了,刚才我们已经看到了大海——连续的傅里叶变换频谱,现在想一想,连续的螺旋线会是什么样子:

    想象一下再往下翻:

    是不是很漂亮?

    你猜猜,这个图形在时域是什么样子?

    哈哈,是不是觉得被狠狠扇了一个耳光。数学就是这么一个把简单的问题搞得很复杂的东西。

    顺便说一句,那个像大海螺一样的图,为了方便观看,我仅仅展示了其中正频率的部分,负频率的部分没有显示出来。

    如果你认真去看,海螺图上的每一条螺旋线都是可以清楚的看到的,每一条螺旋线都有着不同的振幅(旋转半径),频率(旋转周期)以及相位。而将所有螺旋线连成平面,就是这幅海螺图了。

    好了,讲到这里,相信大家对傅里叶变换以及傅里叶级数都有了一个形象的理解了,我们最后用一张图来总结一下:

    好了,傅里叶的故事终于讲完了,下面来讲讲我的故事:

    这篇文章第一次被卸下来的地方你们绝对猜不到在哪,是在一张高数考试的卷子上。当时为了刷分,我重修了高数(上),但是后来时间紧压根没复习,所以我就抱着裸考的心态去了考场。但是到了考场我突然意识到,无论如何我都不会比上次考的更好了,所以干脆写一些自己对于数学的想法吧。于是用了一个小时左右的时间在试卷上洋洋洒洒写了本文的第一草稿。

    你们猜我的了多少分?

    6 分

    没错,就是这个数字。而这 6 分的成绩是因为最后我实在无聊,把选择题全部填上了C,应该是中了两道,得到了这宝贵的 6 分。说真的,我很希望那张卷子还在,但是应该不太可能了。

    那么你们猜猜我第一次信号与系统考了多少分呢?

    45 分

    没错,刚刚够参加补考的。但是我心一横没去考,决定重修。因为那个学期在忙其他事情,学习真的就抛在脑后了。但是我知道这是一门很重要的课,无论如何我要吃透它。说真的,信号与系统这门课几乎是大部分工科课程的基础,尤其是通信专业。

    在重修的过程中,我仔细分析了每一个公式,试图给这个公式以一个直观的理解。虽然我知道对于研究数学的人来说,这样的学习方法完全没有前途可言,因为随着概念愈加抽象,维度越来越高,这种图像或者模型理解法将完全丧失作用。但是对于一个工科生来说,足够了。

    后来来了德国,这边学校要求我重修信号与系统时,我彻底无语了。但是没办法,德国人有时对中国人就是有种藐视,觉得你的教育不靠谱。所以没办法,再来一遍吧。

    这次,我考了满分,而及格率只有一半。

    老实说,数学工具对于工科生和对于理科生来说,意义是完全不同的。工科生只要理解了,会用,会查,就足够了。但是很多高校却将这些重要的数学课程教给数学系的老师去教。这样就出现一个问题,数学老师讲得天花乱坠,又是推理又是证明,但是学生心里就只有一句话:学这货到底干嘛用的?

    缺少了目标的教育是彻底的失败。

    在开始学习一门数学工具的时候,学生完全不知道这个工具的作用,现实涵义。而教材上有只有晦涩难懂,定语就二十几个字的概念以及看了就眼晕的公式。能学出兴趣来就怪了!

    好在我很幸运,遇到了大连海事大学的吴楠老师。他的课全程来看是两条线索,一条从上而下,一条从下而上。先将本门课程的意义,然后指出这门课程中会遇到哪样的问题,让学生知道自己学习的某种知识在现实中扮演的角色。然后再从基础讲起,梳理知识树,直到延伸到另一条线索中提出的问题,完美的衔接在一起!

    这样的教学模式,我想才是大学里应该出现的。

    最后,写给所有给我点赞并留言的同学。真的谢谢大家的支持,也很抱歉不能一一回复。因为知乎专栏的留言要逐次加载,为了看到最后一条要点很多次加载。当然我都坚持看完了,只是没办法一一回复。

    本文只是介绍了一种对傅里叶分析新颖的理解方法,对于求学,还是要踏踏实实弄清楚公式和概念,学习,真的没有捷径。但至少通过本文,我希望可以让这条漫长的路变得有意思一些。

    最后,祝大家都能在学习中找到乐趣…

    展开全文
  • 源:经典算法大全(51个C语言算法+单片机常用算法+机器学十大算法 转载于:https://www.cnblogs.com/LittleTiger/p/10323059.html

    源:经典算法大全(51个C语言算法+单片机常用算法+机器学十大算法

    转载于:https://www.cnblogs.com/LittleTiger/p/10323059.html

    展开全文
  • 包含多种单片机常用滤波算法。主要包括平均,限幅,中位值及其各种组合滤波算法介绍,并包含C代码实例。可以直接套用。非常方便。
  • 单片机常用算法设计

    2020-07-15 23:31:26
    新手学习单片机必备使用资料,网上牛人分享;单片机常用算法设计详细总结
  • 本文件为本人经过测试的能够直接应用于8位单片机的sha1-hash算法源码,解决了以往在PC机上实现或32位编译器实现的sha1算法无法兼容低端处理器的问题。
  • 帮助你理解PID的两种算法 位置式PID 增量式PID 里面有2个例子
  • 算法(Algorithm):计算机解题的基本思想方法和步骤。 算法的描述:是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述,包括需要什么数据(输入什么数据、输出什么结果)、采用什么结构、使用什么语句...

    算法(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%100)printf("\n");
    }
    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\n",p,x);
    }
    printf("\n");
    }

    二、求两个整数的最大公约数、最小公倍数
    分析:求最大公约数的算法思想:(最小公倍数=两个整数之积/最大公约数)
    (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:\n”);
    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”,n);
    printf(“最小公倍数:%d\n”,nm/n);
    }

    三、判断素数
    只能被1或本身整除的数称为素数 基本思想:把m作为被除数,将2—INT( )作为除数,如果都除不尽,m就是素数,否则就不是。(可用以下程序段实现)
    void main()
    { int m,i,k;
    printf(“please input a number:\n”);
    scanf("%d",&m);
    k=sqrt(m);
    for(i=2;i
    if(m%i0) 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):\n”);
    scanf("%d",&x);
    if (x<6||x%2!=0)
    printf(“data error!\n”);
    else
    for(i=2;i<=x/2;i++)
    if (prime(i)&&prime(x-i))
    {
    printf("%d+%d\n",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("\n input 10 numbers:\n");
    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\n",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\n”);
    for(i=0;i<10;i++)
    scanf("%d",&a);
    printf("\n");
    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:\n”);
    for(i=0;i<10;i++)
    printf("%d\n",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:\n”);
    for(i=0;i<10;i++)
    scanf("%d",&a);
    for(i=0;i<10;i++)
    scanf("%d",&b);
    printf("\n");
    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\n",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:\n”);
    for(i=0;i<10;i++)
    scanf("%d",&a);
    printf(“please input the number you want find:\n”);
    scanf("%d",&x);
    printf("\n");
    p=0;
    while(x!=a[p]&&p<10)
    p++;
    if(p>=10)
    printf(“the number is not found!\n”);
    else
    printf(“the number is found the no%d!\n”,p);
    }

    思考:将上面程序改写一查找函数Find,若找到则返回下标值,找不到返回-1

    ②基本思想:一列数放在数组a[1]—a[n]中,待查找的关键值为key,把key与a数组中的元素从头到尾一一进行比较查找,若相同,查找成功,若找不到,则查找失败。(查找子过程如下。index:存放找到元素的下标。)

    void main()
    { int a[10],index,x,i;
    printf(“please input the array:\n”);
    for(i=0;i<10;i++)
    scanf("%d",&a);
    printf(“please input the number you want find:\n”);
    scanf("%d",&x);
    printf("\n");
    index=-1;
    for(i=0;i<10;i++)
    if(xa)
    { index=“i”; break;
    }
    if(index
    -1)
    printf(“the number is not found!\n”);
    else
    printf(“the number is found the no%d!\n”,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 + anew_value;
    }

    十三、PID控制算法
    在过程控制中,按偏差的比例(P)、积分(I)和微分(D)进行控制的PID控制器(亦称PID调节器)是应用最为广泛的一种自动控制器;
    对于过程控制的典型对象──“一阶滞后+纯滞后”与“二阶滞后+纯滞后”的控制对象,PID控制器是一种最优控制;
    PID调节规律是连续系统动态品质校正的一种有效方法,它的参数整定方式简便,结构改变灵活(PI、PD、…)。

    一 模拟PID调节器
    PID调节器各校正环节的作用:
    比例环节:即时成比例地反应控制系统的偏差信号e(t),偏差一旦产生,调节器立即产生控制作用以减小偏差;
    积分环节:主要用于消除静差,提高系统的无差度。积分时间常数TI越大,积分作用越弱,反之则越强;
    微分环节:能反应偏差信号的变化趋势(变化速率),并能在偏差信号的值变得太大之前,在系统中引入一个有效的早期修正信号,从而加快系统的动作速度,减小调节时间。
    PID调节器是一种线性调节器,它将给定值r(t)与实际输出值c(t)的偏差的比例§、积分(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, 2n-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,2n-2) + (b[n-1]pow(2,2n-2) + b[n-2]pow(2,2n-4)),
    然后比较余数M[1]是否大于等于 (pow(2,2)b[n-1] + b[n-2]) * pow(2,2n-4)。这种比较只须根据B[m-1]、B[m-2]、…、B[2
    n-4]便可做出判断,其余低位不做比较。
    若 M[1] >= (pow(2,2)b[n-1] + b[n-2]) * pow(2,2n-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,2n-4);
    若 M[1] < (pow(2,2)b[n-1] + b[n-2]) * pow(2,2n-4), 则假设无效,b[n-2] = 0;余数 M[2] = M[1]。
    (3) 同理,可以从高位到低位逐位求出M的平方根N的各位。
    使用这种算法计算32位数的平方根时最多只须比较16次,而且每次比较时不必把M的各位逐一比较,尤其是开始时比较的位数很少,所以消耗的时间远低于牛顿迭代法。

    1. 实现代码
      这里给出实现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;
      }
    展开全文
  • 单片机PID算法程序

    2013-10-10 22:05:05
    转自:... 比例,积分,微分的线性组合,构成控制量u(t),称为:比例(Proportional)、积分(Integrating)、微分(Differentiation)控制,简称PID控制 ... 在实际应用中,可以根据受控
  • 本文主要是分享资料,讲解不会太多,因为分享的资料里面就有具体的详细解析,而且百度上面也有详细的资料,所以本次博文主要是讲解我用PID算法调温的经验。 PID算法调整温度最大的问题的温度的上升问题以及温度在水...
  • C语言中开平方的算法中要开平方的话,可以在头文件中加#include<math.h>.然后调sqrt(n);函数即可.但在单片机中要开平方.可以用到下面算法: 算法1: 本算法只采用移位、加减法、判断和循环实现,因为它不需要...
  • 51单片机学习笔记———8.点亮流水灯的一种奇葩算法 最近学习51单片机的过程发现了一种脑洞大开点亮流水灯的方法,于此分享一下源码: #include<reg52.h> sbit LED0 = P0^0; sbit LED1 = P0^1; sbit LED2 = P0...
  • 这是一个keil软件的工程代码,实现的是PID算法,AD检测,USART打印。
  • 本博客主要介绍将RSA加密算法应用到单片机编码之中的一种方法。借助单片机矩阵键盘和显示屏模块进行输入和输出操作。因本方案已经应用到省创项目中,再次只重点介绍RSA算法的应用在驱动程序中的编码以及主函数编码。...
  • 原文地址:FFT算法单片机中的使用&&LCD12864驱动作者:元大帝 好久没更新博客了,觉得对不起自己建立博客的初衷。我这个人太懒了,又没有坚持下去的决心,唉~    言归正传,本次创新基金我是要做一个简易的频谱...
  • 51单片机pid算法

    2020-06-24 16:33:49
    用Pid算法进行温度控制,可自行调节温度输出量,用于51单片机学习
  • 单片机的滤波算法

    2019-10-10 19:20:49
    关于滤波,我们常常听说有滤波电路、滤波器、滤波对抗器等等,这些都是有效的解决单片机的信号干扰问题,都是从硬件上进行滤波处理,从而增加检测值的精确度。下面我们来简单介绍一下软件是如何进行单片机滤波的,这...
1 2 3 4 5 ... 20
收藏数 18,575
精华内容 7,430
关键字:

单片机 算法