2013
12-04

# 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

# include <stdio.h>

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

{
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++)
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