分治法的常见问题

计算x的n次幂

朴素算法:xxx......

分治算法:

n为偶数:x的n/2次幂*x的n/2次幂

n为奇数:x的(n-1)/2次幂*x的(n-1)/2次幂

#include<bits/stdc++.h>
using namespace std;
//朴素算法
int simple(int x,int n)
{
    int num=1;
    for(int i=0;i<n;i++)
    {
        num*=x;
    }
    return num;
}
//分治算法----快速幂
int devided(int x,int n)
{
    int num=1;
    while(n)
    {
        if(n%2==1)
        {
            num*=x;
            n--;
        }
        x*=x;
        n/=2;
    }
    return num;
}

找出数组出现次数超过一半的数字

本质上就是求中位数，比较简单的方法是全部排序，然后取中间值，或者统计所有数字及其出现频率。优化的方法就是利用快算排序中的分治思想：

#include <stdio.h>

int partion(int a[], int n)
{
    if( a == NULL || n <= 0 )
        return -1;

    int i, candidate;
    int times = 0;
    for( i=0; i<n; i++ )
    {
        if( times == 0 )
        {
            candidate = a[i];
            times = 1;
        }
        else if( a[i] == candidate )
            ++times;
        else
            --times;
    }
    return candidate;
}

int main(void)
{
    int a[] = {1,2,3,2,2,2,5,4,2};

    int result = partion(a, 9);
    if( result != -1 )
        printf("%d\n", result);
    else
        printf("Error.\n");

    return 0;
}