骑士问题.txt

输入骑士个数

#define OK 1
#define ERROR 0
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int N; //骑士总数

typedef int Status;

//定义循环链表
typedef struct LNode{
  int data;
  LNode *next;
}LNode,*LinkList;

//构造空循环链表
Status InitList(LinkList &L){
  L=(LinkList)malloc(sizeof(LNode));
  L->next=L;
  return OK;
}

//第i个位置之前插入元素e
Status ListInsert(LinkList &L,int i,int e){
  if(i<1) return ERROR; //插入位置不合理
  int j=0;
  LinkList p=L,s;
  while(j<i-1){ //寻找第i-1个结点
    p=p->next;
    j++;
  }
  s=(LinkList)malloc(sizeof(LNode)); //生成新结点,插入L中
  s->data=e;
  s->next=p->next;
  p->next=s;
  return OK;
}

//删除结点s
Status ListDelete(LinkList &L,LinkList &s){
  LinkList p=L;
  while((p->next)!=s){ //寻找结点s
    p=p->next;
  }
  p->next=s->next; //删除结点s
  if(s==L) L=s->next;
  free(s);
  return OK;
}

//初始化循环链表
Status PutList(LinkList &L){
  int i;
  L->data=1;
  for (i=2;i<=N ; i++){
  ListInsert(L,i-1,i);
  }
  return OK;
}

//取第i个结点的地址,赋给结点s
Status GetElem(LinkList L,int i,LinkList &s){
  if(i<1) return ERROR; //位置不合理
  int j=1;
  LinkList p;
  p=L;
  while(j<i){ //寻找第i个结点
    p=p->next;
    j++;
  }
  s=p;
  return OK;
}

//数i个结点，删除最后数的结点,返回后面结点的地址
Status ElemCount(LinkList &L,int i,LinkList &s){
  LinkList p=s;
  while(i!=1){ //数i个结点
    p=p->next;
    i--;
  }
  s=p->next; //结点s返回后面结点的地址
  printf("%d ",p->data);//<<' ';
  ListDelete(L,p); //删除最后数的结点
  return OK;
}

//Josephus问题
void Josephus(int k,int m){
  int total=N; 
  LinkList L,s;
  InitList(L);
  PutList(L);
  GetElem(L,k,s);
  while(total!=1){ //直到只剩一人，循环结束
    ElemCount(L,m,s);
    total--;
  }
  printf("留下的骑士是%d",L->data);//<<endl;
}
//主函数
int main(){
  int k,m;
  char flag='y';
  printf("输入骑士个数:\n");
  scanf("%d",&N);
  printf("开始数的位置:\n");
  scanf("%d",&k);
  printf("每次数的人数:\n"); 
  scanf("%d",&m);
  printf("骑士离开的顺序为:\n");
  Josephus(k,m);
  printf("\n");
  system("pause");
  
}