分治算法

森之张卫东

分治算法
概念：
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

例题
给定两个数a和b，计算出0~9在a和b之间出现的次数

C源代码
[cpp] view plaincopy
# include <stdio.h>  
void handle(int x, int n[]);  
void handle(int x, int n[]);  
int main(void)  
{  
    int a, b;  
    int na[10];  
    int nb[10];  
    int i;  
      
    for(i = 0; i < 10; i++){  
        na = 0;  
        nb = 0;  
    }   
    scanf("%d%d", &a, &b);  
    if(a > b){                      //确保a<b   
        a = a + b;  
        b = a - b;  
        a = a - b;  
    }  
    handle(a - 1, na);  
    handle(b, nb);  
    for(i = 0; i < 10; i++){  
        printf("%d出现%d次\n", i, nb - na);  
    }  
    return 0;  
}  
void handlex(int x, int n[])  
{  
    if(x > 9){  
        n[x % 10] += 1;  
        handlex(x / 10, n);  
    } else{  
        n[x] += 1;  
    }  
}  
void handle(int x, int n[])  
{  
    while(x-- > 0){  
        handlex(x, n);  
    }  
}  
%我们可以将C语言转成Matlab语言，应该不难。
分析：
本程序简单的使用了分治和递归算法。其实把记录数字出现次数的数组声明为全局变量，就不用每次函数调用的时候传递了，代码会更简洁。