• <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成人无码电影| 国内精品久久久久影院老司| 综合久久久久久中文字幕亚洲国产国产综合一区首 | 欧洲性大片xxxxx久久久| 久久噜噜久久久精品66| 亚洲欧美成人久久综合中文网| 久久精品国产99国产精品亚洲| 狠狠色丁香婷婷久久综合不卡| 久久本道综合久久伊人| 久久久久亚洲AV片无码下载蜜桃| 色8久久人人97超碰香蕉987| 国产精品免费久久久久久久久| 欧美久久久久久| 亚洲伊人久久大香线蕉苏妲己| 亚洲国产日韩欧美综合久久| 久久久久无码精品国产| 中文国产成人精品久久亚洲精品AⅤ无码精品| 亚洲国产日韩综合久久精品| 欧美亚洲另类久久综合| 亚洲乱码精品久久久久..| 九九久久精品无码专区| 国产精品久久99| 久久人做人爽一区二区三区| 国产精品丝袜久久久久久不卡 | 久久久久亚洲av无码专区喷水| 久久国产热这里只有精品| 久久精品蜜芽亚洲国产AV| 久久大香萑太香蕉av| 欧美伊人久久大香线蕉综合69 | 久久精品无码一区二区三区日韩 | 亚洲va国产va天堂va久久| 久久一区二区三区99| 99久久99久久精品国产片| 91视频国产91久久久| 精品久久久久久无码专区| 久久精品无码一区二区WWW| 久久夜色精品国产亚洲av| 亚洲国产婷婷香蕉久久久久久| 精品久久人人妻人人做精品 | 久久毛片一区二区| 超级97碰碰碰碰久久久久最新 |