数据是稳定的(即不允许插入操作和删除操作)

在任意时刻，算法都能对它已经读入的数据给出子序列问题的答案，具有这种特性的算法叫做联机算法(online algorithm)

分治（divide-and-conquer)策略：其想法是把问题分成两个大致相等的子问题，然后递归地对他们求解，这是“分”部分。“治”阶段将两个子问题的解合并到一起并可能再做些少量的附加工作，最后得到整个问题的解。

当编写递归例程的时候，关键是要牢记递归地四条基本法则：

  1. 基准情形。 某些基准情形，无须递归就能解出

  2. 不断推进。 每次递归都必须使求解状况朝基准情形推进

  3. 设计法则。 假设所有的递归调用都能运行

  4. 合成效益法则(compound interest rule)。在求解一个问题的同一个实例时，切勿在不同的递归调用中做重复性的工作

如果一个算法用常数时间（O(1)）将问题的大小削减为其一部分（通常是1/2）,那么该算法就是O（logN)。 另一方面，如果使用常数时间只是把问题减少一个常数（如将问题减少1），那么这种算法就是O(N)的。

程序1：输出数组中第K大的数

#include
     
      #define SIZE 100int main(){    int i,j,k,t,n,num[SIZE],tmp[SIZE];    //the original array num as follows    printf("please input the array size(n) : ");    scanf("%d",&n);    printf("please input the array(including %d integer) :\n",n);     for(i=0;i
      
       =0;--j) {     if(num[i]<=tmp[j])     {  break;     }     else     {  tmp[j+1]=tmp[j];     }  } t=j+1; tmp[t]=num[i];    }    //insert num[i] into tmp[j+1] when num[i]>tmp[k]     for(i=k;i
       
        =0;--j) {     if(num[i]<=tmp[j])       break;     else  tmp[j+1]=tmp[j];  } if(j+1<=k-1) {    tmp[j+1]=num[i];  }    }    printf("Following the descending order,the %dth number is : %d\n",k,tmp[k-1]);     return 0;}

程序2：输出文件中的全部数据

#include
     
      #include
      
       int main(){    FILE *fp=fopen("/usr/include/stdio.h","r+");    char* buffer=malloc(sizeof(char)*65535);    if(fp==NULL)    { printf("fp is NULL"); return 0;    }    while(fread(buffer,sizeof(char),65535,fp)!=0)    { printf("%s",buffer);    }    printf("\n");    fclose(fp);     return 0;}

程序3：输出最大子序列和。以下3个算法，数据量很大时，运行时间递减

算法1：

#include
     
      #define SIZE 10int main(){    int num[SIZE];    int i,j;    int tmp,sum=0;    int start=0,end=0;    printf("please input the element of the array[%d] :\n",SIZE);    for(i=0;i

算法2：

#include
     
      #define SIZE 10int maxsubsum(int array[],int left,int right){    int maxleftsum,maxrightsum,maxcentersum;    int maxleftbordersum=0,maxrightbordersum=0;    int leftbordersum=0,rightbordersum=0;    int center,i;    if(left==right) if(array[left]>0)     return array[left]; else     return 0;        center=(left+right)/2;    maxleftsum=maxsubsum(array,left,center);    maxrightsum=maxsubsum(array,center+1,right);        for(i=center;i>=left;--i)    { leftbordersum+=array[i]; if(maxleftbordersum
      
       <=right;++i)    { rightbordersum+=array[i]; if(maxrightbordersum
       
        maxrightsum?(maxleftsum>maxcentersum?maxleftsum:maxcentersum):(maxrightsum>maxcentersum?maxrightsum:maxcentersum); }int main(){    int array[SIZE],left=0,right=SIZE-1,i;    printf("please input the element of the array[%d] :\n",SIZE);    for(i=0;i

算法3：

#include
     
      #define SIZE 10int main(){    int thissum=0,maxsum=0,i;    int array[SIZE];    printf("please input the element of the array[%d] :\n",SIZE);    for(i=0;i
      
       
        maxsum)     maxsum=thissum; else if(thissum<0)     thissum=0;    }    printf("the max_sublist_sum is : %d\n",maxsum);    return 0;}

程序4：对分查找（binary search）

#include
     
      #define SIZE 10int main(){    int array[SIZE],i,goal,left=0,right=SIZE-1,mid;    printf("please input the element of the array[%d]:\n",SIZE);    for(i=0;i
      
       <=right)    { mid=(left+right)/2; if(array[mid]>goal)     right=mid-1; else if(array[mid]

程序5：计算最大公因数的欧几里得算法

#include
     
      Gcd(unsigned int M,unsigned int N){    unsigned int Rem;    while(N>0)    { Rem=M%N; M=N; N=Rem;    }    return M;}int main(){    unsigned int M,N;    printf("please input M and N :");    scanf("%d %d",&M,&N);    printf("the Gcd is : %d\n",Gcd(M,N));     return 0;}

程序6：幂运算

#include
     
      long int Pow(long int x,unsigned int N){    long int tmp;    if(N==0) return 1;    else if(N==1) return x;    tmp=Pow(x*x,N/2);    if(N%2!=0) tmp*=x;    return tmp;  }int main(){    printf("please input the x and N: ");    long int x;    unsigned int N;    scanf("%ld %u",&x,&N);    printf("the result is :%ld\n",Pow(x,N));     return 0;}

程序7：计算两个随机选取出并小于或等于NN的互异正整数互素的概率

#include
     
      #define NN 6unsigned int Gcd(unsigned int M,unsigned int N){    unsigned int Rem;    while(N>0)    { Rem=M%N; M=N; N=Rem;    }    return M;}int main(){    int Rel=0,Tot=0,j,i;    for(i=1;i<=NN;++i) for(j=i+1;j<=NN;++j) {     Tot++;     if(Gcd(i,j)==1)  Rel++;  }    printf("the probability of it that they are prime is :%f\n",(Rel+0.0)/Tot);    return 0;}