参考程序
1．常规算法，复杂度为O(N):
double Power(double x, unsigned int N)
{
double result = 1.0;
for (unsigned int i=0; i<N; i++)
result *= x;
return result;
}
折半算法（二分法），复杂度为O(logN):
double Power(double x, unsigned int N)
{
if (N == 0)
return 1.0;
double t = Power(x, N/2);
if (N % 2 == 0)
return t * t;
else
return t * t * x;
}
2．算法分析：在讲解枚举法时，我们讨论了如何用枚举法求解此题，但如果求解的精度进一步提高，使用枚举法就无能为力了，在此我们再一次讨论如何用二分法求解此题。
由题意知（i,i+1）中若有根，则只有一个根，我们枚举根的值域中的每一个整数x(-100≤x≤100),设定搜索区间[x1，x2]，其中x1=x，x2=x+1。若：
⑴f(x1)=0，则确定x1为f(x)的根；
⑵f(x1)*f(x2)<0，则确定根x在区间[x1，x2]内。
⑶f(x1)*f(x2)>0，则确定根x不在区间[x1，x2]内，设定[x2，x2+1]为下一个搜索区间；
若确定根x在区间[x1，x2]内，采用二分法，将区间[x1，x2]分成左右两个子区间：
左子区间[x1，x]和右子区间[x，x2]（其中x=（x1+x2）/2）。如果f(x1)*f(x)≤0，
则确定根在左区间[x1，x]内，将x设为该区间的右界值（x2=x），继续对左区间进行对分；
否则确定根在右区间[x，x2]内，将x设为该区间的左界值（x1=x），继续对右区间进行对分；
上述对分过程一直进行到区间的间距满足精度要求为止（即x2-x1<0.000005）。此时确定x1为f(x)的根。
#include<stdio.h>
#include<stdlib.h>
void Function(double xa[], double a, double b, double c, double d, double left, double right, double e);//解方程
double F(double a, double b, double c, double d, double x);//函数表达式
int main()
{
double low = -100, high = 100;
double e = 0.000005;
double a = 1, b = -5, c = -4, d = 20;
double x[8] = {0};
printf("%f %f %f %f\n", a, b, c, d);
Function(x, a, b, c, d, low, high, e);//解方程
printf("%.5f %.5f %.5f\n", x[0], x[1], x[2]);
system("pause");
return 0;
}
double F(double a, double b, double c, double d, double x)//函数表达式
{
return ((a * x + b) * x + c) * x + d;
}
void Function(double xa[], double a, double b, double c, double d, double left, double right, double e)
{
double low, high, mid, i;
int top = 0;
for (i=left; i<right; i+=1)
{
low = i;
high = low + 1;
while ((high-low) >= e)
{
mid = (low + high) / 2;
if (F(a, b, c, d, mid) == 0)
{
xa[top++] = mid;
break;
}
if (F(a, b, c, d, low)*F(a, b, c, d, mid) <= 0)
high = mid;
else if (F(a, b, c, d, mid)*F(a, b, c, d, high) <= 0)
low = mid;
else
break;
}
if ((high-low) < e)
xa[top++] = low;
if (top > 1 && abs(xa[top-1] - xa[top-2]) < e)//消除重复的解
top--;
}
}
3．分成两组：
#include<stdio.h>
int count = 0;
int FalseCoin(int a[], int left, int right);
int main()
{
int a[60] = {0};
int i, n = 15;
for (i=0; i<=n; i++)
{
count = 0;
a[i] = -1;
printf("n = %d, count = %d\n", FalseCoin(a, 0, n), count);
a[i] = 0;
}
getchar();
return 0;
}
/*
函数功能：找出伪币，并返回其下标，若无伪币则返回-1。此算法适用于任何情况，且伪币越靠前，越容易找到
输入变量： int a[]， 数组a中存储各硬币的重量
int left, 数组a的左边界
int right, 数组a的右边界
输出变量：无
返回值： int，伪币下标，若无伪币则返回-1
*/
int FalseCoin(int a[], int left, int right)
{
int mid = (left + right) / 2;
int num;
if (left >= right)//如果只有一枚硬币，无法找出伪币，相当于无伪币
{
count++;
return -1;
}
if ((right-left) == 1)//只有两枚硬币，轻者为伪币，等重则无伪币
{
count++;
return (a[left] < a[right]) ? left : (a[left] > a[right]) ? right : -1;
}
if ((right-left) == 2)//如果只有三枚硬币，轻者为伪币，等重则无伪币
{
count++;
if (a[left] < a[left+1])
return left;
else if (a[left] > a[left+1])
return left + 1;
else if (a[right] < a[left])
return right;
else
return -1;
}
//多余三枚硬币，将数组分成两半，分而治之
num = FalseCoin(a, left, mid);
if (num != -1)//找到伪币，直接返回
return num;
else //否则查找另一半
return FalseCoin(a, mid+1, right);
}
分成4组：
int FalseCoin(int a[], int len, int left, int right)
{
int left1, right1, left2, right2, left3, right3, left4, right4;
int sum1, sum2, sum3, sum4;
int q, i;
if (left > right)//如果子数组没有硬币
{
return -1;
}
if (right == left)//如果子数组只有一枚硬币，将其与相邻的硬币比较
{
if (left > 0)
return (a[left]<a[left-1]) ? left : (a[left]>a[left-1]) ? left-1 : -1;
if (right < len-1)
return (a[right]<a[right+1]) ? right : (a[right]>a[right+1]) ? right-1 : -1;
return -1;
}
if ((right-left) == 1)//只有两枚硬币，轻者为伪币，等重则无伪币
{
count++;
return (a[left] < a[right]) ? left : (a[left] > a[right]) ? right : -1;
}
if ((right-left) == 2)//如果只有三枚硬币，轻者为伪币，等重则无伪币
{
count++;
if (a[left] < a[left+1])
return left;
else if (a[left] > a[left+1])
return left + 1;
else if (a[right] < a[left])
return right;
else
return -1;
}
//将硬币分成4等份，若硬币总数不是4的倍数，则把另外不足4个的硬币先放在一边
q = (right - left + 1) / 4;
left1 = left;
right1 = left1 + q - 1;
left2 = right1 + 1;
right2 = left2 + q - 1;
left3 = right2 + 1;
right3 = left3 + q - 1;
left4 = right3 + 1;
right4 = left4 + q - 1;
//累计每组硬币的重量
sum1 = sum2 = sum3 = sum4 = 0;
for (i=left1; i<=right1; i++)
sum1 += a[i];
for (i=left2; i<=right2; i++)
sum2 += a[i];
for (i=left3; i<=right3; i++)
sum3 += a[i];
for (i=left4; i<=right4; i++)
sum4 += a[i];
//将硬币两两比较
count++;
if (sum1 != sum2)//伪币在第1，2组硬币中
{
if (sum1 < sum2)
return FalseCoin(a, len, left1, right1);
else
return FalseCoin(a, len, left2, right2);
}
count++;
if (sum3 != sum4) //伪币在第3，4组硬币中
{
if (sum3 < sum4)
return FalseCoin(a, len, left3, right3);
else
return FalseCoin(a, len, left4, right4);
}
return FalseCoin(a, len, right4+1, right);//等重，伪币在剩余的硬币中
}
评论