回 帖 发 新 帖 刷新版面

主题:[讨论]编写一算法解决约瑟夫问题

设有N个人为坐在圆桌周围,现从第S个人开始报数,数到第M个人出列,然后从出列的下一个人重新开始报数,数到第M个人又出列……如此重复直到所有的人全不出列为止,例如当N=8,M=4,S=1,得到的新序列为:4,8,5,2,1,3,7,6

回复列表 (共25个回复)

21 楼

[color=C0C0C0]以前写的个代码。
发出供LZ参考!!![/color]#include <stdio.h>
[color=0000FF]#include <stdlib.h>
#define N 15
#define M 3

typedef struct node
{     int index;
    struct node * next;
} Node, *pNode;
void initlist(pNode * list);
void output(pNode list);
void main()
{    pNode headlist = NULL;
   initlist(&headlist);
   output(headlist);
   system("pause");
} void initlist(pNode * list)
{     pNode temp,temp1;
    int i = 0;
    temp = (pNode)malloc(sizeof(Node));
    if(temp == NULL)
    {
        printf("Malloc Failure!\n");
        exit(-1);
    }
    temp1 = temp;
    while(i < N)
    {
        temp->next = (pNode)malloc(sizeof(Node));
        if(temp->next == NULL)
        {
            printf("Malloc Failure!\n");
            exit(-1);
        }
        temp = temp->next;
        temp->index = i + 1;
        i++;
    }
    temp->next = temp1->next;
    *list = temp1->next;
    free(temp1);
} void output(pNode list)
{

    pNode temp1,temp2;
    temp1 = list;
    temp2 = temp1;
    int number = 1,count = 0;
    while(number < N)
    {
        count++;
        if(count == M)
        {
            temp2->next = temp1->next;
            count = 0;
            free(temp1);
            temp1 = temp2->next;
            number ++;
            continue;
        }
        temp2 = temp1;
        temp1 = temp1->next;
    }
    printf("The last person is:%d\n",temp1->index);
    free(temp1);
}[/color]

22 楼

我的博客里有这样的程序。欢迎你到我那里去看。不过我是用C++写的。不知道你看的懂吗?

23 楼


#include <iostream.h>
struct Node
{
    int data;
    struct Node* next;
};

 //删除节点超做
void deletelist(Node* h)
{
    Node* q=h->next;
    h->next=q->next;
    delete q;
}
  





  //创建一个不带头接点的链表
   Node* createlist(int m)
   {
       Node* head=new Node;
       Node* p=head;
       p->data=1;
       p->next=NULL;
       for(int i=2;i<=m;i++)
       {
           Node* q=new Node;
           q->data=i;
           p->next=q;
           p=q;
           if(i==m)
           {
               p->next=head;
           }//最后一个指针指向头节电

       }
           return head;
   }
       
 //主要调用完成超做函数
   void fun(Node* h,int k,int n)
   {
       Node*p=h;
       int m=1;
       int a=1;
       int w;
       
           while(m<=k-2)
           {
               p=p->next;
               m++;
               if((m==k-1)&&(a<=n-1))
               {    
                   w=p->next->data;
                cout<<"被弹出的第"<<a<<"个元素为"<<endl;
                   cout<<w<<endl;             
                   deletelist(p);
                   m=0;
                   a++;
               
               if(a==n)
               {  
                   cout<<"被弹出的第"<<n<<"个元素为"<<endl;
                   cout<<p->data;
                   cout<<endl;
                   

               }
               }
              
       }
   
   }  

     //主函数
           int main()
              {  int m;
               int k;

                  cout<<"请输入元素个数M"<<endl;
                   cin>>m;
                  cout<<"请输入弹出的元素的位数K"<<endl;
                  cin>>k;
                 
                    Node* head=createlist(m);
               
                  fun(head,k,m);
                   
                  return(0);


              }

24 楼

我前几天用C++写的 通过测试了
#include <iostream.h>
struct Tnode
{
  int data;
  Tnode *next;
};//节点定义
 
class TPclass
{
   public:
      TPclass(int ms,int mb,int mm);
      void Creat();
      //int OutNode(Tnode *p);
     void Print();
      ~TPclass()
      {
     Tnode *temp;
 for(temp=flag;temp->next!=NULL;temp=temp->next)
   delete(temp); 
      }
   protected:
       Tnode *head,*tail,*flag;
       int sump,beginp,m;
};
TPclass::TPclass(int ms,int mb,int mm)//初始化
{
                     head=NULL;
                 tail=NULL;
                 sump=ms;
                 beginp=mb;
                 m=mm;
                 flag=NULL;
                 
}
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;//temp:开始的变量  
    while(temp->data!=beginp)
        temp=temp->next;
    
    while(sump!=2)//留两个 可以设置变量 让用户选择
    {       
    for(int i=1;i<=m;i++)//选人
       temp=temp->next;  
      p=temp->next;//p=temp
      temp->next=p->next;
      cout<<p->data<<endl;
      delete(p);
      sump--;
    }    
     flag=temp;  
    for(int i=1;i<=2;i++)
    {
      cout<<"the last"<<temp->data;//因为留了两个
      temp=temp->next;
    }

}
void main()
{
    int stop;
TPclass TP(20,5,2);
TP.Creat();
TP.Print();
cin >>stop;

}

25 楼

到这个网站看有没有
算法源码吧 [url=http://www.sfcode.cn/]http://www.sfcode.cn/[/url]

我来回复

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