#include <iostream>
using namespace std;
struct child
{
int num;
child *link;
};
;void init(int n);
;void gameStart(int n,int m);
child *head;
child *present;
child *end;
;int main()
{
int n,m;
cout <<"请输入孩子的个数：";
cin >>n;
cout <<"请输入正整数m：";
cin >>m;
init(n);
gameStart(n,m);
cout <<"第" <<present->num <<"个孩子将获得胜利！" <<endl;
delete present;
return 0;
}
void init(int n)
{
head=new child;
head->num=1;
present=head;
for (int i=1;i<n;i++)
{
present->link=new child;
present->link->num=i+1;
present=present->link;
}
present->link=head;
end=present;
present=head;
}
void gameStart(int n,int m)
{
child *pGuard=end;
while (n!=1)
{
for (int j=1;j<m;j++)
{
pGuard=present;
present=present->link;
}
pGuard->link=present->link;
delete present;
present=pGuard->link;
n--;
}
}
这是个约瑟夫环问题
我想问下
present->link=head;
end=present;
present=head;
具体什么意思
貌似是将首尾相连形成循环链表吧。。
请详细解释下。。谢谢！ 求解。。
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
@洃c小强 I saw this question in the middle of the night, so I’ll add something to it.
The problem with Joseph Ring is that there are
1..nprisoners numberednsitting in a circle to report their numbers. The prisoner numberedmcomes out of the queue and is killed, and then the next one of the prisoners who just came out of the queue is One person starts counting from 1, and so on, until there is only one person left. And report the person's number g(n,m).This is a classic question in computer algorithms.
The conventional solution is to model based on the problem.
Among them
is the model of the prisoner. Each prisoner has a number
numand a pointer to the next prisoner numberlink. In this way, a one-way linked list can be established.However, the Joseph ring is cyclic from head to tail, so
present->link=head;is needed to convert the one-way linked list into a ring linked list.After completing the model construction, you need to specify the start and end positions
is used to complete this function.
The following
gameStartis to complete the function of deleting the linked list node based on conditions.Except for the background of the Joseph ring, in fact, there are only two basic functions of this program: 1. Build a ring linked list; 2. Delete ring linked list nodes according to conditions;
This makes the program much easier to understand. ^-^
In addition, the solution in the question uses simulation to solve the problem of Joseph ring. In fact, in mathematics, there is a direct answer to the Joseph Ring
g(n,m)=?.The code written in Python is as follows:
That’s probably it.
I didn’t look carefully and I don’t understand Joseph Ring and he doesn’t know C++. But it looks like it
The purpose of these three sentences is to reset the link and end pointers of present and present so that they point to the head of the linked list. That is to say, the Joseph ring has been constructed at this time, and the pointers can be set to the initial value of the linked list. After using it later, I looked at the function name
init. I think my guess was absolutely right