• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            ZOJ 2060 Fibonacci Again

            Posted on 2010-09-28 11:57 李東亮 閱讀(622) 評論(0)  編輯 收藏 引用

            Fibonacci Again

            【題目描述】

            There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2)
            Input
            Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000)
            Output
            Print the word "yes" if 3 divide evenly into F(n).
            Print the word "no" if not.
            Sample Input
            0
            1
            2
            3
            4
            5
            Sample Output
            no
            no
            yes
            no
            no
            no

            這道題應該說是很簡單的題,如果說考察了什么知識點的話時能說是(a+b%n = (a%n + b%n)%n,但是這個題卻有多種思路,可以從很多方面優化,比較有意思。

            【解題思路1】:

            最簡單的思路,開一個大小為n的數組,初始化為0,遍歷一遍,如果某一項滿足條件則設置為1,就不多說了,代碼如下:

            #include <stdio.h>
            #include 
            <stdlib.h>

            int r[1000000];
            int main(void)
            {
                
            int a, b, tmp;
                
            int i;
                
            int n;
                a 
            = 7;
                b 
            = 11;
                r[
            0= r[1= 0;
                
            for (i = 2; i < 1000000++i)
                {
                    tmp 
            = ((a%3+ (b%3)) % 3;
                    
            if (tmp == 0)
                        r[i] 
            = 1;
                    a 
            = b;
                    b 
            = tmp;
                }
                
            while (scanf("%d"&n) == 1)    
                {
                    
            if (r[n] == 0)
                        printf(
            "no\n");
                    
            else
                        printf(
            "yes\n");
                }
                
            return 0;
            }

            這個提交上去,由于執行時只查表,時間不算多10ms,但是內存消耗不小。下面看幾種優化的方法。

            【思路2

            這種題一般情況下會有規律。把前幾個能被3整除的數的下標列出來一看,規律就出現了:2 6 10 14…,這就是一個等差數列嘛,這就好辦了,an = a1 + (n-1)*4,那么an-a1肯定能被4整除。代碼如下:

            #include <stdio.h>
            #include 
            <stdlib.h>

            int main(void)
            {
                
            int n;
                
            while (scanf("%d"&n) == 1)    
                {
                    
            if ((n-2)%4 == 0)
                        printf(
            "yes\n");
                    
            else
                        printf(
            "no\n");
                }
                
            return 0;
            }

            該解法如果說還可以優化的話,那只能把取余運算變為位運算了。

            if ((n-2)&3)

                                 printf("no\n");

                          else

                                 printf("yes\n");

            【思路3

            如果把數列前幾項的值列出來,會發現數組中每8項構成一個循環。這也很好辦。

            代碼如下:

            #include <stdio.h>
            #include 
            <stdlib.h>

            int a[8];
            int main(void)
            {
                
            int n;
                a[
            2= a[6= 1;
                
            while (scanf("%d"&n) == 1)
                    printf(
            "%s\n", a[n%8== 0 ? "no" : "yes" );
                
            return 0;
            }

            其實這個還可以優化,我們仔細觀察可以看到這些滿足條件的下標有一個特點:

            N%8 == 2或者n%8==6

            代碼如下:

            #include <stdio.h>
            #include 
            <stdlib.h>

            int main(void)
            {
                
            int n;
                
            while (scanf("%d"&n) == 1)
                {
                    
            if (n%8 == 2 || n%8 == 6)
                        printf(
            "yes\n");
                    
            else
                        printf(
            "no\n");
                }
                
            return 0;
            }

             

             

            posts - 12, comments - 1, trackbacks - 0, articles - 1

            Copyright © 李東亮

            久久国产福利免费| 亚洲精品无码专区久久久| 久久99亚洲网美利坚合众国| 精品免费久久久久久久| 国产精品久久午夜夜伦鲁鲁| 色综合久久88色综合天天| 久久精品免费网站网| 久久成人小视频| 亚洲国产欧美国产综合久久| 久久91精品久久91综合| 久久综合视频网站| 久久永久免费人妻精品下载| 99热都是精品久久久久久| 久久久无码精品亚洲日韩京东传媒 | 久久久无码精品亚洲日韩软件| 国产69精品久久久久APP下载 | 国产精品成人久久久久三级午夜电影 | 久久午夜电影网| 久久精品一区二区影院| 久久人爽人人爽人人片AV| 久久综合九色综合久99| 久久91精品久久91综合| 777午夜精品久久av蜜臀| 久久免费大片| 久久久久久久99精品免费观看| 久久国产欧美日韩精品| 亚洲国产精品久久久久网站| 久久久一本精品99久久精品88| 久久精品国产欧美日韩| 青草影院天堂男人久久| 久久久久人妻精品一区二区三区| 国内精品久久国产| 性做久久久久久久久老女人| 国产精自产拍久久久久久蜜| 久久久精品午夜免费不卡| 91久久婷婷国产综合精品青草| 亚洲另类欧美综合久久图片区| 久久99国产一区二区三区| 久久国产成人精品麻豆| 一级做a爰片久久毛片人呢| 久久夜色tv网站|