• <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>

            技術(shù),瞎侃,健康,休閑……

            mahu@cppblog 人類(lèi)的全部才能無(wú)非是時(shí)間和耐心的混合物
            posts - 11, comments - 13, trackbacks - 0, articles - 12
              C++博客 :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            The 3n + 1 problem

            Posted on 2006-06-10 00:41 mahudu@cppblog 閱讀(1315) 評(píng)論(3)  編輯 收藏 引用 所屬分類(lèi): C/C++

            Background

            Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

            The Problem

            Consider the following algorithm:

            1.	input n

            2. print n

            3. if n = 1 then STOP

            4. if n is odd then tex2html_wrap_inline44

            5. else tex2html_wrap_inline46

            6. GOTO 2

            Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

            It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

            Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

            For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

            The Input

            The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

            You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

            You can assume that no opperation overflows a 32-bit integer.

            The Output

            For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

            Sample Input

            1 10
            100 200
            201 210
            900 1000

            Sample Output

            1 10 20
            100 200 125
            201 210 89
            900 1000 174

            Solution ?

            #include <iostream>

            using namespace std;

            ?

            int cycle(intm)

            {

            ?? int i = 1;

            ?? while (m != 1){

            ????? if(m%2)

            ??????? m = m*3 + 1;

            ????? else

            ??????? m /= 2;

            ????? i++;

            ?? }

            ?? return i;

            }??

            ?

            int main()

            {

            ?? int m,n,max,temp;

            ?? int mOriginal,nOriginal;

            ?? int i;

            ?

            ?? while (cin >> m >> n){

            ????? mOriginal = m;

            ????? nOriginal = n;

            ????? if (m > n){

            ??????? temp = m;

            ??????? m = n;

            ??????? n = temp;

            ????? }

            ?

            ????? max = cycle(m);

            ????? for (i = m+1; i <= n; i++){

            ??????? temp = cycle(i);

            ??????? if (temp > max){

            ?????????? max = temp;

            ??????? }

            ????? }?

            ????? cout << mOriginal << " " << nOriginal << " " << max << endl;

            ?? }

            ?? return 0;

            }

            Feedback

            # re: The 3n + 1 problem  回復(fù)  更多評(píng)論   

            2007-11-14 20:34 by 無(wú)意中看到
            你這個(gè)程序?qū)儆诤茈y通過(guò)的,基本上會(huì)碰到超時(shí)問(wèn)題
            輸入: 1 1000000
            看你多牛的計(jì)算機(jī)3秒能搞出來(lái)
            這是典型的dp問(wèn)題,暴力是不好用的

            # re: The 3n + 1 problem  回復(fù)  更多評(píng)論   

            2008-10-18 17:17 by TaiwanNo.1
            /*
            這個(gè)可以以0.7 sec完成
            */
            #include <stdio.h>

            int compute(int a)
            {
            int cnt = 1;
            while(a > 1)
            {
            a & 0x01 ? (a = (a<<1) + a + 1) : (a >>= 1);
            ++cnt;
            }
            return cnt;
            }


            int a, b, c;
            int i, j;
            int main(void)
            {

            while(0 < scanf("%d %d", &i, &j))
            {
            c = 0;
            i < j ? (a = i, b = j) : (a = j, b = i);
            while(a <= b)
            {
            int tmp = compute(a++);
            if(tmp > c)
            c = tmp;
            }
            printf("%d %d %d\n", i, j, c);
            }
            return 0;
            }

            # re: The 3n + 1 problem  回復(fù)  更多評(píng)論   

            2011-01-16 13:39 by UDHeart
            @TaiwanNo.1
            ...我就是這樣寫(xiě)的,沒(méi)有這么快
            波多野结衣久久一区二区| 天天久久狠狠色综合| 久久久这里只有精品加勒比| 色偷偷久久一区二区三区| 精品欧美一区二区三区久久久| 欧美久久久久久| 久久久久亚洲AV无码永不| 久久只有这里有精品4| 蜜臀av性久久久久蜜臀aⅴ | 久久久久99精品成人片牛牛影视| 久久精品国产精品亚洲精品 | 国产成人无码精品久久久免费| 无码国内精品久久人妻蜜桃 | 欧美日韩精品久久久久| 色综合久久精品中文字幕首页| 久久久久久久综合日本| 久久久久免费看成人影片| 久久久久久久综合日本| 青青青伊人色综合久久| 亚洲精品国精品久久99热一| 久久播电影网| 久久精品国产99国产精品澳门| 久久精品国产亚洲av日韩| 香港aa三级久久三级老师2021国产三级精品三级在 | 91精品国产综合久久香蕉 | 婷婷久久久亚洲欧洲日产国码AV | 国产精品毛片久久久久久久 | 色悠久久久久久久综合网| 久久精品国产免费一区| 久久精品青青草原伊人| 久久亚洲国产成人精品无码区| 久久久久久一区国产精品| 99麻豆久久久国产精品免费 | 亚洲国产精品无码久久久久久曰| 久久伊人影视| 久久国产精品波多野结衣AV| 精品久久久久久中文字幕人妻最新 | 青青草原综合久久大伊人| 人妻少妇精品久久| 亚洲国产成人精品女人久久久 | 四虎亚洲国产成人久久精品|