VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 611|回复: 0

[推荐] 约瑟夫环

[复制链接]
09_avatar_middle
最佳答案
0 
在线会员 发表于 2015-4-7 13:56:11 | 显示全部楼层 |阅读模式
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时把编号从0~n-1,最后结果+1即为原问题的解。
namespaceYSFH

{

classProgram

{

staticvoidMain(string[]args)

{

YSFHResult(3,12,4);

}

staticvoidYSFHResult(intbegin,intmax,intm)

{

inttemp=begin;

intnum=0;

ArrayListarray=newArrayList();

for(inti=0;i<max;i++)

{

array.Add(i+1);

}

intintsmax=array.Count;

Console.WriteLine("共有人数"+array.Count.ToString());

for(inti=0;i<intsmax;i++)

{

while(true)

{

for(intn=temp;n<array.Count;n++)

{

num++;

if(num==m)

{

temp=n;

break;

}

}

if(num==m)break;

temp=0;

}

Console.WriteLine("["+(array[temp]).ToString()+"]出列");

array.RemoveAt(temp);

num=0;

}

Console.WriteLine("约瑟夫环结束!");

Console.ReadKey();

}

}

}

C语言递归算法
#include<stdio.h>

#include<stdlib.h>

struct_Node

{

intdata;

struct_Node*next;

};

typedefstruct_Nodenode_t;

typedefstruct_Linklist

{

node_t*phead;

node_t*ptail;

intlen;

}Linklist;

staticnode_t*GetNode(inti)//新建并初始化节点

{

node_t*pNode;

pNode=(node_t*)malloc(sizeof(node_t));

if(!pNode)

{

printf("Error,thememoryisnotenough!\n");

exit(-1);

}

pNode->data=i;

pNode->next=NULL;

returnpNode;

}

voidinit_list(Linklist*plist)//用第一个节点初始化循环单链表

{

node_t*p;

p=GetNode(1);

//printf("TheNewNodeis:%d\n",p->data);//****TEST****

plist->phead=p;

plist->ptail=p;

p->next=plist->phead;

plist->len=1;

}

staticvoidCreate_List(Linklist*plist,intn)//把其余数据添加到循环单链表中

{

inti=0;

node_t*pNew;

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

{

pNew=GetNode(i);

/********TEST********

printf("TheNewNodeis:%d\n",pNew->data);

********TEST********/

plist->ptail->next=pNew;

plist->ptail=pNew;

pNew->next=plist->phead;

plist->len++;

}

printf("Completesthee-waycirculationchaintablethefoundation!\n");

}

voidPrint_List(Linklist*plist)//输出链表内容

{

node_t*pCur=plist->phead;

do

{

printf("The%dperson.\n",pCur->data);

pCur=pCur->next;

}while(pCur!=plist->phead);

printf("ThelengthoftheList:%d\n",plist->len);

}



约瑟夫回环函数实现



voidjoseph(Linklist*plist,intm)//约瑟夫回环函数实现

{

node_t*pPre=plist->ptail;

node_t*pCur=plist->phead;

inti;

while(plist->len!=1)

{

i=0;

while(i<m-1)

{

pPre=pPre->next;

i++;

}

pCur=pPre->next;

pPre->next=pCur->next;

free(pCur);

plist->len--;

}

printf("Thelastoneis:%d\n",pPre->data);

}

intmain()

{

intn=0;

printf("PleaseinputtheLengthoftheCirclelist:");

scanf("%d",&n);

intm=0;

printf("PleaseinputtheStoppoint:");

scanf("%d",&m);

LinklistpList;

init_list(&pList);

Create_List(&pList,n);

Print_List(&pList);

joseph(&pList,m);

return0;

}




上一篇:线性
下一篇:求助…最小生成数算法问题,请各大网友帮忙…
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2020-1-28 03:08

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表