Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1541066
  • 博文数量: 327
  • 博客积分: 10000
  • 博客等级: 上将
  • 技术积分: 3556
  • 用 户 组: 普通用户
  • 注册时间: 2005-04-05 21:28
个人简介

东黑布衣,流浪幽燕。 真诚善良,值得信赖。

文章分类

全部博文(327)

我的朋友

分类: BSD

2018-04-21 21:59:48



Codebegin

  1. #include "stdafx.h"
  2. #include <stdio.h>
  3. #include <memory.h>

  4. __int64 fb[1005];/* n很大的时候数组会溢出 */

  5. __int64 fib0(int n)/*自顶而下递归*/
  6. {
  7.    return (2>n)?(__int64)n /*达到递归基直接取值*/
  8.       :fib0(n-1)+fib0(n-2);
  9. }

  10. __int64 fib1(int n)/*memoization*/
  11. {
  12.    if(0==n)
  13.       return (__int64)(fb[0]=0);
  14.    if(1==n)
  15.       return (__int64)(fb[1]=1);
  16.    if(fb[n]>=0){/*不是-1说明之前算过了,直接返回,剪掉一颗子树节省大量时间*/
  17.       return (__int64)(fb[n]);
  18.    }else{
  19.       return fb[n]=fib1(n-1)+fib1(n-2);
  20.    }
  21. }

  22. __int64 fib2(int n)/*自底而上迭代*/
  23. {
  24.    __int64 f=0;
  25.    __int64 g=1;
  26.    while(0<n--)
  27.    {
  28.       g=g+f;
  29.       f=g-f;
  30.    }
  31.    return f;
  32. }

  33. /* c = a*b
  34. a[0][0] a[0][1] b[0][0] b[0][1] c[0][0] c[0][1]
  35. a[1][0] a[1][1] b[1][0] b[1][1] c[1][0] c[1][1]

  36. i=0 j=0: i k k j
  37. c[0][0]+=a[0][0]*b[0][0] k=0
  38. c[0][0]+=a[0][1]*b[1][0] k=1
  39. i=0 j=1: i k k j
  40. c[0][1]+=a[0][0]*b[0][1] k=0
  41. c[0][1]+=a[0][1]*b[1][1] k=1
  42. i=1 j=0: i k k j
  43. c[1][0]+=a[1][0]*b[0][0] k=0
  44. c[1][0]+=a[1][1]*b[1][0] k=1
  45. i=1 j=1: i k k j
  46. c[1][1]+=a[1][0]*b[0][1] k=0
  47. c[1][1]+=a[1][1]*b[1][1] k=1
  48. */
  49. void multi_mtrx1(__int64 a[2][2],__int64 b[2][2])
  50. {
  51.    int i,j,k;
  52.    __int64 c[2][2];
  53.    memset(c,0,sizeof(c));
  54.    for(i=0;i<2;i++){
  55.       for(j=0;j<2;j++){
  56.          for(k=0;k<2;k++){
  57.             c[i][j]+=a[i][k]*b[k][j];
  58.             //c[i][j]%=c[i][j];/*加上这一句*/
  59.          }
  60.       }
  61.    }
  62.    for(i=0;i<2;i++)
  63.       for(j=0;j<2;j++)
  64.          a[i][j]=c[i][j];
  65. }


  66. /* 这种方法比较难于理解,好处是如果n比较大,且矩阵比较稀疏的时候可以剪枝
  67. i=0 k=0: i k k j
  68. c[0][0]+=a[0][0]*b[0][0] j=0
  69. c[0][1]+=a[0][0]*b[0][1] j=1
  70. i=0 k=1: i k k j
  71. c[0][0]+=a[0][1]*b[1][0] j=0
  72. c[0][1]+=a[0][1]*b[1][1] j=1
  73. i=1 k=0: i k k j
  74. c[1][0]+=a[1][0]*b[0][0] j=0
  75. c[1][1]+=a[1][0]*b[0][1] j=1
  76. i=1 k=1: i k k j
  77. c[1][0]+=a[1][1]*b[1][0] j=0
  78. c[1][1]+=a[1][1]*b[1][1] j=1
  79. */
  80. void multi_mtrx2(__int64 a[2][2],__int64 b[2][2])
  81. {
  82.    int i,j,k;
  83.    __int64 c[2][2];
  84.    memset(c,0,sizeof(c));
  85.    for(i=0;i<2;i++){
  86.       for(k=0;k<2;k++)
  87.       {
  88.          if(0==a[i][k])/*剪枝,但其实对于2x2的矩阵意义不大*/
  89.             continue;

  90.          for(j=0;j<2;j++){
  91.             c[i][j]+=a[i][k]*b[k][j];
  92.             //c[i][j]%=c[i][j];/*加上这一句*/
  93.          }
  94.       }
  95.    }
  96.    for(i=0;i<2;i++)
  97.       for(j=0;j<2;j++)
  98.          a[i][j]=c[i][j];
  99. }

  100. void quick_pow(__int64 rslt[2][2],int power)
  101. {
  102.    __int64 fi[2][2];
  103.    rslt[0][0]=rslt[1][1]=1;
  104.    rslt[0][1]=rslt[1][0]=0;
  105.    fi[1][1]=0;
  106.    fi[0][0]=fi[0][1]=fi[1][0]=1;
  107.    while(power){
  108.       if(power&1)
  109.          multi_mtrx2(rslt,fi);
  110.       multi_mtrx2(fi,fi);
  111.       power>>=1;
  112.    }
  113. }

  114. __int64 fib3(int n)
  115. {
  116.    __int64 rslt[2][2];
  117.    quick_pow(rslt,n);
  118.    return rslt[0][1];
  119. }

  120. int main(int argc, char* argv[])
  121. {
  122.    int n;
  123.    memset(fb,-1,sizeof(fb));
  124.    /* 最大n为103,超出程序就不会给出正确结果 */
  125.    while(-1!=scanf("%d",&n) && -1!=n)
  126.    {
  127.       printf("fib3 result is %lld\n",fib1(n));
  128.       printf("fib3 result is %lld\n",fib2(n));
  129.       printf("fib4 result is %lld\n",fib3(n));
  130.    }
  131.    return 0;
  132. }
Codeend


最后附上POJ的一道题,该题只需要计算Fn mod 10000, 这样在矩阵乘法的函数当中
加上mod操作,而所有是数组也不用__int64, 用int 就可以
c[i][j]+=a[i][k]*b[k][j]; =>
c[i][j]+=a[i][k]*b[k][j];
c[i][j]%=c[i][j];/*加上这一句*/

「POJ3070」Fibonacci

Description

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn ? 1 + Fn ? 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

An alternative formula for the Fibonacci sequence is

.

Given an integer n, your goal is to compute the last 4 digits of Fn.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number ?1.

Output

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input
0
9
999999999
1000000000
-1

Sample Output
0
34
626
6875

.

Note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:

.








阅读(2896) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~