学步园

题目链接：  http://2012.nwerc.eu/en/results/problems/

题目大意：  给出顶点数为N的图，每个顶点只与相邻的两个顶点相连

                    所有顶点就连成一个最大环

                    问删除一些边，但是不能使任何一个顶点成为孤立点

                    也就是说每个顶点至多删除一条边，有多少种情况？

                    如：  N=4时（绿色表示删除的边）

解题思路：  这道题有规律，写出前四个就可以找出来了

                    N=3   4

                    N=4   7

                    N=5   11

                    N=6   18

                    N=7   29

                    显然每一项是前面两项相加，Fibonacci数列

                    范围 3 ≤ n ≤ 10000 ,第一项第二项分别是4和7，需要用高精度处理

代码：

//Fibonacci 数列
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 2101
int gaojing (int a[],int b[])  //高精度加法,这个函数使得: b=a,a=a+b***这里是关键，可以自己想
{
    int i1,h,hc,c[SIZE]={0};
    memcpy(c,a,sizeof(c)); //把a数组拷贝给c数组
    for (i1=SIZE;i1>=0;i1--)
    {
        if (a[i1]!=0)  //纪录 a数组最大的位数
            break;
    }
    hc=i1+1;
    for (i1=0;i1<SIZE;i1++)
    {
        a[i1]+=b[i1];   //a ＝ a ＋ b，两数组相加，这个for循环是高精度加法的 核心思想
        if (a[i1]>=10)   //大于10，进1
        {
            a[i1+1]+=(a[i1]/10);
            a[i1]%=10;
        }
        if (a[i1]!=0)  //纪录a的最大位数
        {
            h=i1;
        }
    }
    memcpy(b,c,sizeof(c));
    return h;
}
 
int main ()
{
    int n,i1,h;
    while (scanf ("%d",&n)!=EOF && n>=3)
    {
        int a[SIZE]={0},b[SIZE]={0};
        a[0]=3;
        b[0]=1;
        //当大于或者等于3的时候
        for(i1=3;i1<=n;i1++)
        {
            h=gaojing(a, b);
        }
        for (i1=h;i1>=0;i1--)  //倒过来输出，因为我的数字是倒置输入到数组的
            printf("%d",a[i1]);
        printf("\n");
    }
    return 0;
}

注：原创文章，转载请注明出处