计算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;
}
