搜搜做题作业网问一个数论的同余问题,与递归有关的!
来源：学生作业帮 编辑：搜搜做题作业网作业帮 分类：综合作业 时间：2024/07/02 04:02:06
问一个数论的同余问题,与递归有关的!
一个序列如下定义：
f(1) = 1,f(2) = 1,f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
给定A,B,n求f(n).
我是用程序去直接计算这个f(n)的,但是数据量过大的时候非常的耗时,这个利用数学知识,可不可以进行恒等变形,减小运算量?
一个序列如下定义：
f(1) = 1,f(2) = 1,f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
给定A,B,n求f(n).
我是用程序去直接计算这个f(n)的,但是数据量过大的时候非常的耗时,这个利用数学知识,可不可以进行恒等变形,减小运算量?
（1）递归算法的确效率是比较低的,你看能不能尝试用非递归的算法做.
如果能消除算法的递归调用,会比递归的明显要快很多的.
自己定义一个栈来模拟下递归调用.
（2）后面是对7求余.就是说f(n)总是在0-6之间.那你可以编程输出到了哪两个数是等于f(1),f(2),则可以得到周期,自己可以得到f(n)了.
那问题就转化为求周期了.
对于周期公式还在想.可能做不出来.
如果能消除算法的递归调用,会比递归的明显要快很多的.
自己定义一个栈来模拟下递归调用.
（2）后面是对7求余.就是说f(n)总是在0-6之间.那你可以编程输出到了哪两个数是等于f(1),f(2),则可以得到周期,自己可以得到f(n)了.
那问题就转化为求周期了.
对于周期公式还在想.可能做不出来.