流云

风驰影跃长 月映霜华裳
随笔 - 23, 文章 - 6, 评论 - 53, 引用 - 0

导航

<2008年11月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

留言簿(0)

随笔分类

随笔档案

文章分类

文章档案

相册

收藏夹

东观沧海

云散之处

搜索

最新评论

阅读排行榜

评论排行榜

约瑟夫(Joseph)环

题目描述:编号为1,2,...,nn个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一     开始,任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报 数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。

*需求分析

    利用单向循环链表存储结构模拟此过程。程序输入、输出值均为正整数(其中人数限定<=30),程序的功能是按照出列的顺序印出各人的编号。

*测试数据:m=20,n=7,7个人的密码为:3,1,7,2,4,8,4;

*测试结果:出列顺序为6,1,4,7,2,3,5.

*附录(源程序):

//约瑟夫(Joseph)环

#include<iostream.h>
#include<conio.h>

//定义单链存储结构

typedef struct LNode{

    int data;

    struct  LNode   *next;

}LNode,*LinkList;

void main()

{

    int m,n,t[30],j(0);     //定义初始报数上限值m、人数n

    cout<<"输入初始报数上限值m(正整数):";

    cin>>m;

    cout<<"输入人数n(正整数,<=30):";

    cin>>n;

    cout<<"输入各人的密码(以空格符为分隔号):"<<endl;

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

        cin>>t[i];     

    LinkList p,head;

    head=new LNode;

    head->data=0;

    head->next=0;

    p=head;

//初始化单向循环链表

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

    {

        struct  LNode *s=new LNode;

        s->data=i;

        //s->next=0;

        p->next=s; 

        p=p->next;     

    }

    p->next=head;

//处理出列顺序

    while(p->data!=p->next->next->data&&j<m)

    {

        if(j==m-1){

            int n=p->next->data;   

            m=t[n];

            j=0;

            cout<<n+1<<endl;

            if(p->data==p->next->next->data)

                break;             

            p->next=p->next->next;     

        }

        if(p->data==p->next->next->data){

            cout<<p->next->data+1<<endl;    //倒数第二个出列者

            break;  }  

        p=p->next;

        j++;       

    }  

    cout<<p->data+1<<endl;  //最后一个出列者

//暂停  

    getch();

}

posted on 2005-07-01 21:53 流云 阅读(3665) 评论(3)  编辑 收藏

评论

# 免费电影资源的共享

终于搜索到了一个可以免费在线看电影的网站了,现在分给大家共享:

免费电影http://www.38138.com 是个纯免费的电影网站,可以全免费的在线看电影
免费电影,所有免费电影,免费电影在线看
2005-08-14 23:20 | greg

# re: 约瑟夫(Joseph)环

看不懂是什么 意思
2005-10-21 17:40 |

# re: 约瑟夫(Joseph)环

数据结构题~
2006-01-09 10:15 | CPP
标题  
姓名  
主页
验证码 *
内容   
  登录  使用高级评论  Top
[使用Ctrl+Enter键可以直接提交]