61阅读

斐波那契数列-如何打印斐波拉契数列以及质数列表

发布时间:2017-11-05 所属栏目:欧拉定理

一 : 如何打印斐波拉契数列以及质数列表

这其实是两道非常基础和简单地题。但somehow每隔一段时间我老是会不经意地想起这两个问题,有时候卡克没有一下想起解法还会急的直冒汗...................

言归正传,贴出这两题代码

(1)打印斐波拉契数列

//Javaprogram for Fibonacci number using Loop. public static int fibonacciLoop(int number){ if(number == 1 || number == 2){ return 1; } int fibo1=1, fibo2=1, fibonacci=1; for(int i= 3; i<= number; i++){ fibonacci = fibo1 + fibo2; //Fibonacci number is sum of previous two Fibonacci number fibo1 = fibo2; fibo2 = fibonacci; } return fibonacci; //Fibonacci number }
(2)打印质数
public static void prime( int number) { for (int i=2; isqrt(i)) { System.out.println(i); } } return 0;}

二 : 斐波那契数列的都有哪些常见的性质?越详尽越好。

斐波那契数列

斐波那契数列的都有哪些常见的性质?越详尽越好。


随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..…

从第二项开始,每个奇数项的平方都比前后两项之积多1,每个偶数项的平方都比前后两项之积少1。

斐波那契数列的第n项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数。

斐波那契数列(f(n),f(0)=0,f⑴=1,f⑵=1,f⑶=2……)的其他性质:

1.f(0)+f⑴+f⑵+…+f(n)=f(n+2)-1。

2.f⑴+f⑶+f⑸+…+f(2n-1)=f(2n)。

3.f⑵+f⑷+f⑹+…+f(2n) =f(2n+1)-1。

4.[f(0)]^2+[f⑴]^2+…+[f(n)]^2=f(n)·f(n+1)。

5.f(0)-f⑴+f⑵-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]-1。

6.f(n+m)=f(n+1)·f(m)+f(n)·f(m-1)。

每3个连续的数中有且只有一个被2整除,

每4个连续的数中有且只有一个被3整除,

每5个连续的数中有且只有一个被5整除,

每6个连续的数中有且只有一个被8整除,

每7个连续的数中有且只有一个被13整除,

每8个连续的数中有且只有一个被21整除,

每9个连续的数中有且只有一个被34整除,

三 : hdu4549---M斐波那契数列(矩阵+欧拉定理)

Problem Description
M斐波那契数列F[n]是一种整数数列,它的定义如下:

F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n>1 )

现在给出a, b, n,你能求出F[n]的值吗?

Input
输入包含多组测试数据;
每组数据占一行,包含3个整数a, b, n( 0<= a, b, n<= 10^9 )

Output
对每组测试数据请输出一个整数F[n],由于F[n]可能很大,你只需输出F[n]对1000000007取模后的值即可,每组数据输出一行。

Sample Input

0 1 0 6 10 2

Sample Output

0 60

Source
2013金山西山居创意游戏程序挑战赛——初赛(2)

Recommend
liuyiding | We have carefully selected several similar problems for you: 5189 5188 5186 5185 5184

可以发现,每一项上面的指数,刚好是fib数
但是直接做指数太大,mod为素数
所以根据欧拉定理
mod的欧拉函数值为mod-1
a^b = a^(b%(mod - 1)
然后就可以做了

/*************************************************************************>File Name: hdu4549.cpp>Author: ALex>Mail: zchao1995@gmail.com>Created Time: 2015年03月16日 星期一 20时12分13秒 ************************************************************************/#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;typedef long long LL;typedef pairPLL;const LL mod = 1000000006;class MARTIX{ public: LL mat[3][3]; MARTIX(); MARTIX operator * (const MARTIX &b)const; MARTIX& operator = (const MARTIX &b);};MARTIX :: MARTIX(){ memset (mat, 0, sizeof(mat));}MARTIX MARTIX :: operator * (const MARTIX &b)const{ MARTIX ret; for (int i = 0; i<2; ++i) { for (int j = 0; j<2; ++j) { for (int k = 0; k<2; ++k) { ret.mat[i][j] += this ->mat[i][k] * b.mat[k][j]; ret.mat[i][j] %= mod; } } } return ret;}MARTIX& MARTIX :: operator = (const MARTIX &b){ for (int i = 0; i<2; ++i) { for (int j = 0; j<2; ++j) { this ->mat[i][j] = b.mat[i][j]; } } return *this;}MARTIX fastpow(MARTIX A, int n){ MARTIX ans; ans.mat[0][0] = ans.mat[1][1] = 1; while (n) { if (n & 1) { ans = ans * A; } n>>= 1; A = A * A; } return ans;}LL fast(LL a, LL n){ LL b = 1; while (n) { if (n & 1) { b = a * b % 1000000007; } a = a * a % 1000000007; n>>= 1; } return b;}int main (){ LL a, b, n; while (~scanf("%lld%lld%lld", &a, &b, &n)) { MARTIX F; F.mat[0][0] = F.mat[0][1] = F.mat[1][0] = 1; if (n == 0) { printf("%lld\n", a); continue; } if (n == 1) { printf("%lld\n", b); continue; } MARTIX A; A.mat[0][0] = 1; A.mat[0][1] = 0; F = fastpow(F, n - 1); F = A * F; LL cnt1 = F.mat[0][1]; LL cnt2 = F.mat[0][0]; LL ans = fast(a, cnt1); ans = ans * fast(b, cnt2) % 1000000007; printf("%lld\n", ans); } return 0;}

本文标题:斐波那契数列-如何打印斐波拉契数列以及质数列表
本文地址: http://www.61k.com/1062229.html

61阅读| 精彩专题| 最新文章| 热门文章| 苏ICP备13036349号-1