python | 秦九昭算法详细介绍

本文主要是介绍python | 秦九昭算法详细介绍，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一.算法简介

作用：

一般地，一元n次多项式的求值需要经过(n+1)*n/2次乘法和n次加法

而秦九韶算法只需要n次乘法和n次加法。

意义：

该算法看似简单，其最大的意义在于将求n次多项式的值转化为求n个一次多项式的值。在人工计算时，利用秦九韶算法和其中的系数表可以大幅简化运算；对于计算机程序算法而言，加法比乘法的计算效率要高很多，因此该算法仍有极大的意义，用于减少CPU运算时间。

详细算法作用过程：

 二、算法应用：

1、求多项式的值

from functools import reduce

def func(factors, x):
    value = reduce(lambda a, b: a * x + b, factors)#a负责储存结果，b负责去集合里取值
    return value

def qFun(factors,x):
    sum = factors[0]
    for i in range(len(factors)-1):
        sum=sum*x
        sum=sum+factors[i+1]
    return sum

factors = (3,2,4,5,6,3)
x=2
print(qFun(factors,x))
print(func(factors,x))

两个函数功能相同，但第一个高级点，第二个是傻瓜式实现

*plus*

help(reduce)结果是：

Help on built-in function reduce in module _functools:

reduce(...)
    reduce(function, sequence[, initial]) -> value
    
    Apply a function of two arguments cumulatively to the items of a sequence,
    from left to right, so as to reduce the sequence to a single value.
    For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
    ((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
    of the sequence in the calculation, and serves as a default when the
    sequence is empty.

中文解释下，就是操作一个集合，把一系列数迭代操作成一个数。

不理解就看蓝色字的例子：）

2.大整数取模（hdu 1212 Big Number）

（1）题意：

给你一个长度不超过1000的大数A，还有一个数值不超过100000的B，快速求A % B。

（2）分析：

由秦九昭算法可知，任意一个整数n = akak-1ak-2.......a2a1a0可以拆分为：

n = (((((ak)*10 + ak-1)*10 + ak-2)*10 + .......)*10 + a1)*10+a0

例如：1234 = ((1*10 + 2)*10 + 3)*10 + 4

 则大整数取模就可以转化为n个多项式每步取模。

（3） 贴份代码：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000 + 7;
char str[maxn];
int Horner(int mod){//秦九昭算法
    int len = strlen(str);
    int ans = 0;
    for(int i = 0;i<len;i++){
        ans = (ans*10 + str[i] - '0')%mod;
    }
    return ans;
}
int main()
{
    int mod;
    while(scanf("%s%d",str,&mod)!=EOF){
        int num = Horner(mod);
        printf("%d\n",num);
    }
    return 0;
}

这篇关于python | 秦九昭算法详细介绍的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！