前段时间忙这考试,快考完了,继续坚持。
http://acm.nit.net.cn/showproblem.jsp?pid=1019
Fib问题,矩阵解法。注意数据范围
#include <stdio.h>
#define NTYPE long long
#define MTYPE int
const int A[2][2] = {{1, 1},
{1, 0}};
int main()
{
MTYPE m;
NTYPE n;
while(scanf("%lld %d", &n, &m) != EOF)
{
printf("%d\n", Fib(n, m));
}
return 0;
}
void A_power(int result[][2], NTYPE n, MTYPE m)
{
int temp[2][2]={{1, 1},
{1, 0}};
int ttemp[2][2];
int result_temp[2][2]={{1, 1},
{1, 0}};
while(n)
{
if(n & 1)
{
result_temp[0][0] = result[0][0] * temp [0][0] + result[0][1] * temp [1][0];
result_temp[0][1] = result[0][0] * temp [0][1] + result[0][1] * temp [1][1];
result_temp[1][0] = result[1][0] * temp [0][0] + result[1][1] * temp [1][0];
result_temp[1][1] = result[1][0] * temp [0][1] + result[1][1] * temp [1][1];
result[0][0] = result_temp[0][0]%m;
result[0][1] = result_temp[0][1]%m;
result[1][0] = result_temp[1][0]%m;
result[1][1] = result_temp[1][1]%m;
}
ttemp[0][0] = temp[0][0] * temp [0][0] + temp [0][1] * temp [1][0];
ttemp[0][1] = temp[0][0] * temp [0][1] + temp [0][1] * temp [1][1];
ttemp[1][0] = temp[1][0] * temp [0][0] + temp [1][1] * temp [1][0];
ttemp[1][1] = temp[1][0] * temp [0][1] + temp [1][1] * temp [1][1];
temp[0][0] = ttemp[0][0]%m;
temp[0][1] = ttemp[0][1]%m;
temp[1][0] = ttemp[1][0]%m;
temp[1][1] = ttemp[1][1]%m;
n >>= 1;
}
}
int Fib(NTYPE n, MTYPE m)
{
int result[2][2]={{1, 1},
{1, 0}};
if( n >= 2)
{
A_power(result, n-2, m);
}
return result[0][0] % m;
}
分享到:
相关推荐
要求使用合适的逻辑电路的设计方法,通过工具软件 logisim 进行斐波那契(Fibonacci)数列计算器设计和验证,记录实验结果,验证设计是否达到要求。 通过斐波那契(Fibonacci)数列计算器的设计、仿真、验证 3 个训练...
Fibonacci(斐波那契)数列的JAVA解法,包含了斐波那契数列常见问题的一些算法。
Fibonacci Heap (斐波那契堆)的定义和实现。
Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个。 最近在玩Python,在粗略的看了一下Learning Python和Core Python之后,偶然发现网上有个帖子Python程序员的进化写的很有意思。...
根据给定的n值,计算Fibonacci数 程序输出FIB(n)
fibonacci序数列,提供一个模块提供学习
Fibonacci数列斐波那契数列PPT学习教案.pptx
斐波那契回调划线,自动划线,支撑位和阻力位
matlab 斐波那契法 代码 运筹学作业编程实现
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。java代码实现该数列
封装的Fibonacci 斐波那契数列。输入想要的斐波那契数列的长度,输出结果数列
在clion中对fibonacci heap的完全实现,亲测有效。
用logisim实现斐波那契数列,斐波那契数列的计算公式为:f(n+2)=f(n+1)+f(n),f(1)=f(2)=1。
很小的程序,运行程序时开子线程运算Fibonacci序列,父线程输出
本代码使用C++语言书写,编译环境VS2013。...斐波那契数列(Fibonacci Sequence)又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、…… 本代码是练习作品,如有错误或修改,请指正,感谢感谢。
递归方法 def fibonacci(n): if n <= 1: return n else: return fibonacci(n-1) + fibonacci(n-2) n = int(input("请输入要计算的斐波那契数列的项数:")) print("斐波那契数列的第", n, "项为:", fibonacci(n)) 2...
算法-数论- 斐波那契数列(Fibonacci).rar
斐波那契程序取一个整数,并打印出斐波那契数列的该项。 在程序中创建斐波那契数列。 只存储最后两个值。
C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++...
# 题目:斐波那契数列。 # 程序分析:斐波那契数列(Fibonacci sequence),从1,1开始,后面每一项等于前面两项之和。图方便就递归实现,图性能就用循环。