参考程序 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);//等重，伪币在剩余的硬币中 }

评论