我的用链表编的人围圈踢人问题最后记录留下人的位置大家讨论讨论

主题：我的用链表编的人围圈踢人问题最后记录留下人的位置大家讨论讨论

xxgamexx [专家分：90] 发布于 2007-03-26 12:12:00

题目:n 个人围成一圈, 并依次编号1～n，。从编号为1 的人开始，按顺时针方向每隔一人选出一个，
剩下的人重新围成一圈，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个
幸运儿，请问开始时应该站在什么位置？（设3<=n<=50）

我的想法,主要算法  ,没有经过调试

struct Tnode
{
   int pos;//位置
   Tnode *next;
}Tnode *head;

    Tnode *p=head;
   int count;//人的个数

...
while(count!=2)//最后留下的2个人
{
if(*p->next->next==NULL)     //判断从下一个循环是踢第一个人,还是跳一个人,踢下一个
       *p=head;   //设置下循环踢人的位置

else

      *p=head->next;

    for(  ;*p->next!=NULL||*p->next->next!=NULL;*p=*p->next->next)
     {
         DelNode(p);          //删除当前节点

          count--;        //人数减1
      }
}

count>>head.pos>>head->next.pos;//输出

因为要记录人的幸运位置  所以我觉得用链表简单些,用数组应该也行,但是我不知道如何处理数组中让元素踢出数组.

大家有什么好想法  来说说啊~

本帖地址： http://bbs.pfan.cn/post/222854.html

回复列表（共8个回复）

沙发

bpttc [专家分：8790] 发布于 2007-03-26 15:50:00

用循环链表

板凳

bpttc [专家分：8790] 发布于 2007-03-26 15:51:00

//函数原型 int Josephus( int N, int S, int M );
//输入参数 N个人围成一圈,从第S个人开始报数,报到M的人出列
//输出结果最后剩下的人的序列号
//作者 bpt

#include <stdlib.h>

#define FREE(X) { free(X); X = NULL; }

int Josephus( int N, int S, int M )
{
        if  ( M <= 1
              || N <= 1
              || S <= 0
              || S > N )
        {
                return 0;
        }

        typedef struct linklist_node
        {
                int num;
                struct linklist_node* next;
        }* List;

        List head = NULL;
        List previous = NULL;
        List s = NULL;
        List p = NULL;
        int i, j;

        //1.构建单向循环列表
        head = (List)malloc( sizeof(struct linklist_node) );
        if ( NULL == head )
        {
                exit(1);
        }

        for ( i = 1, previous = head; i <= N; ++i )
        {
                p = (List)malloc( sizeof(struct linklist_node) );
                if ( NULL == p )
                {
                        exit(1);
                }
                p->num = i;
                if ( S == i )
                {
                        s = p;  //为定位头指针做准备
                }
                previous->next = p;
                previous = p;
        }
        p->next = head->next;
        head->next = s;    //定位头指针

        //2.模拟出列
        for ( i = 1; i <= N-1; ++i )
        {
                previous = head;
                for ( j = 1; j <= M-1; ++j ) //数到第M-1个
                {
                        previous = previous->next;
                }
                p = previous->next;       //p指向第M个
                head->next = p->next;     //定位头指针指向第M+1个
                previous->next = p->next; //删除第M个
                FREE(p);
        }

        //3.回收头节点
        i = head->next->num;
        FREE(head->next);
        FREE(head);
        return i;
}

3 楼

xxgamexx [专家分：90] 发布于 2007-03-26 17:28:00

我把上面用类的思想封装了  自己实现了上面功能   希望大家提点意见啊~
#include <iostream.h>
struct Tnode
{
  int data;
  Tnode *next;
};

class TPclass
{
   public:
      TPclass(int ms,int mb,int mm);
      void Creat();
     void Print();
      ~TPclass()
      {
     Tnode *temp;
for(temp=head;temp->next!=tail;temp=temp->next)
   delete(temp);
      }
   protected:
       Tnode *head,*tail;//头和尾
       int sump,beginp,m;//人数总和,开始的位置,跳的人数
};
TPclass::TPclass(int ms,int mb,int mm)
{
                    head=NULL;
                 tail=NULL;
                 sump=ms;
                 beginp=mb;
     m=mm;

}
void TPclass::Creat()
{
      Tnode *temp=NULL;
      int number=1;
       head=new Tnode;
        tail=new Tnode;
       head->data=1;
       head->next=tail;

       tail->data=sump;
       tail->next=head;//初始化头和尾,然后再往中间插节点

      while(number!=(sump-1))//往中间按顺序插人
        {
          temp=new Tnode;
          temp->data=sump-number;
          temp->next=head->next;
          cout<<temp->data<<endl;
          head->next=temp;
          number++;
        }

}

void TPclass::Print()
{
    Tnode *temp=head,*p=NULL,*flag;
    while(temp->data!=beginp)
        temp=temp->next;

    while(sump!=2)//输出直到留下2个人
    {


    for(int i=1;i<=m;i++)
       temp=temp->next;
      p=temp->next;//p=temp
      flag=temp;
      temp->next=p->next;
      cout<<p->data<<endl;
      delete(p);
      sump--;
    }
    cout<<"the last"<<flag->data;
    cout<<"the last"<<flag->next->data;
}
void main()
{
TPclass TP(20,5,2);
TP.Creat();
TP.Print();

}

4 楼

argentmoon [专家分：13260] 发布于 2007-03-26 18:18:00

意见么……这题有公式

5 楼

bpttc [专家分：8790] 发布于 2007-03-26 22:06:00

总而言之，模拟解法不如用数学解法来得快

6 楼

xxgamexx [专家分：90] 发布于 2007-03-26 22:53:00

[quote]总而言之，模拟解法不如用数学解法来得快[/quote]
什么意思?　不懂

7 楼

seekmm [专家分：380] 发布于 2007-03-31 22:57:00

请参见具体数学P90页.....

8 楼

liudan319 [专家分：3780] 发布于 2007-04-03 12:19:00

循环链表

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：我的用链表编的人围圈踢人问题最后记录留下人的位置大家讨论讨论

回复列表（共8个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：我的用链表编的 人围圈踢人问题 最后记录留下人的位置 大家讨论讨论

回复列表 （共8个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：我的用链表编的人围圈踢人问题最后记录留下人的位置大家讨论讨论

回复列表（共8个回复）