数据结构中的约瑟夫环问题用C语言怎么编写出来啊?
你看下我以前写的这个吧，差不多，你稍微改下就行，http://wenku.baidu.com/view/34859501d0d233d4b14e699f
#include
using namespace std;
struct Node//循环节点的定义
{
int number;//编号
Node *next;
};
Node *CreateList(Node *L,int &n,int &m);//建立约瑟夫环函数
void Joseph(Node *L,int n,int m);//输出每次出列号数函数
Node *DeleteList(Node **L,int i,Node *q);//寻找每次出列人的号数
int LengthList(Node *L);//计算环上所有人数函数
void main()//主函数
{
Node *L;
L=NULL;//初始化尾指针
int n, m;
cout<<"请输入人数N：";
cin>>n;//环的长度
if(n<1){cout<<"请输入正整数!";}//人数异常处理
else
{
cout<<"请输入所报数M：";
cin>>m;
if(m<1){cout<<"请输入正整数!";}//号数异常处理
else
{
L=CreateList(L,n,m);//重新给尾指针赋值
Joseph(L,n,m);
}
}
system("pause");
}
Node *CreateList(Node *L,int &n,int &m)//建立一个约瑟夫环（尾插法）
{
Node *q;
for(int i=1;i<=n;i++)
{
Node *p;
p=new Node;
p->number=i;
p->next=NULL;
if(i==1) L=q=p;//工作指针的初始化
else
{
q->next=p;
q=q->next;
}
}
q->next=L;
if(L!=NULL){return(L);}//返回尾指针
else cout<<"尾指针异常!"<<endl;//尾指针异常处理
}
void Joseph(Node *L,int n,int m)//输出每次出列的人
{
int k;
cout<<"请输入第一个报数人：";
cin>>k;
if(kn){cout<<"请输入1-"<<n<<"之间的数"<<endl;}
else
{
cout<<"
出列顺序:
";
for(int i=1;i<n;i++)
{
Node *q = new Node;
if(i==1) q=DeleteList(&L,k+m-1,q);//第一个出列人的号数
else q=DeleteList(&L,m,q);
coutnumber<<endl;
delete q;//释放出列人的存储空间
}
coutnumber<<endl;;//输出最后出列人的号数
}
}
Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人
{
if(i==1) i+=LengthList(*L);//顺序依次出列情况的处理方式
Node *p;
p=*L;
int j=0;
while(jnext;j++;}
q = p->next;
p->next=p->next->next;
*L = p->next;
return(q);
}
int LengthList(Node *L)//计算环上的人数
{
if(L){cout<<"尾指针错误!"<<endl;}//异常处理
else
{
int i=1;
Node *p=L->next;
while(p!=L)
{
i++;
p=p->next;
}
return(i);
}
}
圈子，问最后留下的是原来第几号的那位。
1. 程序分析：这是一个比较经典的算法--约瑟夫环问题.
2.个人分析: 算法比较经典,对于这样的问题本应该使用链表的形式会比较容易.约瑟夫环算法
则体现了使用数组来完成链表该完成的功能,虽然形式上完全不相同,但却求出了
相同的结果.有异曲同工之妙.总之我个人认为是数组中非常经典的算法了.希望本
人写的代码不会叫大家啐骂!
3.程序源代码：
#include <stdio.h>
#define N 50
#define S 3
void main()
{
int a[N];
int i,k;
int sum=N;
k=0;
for(i=0;i<N;i++)
a[i]=i+1;
for(i=0;i<N;i++)
printf("%-4d",a[i]);
printf("\n");
for(i=0;;i++)
{
if(sum==1)
break;
if(a[i%N]!=0)
{
k++;
}
if(k==S)
{
k=0;
//printf("%4d",a[i%N]);
a[i%N]=0;
sum--;
}
}
for(i=0;i<N;i++)
if(a[i]!=0)
printf("\n最后一个数为:%d\n",a[i]);
}
两年前念书的时候写的,献丑了!
#include <iostream>
using namespace std;
#define FALSE 0
#define TRUE 1
#define MODNUM 3
typedef int BOOL;
void main(void)
{
____BOOL bLoop;
____int iRotation=0,iCounteract=0,iLast;
____int iTotalNumber,iNTotalNumber=0;
____char *piInGameing;
____cout<<"请输入共有几人参加游戏\n";
____cin>>iTotalNumber;
____piInGameing=new char[iTotalNumber];
____for(int i=0;i<iTotalNumber;i++)
____ ___piInGameing[i]='1';
____do{
____ ____bLoop=FALSE;
____ ____for(int i=0;i<iTotalNumber;i++)
____ ____{
____ ____ ___if('0'!=piInGameing[i])
____ ____ ___{
____ ____ ____ ___bLoop=TRUE;
____ ____ ____ ___if(0==(iNTotalNumber+(i+1)-iCounteract)%MODNUM)
____ ____ ____ ____ ___piInGameing[iLast=i]='0';
____ ____ ___}
____ ____ ___else
____ ____ ____ ___iCounteract++;
____ ____}
____ ____iRotation++;
____ ____iNTotalNumber=iRotation*iTotalNumber%MODNUM;
____}while(bLoop);
____delete [] piInGameing;
____cout<<"最后一个是原来的第"<<iLast+1<<"号\n";
}
//注:各句开头的下画线'_'全都代表空格
#include<stdio.h>
#include<malloc.h>
#define Namelength 10
typedef struct CLNode{
char*name;
int ID;
int pastword;
struct CLNode *next;
}child,*ptrchild;
ptrchild CreateCList(int n)
{int i;
ptrchild p,head,rear;
printf("please input the children information:");
rear=head=(ptrchild)malloc(sizeof(child));
rear->next=head;
for(i=0;i<n;i++)
{getchar();
p=(ptrchild)malloc(sizeof(child));
p->ID=i+1;
p->name=(char*)malloc(Namelength*sizeof(char));
gets(p->name);
scanf("%d",&(p->pastword));
rear->next=p;
rear=p;
}
rear->next=head;
return head;
}
Joshpus(ptrchild head,int m)
{ptrchild p,q;int i=0;
p=head;
while(head->next!=head)
{while(i<m)
{q=p;
p=p->next;
if(p==head){q=head;p=p->next;}
i++;
}
printf("\nID:%d Name:%s",p->ID,p->name);
q->next=p->next;
m=p->pastword;
i=0;
free(p);
p=q;
}
printf("\n");
}
main()
{ptrchild CL;
int n,m;
printf("please input the number of children:");
scanf("%d",&n);
CL=CreateCList(n);
printf("please input the initial value of m:");
scanf("%d",&m);
Joshpus(CL,m);
}
数据结构课程设计《报数游戏》队列问题 c语言
答：约瑟夫环问题：如果你用队列做的话，设一个计数器，如果计数器<m就出队后再入队，等于m时那个元素只出队不入队，输出这个元素并且让m等于0。循环到队列为空就行了。
用c语言实现约瑟夫环
答：正好之前写过基础的约瑟夫环，稍作修改就可以满足你的题目 include <stdio.h>#include <stdlib.h>typedef struct _node { int id; int key; struct _node *next;} Linklist;int main() {int n, m;scanf("%d %d", &n, &m);int i, count = 0;Linklist *head = (Linklist*...
急!!帮忙解读一个C++数据结构的问题,要求详细一点~~我要写实验报告,而...
答：//这个是带密码的约瑟夫环问题，并且的确是用链表做的0.0 //有不懂的请在问题补充里说明 //个人理解，如有不当还请见谅 include<iostream> include"LinkList.h"using namespace std;void Creat(LinkList &y,int &n) //构造约瑟夫环y,人数为n { //每个人包含两个信息:一个是他的密码...
C++ 初学者的问题..
答：josephus是一个数学问题。首先，为了解决这个问题建立了一个链表。struct jose就是建立链表的节点（结构体），里面有一个code变量储存小孩的编号（可参考单链表的建立），同时定义了一个结构体指针＊next，用来指向下一个节点。而Jose *pCur, *pivot都是定义了一个结构体指针，这两个指针在creatRing中...
求用数据结构(c语言版)编写选猴王的程序,
答：这个是最基础的约瑟夫环 用数组 或者链表实现均可。数组实现如下：include<stdio.h>#define MAX 1005int main(void){ int monkey[MAX]={0}; int n,temp=0; int monkeyOut=0; int count = 0; scanf("%d",&n); do{ temp++;//逐个枚举圈中的所有位置 if(temp>...
c语言 数据结构 约瑟夫环 创建单向循环链表 一直报错
答：怎么可能就好了，不敢细看，为何不把调用的写在上面？函数调用参数就有错误，CreateList（&L），L在main函数中是一个指针，接收的就应该是二级指针，而你用地址接收了。把所有程序写在main函数中估计都比现在短。，也能更清晰。
约瑟夫环公式是怎样推导出来的?
答：依此规律重复下去，直到圆桌周围的人全部出列。这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head。2、解决问题的核心步骤：1.建立一个具有n个链结点，无头...
数据结构设计约瑟夫环问题
答：printf("约瑟夫环求解,当前设置最大人数为%d.\n",SIZE);printf("报数上限:\n");scanf("%d",&m);printf("总人数为:\n");scanf("%d",&n);for(i=0;i<n;i++){ printf("第%d人的密码为:",i+1);scanf("%d",&array[i]);} joseph(array, m, n) ;return 0;} 这是我之前做的...
数据结构——关于解约瑟夫环问题!
答：/*从headPtr1指向的循环链表中选大王，数到n的猴子淘汰，将依次淘汰出来的猴子插入到headPtr2指向的链表中*/ void selectKing(LISTNODEPTR headPtr1,int n)/*n>=2*/ { LISTNODEPTR prePtr1=NULL,currentPtr1,headPtr2=NULL,tailPtr2;int count;count=1;currentPtr1=headPtr1;while(currentPtr1...
数据结构约瑟夫环的问题...
答：我个人觉得用数组做不方便，还是链表好。我编了个循环链表做的约瑟夫环，可以给你参考参考。include<stdio.h> include<stdlib.h> typedef struct Node { int key;//每个人持有的密码 int num;//这个人的编号 struct Node *next;//指向下一个节点 }Node,*Link;//=== void InitList(Link &L)...
