首页 > ACM题库 > HDU-杭电 > HDU 1250 Hat’s Fibonacci-高精度-[解题报告] C++
2013
12-04

HDU 1250 Hat’s Fibonacci-高精度-[解题报告] C++

Hat’s Fibonacci

问题描述 :

A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1.
F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n – 1) + F(n-2) + F(n-3) + F(n-4)
Your task is to take a number as input, and print that Fibonacci number.

输入:

Each line will contain an integers. Process to end of file.

输出:

For each case, output the result in a line.

样例输入:

100

样例输出:

4203968145672990846840663646


Note:
No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.

2011-12-26 00:33:25

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1250

题意:F[1] = F[2] = F[3] = F[4] = 1。F[n] = F[n-1]+F[n-2]+F[n-3]+F[n-4]。输入n,求F[n]。大数运算。

代码:

# include <stdio.h>


int a[6][2100] ;
int buff[2100] ;


void add(int x[], int y[])
{
    int i, *p, *q, cc = 0 ;
    if (x[0] < y[0]) p = x, q  = y ;
    else p = y, q = x ;
    
    for (i = 1 ; i <= q[0] ; i++)
    {
        if (i <= p[0]) buff[i] = p[i] ;
        else buff[i] = 0 ;
        buff[i] += q[i] + cc ;
        cc = buff[i] / 10 ;
        buff[i] %= 10 ;
    }
    if (cc != 0) buff[i++] = cc ;
    buff[0] = i-1 ;
    for (i = 0 ; i <= buff[0] ; i++)
        x[i] = buff[i] ;
}


void cpy(int a[], int b[])
{
    int i ;
    for (i = 0 ; i <= b[0] ; i++)
        a[i] = b[i] ;
}


void output (int a[])
{
    int i ;
    for (i = a[0]  ; i>= 1 ; i--)
        printf ("%d", a[i]) ;
    printf ("\n") ;
}


int main ()
{
    int n, i, j ;
    while (~scanf ("%d", &n))
    {
        if (n <= 4){
            puts ("1") ;
            continue ;
        }
        for (i = 0 ; i < 4 ; i++)
            a[i][0] = a[i][1] = 1 ;
        for (i = 0 ; i < n -4 ; i++)
        {
            a[4][0] = 1, a[4][1] = 0 ;
            for (j = 0 ; j < 4 ; j++)
                add(a[4], a[j]) ;
            for (j = 1 ; j < 5 ; j++)
                cpy (a[j-1], a[j]) ;
        }
        output (a[4]) ;
    }
    return 0 ;
}


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks