一 : 丢手帕问题

约瑟夫问题(一)

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

约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。 题目中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=0;i<n;i++)base[i]=1;

丢手帕 丢手帕问题

pos=m-1;

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

delete[]base;

system("PAUSE");

return 0;

}

// 魔比斯环算法 /

// n个人，从第k个人开始数，数到a的离开 /

// 问你最后一个离开的是谁,或者所有的 /

// 人离开顺序 /

/////////////////////////////////////////

#include <iostream>

using namespace std;

class Moebius {

private:

int* place;

int n; //圈内人数

int k; //从第k个人报数

int a; //报数的终止值(从1 - a报数)

void delPlace(int); //报数为a的人离开环

public:

Moebius (){}; //无参构造函数

Moebius ( int, int, int );//构造函数

void Moebius::listInit (); // 得到环的原始顺序列表

void Moebius::listMove ();//得到环的出圈顺序

};

Moebius::Moebius ( int _n, int _k, int _a ) { // 定义构造函数 int i;

n = _n;

k = _k;

a = _a;

place = new int[n];

for ( i = 0; i < n; i++ )

place[i] = i + 1;

}

丢手帕 丢手帕问题

void Moebius::listInit () { // 输出环内人员原始顺序列表 int i;

cout << "魔比斯环初始人员顺序列表：" << endl;

for ( i = 0; i < n; i++ )

cout << " " << place[i];

cout << endl;

}

void Moebius::listMove () { //输出环内人员离开顺序

int iPlace = k - 1; //确定第一个报数的人的位置

cout << "魔比斯环内的人离开顺序列表：" << endl;

while ( n ) { //直到环内没人为止

iPlace = (iPlace + a - 1) % n; //确定下一个离开的人

cout << " " << place[iPlace];

delPlace(iPlace);//报数后离开环

n--;//环内少一人

}

cout << endl;

}

void Moebius::delPlace ( int iPlace ) {//下标为iPlace的人离开环 int i;

for ( i=iPlace; i < n - 1; i++)

place[i] = place[i + 1];

}

//主函数

void main () {

int n,k,a;

cout << endl << "请输入环内人数：";

cin >> n;

cout << endl << "请输入从第几个人开始报数:";

cin >> k;

cout << endl << "请输入每次报数从1报到几:";

cin >> a;

Moebius m(n,k,a);

丢手帕 丢手帕问题

m.listInit();

m.listMove();

}

c#的，用數組或者鏈表模擬都行，最基本的方法

using System;

class test {

static void Main() {

int n, m, k;

Console.WriteLine("請輸入人數n:");

n = int.Parse(Console.ReadLine());

Console.WriteLine("請輸入報數a:");

m = int.Parse(Console.ReadLine());

Console.WriteLine("請輸入開始的編號k:"); k = int.Parse(Console.ReadLine());

--k;

int[] a = new int[n];

for(int i = 0; i < n; ++i)

a[i] = i + 1;

int c = 0;

int r = n;

while(r > 1) {

if(a[k] != 0 && ++c == m) {

Console.WriteLine("編號為{0}的人被T出", a[k]); a[k] = 0;

c = 0;

--r;

}

if(++k == n) k = 0;

}

for(k = 0; a[k] == 0; ++k);

Console.WriteLine("最后剩下的人的編號是: {0}", a[k]); }

}

二 : 丢手帕

　　今天，我们在操场上做了个有趣的游戏，游戏的名字叫“丢手帕”。

　　首先，老师让大家围成一个圆圈，老师先推选我当丢手帕的人，我十分开心。开始游戏了，同学们全都蹲下，边拍手边唱着丢手娟的歌：“丢，丢，丢手娟……”只见我拿起手拍蹦蹦跳跳地围着圆圈跑，忽然，我发现刘雨棠没有注意我，我就轻轻地把手帕丢在她的身后，我若无其事地走了。可同学们的阳光齐刷刷地盯着刘雨棠，她似乎觉察到了，扭头一看，看见手帕就在自己的身后，连忙拿起手帕飞快的向我跑过来，还好，我立刻回到了我的位置上蹲下，她没有抓到我。

　　游戏继续进行着，刘雨棠把手帕又放在朱清林的身后，朱清林立刻拿起手帕去追，可是已经晚了，刘雨棠也迅速地回到了她的位置上。老师说：“丢给男生吧！”朱清林一听连忙把手帕丢给杨邦国，谁知，杨邦国拿起手拍拼命奔跑，把她追到了，她只好给大家表演了一个节目。

　　这真是一场紧张而好玩的游戏。

　　四川南充市高坪七小二年级：谢芝瑜

 

三 : 丢手帕

“当当当，当当当……”下课的钟声敲响了，我和同学们一起到操场围成了一个大圆圈，高高兴兴地玩起了丢手帕的游戏。

大家选我来丢手帕，我高兴得一蹦三尺高，迫不及待地拿出了我最心爱的手帕，然后围着圆圈跑起来，一边跑一边寻找目标。我看见大部分的同学都眼睛紧紧地盯着我，唯恐我把手帕丢他的身后，这时，我发现沈志超在东张西望，一点儿防备都没有，我心里暗暗窃喜。我悄悄地跑到了沈志超身后，把手帕轻轻地丢在他的后面，沈志超一点儿也没发觉，可把旁边的陈圆林给急坏了，他拼命地朝沈志超使眼色，可沈志超浑然不觉，最后陈园林实在忍不住了，点了点沈志超，又往他背后指去。沈志超这才发现自己身后的手帕，可已经晚了，我已经跑完了一圈把他抓住了。大家让沈志超表演一个节目，沈志超没有办法，只好扭扭捏捏地来到圆圈中间，背起了《忆江南》这首古诗……

我们玩得可高兴了，忽然上课铃响了，大家赶紧向教室跑去，游戏只好暂时结束。

四 : 丢手帕问题

约瑟夫问题(一)

这是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=0;i<n;i++)base[i]=1;

pos=m-1;

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

delete[]base;

system("PAUSE");

return 0;

}

// 魔比斯环算法 /

// n个人，从第k个人开始数，数到a的离开 /

// 问你最后一个离开的是谁,或者所有的 /

// 人离开顺序 /

/////////////////////////////////////////

#include <iostream>

using namespace std;

class Moebius {

private:

int* place;

int n; //圈内人数

int k; //从第k个人报数

int a; //报数的终止值(从1 - a报数)

void delPlace(int); //报数为a的人离开环

public:

Moebius (){}; //无参构造函数

Moebius ( int, int, int );//构造函数

void Moebius::listInit (); // 得到环的原始顺序列表

void Moebius::listMove ();//得到环的出圈顺序

};

Moebius::Moebius ( int _n, int _k, int _a ) { // 定义构造函数 int i;

n = _n;

k = _k;

a = _a;

place = new int[n];

for ( i = 0; i < n; i++ )

place[i] = i + 1;

}

void Moebius::listInit () { // 输出环内人员原始顺序列表 int i;

cout << "魔比斯环初始人员顺序列表：" << endl;

for ( i = 0; i < n; i++ )

cout << " " << place[i];

cout << endl;

}

void Moebius::listMove () { //输出环内人员离开顺序

int iPlace = k - 1; //确定第一个报数的人的位置

cout << "魔比斯环内的人离开顺序列表：" << endl;

while ( n ) { //直到环内没人为止

iPlace = (iPlace + a - 1) % n; //确定下一个离开的人

cout << " " << place[iPlace];

delPlace(iPlace);//报数后离开环

n--;//环内少一人

}

cout << endl;

}

void Moebius::delPlace ( int iPlace ) {//下标为iPlace的人离开环 int i;

for ( i=iPlace; i < n - 1; i++)

place[i] = place[i + 1];

}

//主函数

void main () {

int n,k,a;

cout << endl << "请输入环内人数：";

cin >> n;

cout << endl << "请输入从第几个人开始报数:";

cin >> k;

cout << endl << "请输入每次报数从1报到几:";

cin >> a;

Moebius m(n,k,a);

m.listInit();

m.listMove();

}

c#的，用數組或者鏈表模擬都行，最基本的方法

using System;

class test {

static void Main() {

int n, m, k;

Console.WriteLine("請輸入人數n:");

n = int.Parse(Console.ReadLine());

Console.WriteLine("請輸入報數a:");

m = int.Parse(Console.R eadLine());

Console.WriteLine("請輸入開始的編號k:"); k = int.Parse(Console.ReadLine());

--k;

int[] a = new int[n];

for(int i = 0; i < n; ++i)

a[i] = i + 1;

int c = 0;

int r = n;

while(r > 1) {

if(a[k] != 0 && ++c == m) {

Console.WriteLine("編號為{0}的人被T出", a[k]); a[k] = 0;

c = 0;

--r;

}

if(++k == n) k = 0;

}

for(k = 0; a[k] == 0; ++k);

Console.WriteLine("最后剩下的人的編號是: {0}", a[k]); }

}

本文标题：丢手帕-丢手帕问题
本文地址： http://www.61k.com/1094873.html