霍纳规则(C/C++,Scheme)

一、背景

霍纳(Horner)规则是采用最少的乘法运算策略,来求多项式

A(x)=anxn+an1xn1+...+a1x+a0

在x0处的值。

该规则为

A(x0)=(...((anx0+an1)x0+...+a1)x0+a0)

二、分析

如果光看着式子或许会有点烦躁,不妨手动设定几个值到式子中去来手工运算一番,这样一来也会有些亲身的理解。

通过分解我们注意到,从右往左来看,每一个小式子都是如此:

somethingx0+ai

三、代码

C语言版

#include <stdio.h>
#include <stdlib.h>

int hornerRule(int list[],int m,int x0);

int main()
{
    int m,x0;
    printf("Enter an integer (length of list): \n");
    scanf("%d",&m);
    int list[m];
    printf("Enter some integers for list: \n");
    int i;
    for(i=m-1;i>=0;i--)
    {
        scanf("%d",&list[i]);
    }
    printf("Enter an integer for x0: \n");
    scanf("%d",&x0);
    printf("%d",hornerRule(list,m,x0));

    return 0;
}

int hornerRule(int list[],int m,int x0)
{
    if(m<=1)
        return list[0];
    else
        return list[0]+(hornerRule(list+1,m-1,x0))*x0;
}

C++语言版

#include <iostream>

using namespace std;

int hornerRule(int list[],int m,int x0);

int main()
{
    int m,x0;
    cout<<"Enter an integer (length of list):"<<endl;
    cin>>m;
    int list[m];
    cout<<"Enter some integers for list:"<<endl;
    for(int i=m-1;i>=0;i--)
    {
        cin>>list[i];
    }
    cout<<"Enter an integer for x0:"<<endl;
    cin>>x0;

    cout<<hornerRule(list,m,x0);

    return 0;
}

int hornerRule(int list[],int m,int x0)
{
    if(m<=1)
        return list[0];
    else
        return list[0]+(hornerRule(list+1,m-1,x0))*x0;
}

四、测试

霍纳规则(C/C++,Scheme)

五、进阶

(PS:博主有一段时间没有碰Scheme有点忘了,所以下面的代码可能有些……粗糙)
关于Scheme可以看这里:
专栏:SICP练习
专栏:Scheme归纳

(define (Horner list m x0)
  (define (Horner-iter ls n)
    (if (<= n 1)
    (car ls)
    (+ (car ls) (* (Horner-iter (cdr ls) (- n 1)) x0))))
  (Horner-iter list m))

(define list '(1 2 1 0 3 1))
;Value: list

(Horner list 6 10)
;Value: 130121



为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp

上一篇:流量统计软件BANDWIDTHD实战


下一篇:独家下载 | “伏羲”神算!阿里巴巴经济体核心调度系统揭秘