练习：
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次基本运算
评论