问答 （数学趣味类）《又是馒头惹的？》√已有答案√欢迎拓展和应用√

blueicenan

一寺庙有100个和尚，每天早上吃100个馒头，每人一个，雷打不动，已成规矩。

某日开饭前，一外地尚入寺，言头晚未吃饭，看来是要加入用膳行列。
   主持两难，很快想了个办法：所有和尚（101人）围一圈，从他开始顺一个方向报数
，报到一百者拿一个馒头走人，其下一个重新从一开始继续顺序报数，报到一百者即可拿
馒头走人，下一个再从一开始周而复始。
数报了一百圈，馒头拿光了，剩下干瞪眼的恰是那位云游和尚。
   主持究竟把他安排在圈中哪个位置上？

killl

约瑟夫环

yudie

21吧

约瑟夫环

killl

约瑟夫环问题求解算法C语言源代码

.约瑟夫算法：n个人围成一圈，每人有一个各不相同的编号，选择一个人作为起点，然后顺时针从1到k数数，每数到k的人退出圈子，圈子缩小，然后从下一个人继续从1到k数数，重复上面过程。求最后推出圈子的那个人原来的编号。

思路：按照上面的算法让人退出圈子，直到有n-1个人推出圈子，然后得到最后一个退出圈子的人的编号。

程序：坐成一圈的人的编号不需要按序排列

#define N 100
int yuesefu1(int data[],int sum,int k)
{
int i=0,j=0,count=0;
while(count<sum-1)
{
if(data!=0)/*当前人在圈子里*/
j++;
if(j==k)/*若该人应该退出圈子*/
{
data=0;/*0表示不在圈子里*/
count++;/*退出的人数加1*/
j=0;/*重新数数*/
}
i++;/*判断下一个人*/
if(i==sum)/*围成一圈*/
i=0;
}
for(i=0;i<sum;i++)
if(data!=0)
return data;/*返回最后一个人的编号*/
}

void main()
{
int data[N];
int i,j,total,k;
printf("\nPlease input the number of every people.\n");
for(i=0;i<N;)/*为圈子里的人安排编号*/
{
int input;
scanf("%d",&input);
if(input==0)
break;/*0表示输入结束*/
for(j=0;j<i;j++)/*检查编号是否有重复*/
if(data[j]==input)
break;
if(j>=i&&input>0)/*无重复,记录编号,继续输入*/
{
data=input;
i++;
}
else
printf("\nData error.Re-input:");
}
total=i;
printf("\nYou have input:\n");
for(i=0;i<total;i++)
{
if(i%10==0)
printf("\n");
printf("%4d",data);
}
printf("\nPlease input a number to count:");
scanf("%d",&k);
printf("\nThe last one&#39;&#39;&#39;&#39;s number is %d",yuesefu1(data,total,k));
}

yzh_nj_china

原来叫约瑟夫环哦~~~

fferror

没抢到。。。

yudie

约瑟夫环问题来源于公元6世纪犹太人的反罗马起义，这个问题是是相当的经典啊，以至于几乎所有的编程入门和算法书籍都会提到这个问题，哈哈。

转帖一个优化算法

1. long Josephus(long n,long m,long k)   //分别为：人数，出圈步长，起使报数位置,
2.   {  
3.   if (m == 1)
4.     k = k == 1 ? n : (k + n - 1) % n;
5.   else
6.     {
7.     for (long i = 1; i <= n; i++)
8.       {
9.       if ((k + m) < i)
10.         {
11.         x = (i - k + 1) / (m - 1) - 1;
12.         if (i + x < n)
13.           {
14.           i = i + x;
15.           k = (k + m * x);
16.         }
17.         else
18.           {
19.           k = k + m * (n - i) ;
20.           i = n;
21.         }      
22.       }
23.       k = (k + m - 1) % i + 1;
24.     }
25.   }
26. return k; //返回最后一人的位置
27. }

复制代码

该算法的算法复杂度在m<n时已经与一个圈中的人数n没有关系了

yzh_nj_china

方丈好厉害啊~~
有没有数学方法呢？
下面的是matlab求解~~具体的哪个和尚拿到馒头~~~（去跟别人吹，这是我自己算出来的~~~）
约瑟夫环问题求解：
请输入人数:101
输入开始报数的是第几个人：1
数到第几个人开始出列?100
开始报数......
第100号出列
第99号出列
第101号出列
第2号出列
第5号出列
第9号出列
第14号出列
第20号出列
第27号出列
第35号出列
第44号出列
第54号出列
第65号出列
第77号出列
第90号出列
第8号出列
第26号出列
第45号出列
第63号出列
第83号出列
第7号出列
第33号出列
第58号出列
第84号出列
第16号出列
第47号出列
第76号出列
第13号出列
第50号出列
第86号出列
第29号出列
第69号出列
第15号出列
第60号出列
第6号出列
第59号出列
第12号出列
第68号出列
第28号出列
第85号出列
第49号出列
第18号出列
第81号出列
第55号出列
第32号出列
第3号出列
第88号出列
第72号出列
第61号出列
第51号出列
第43号出列
第42号出列
第48号出列
第57号出列
第71号出列
第87号出列
第1号出列
第31号出列
第66号出列
第96号出列
第39号出列
第92号出列
第41号出列
第10号出列
第78号出列
第53号出列
第36号出列
第25号出列
第30号出列
第40号出列
第70号出列
第94号出列
第37号出列
第93号出列
第67号出列
第46号出列
第38号出列
第64号出列
第91号出列
第34号出列
第17号出列
第11号出列
第24号出列
第89号出列
第79号出列
第97号出列
第73号出列
第75号出列
第23号出列
第74号出列
第80号出列
第62号出列
第82号出列
第19号出列
第22号出列
第98号出列
第95号出列
第56号出列
第4号出列
第52号出列
第21号出列

killl

#include<stdio.h>
#include<stdlib.h>
//#include<alloc.h>
struct node
{
  int number;
  struct node* next;
};
struct node * CreatList(int num)
{
  int i;
  struct node *ptr1,*head;
  if((ptr1=(struct node*)malloc(sizeof(struct node)))==NULL)
  {
    perror("malloc");
    return ptr1;
  }
  head=ptr1;
  ptr1->next=head;
  for(i=1;i<num;i++)
  {
    if((ptr1->next=(struct node*)malloc(sizeof(struct node)))==NULL)
    {
      perror("malloc");
      ptr1->next=head;
      return head;
    }
    ptr1=ptr1->next;
    ptr1->next=head;
  }
  return head;
}
void main()
{
  int i,j=0,n=101,m=100;
  struct node*head,*ptr;
  head=CreatList(n);
  for(i=1;i<=n;i++)
  {
    head->number=i;
    head=head->next;
  }
  i=0;
  while(head->next!=head)
  {
    if(i==m)
    {
      j=j+1;
      if(j%5==0){printf("\n");}
      ptr=head;
      printf("%d: kick:%d\t",j,ptr->number);
      ptr=head->next;
      head->next=ptr->next;
      head=head->next;
      free(ptr);

      i=0;
    }
    else
    {
      head=head->next;
      i++;
    }
  }
  printf("\nlast:%d\n",head->number);
  free(head);
  getchar();
}

fferror

仿佛比计算机版还专业些。
我是不是要开compiler了？

killl

引用第7楼yzh_nj_china于2007-12-17 17:35发表的 :
方丈好厉害啊~~
有没有数学方法呢？
下面的是matlab求解~~具体的哪个和尚拿到馒头~~~（去跟别人吹，这是我自己算出来的~~~）
约瑟夫环问题求解：
请输入人数:101
.......

请问有没有代码提供呢？

jingmouren

Knuth的ConcreteMathematics上好像有计算公式

yzh_nj_china

好的~~~~
以下是matlab的求法~~

clear;
clc;
syms n s m s1 t w arr_size;%定义几个变量
%n为人数， s为从第几个人开始报数,m为数到第几个人
disp(&#39;约瑟夫环问题求解：&#39;);
n=input(&#39;请输入人数:&#39;);
arr_size = n;
s=input(&#39;输入开始报数的是第几个人：&#39;);
m=input(&#39;数到第几个人开始出列?&#39;);
a =(1:1:n);%定义一个数组
s1 = s-1;
disp(&#39;开始报数......&#39;);
for t=n:-1:1
s1 = rem((s1 +m-1),t);%求出列元素下标
w = a(s1+1);%通过下标求数列元素值
%disp(w); % 显示第几号人出列
fprintf(&#39;第%d号出列\n&#39;,w)
pause(0.5);%暂停0.5秒，以便看到动态过程
%移动数组元素
for t=s1+1:1:arr_size-1
a(t)=a(t+1);
end
arr_size = arr_size-1;
end
disp(&#39;完毕.......&#39;);

killl

引用第11楼jingmouren于2007-12-17 18:35发表的 :
Knute的ConcreteMathematics上好像有计算公式

承蒙pm告知，verycd上有这本书 ：

http://www.verycd.com/topics/90442/

《Concrete Math 具体数学 中文版＋英文版＋6套试题》

[

1. ed2k://|file|Concrete.Math(具体数学)(中文版.英文版.6套试题).zip|29647125|2c39a20f7700070650db2eca3f257983|h=X435HG7XGUKF2OGJ36AW5QMTTYXVWDV7|/

复制代码

中文名称：Concrete Math 具体数学 中文版＋英文版＋6套试题
地区：大陆
语言：普通话
简介：


【书名】具体数学：计算机科学基础（英文版.第2版）
【原书名】Concrete Mathematics A Foundation for Computer Science(Second Edition)
【原出版社】Addison Wesley
【作者】（美）Ronald L.Graham,Donald E.Knuth,Oren Patashnik
【丛书名】经典原版书库
【出版社】机械工业出版社
【书号】7-111-10576-1
【开本】32开
【页码】680
【出版日期】2002-8-1
【版次】1-1
【文件语言】 中文
【文件格式】 PDF/PDG
【文件大小】
【内容简介】

作者onald E.Knuth
算法和程序设计技术的先驱者，是计算机排版系统TEX和METAFONT的发明者。　　Donald.E.Knuth(唐纳德.E.克努特，中文名高德纳)是斯坦福大学计算机程序设计艺术的荣誉退休教授，Knuth教授获得了许多奖项和荣誉，包括美国计算机协会图灵奖(ACM Turing Award)，美国前总统卡特授予的科学金奖(Medal of Science)，美国数学学会斯蒂尔奖(AMS Steele Prize)，以及1996年11月由于发明先进技术荣获的极受尊重的京都奖(KyotoPrize)。他因这些成就和大量创造性的影响深远的著作(19部书和160篇论文)而誉满全球。

This book introduces the mathematics that supports advanced computer Programming and the analysis of algorithms. The primary aim of its well-known authors is to provide a solid and relevant base of mathematical skills--the skills needed to solve complex problems, to evaluate horrendous sums, and to discover subtle Patterns in data. It is an indispensable text and reference not only for computer scientists--the authors themselves rely heavily on it! but for serious users Of mathematics in virtually every discipline. Concrete mathematics is a blending of continuous and disCRETE mathematics: "More concretely," the authors explain, "it is the controlled manipulation of mathematical formulas,using a collection of techniques for solving problems." The subject mater is primarily an expansion of the Mathematical Preliminaries section in Knuth&#39;s c1assic Art of Computer Programming, but the style of presentation is more leisurely, and individual topics are covered more deeply. Several new topics have been added, and the most significant ideas have been traced to their historical roots. The book includes more than 500 exercises, divided into six categories. Complete answers are provided for all exercises, except research problems, making the book particularly valuable for self-study.

磁铁

嘿嘿，由于 众多回帖者的优秀解答和知识拓展，此帖被评为精华。
blueicenan快给以上诸位分红包吧，西西

killl

这本书的关于约瑟夫环部分内容：

from verycd

jingmouren

楼上贴得图太大了，看不全
公式在第9页
J(bmbm-1.....b1b0)2)=(bm-1...b1b0bm)2;
也就是说，以计算机程序设计的用语，循环左移一位我们从n取得J(n)

yzh_nj_china

这个时候应该期待非计算机的求解···
再感叹一下，老方丈怎么这么厉害~~~~~
原来老joscphus比老方丈还厉害啊~~~~~

以I世纪著名历史学家Flavius Joscphus命名的。据传说，Joscphus若没有数学才能，他就不会在活着的时候出名，在犹太人和古罗马人战争期间，他是陷入罗马人陷阱的41个犹太反抗者之一。反抗者宁死不做俘虏，他们决定围成一个圆圈，且环绕圆圈来进行，杀死所有第三个剩下的人直到没有一个人留下。但是Joseph us和一个不告发的同谋者感到自杀是愚蠢的行为，所以他快速计算出在此恶性循环中他和他的朋友该站的地方。

killl

引用第17楼yzh_nj_china于2007-12-17 19:29发表的 :
这个时候应该期待非计算机的求解···
再感叹一下，老方丈怎么这么厉害~~~~~

方丈这个职位对于学历要求很高啊

磁铁

冰冰总是一到分红包就消失啊