算法设计与分析笔记（一）

递归与分治策略

        递归的概念，典型应用：Hanoi问题，程序如下： #include<stdio.h>void hanoi(int n, char a, char b, char c){ if(n>0) {  hanoi(n-1,a,c,b);  printf("move %c to %c /n",a,b);  hanoi(n-1,c,b,a); }}void main(){ int n; printf("please input a number:"); scanf("%d",&n); hanoi(n,'a','b','c');}

        分治的基本思想：将一个规模为N的问题分解成K个规模较小的子问题，然后递归解决这些问题。

        二分搜索技术：#include<stdio.h>#define MAX 100int binarySearch(int a[], int x, int n){ int left=0,right=n-1; while(left<=right) {  int middle=(left+right)/2;  if(x==a[middle]) return middle+1;  if(x>a[middle]) left=middle+1;  else right=middle-1; } return -1;}void main(){ int a[MAX]; int find,sum,i; printf("please input the sum of List:"); scanf("%d",&sum); printf("please input %d number/n",sum); for(i=0;i<sum;i++) scanf("%d",&a[i]); printf("which number do you want find?"); scanf("%d",&find); printf("the %d th number is OK",binarySearch(a,find,sum));}

        大整数的乘法

        Strassen矩阵乘法

        棋盘覆盖

        合并排序

        快速排序

        线形时间选择

        最接近点对问题

        循环赛日程表