-
Notifications
You must be signed in to change notification settings - Fork 1
/
Josephus.cpp
82 lines (67 loc) · 1.75 KB
/
Josephus.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include "CircularLinkList.h"
#include "NormalData.h"
using namespace std;
const int N = 7;
const int K = 3;
void Josephus(int n, int k)
{
int fn = 0;
for (int i = 2; i <= n; ++i)
{
fn = (fn + k) % i;
#ifdef DEBUG
cout << "i = " << i << "; fn = " << fn << endl;
#endif
}
cout << "The solution of Josephus problem with N = " << n << "[0, N - 1], K = " << k << " is " << fn << "." << endl;
}
void JosephusLinkList(int n, int k)
{
vector<int> v;
initializeIndexVector(v, n);
CircularLinkList list(v);
while (list.current != NULL)
{
// Because this is not bidirection link list, we need to keep
// the previous node pointer in order to link it to the node
// after the deleted node.
LinkListNode *prev = NULL;
#ifdef DEBUG
printCircularLinkList(list);
#endif
for (int i = 0; i < k - 1 && list.current != NULL; ++i)
{
prev = list.current;
list.current = list.current->next;
}
LinkListNode *p = list.current;
if (p != NULL)
{
list.current = p->next;
// If the prevous node is the current node, there is only
// one node in the circular list. We need to set the circular
// link list to empty after we delete the last node on the list.
if (prev != p)
{
prev->next = list.current;
}
else
{
list.current = NULL;
}
#ifdef DEBUG
cout << "Delete node " << p->val << endl << endl;;
#endif
delete p;
}
}
}
#ifndef EXPORTED
int main()
{
// Josephus(N, K);
JosephusLinkList(N, K);
return 0;
}
#endif