C语言约瑟夫问题

约瑟夫问题：

#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=1i<=n-1i++)

//赋初值

{

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=1i<=ni++)

{

cout<

data<<'\t'

p=p->pNext

}

cout<<'\n'

return

}

else

for(i=1i

pNext

//q为报m的结点

cout<

data<<"\t"

//输出报m的结点的值

k=(q->pNext)->data

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

p->pNext=q->pNext

//删除报m的结点

}

cout<

data<<'\n'

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

}

#include<stdio.h>

#define size 100 /* 输入人数的上限 */

void main()

{

int person[size]

int i, j/* 循环修正变量 */

int arrayLen/* 数组长度 */

int start, overNum/* 开始位置各跨过位置 */

int deleNum/* 出列人所在数组中的下标 */

int name, total/* 输入时,人的信息以及人的总数 */

printf( "请输入圆桌上人的总数: " )

scanf( "%d", &arrayLen )printf( "\n" )

if( ( arrayLen >size ) || ( arrayLen <0 ) )

{

printf( "超出范围,请重新输入: " )

scanf( "%d", &arrayLen )printf( "\n" )

}

printf( "请输入各个人的信息(整数): \n" )

for( i = 0i <arrayLeni++ )

{

scanf( "%d", &name )

person[i] = name

}

printf( "你输入的数据的顺序为: \n" )

for( i = 0i <arrayLen - 1i++ )

printf( " %d ==>", person[i] )

printf( "%d \n", person[arrayLen - 1] )

printf( "你打算从第几个人开始? 请输入开始号: " )

scanf( "%d", &start )

printf( "\n" )

start = start - 1

printf( "请输入相邻两出列人之间的间隔: " )

scanf( "%d", &overNum )

printf( "\n" )

total = arrayLen

printf( "程序运行后,出列人的顺序为:\n\n" )

for( i = 0i <totali++ ) /* 要打印total个人的情况,故做total次 */

{

if ( arrayLen == 1 )

printf( "%d", person[0] )/* 如果是数组只剩一个元素,直接出列 */

else

{

deleNum = ( start + overNum - 1 ) % arrayLen/* 此取模保证循环 */

printf( "%d ==>", person[deleNum] )

for ( j = deleNumj <arrayLenj++ ) /* 将出列元素后面的各元素前移 */

person[j] = person[j+1]

start = deleNum

arrayLen = arrayLen - 1/* 移动完毕后,数组长度减1 */

}

}

printf( "\n\n" )

}

#include<stdio.h>

#include<stdlib.h>

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=1i<=ni++){

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)

}

}

---