2、例程:
#include
#include
typedef int ElemType
typedef struct LNode{
ElemType dataint num
struct LNode *next
}LNode,*LinkList
void CreateList_L(LinkList *L,int n)
{ int i=0
ElemType e
LinkList p,q
*L=(LinkList)malloc(sizeof(LNode))
(*L)->next=NULL(*L)->data=n
q=*L
while(i
data=ep->num=i+1
p->next=NULL
q->next=p
q=p
i++
}
p->next=(*L)->next
}
void PrintList(LinkList L)
{ int i=0
LinkList p
p=L->next
while(i
data)
{
printf("%5d",p->data)
p=p->next
i++
}
printf("\n")
}
void Put(LinkList *L)
{ int i,mLinkList p,q
printf("input a number:\n")
scanf("%d",&m)
q=(*L)->next
while((*L)->data)
{for(i=0i
next
}
printf("%5d",q->num)
m=q->data
p->next=q->next
free(q)
q=p->next
(*L)->data=(*L)->data-1
}
}
void main()
{LinkList L
int a
printf("请输入人数:")
scanf("%d",&a)
printf("请输入密码:")
CreateList_L(&L,a)
printf("您输入的数字为:\n")
PrintList(L)
Put(&L)
}
约瑟夫问题:#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'
//输出最后一个结点的值
}
怎么了,代码看不懂?约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后结果+1即为原问题的解。
首先我们列出一些有关约瑟夫环的结果:
1 1 2 2 3 2 4 1 5 4 6 1 7 4 8 7 9 1 10 4
11 7 12 10 13 13 14 2 15 5 16 8 17 11 18 14 19 17 20 2021 2 22 5 23 8 24 11 25 14 26 17 27 20 28 23 29 26 30 29
31 1 32 4 33 7 34 10 35 13 36 16 37 19 38 22 39 25 40 28
41 31 42 34 43 37 44 40 45 43 46 46 47 2 48 5 49 8 50 11
51 14 52 17 53 20 54 23 55 26 56 29 57 32 58 35 59 38 60 41
61 44 62 47 63 50 64 53 65 56 66 59 67 62 68 65 69 68 70 171 4 72 7 73 10 74 13 75 16 76 19 77 22 78 25 79 28 80 31
81 34 82 37 83 40 84 43 85 46 86 49 87 52 88 55 89 58 90 61
91 64 92 67 93 70 94 73 95 76 96 79 97 82 98 85 99 88 100 91
意思是,前一个数为约瑟夫环的人数,后一个数为最后出去的人的号码。
从上面的表中我们可以归纳出以下两个规则:
规则1:若上一组数字中最后保留号比人数少一,则下一数从1开始记。
例如第三组(3,2)为上一组,最后保留好为2,比3少1,下一组的数字(4,1),最后保留号为1
规则2:若上一组数字为最后保留号与人数相等,则下一数从2开始记。