FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

[旧文整理]Horner规则的小题目

FunctionGHW posted @ 2013年3月05日 21:22 in C语言 with tags c 递归 Horner规则 , 1547 阅读

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

《数据结构基础(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规则的迭代版本

 

AP SSC Assignment Mo 说:
2022年9月09日 21:27

Department of Government Examinations and Secondary Education Board Andhra Pradesh has conducted the Assignment Exams multiple times in the academic year in Session-1 and Session-2 (Term-1 & Term-2). There are four exams are conducted Assignment-1, Assignment-2, Assignment-3 and Assignment-4. AP SSC Assignment Model Paper Every Class 10th Standard Student Studying in Government & Private Schools in Telugu Medium, English Medium & Urdu Medium can download the AP 10th Assignment Model Paper 2023 with answer solutions for theory, objective and bit questions. Subject experts of the board have designed and introduced the practice question bank for all Part-A, Part-B, Part-C, and Part-D exams.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter