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 阅读(1979) 评论(3)  编辑 收藏 引用 所属分类: POJ

约瑟夫环实在是太奇妙啦(我很高兴我的这篇原创文章被不少人转载了,虽然他们都没有引用出处... ...)!
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;
} // 这是从网上找的做法,号称打表法,这些数据依旧要通过建立循环链表或是别的模拟法来求出。但是单纯为了AC,这种做法真的是相当有效,讲白了就是有目的的穷举结果。
1012模拟法 C: 可惜呀可惜!这个总是 超时!我不知道是什么原因。但是思路是正确的,可能有些地方我没有考虑到,看到这篇日志的人请指点。
#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,建议看一个牛人的ACM博客: www.cppblog.com/AClayton/archive/2007/11/06/35964.html
我就是看这篇博文的,很牛的一个人 AClayton ,写的日期刚好是我生日,下面是其全部博文:
--------------------------------------------------------------------------------------------------------------------------------------------

 在没有明白约瑟夫问题之前,只能用模拟来做.
      约瑟夫问题是这样的:
      假设n个人,编号为1到n,排成一个圈,顺时针从1开始数字m,数到m的人杀了,剩下的人继续游戏.活到最后的一个人是胜利者.一般来说需要编程求解最后一个人的编号.
      思路是这样的:
     假设当前剩下i个人(i<=n),显然这一轮m要挂(因为总是从1开始数).经过这一轮,剩下的人是:1 2 3 ... m- 1 m + 1 ... i, 我们将从m+1开始的数映射成1, 则m+2对应2, n对应i - m, 1对应成i - m + 1  m - 1对应i - 1,那么现在的问题变成了已知i - 1个人进行循环报数m,求出去的人的序号。假设已经求出了i- 1个人循环报数下最后一个出去的人的序号X0,那么它在n个人中的序号X1=(X0+ m - 1) % n + 1,  最初的X0=1 ,反复迭代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}
  

      这倒题其实不是完全的约瑟夫问题,而是稍微变了形.呵呵,聪明的读者自己发现!这一点费了我很久的时间,还害我逃了课被点名...
    这道题的我解法是这样的.

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

       读一个数处理一个数, Memory 68K,时间31MS,如果觉得效率不高. 优化的办法是打表~

-----------------------------------------------------------------------------------------------------------------------------
由此可见,将问题化归为数学问题,用初等高等或是数论来解决的能力是多么重要。
下面是我根据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 问题详解  回复  更多评论   

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

# re: POJ 1012 2244 Joseph 问题详解[未登录]  回复  更多评论   

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

好吧。。人艰不拆。。。中间那段黑体我感觉说到点子上了

# re: POJ 1012 2244 Joseph 问题详解  回复  更多评论   

2014-03-13 21:54 by shang
第一题的超时是因为 输入数据有很多组 你要是每次都算的话就会超 所以要先打表存起来 O(1)询问就不会超了

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理