本来打算最近好好整理几篇博客的，但是最近忙于学校的实习(其实感觉就像报了个培训班)，蛋疼死了。看着博客那么空就先整理篇简单的吧，呵呵。

在《数据结构基础(C语言版)(第2版)》(Fundamentals of Data Structures in C, 2nd) 看到的一个小题目——Horner规则。一个递归版本，一个迭代版本，原来是两篇博文(好吧,纯属凑数)。不过这个递归算是我首次尝试写递归程序了。其实感觉迭代比递归更好，毕竟程序太小。重在思想吧，递归的形式确实简洁点。

递归版本：

#include <stdio.h>

/*Horner规则使多项式求值所需乘法次数最少
 *   对 A(x) = a[n]x^n + a[n-1]x^(n-1) + ... + a[1]x^1 + a[0]x^0
 *     有A(x) = (...((a[n]x + a[n-1])x + ... + a[1])x + a[0])
 *
 *   这是个递归实现:
 *     coeffi_array: 系数数组首地址;
 *     max_index: 系数数组的最后一项的索引(上式中的 n );
 *     x: 呵呵,未知数呗. 用具体的数带入
 *   
 *   Note: 规定在多项式的常数项中(a[0]), 有 0^0 = 1.
 * */
int horner_recursive(const int *coeffi_array, int max_index, int x)
{
    if ( !max_index )
    {
        return *coeffi_array;
    }
    return horner_recursive(coeffi_array + 1, max_index - 1, x) * x + *coeffi_array;
}

//Application start.
int main(void)
{
    int result = 0, 
        i = 0, 
        x = 0, 
        amount = 0;
    do
    {
        printf("Input the amount of coefficients(include zero.):");
        scanf("%d", &amount);
    } while (amount <= 0);

    int a[amount];
    printf("Input the cofficients(Like:x,y,z  or  x y z):");
    for (i = 0; i < amount; ++i)
    {
        scanf("%d", &a[i]);
    }

    printf("Input the x:");
    scanf("%d", &x);

    result = horner_recursive(a, amount - 1, x);
    printf("The result is :%d", result);

    getch();
    return 0;
}
                
                

迭代版本：

#include <stdio.h>

/*Horner规则使多项式求值所需乘法次数最少
 *   对 A(x) = a[n]x^n + a[n-1]x^(n-1) + ... + a[1]x^1 + a[0]x^0
 *     有A(x) = (...((a[n]x + a[n-1])x + ... + a[1])x + a[0])
 *
 *   这是个迭代实现:
 *     coeffi_array: 系数数组首地址;
 *     max_index: 系数数组的最后一项的索引(上式中的 n );
 *     x: 呵呵,未知数呗. 用具体的数带入
 *
 *   Note: 规定在多项式的常数项中(a[0]), 有 0^0 = 1.
 * */
int horner_iterative(const int *coeffi_array, int max_index, int x)
{
    int result = coeffi_array[max_index];
    while(max_index)
    {
        result = result * x + coeffi_array[--max_index];
    }
    return result;
}

//Application start.
int main(void)
{
    int result = 0, 
        i = 0, 
        x = 0, 
        amount = 0;
    do
    {
        printf("Input the amount of coefficients(include zero.):");
        scanf("%d", &amount);
    } while (amount <= 0);

    int a[amount];
    printf("Input the cofficients(Like:x,y,z  or  x y z):");
    for (i = 0; i < amount; ++i)
    {
        scanf("%d", &a[i]);
    }

    printf("Input the x:");
    scanf("%d", &x);

    result = horner_iterative(a, amount - 1, x);
    printf("The result is :%d", result);

    getch();
    return 0;
}
                
    

2013-3-11， 在此补上旧文链接。

旧文链接: Horner规则的递归实现

旧文链接: Horner规则的迭代版本