조세프 문제 체인 구현

7673 단어
#include 
using namespace std;
struct Node {
	int data;
	Node* next;
	Node(int _data, Node* _next) :data(_data), next(_next) {};
};
Node* CreatLinkedList(int n) {
	Node* head = new Node(1, nullptr);
	Node* next = head;
	for (int i = 2; i <= n; i++) {
		Node* p = new Node(i, nullptr);
		next->next = p;
		next = p;
	}
	next->next = head;
	return head;
}
int solve(int n, int m) {
	if (m == 1 || n < 2)
		return n;
	Node* head = CreatLinkedList(n);
	Node* cur = head;
	Node* pre = head;
	int cnt = 1;
	while (cur->next != cur) {
		if (cnt == m) {
			cnt = 1;
			pre->next = cur->next;
			cur = pre->next;
		}
		else {
			cnt++;
			pre = cur;
			cur = cur->next;
		}
	}
	return pre->data;
}
int main() {
	int n, m;//n , m
	cin >> n >> m;
	cout << solve(n, m);
	return 0;
}

좋은 웹페이지 즐겨찾기