• <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 問題詳解

            Posted on 2010-08-17 13:42 Brian 閱讀(2123) 評論(3)  編輯 收藏 引用 所屬分類: POJ

            約瑟夫環(huán)實(shí)在是太奇妙啦(我很高興我的這篇原創(chuàng)文章被不少人轉(zhuǎn)載了,雖然他們都沒有引用出處... ...)!
            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)上找的做法,號稱打表法,這些數(shù)據(jù)依舊要通過建立循環(huán)鏈表或是別的模擬法來求出。但是單純?yōu)榱薃C,這種做法真的是相當(dāng)有效,講白了就是有目的的窮舉結(jié)果。
            1012模擬法 C: 可惜呀可惜!這個(gè)總是 超時(shí)!我不知道是什么原因。但是思路是正確的,可能有些地方我沒有考慮到,看到這篇日志的人請指點(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;
            }
            對于 2244,建議看一個(gè)牛人的ACM博客: www.shnenglu.com/AClayton/archive/2007/11/06/35964.html
            我就是看這篇博文的,很牛的一個(gè)人 AClayton ,寫的日期剛好是我生日,下面是其全部博文:
            --------------------------------------------------------------------------------------------------------------------------------------------

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

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

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

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

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

            POJ 1012 2244 Joseph 問題詳解 - Icho - Brian Warehouse}

            POJ 1012 2244 Joseph 問題詳解 - Icho - Brian Warehouse

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

            -----------------------------------------------------------------------------------------------------------------------------
            由此可見,將問題化歸為數(shù)學(xué)問題,用初等高等或是數(shù)論來解決的能力是多么重要。
            下面是我根據(jù)AClayton的思路簡化后的代碼,可直接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 問題詳解  回復(fù)  更多評論   

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

            # re: POJ 1012 2244 Joseph 問題詳解[未登錄]  回復(fù)  更多評論   

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

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

            # re: POJ 1012 2244 Joseph 問題詳解  回復(fù)  更多評論   

            2014-03-13 21:54 by shang
            第一題的超時(shí)是因?yàn)?輸入數(shù)據(jù)有很多組 你要是每次都算的話就會超 所以要先打表存起來 O(1)詢問就不會超了
            久久精品a亚洲国产v高清不卡| 香港aa三级久久三级| 久久久久婷婷| 精品人妻伦一二三区久久 | 日韩精品久久久肉伦网站 | 99精品伊人久久久大香线蕉| 久久久久免费看成人影片| 亚洲精品乱码久久久久久| 伊人久久精品无码av一区| 少妇精品久久久一区二区三区| 色综合久久无码五十路人妻| 久久综合给合久久国产免费| 久久电影网一区| 欧美日韩精品久久久久| 亚洲精品无码专区久久久| 国产成人久久AV免费| 91久久精品电影| 婷婷久久五月天| 久久夜色精品国产噜噜亚洲AV| 99热成人精品热久久669| 久久国产V一级毛多内射| 亚洲欧美日韩精品久久亚洲区 | 亚洲国产精品无码久久久秋霞2 | 亚洲AV日韩精品久久久久久| 国产精品99久久精品| 久久久艹| 国产精品99久久免费观看| 久久国产成人| 狠狠色丁香久久综合婷婷| 亚洲精品成人网久久久久久| 潮喷大喷水系列无码久久精品| 狠狠色丁香婷婷综合久久来来去 | 精品国产乱码久久久久久郑州公司| 国产精品久久久天天影视香蕉| 亚洲国产另类久久久精品黑人| 久久精品国产99久久香蕉| 国产成人无码久久久精品一| 久久久午夜精品| 精品久久人人爽天天玩人人妻| 久久99精品久久只有精品| 伊人久久成人成综合网222|