C语言编程 丢手帕问题

约瑟夫问题(一)

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

*问题分析与算法设计

约瑟夫问题并不难，但求解的方法很多；题目的变化形式也庆镇竖很多。这里给出一种实现方法。

题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。这个是愿意。

现在的衍生问题

就是说有n个人围成一圈，然后说从任意指定的一个

人那里为起点，以m个人为单位，每转m个人第m个人被杀死。当起始人也就是所谓的

第1个人是最后被杀死的，这个m就是为所求，满足这样就叫joseph问题。

然后带一个超叼的递归实现

#include<iostream.h>

#include<stdlib.h>

void make(int *base,int n,int pos,int c,int m)//参数的意义。base数组名，n数组长度。pos跑格的一个誉大东西。c计算次数的。m每次跑路的长度。

{

int j=0

cout<<"NO. "<<++c<<" 第"<<pos+1<<"位出旅肢列"<<endl//输出

base[pos]=0//踢掉

if(c==n)return //出口

while(j-m)if(base[pos=(pos+1)%n])j++//递归点 ,每次数到几这个3就改到几

make(base,n,pos,c,m)//递归

}

int main()

{

int n,m,c=0,pos//从N开始数,则把pos改为N-1就行了.

cout<<"请输入总人数"<<endl

cin>>n

cout<<"请输入要隔几个人:"<<endl

cin>>m

int *base=new int[n]

for(int i=0i<ni++)base[i]=1

pos=m-1

make(base,n,pos,c,m)

delete[]base

system("PAUSE")

return 0

}

這個我昨天寫過 c#的，用數組或者鏈表模擬都行，最基本的方法 using Systemclass test { static void Main() { int n, m, kConsole.WriteLine("請輸入人數n:")n = int.Parse(Console.ReadLine())Console.WriteLine("镇弯隐請輸入報數a:")m = int.Parse(Console.ReadLine())Console.WriteLine("請輸入開始的編號k:")k = int.Parse(Console.ReadLine())--kint[] a = new int[n]for(int i = 0i <n++i) a[i] = i + 1int c = 0int r = nwhile(r >1) { if(a[k] != 0 &&++c == m) { Console.WriteLine("編號為{0}的人被T出", a[k])a[k] = 0c = 0--r} if(++k == n) k = 0} for(k = 0a[k] == 0++k)Console.WriteLine("最后剩下的人的編號御厅闹槐是: {0}", a[k])} }

---