• <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 人類的全部才能無(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 閱讀(1311) 評(píng)論(3)  編輯 收藏 引用 所屬分類: 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)有這么快
            国产精品一久久香蕉国产线看| 一级做a爱片久久毛片| 久久亚洲精品国产亚洲老地址| 久久久99精品一区二区| 久久夜色撩人精品国产| 日韩乱码人妻无码中文字幕久久| 精品无码久久久久国产动漫3d| 男女久久久国产一区二区三区| 久久精品国产免费| 2019久久久高清456| 99久久中文字幕| 色综合久久夜色精品国产| 69SEX久久精品国产麻豆| 久久久久久亚洲精品无码| 中文字幕日本人妻久久久免费| 久久大香香蕉国产| 一本久久精品一区二区| 久久99精品久久久久久| 久久午夜夜伦鲁鲁片免费无码影视 | 国产成人久久777777| 亚洲日韩欧美一区久久久久我| 久久精品国产亚洲av水果派| 狠狠久久综合伊人不卡| 久久综合给久久狠狠97色| 久久国产成人午夜aⅴ影院| avtt天堂网久久精品| 国产成人精品综合久久久久| 久久国产精品免费一区| 久久精品这里热有精品| 精品久久人妻av中文字幕| 久久亚洲sm情趣捆绑调教| 久久精品无码免费不卡| 一本久久a久久精品综合夜夜 | 久久久WWW成人| 久久国产精品久久精品国产| 无码久久精品国产亚洲Av影片| 久久精品国产2020| 久久精品日日躁夜夜躁欧美| 久久精品综合网| 亚洲中文字幕伊人久久无码| 亚洲国产综合久久天堂|