# 浅议约瑟夫问题

①最常用的方法是使用循环链表的解决。首先， 将这39 个犹太人构成一个循环链表，每个犹太人等同与一个结点，这个结点有后继结点相连，最后的结点与第一个结点相连。我实现的思路如下所示：

 public class Node
{
private Node preNode;
private Node nextNode;

private int id;

public Node PreNode
{
get {
return preNode;
}
set {
preNode = value;
}
}

public Node NextNode {
get {
return nextNode;
}
set {
nextNode = value;
}
}

public int ID
{
get {
return id;
}
set {
id = value;
}
}

{
get {
}
set {
}
}

}

循环链表

private Node firstNode = null;
private Node lastNode=null;
private Node nextNode = null;
private int count = 0;

public int Count
{
get {
return count;
}
set {
count = value;
}
}

public Circle()
{

}

{
count++;
Node node = new Node();
node.ID = id;

}

{
count++;
Node node = new Node();
node.ID = id;

}

{
if (firstNode == null)
{

firstNode = node;
lastNode = firstNode;

lastNode.NextNode = firstNode;
lastNode.PreNode = firstNode;

firstNode.NextNode = lastNode;
firstNode.PreNode = lastNode;
}
else
{
lastNode.NextNode = node;

node.PreNode = lastNode;
node.NextNode = firstNode;

firstNode.PreNode = node;
lastNode = node;
}
}

public Node NextNode()
{
Node node=new Node();
if (nextNode == null)
{
node = firstNode;
nextNode = firstNode.NextNode;

}
else
{
node = nextNode;
nextNode = node.NextNode;
}
return node;
}

public void RemoveNode(Node node)
{
count--;
Node _preNode = node.PreNode;
Node _nextNode = node.NextNode;
_preNode.NextNode = _nextNode;
_nextNode.PreNode = _preNode;
}

List<Node> outList = new List<Node>();
int index = 0;
int n = 7;
uint m = 20;
List<Node> nodeList = new List<Node>();
Node nd = new Node();
nd.ID = 1;

nd = new Circle.Node();
nd.ID = 2;

nd = new Circle.Node();
nd.ID = 3;

nd = new Circle.Node();
nd.ID = 4;

nd = new Circle.Node();
nd.ID = 5;

nd = new Circle.Node();
nd.ID = 6;

nd = new Circle.Node();
nd.ID = 7;

Circle c = new Circle();
foreach (Node node in nodeList)
{
}

这是把所有的数据添加到泛型数组中。

在进行点名，出列。相应的源代码如下：

while (c.Count > 0)
{
index++;
nd = c.NextNode();
if (index == m)
{
c.RemoveNode(nd);
index = 0;
}
}

foreach (Circle.Node node in outList)
{
Console.WriteLine(node.ID);
}


②基于位图算法的思想，

   public static bool CheckArray(bool[] array)
{
int temp = 0;
for (int i = 0; i < array.Length; i++)
{
if (array[i])
{
temp++;
}
}
return temp == 1;
}
int[] array = new int[M];
;
bool[] blarray = new bool[M];
for (int i = 0; i < M; i++)
{
array[i] = (i + 1);
blarray[i] = true;
}
int count = 0;
int index = 0;

while (!CheckArray(blarray))
{

if (blarray[index])
{
count++;

}
if (count == N)
{
Console.WriteLine("数字" + array[index] + "出列");
count = 0;
blarray[index] = false;
}
index++;
if (index == M)
{
index = 0;
}

}

2

|
2月前
|

2024春节联欢晚会中，刘谦老师的魔术节目可以说是我心目中的全场最佳~春晚刚结束网上就有大佬给出了第二个魔术（拼扑克牌）的数学模拟，也有大佬发布了代码程序。博主在模拟了魔术过程之后，也在此分享一下程序代码和思路。同时，也借此回顾一下经典的数学问题：约瑟夫环问题。
60 8
|
2月前
DongDong认亲戚 - 并查集
DongDong认亲戚 - 并查集
10 0
|
2月前

22 0
|
12月前
|

84 0
[软考]之树和二叉树
[软考]之树和二叉树
63 0
|
IDE Java 开发工具
[软考]之树与二叉树的遍历
[软考]之树与二叉树的遍历
61 0
|

【每日算法Day 74】经典面试题：约瑟夫环，我敢打赌你一定不会最后一种方法！
【每日算法Day 74】经典面试题：约瑟夫环，我敢打赌你一定不会最后一种方法！
68 0
|

NOIP2005 普及组：校门外的树
213 0
|

LeetCode | 循环队列的爱情【恋爱法则——环游世界】

96 0
7-11 玩转二叉树 —— 程序设计天梯赛

87 0