Question

数组实现约瑟夫环问题,用C++编写

我是想用一个循环,人数为n,密码为m.当报的数等于密码m时,此人出列,记下他的位置,下一个人重新从一开始报.请教高手能够按照这个思路指导我,谢谢.

Answer 1

刚好有个现成的，楼主加分，，嘿嘿：
#include "stdio.h"
#include "stdlib.h"
#define S sizeof(struct node)

struct node
{
int num;
struct node *next;
};

typedef struct node NODE;

NODE *createlinklist(int n)
{
NODE *head,*p,*q;
int i=1;
head=p=(struct node*)malloc(sizeof(struct node));
p->num=i;
for(i=2;i<=n;i++)
{
q=(struct node*)malloc(sizeof(struct node));
if(q==0) return(0);
p->next=q;
p=q;
p->num=i;
}
p->next=head; /*使链表尾指向链表头 形成循环链表*/

return head;
}

void printlinklist(NODE *p,int n)
{
int i;
NODE *q = p;
if(NULL == q->next){
printf("the list is NULL!");
return;
}
printf("所有玩家的信息列表:\n");
for(i=1;i<=n;i++)
{
if(NULL == q){
printf("the list is NULL!");
return;
}
printf("%d ",p->num);
p=p->next;
}
printf("\n");
}

void joseph(NODE *p,int n,int m)
{
int i,j;
NODE *q;
for(i=1;i<n;i++)
{
for(j=1;j<=m-1;j++)
{
p=p->next;
}
q=p->next;
p->next = q->next;
printf("%d ",q->num);
free(q);
}
printf("\n最后剩余的是第%d号.\n",p->num);
p->next=NULL;
}

void main()
{
NODE *head;
int n,m;
printf("请输入人数N:\n");
scanf("%d",&n);
printf("请密码M:\n");
scanf("%d",&m);
head=createlinklist(n);
printlinklist(head,n);
printf("依次被选出的是:\n");
joseph(head,n,m);
}

Answer 2

#include <iostream>

using namespace std;

int main() {
int m, n;
while (cin >> n >> m) {
int* a = new int[n];
for (int i = 0; i < n; i++) a[i] = i + 1;
int j = 1; //用于报数
int k = 0; //遍历数组
int l = n; //跟踪剩余人数
while (l > 1) {//剩余人数大于1，继续报数
if (a[k]) {
if (j++ == m) { //报到m出局
j = 1; //重新报数
a[k] = 0; //记下位置
l--;//人数减1
}
}
if (++k == n) k = 0; //循环数组
}
while (a[--i] == 0); //找到最后一个人，即为答案
cout << a[i] << endl;
delete[] a;
}
return 0;
}

Answer 3

嘿嘿 我不是为了分，， 我是为了学习 做做题而已，，

才学习数据结构 请大家嘲笑把

// help.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

typedef struct node{
int number;
struct node *next;
} linkNode,*link;

//建立一个单循环链表
link CreateLink(int personNumber, link lk) {
linkNode* head = lk;

for (int i = 1; i <= personNumber; i++) {
head->number = i;

if (i == personNumber) {
head->next = lk;
}
else {
head->next = new node();
head = head->next;
}
}

//返回头节点是number为personNumber链表，方便查找number为1的前趋节点
return head;
}

void ShowNumberByM(int m, link lk) {

int index = 0;
linkNode* tempNode = lk->next;
linkNode* pravNode = lk;

while (true) {
index ++;
if (index == m) {
printf("%d,", tempNode->number);
pravNode->next = tempNode->next;
delete tempNode;
if (pravNode->next == pravNode) {
printf("%d over", pravNode->number);
break;
}
tempNode = pravNode->next;
index = 0;
}
else{
pravNode = tempNode;
tempNode = tempNode->next;
}
}

}

int _tmain(int argc, _TCHAR* argv[])
{
link l = new node();

ShowNumberByM(5, CreateLink(9, l));
}

Answer 4

用数组实现的那个不错。。

Answer 5

写一个好写，不过让人给你讲明白了我估计没多少人赶接这活。这种东西网上很多，还是搜索一下吧。