练习： 1．  小猴吃枣：小猴第一天摘下若干枣子，当即吃掉了一半，不过瘾又多吃了一个；第二天吃了剩下的一半又多吃了一个；以后每一天都吃了前一天剩下的一半多一个。到第十天小猴再想吃时，见到只剩下一只枣子了。问第一天这堆枣子有多少？   2．  MyCathy函数定义如下： x – 10  ，    x > 100 M（x）= {    M（M（x+11））， x <= 100 分别用递归和非递归方式编写函数计算给定x的M（x）的值。 3．  使用递归函数表达欧几里德算法。     4．  设对于给定的x和系数a[i]求下列n阶多项式的值： n阶多项式：Pn(x) = an.x^n + a(n-1).x^(n-1) + ... + a1.x + a0 函数接口：double Poly(double coeff[], int n, double x);     参考程序： 1. 算法分析：可用递归方法，返回第n天的桃子数量。   递归公式：F（n） = 1， n= 10； F（n） = （F（n+1）+ 1）*2， n= 10； #include <stdio.h>   int Peach(int n);   int main(void) {     int i;     for (i=1; i<=10; i++)         printf("第%d天这堆枣子有%d个\n", i, Peach(i));        getchar();     return 0;   }     int Peach(int n) {     if (n < 10)         return (Peach(n+1) + 1) * 2;     else         return 1;     }   2.递归算法： int M(int x) {     if (x > 100)         return x - 10;     else     return M(M(x + 11)); } 非递归算法: int M(int x) {     int level = 1;       if (x > 100)         return x - 10;     else     {         level++;         x += 11;     }     while (level > 0)     {         if (x > 100)         {             level--;             x -= 10;         }         else         {             level++;             x += 11;         }     }     return x; }   3. int Gcd(int m, int n)//欧几里德方法，递归 {     if (m<0 || n<0) //预防错误         return 0;     if (n == 0)         return m;        return Gcd(n, m%n); }   4. #include<stdio.h>   double Poly(double coeff[], int n, double x); double Horner2(double coeff[], int n, double x); double Horner(double coeff[], int max, int n, double x);   int main() {     double a[1000] = {1, 2, 3, 4, 5, 6, 7, 8, 9};     int n = 5;     double x = 3.5;         printf("%f\n", Poly(a, n, x));     printf("%f\n", Horner(a, n, n, x));         getchar();     return 0;       } //1. 一般计算方法 double Poly(double coeff[], int n, double x)//计算n次多项式的值，coeff[0:n]为多项式的系数 {     int i;     double y = 1;     double value = coeff[0];         for (i=1; i<=n; i++) //n循环, 累加下一项     {        y *= x; //一次乘法                 value += y * coeff[i]; //一次加法和一次乘法     }         return value; } //3n次基本运算   //2. Horner法则(秦九韶方法)：P(x)=((cn*x+cn-1)*x+cn-2)*x+···)*x+c0 double Horner2(double coeff[], int n, double x) {     int i;     double value = coeff[n];         for(i=1; i<=n; i++) //n循环         value = value * x + coeff[n-i]; //一次加法和一次乘法         return value; } //2n次基本运算   //3.递归算法 /* 多项式求值的递归算法 n阶多项式：Pn(x) = an.x^n + a(n-1).x^(n-1) + ... + a1.x + a0 利用Horner法则,把上面公式改写成:     Pn(x) = an.x^n + a(n-1).x^(n-1) + ... + a1.x + a0          = ((...((((an)x + a(n-1))x + a(n-2))x + a(n-3))x...)x + a1)x + a0 */ double Horner(double coeff[], int max, int n, double x) {     double value;         if (n == 0)         value = coeff[max-n];     else         value = Horner(coeff, max, n-1, x) * x + coeff[max-n];       return value; } //2n次基本运算   //也可以写成 double Horner(double coeff[], int max, int n, double x) {     double coeff[max-n];         if (n > 0)         value = Horner(coeff, max, n-1, x) * x + coeff[max-n];       return value; } //2n次基本运算

评论