C语言编程求解约瑟夫问题

约瑟夫环的问题，我给你一个，程序首先输入小孩子个数，然后输入W

首先输出每个小孩子的编号，然后输出出列的数序，最后输出留下的小孩的编号

#include<stdioh>

int Josephus(int Child,int n,int m);

void main()

{

int allChild,j,k,l;

scanf("%d%d",&j,&k);

//cin>>j>>k;

if((allChild= new int[j])!=NULL)

{

for(l=0;l<j;l++)

{

printf("%d,",l+1);

//cout<<l+1<<",";

allChild[l]=l+1;

}

printf("\n");

//cout<<endl;

printf("%d",Josephus(allChild,j,k));

//cout<<Josephus(allChild,j,k);

}

}

int Josephus(int Child,int n,int m)

{

int i=-1,j=0,k=1;

while(1)

{

for(j=0;j<m;)

{

i=(i+1)%n;

if(Child[i]!=-1)

j++;

}

if(k==n)

break;

//cout<<Child[i]<<",";

printf("%d,",Child[i]);

Child[i]=-1;

k=k+1;

}

printf("\n");

//cout<<endl;

return(Child[i]);

}

package 约瑟夫环;

import javautilLinkedList;

import javautilList;

/

约瑟夫环问题的一种描述是：编号为123……n的n个人按顺时针方向围坐一圈 ，每人手持一个密码（正整数），

开始任意选一个整数作为报数上限值，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，

将他的密码作为新的m值，从他顺时针下一个人开始重新从1开始报数，

如此下去直到所有的人全部都出列为止。试设计程序实现，按照出列的顺序打印各人的编号。

@author Administrator

/

public class Question2 {

class person {

int password;

int number;

int state = 1;

public person(int password, int number) {

thispassword = password;

thisnumber = number;

}

public person(int number){

thisnumber = number;

}

}

public int ListLength(List<person> list) {

int count = 0;

if (list != null) {

for (person p : list) {

if (pstate != 0) {

count++;

}

}

}

return count;

}

public void cacle() {

// 初始化数据

List<person> list = new LinkedList<person>();

listadd(new person(3,1));

listadd(new person(1,2));

listadd(new person(7,3));

listadd(new person(2,4));

listadd(new person(4,5));

listadd(new person(8,6));

listadd(new person(4,7));

int position = -1;//初始位置

int m = 20; //第一次报多少的人出来

int count = 0;//已经报了多少人

while (ListLength(list) != 0) {

position = (position + 1) % listsize();// 位置定位

if (((person) listget(position))state != 0) {

count++;

}

if (count == m) {

person p = listget(position);

Systemoutprint(pnumber+" ");

pstate = 0;

m = ppassword;

listset(position, p);

count = 0;

}

}

}

public static void main(String[] args) {

Question2 q= new Question2();

qcacle();

}

}

跟这差不多的。

var

k:longint;

i,j,m,s:longint;

begin

readln(k);

for m:=2 to 9999999 do

begin

i:=2k;

j:=0;

s:=1;

while i>k do

begin

j:=(j+m) mod i;

if j=0 then j:=i;

if j<=k then begin s:=0;break; end;

dec(i);

dec(j);

end;

if s=1 then begin writeln(m);halt; end;

end;

end

约瑟夫问题：

#include

struct

Node

{

int

data;

Node

pNext;

};

void

main()

{

int

n,k,m,i;

Node

p,q,head;

cout<<"输入n的值:";

cin>>n;

cout<<"输入起始报数人号码k的值:";

cin>>k;

cout<<"输入

数到m出列的m的值:";

cin>>m;

head=(Node)new

Node;

//确定头结点

p=head;

for(i=1;i<=n-1;i++)

//赋初值

{

p->data=i;

p->pNext=(Node)new

Node;

//为下一个新建内存

p=p->pNext;

}

p->data=n;

//最后一个单独处理

p->pNext=head;

//指向头，形成循环链表

p=head;

while(p->data!=(p->pNext)->data)

//p->data==(p->pNext)->data表示只剩下一个结点的

{

while(p->data

!=k)

//寻找编号为k的结点

p=p->pNext;

if(m==1)

{

for(i=1;i<=n;i++)

{

cout<

data<<'\t'

;

p=p->pNext

;

}

cout<<'\n';

return;

}

else

for(i=1;i

pNext;

//q为报m的结点

cout<

data<<"\t";

//输出报m的结点的值

k=(q->pNext)->data;

//k为下一个报数的起点

p->pNext=q->pNext;

//删除报m的结点

}

cout<

data<<'\n';

//输出最后一个结点的值

}

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

链表方法：这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head 解决问题的核心步骤：（程序的基本算法） 1建立一个具有n个链结点，无头结点的循环链表； 2确定第1个报数人的位置； 3不断地从链表中删除链结点，直到链表为空。 void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数 { / p为当前结点 r为辅助结点，指向p的前驱结点 list为头节点/ LinkList p,r,list; /建立循环链表/ for(int i=0；i<n；i++) { p=(LinkList)malloc(sizeof(LNode)); p->data=i; if(list==NULL) list=p; else r->link=p; r=p; } p->link=list; /使链表循环起来/ p=list;　/使p指向头节点/ /把当前指针移动到第一个报数的人/ for(i=0;i<k;i++) { r=p； p=p->link; } /循环地删除队列结点/ while(p->link!=p) { for(i=0;i<m-1;i++) { r=p; p=p->link; } r->link=p->link; printf("被删除的元素：%4d ",p->data); free(p); p=r->link; } printf("\n最后被删除的元素是：%4d",P->data); }

#include<stdioh>

#include<stdlibh>

struct listNode{

int data;

struct listNode nextPtr;

};

typedef struct listNode LISTNODE;

typedef LISTNODE LISTNODEPTR;/LISTNODEPTR：指向LISTNODE指针/

LISTNODEPTR createList(int n);

void selectKing(LISTNODEPTR headPtr1,int n);

void printList(LISTNODEPTR currentPtr);/打印链表/

void destroyList(LISTNODEPTR headPtr);/释放链表各个结点/

int main()

{

LISTNODEPTR headPtr1=NULL,headPtr2=NULL;

int count,monkeys;

int n;

printf("input the amount of monkeys:");

scanf("%d",&monkeys); /猴子个数/

printf("input the count number:");

scanf("%d",&count); /count＝3，表示每次数到3的猴子出局/

headPtr1=createList(monkeys);/创建循环链表/

selectKing(headPtr1,count);/选大王。headPtr1指向循环链表。headPtr2指向由淘汰猴子组成地链表/

system("PAUSE");

return 0;

}

/创建循环链表，容纳n个猴子。返回指向链表头结点的指针/

LISTNODEPTR createList(int n)

{

LISTNODEPTR headPtr=NULL,tailPtr,currentPtr;

int i;

for(i=1;i<=n;i++){

currentPtr=(LISTNODEPTR)malloc(sizeof(LISTNODE));

if(currentPtr==NULL)

printf("memory malloc wrong\n");

else{

currentPtr->data=i;

currentPtr->nextPtr=NULL;

if(headPtr==NULL){/若是作为头结点/

headPtr=currentPtr;

tailPtr=currentPtr;

}

else{/将结点追加到链表末尾/

tailPtr->nextPtr=currentPtr;

tailPtr=currentPtr;

}

}

}

tailPtr->nextPtr=headPtr;/形成循环链表/

return headPtr;

}

/从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!=currentPtr1->nextPtr){

/往后数一个猴子/

prePtr1=currentPtr1;

currentPtr1=currentPtr1->nextPtr;

count++;

/若数到n，则淘汰currentPtr指向的猴子/

if(count%n==0){

/从headPtr1指向链表中拆下currentPtr指向的结点/

prePtr1->nextPtr=currentPtr1->nextPtr;

currentPtr1->nextPtr=NULL;

/将currentPtr1指向的结点插入到headPtr2指向链表中/

if(headPtr2==NULL){/若headPtr2指向的为空链表/

headPtr2=currentPtr1;

tailPtr2=currentPtr1;

}

else{ /将拆下来的结点组装到headPtr2指向的链表上/

tailPtr2->nextPtr=currentPtr1;

tailPtr2=tailPtr2->nextPtr;

}

/currentPtr1指向上一个结点，为下一次数数做准备/

currentPtr1=prePtr1;

}

}

printf("大王是：%d\n",currentPtr1->data);

printf("淘汰的猴子是：");

printList(headPtr2);

/释放链表/

destroyList(headPtr2);

free(currentPtr1);

}

/函数功能：遍历链表，打印链表中各结点的值。

参数说明：指向结点的指针，接收链表头接点的值/

void printList(LISTNODEPTR currentPtr)

{

if (currentPtr==NULL)

printf("the list is empty\n");

else{

printf("the list is:\n");

while(currentPtr!=NULL){

printf("%d--->",currentPtr->data);

currentPtr=currentPtr->nextPtr; /currentPtr指向下一个结点/

}

printf("NULL\n\n");

}

}

void destroyList(LISTNODEPTR headPtr)

{

LISTNODEPTR tempPtr;

while (headPtr!=NULL){

tempPtr=headPtr;

headPtr=headPtr->nextPtr;

free(tempPtr);

}

}

以上就是关于C语言编程求解约瑟夫问题全部的内容，包括:C语言编程求解约瑟夫问题、求解约瑟夫环问题(Java)、约瑟夫问题（编程求解）等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！