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

            Brian Warehouse

            Some birds aren`t meant to be caged, their feathers are just too bright... ...
            posts - 40, comments - 16, trackbacks - 0, articles - 1

            POJ 1012 2244 Joseph 問(wèn)題詳解

            Posted on 2010-08-17 13:42 Brian 閱讀(2100) 評(píng)論(3)  編輯 收藏 引用 所屬分類(lèi): POJ

            約瑟夫環(huán)實(shí)在是太奇妙啦(我很高興我的這篇原創(chuàng)文章被不少人轉(zhuǎn)載了,雖然他們都沒(méi)有引用出處... ...)!
            1012 Joseph
            Description

            The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

            Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.

            Input

            The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.

            Output

            The output file will consist of separate lines containing m corresponding to k in the input file.
            2244 Eeny Meeny Moo

            Description

            Surely you have made the experience that when too many people use the Internet simultaneously, the net becomes very, very slow.
            To put an end to this problem, the University of Ulm has developed a contingency scheme for times of peak load to cut off net access for some cities of the country in a systematic, totally fair manner. Germany's cities were enumerated randomly from 1 to n. Freiburg was number 1, Ulm was number 2, Karlsruhe was number 3, and so on in a purely random order.
            Then a number m would be picked at random, and Internet access would first be cut off in city 1 (clearly the fairest starting point) and then in every mth city after that, wrapping around to 1 after n, and ignoring cities already cut off. For example, if n=17 and m=5, net access would be cut off to the cities in the order [1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7]. The problem is that it is clearly fairest to cut off Ulm last (after all, this is where the best programmers come from), so for a given n, the random number m needs to be carefully chosen so that city 2 is the last city selected.

            Your job is to write a program that will read in a number of cities n and then determine the smallest integer m that will ensure that Ulm can surf the net while the rest of the country is cut off.

            Input

            The input will contain one or more lines, each line containing one integer n with 3 <= n < 150, representing the number of cities in the country.
            Input is terminated by a value of zero (0) for n.

            Output

            For each line of the input, print one line containing the integer m fulfilling the requirement specified above.
             
            1012打表做法 C :
            #include<stdio.h>
            int a[14]={2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,13482720};
            int main()
            {
             int i;
             while ( scanf("%d",&i), i != 0 )
              printf("%d\n",a[i-1]);
             return 0;
            } // 這是從網(wǎng)上找的做法,號(hào)稱(chēng)打表法,這些數(shù)據(jù)依舊要通過(guò)建立循環(huán)鏈表或是別的模擬法來(lái)求出。但是單純?yōu)榱薃C,這種做法真的是相當(dāng)有效,講白了就是有目的的窮舉結(jié)果。
            1012模擬法 C: 可惜呀可惜!這個(gè)總是 超時(shí)!我不知道是什么原因。但是思路是正確的,可能有些地方我沒(méi)有考慮到,看到這篇日志的人請(qǐng)指點(diǎn)。
            #include<stdio.h>
            int main()
            {
             int i,m,k,cur,rest;
             
             while(1)
             {
              i=0; // the use ... sort of m in the question
              m=0;
              scanf("%d",&k);
              if (k == 0) break;
              while (1)
              {
               i++;
               rest=2*k; // good + bad guys
               cur=0;
               while (1)
               {
                cur=(cur+i-1)%rest; // find next from ZERO!
                if (cur >= k)
                 rest--;
                else break;
               }
               if (rest == k)
               {
                m=i;
                break;
               }
              }
              printf("%d\n",m);
             }
             return 0;
            }
            對(duì)于 2244,建議看一個(gè)牛人的ACM博客: www.shnenglu.com/AClayton/archive/2007/11/06/35964.html
            我就是看這篇博文的,很牛的一個(gè)人 AClayton ,寫(xiě)的日期剛好是我生日,下面是其全部博文:
            --------------------------------------------------------------------------------------------------------------------------------------------

             在沒(méi)有明白約瑟夫問(wèn)題之前,只能用模擬來(lái)做.
                  約瑟夫問(wèn)題是這樣的:
                  假設(shè)n個(gè)人,編號(hào)為1到n,排成一個(gè)圈,順時(shí)針從1開(kāi)始數(shù)字m,數(shù)到m的人殺了,剩下的人繼續(xù)游戲.活到最后的一個(gè)人是勝利者.一般來(lái)說(shuō)需要編程求解最后一個(gè)人的編號(hào).
                  思路是這樣的:
                 假設(shè)當(dāng)前剩下i個(gè)人(i<=n),顯然這一輪m要掛(因?yàn)榭偸菑?開(kāi)始數(shù)).經(jīng)過(guò)這一輪,剩下的人是:1 2 3 ... m- 1 m + 1 ... i, 我們將從m+1開(kāi)始的數(shù)映射成1, 則m+2對(duì)應(yīng)2, n對(duì)應(yīng)i - m, 1對(duì)應(yīng)成i - m + 1  m - 1對(duì)應(yīng)i - 1,那么現(xiàn)在的問(wèn)題變成了已知i - 1個(gè)人進(jìn)行循環(huán)報(bào)數(shù)m,求出去的人的序號(hào)。假設(shè)已經(jīng)求出了i- 1個(gè)人循環(huán)報(bào)數(shù)下最后一個(gè)出去的人的序號(hào)X0,那么它在n個(gè)人中的序號(hào)X1=(X0+ m - 1) % n + 1,  最初的X0=1 ,反復(fù)迭代X0和X1可以求出.
                 簡(jiǎn)單約瑟夫問(wèn)題的解法:
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse#include <stdio.h >
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehousemain()
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian WarehousePOJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse{
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            int n, m,i, s=0
            ;
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    printf( 
            "N  M  =  "); scanf("%d%d ",&n,&
            m);
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            for(i=2;i<=n;i++)s=(s+m)%
            i;
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    printf(
            "The winner is %d\n ", s+1
            );
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse}
              

                  這倒題其實(shí)不是完全的約瑟夫問(wèn)題,而是稍微變了形.呵呵,聰明的讀者自己發(fā)現(xiàn)!這一點(diǎn)費(fèi)了我很久的時(shí)間,還害我逃了課被點(diǎn)名...
                這道題的我解法是這樣的.

            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse#include   <stdio.h >
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse
            int y(int n,int m)
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian WarehousePOJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse
            {
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            int s=1
            ,i;
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            for(i=2;i<=n-1;i++
            )
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse        s
            =(s+m-1)%i+1
            ;
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            return s+1
            ;
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse}

            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehousemain()
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian WarehousePOJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse{
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            int
             m,n;
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            while(1
            )
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian WarehousePOJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse
            {
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    scanf(
            "%d",&
            n);
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            if(n==0)break
            ;
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse     
            for(m=1
            ;;)
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian WarehousePOJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse     
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse
            {
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse         
            if(y(n,m)==2)break
            ;
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse         m
            ++
            ;
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse     }

            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse   
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    printf(
            "%d\n",m);
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    
            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse    }

            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse}

            POJ 1012 2244 Joseph 問(wèn)題詳解 - Icho - Brian Warehouse

                   讀一個(gè)數(shù)處理一個(gè)數(shù), Memory 68K,時(shí)間31MS,如果覺(jué)得效率不高. 優(yōu)化的辦法是打表~

            -----------------------------------------------------------------------------------------------------------------------------
            由此可見(jiàn),將問(wèn)題化歸為數(shù)學(xué)問(wèn)題,用初等高等或是數(shù)論來(lái)解決的能力是多么重要。
            下面是我根據(jù)AClayton的思路簡(jiǎn)化后的代碼,可直接AC: 注意,題目讓你先讓City 1 掛掉
            2244  編譯器 C :
            #include<stdio.h>
            void main()
            {
             
            int i,r,m,n;
             
            while (scanf("%d",&n) && n)
             {
                
            for (m=1; ; m++)
                {
                 
            for (r=1,i=2; i<=n-1; i++)
                  r
            =(r+m-1)%+ 1;
                 
            if(r==1break;
                }
                printf(
            "%d\n",m);
             }
            // 164K  16MS
             

            Feedback

            # re: POJ 1012 2244 Joseph 問(wèn)題詳解  回復(fù)  更多評(píng)論   

            2013-04-27 12:42 by libai
            你這也叫詳解???、我擦

            # re: POJ 1012 2244 Joseph 問(wèn)題詳解[未登錄](méi)  回復(fù)  更多評(píng)論   

            2013-09-16 13:31 by Icho
            @libai

            好吧。。人艱不拆。。。中間那段黑體我感覺(jué)說(shuō)到點(diǎn)子上了

            # re: POJ 1012 2244 Joseph 問(wèn)題詳解  回復(fù)  更多評(píng)論   

            2014-03-13 21:54 by shang
            第一題的超時(shí)是因?yàn)?輸入數(shù)據(jù)有很多組 你要是每次都算的話(huà)就會(huì)超 所以要先打表存起來(lái) O(1)詢(xún)問(wèn)就不會(huì)超了
            久久人人爽人人爽人人片av高请 | 色婷婷久久久SWAG精品| 久久久久久久99精品免费观看| 丰满少妇人妻久久久久久| 99久久国产免费福利| 麻豆久久| 欧美久久精品一级c片片| 热综合一本伊人久久精品| 日韩人妻无码精品久久免费一| 国产免费久久精品99久久| 精品久久久无码21p发布| 久久精品国产精品青草app| 伊人久久精品影院| 国产精品熟女福利久久AV| 久久精品人人做人人爽电影蜜月| 久久99热精品| 久久超乳爆乳中文字幕| 久久亚洲AV无码西西人体| 国产精品久久久久久久久| 国产精品一区二区久久精品涩爱 | 欧美黑人激情性久久| 91久久国产视频| 精品999久久久久久中文字幕| 一本久久综合亚洲鲁鲁五月天| 国产99久久九九精品无码| 国内精品久久久久影院日本| 波多野结衣AV无码久久一区| 久久亚洲国产精品五月天婷| 久久超碰97人人做人人爱| 久久亚洲精品无码AV红樱桃| 狠狠精品久久久无码中文字幕| 香蕉99久久国产综合精品宅男自 | 久久九九久精品国产| 四虎国产精品免费久久久| 国产精品久久久天天影视| 亚洲香蕉网久久综合影视| 亚洲午夜久久久影院| 久久精品中文无码资源站| 久久综合综合久久综合| 国产麻豆精品久久一二三| 国产精品99久久久久久人|