🎈1. 조세퍼스 순열이란??
전산학이나 수학에서 요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)은 다음과 같이 정의한다.n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.예를 들어 (7,3) 요세푸스 순열은 {3,6,2,7,5,1,4}이며 4번째 위치한 사람이 마지막으로 제외되게 된다.이 순열은 역사가 요세푸스가 겪은 일화에서 유래하였다.
[출처]:링크텍스트
🎆2.문제 설명
<조세퍼스 순열>
-1번부터 n번까지 n(사람수)명의 사람이 원을 이루면서 앉아있고, 양의 정수 m(m<=n)(간격)이 주어진다
-이제 순서대로 m번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다
-이 과정은 n명의 사람이 모두 제거될때 까지 계속된다
-원에서 사람들이 제거되는 순서를 (n,m)-조세퍼스 순열이라고 한다
예를 들어 (7,3)-조세퍼스 순열은 <3,6,2,7,5,1,4>이다 n과 m이 주어지면(n,m)-조세퍼스 순열을 구하는 프로그램을 작성한다
🎇3. 코드 + 주석
jocepus.main [1]
#define _CRT_SECURE_NO_WARNINGS
#include "22강 list Queue.h"
#include <stdio.h>
//--------------------------------------------------------------------------------
// main()
//--------------------------------------------------------------------------------
int main()
{
Queue que; /* 큐생성*/
int N, M; /* N : 인원수, M : 간격 수 */
int i;
int getData; /* deueue한 데이터 저장 변수 */
createQueue(&que); /* 큐 생성 및 초기화*/
printf("N(인원수)와 M(간격수)를 입력하시오 (M<=N) : ");
scanf("%d %d", &N, &M);
for (i = 1; i <= N; ++i) //queue 1~N까지의 순번 저장
enqueue(&que, i);
printf("(%d,%d)조세퍼스의 순열 : ", N, M);
while (!isQueueEmpty(&que)) {
for (i = 1; i < M; ++i) {
if (dequeue(&que, &getData) == TRUE)
enqueue(&que, getData);
}
if (dequeue(&que, &getData) == TRUE)
printf("%4d", getData);
}
printf("\n\n");
destroyQueue(&que);
getchar( ); getchar( );
return 0;
}
jocepus.cpp [2]
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include "22강 list Queue.h"
/*--------------------------------------------------------------------------------------
Function name : createQueue - 큐 초기화 함수
Parameters : qp - 큐 구조체의 주소
Returns : 성공 - TRUE / 실패 - FALSE
--------------------------------------------------------------------------------------*/
BOOL createQueue(Queue * qp)
{
if (qp == NULL) { /* qp 포인터 NULL check */
return FALSE;
}
qp->head = (Node *)calloc(1, sizeof(Node)); /* 헤드 노드 생성 */
if (qp->head == NULL) {
return FALSE;
}
qp->tail = (Node *)calloc(1, sizeof(Node)); /* 테일 노드 생성 */
if (qp->tail == NULL) {
free(qp->head);
return FALSE;
}
else { /* 헤드노드가 테일노드를, 테일노드가 테일노드를 가리키게 함 */
qp->head->next = qp->tail;
qp->tail->next = qp->tail;
return TRUE;
}
}
/*--------------------------------------------------------------------------------------
Function name : isQueueEmpty - 큐가 비어있는가 검사
Parameters : qp - 큐 구조체의 주소
Returns : 완전히 비어있으면 TRUE 리턴, 비어있지 않으면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL isQueueEmpty(const Queue *qp)
{
if (qp == NULL) { /* qp 포인터 NULL check */
return FALSE;
}
/* 큐가 완전히 비어있으면 TRUE, 아니면 FALSE 리턴 */
if (qp->head->next == qp->tail)
return TRUE;
else
return FALSE;
}
/*--------------------------------------------------------------------------------------
Function name : enqueue - 큐에 데이터 하나를 저장함
Parameters : qp - 큐 구조체의 주소
enqueData - 큐에 저장할 데이터
Returns : 성공적으로 저장하면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL enqueue(Queue * qp, int enqueData)
{
Node *cur;
if (qp == NULL) { /* qp 포인터 NULL check */
return FALSE;
}
Node *np = (Node *)calloc(1, sizeof(Node)); /* 새로운 노드 생성 */
if (np == NULL) /* 메모리 할당 실패하면 enqueue실패 */
{
return FALSE;
}
/* 노드를 테일 노드 바로 앞에 노드 추가 */
cur = qp->head;
while (cur->next != qp->tail) /* 테일 노드 바로 앞노드를 cur로 가리키게 이동 시킴 */
cur = cur->next;
cur->next = np;
np->next = qp->tail;
np->data = enqueData; /* 데이터 복사 */
return TRUE;
}
/*--------------------------------------------------------------------------------------
Function name : dequeue - 큐에서 데이터 하나를 꺼냄
Parameters : qp - 큐 구조체의 주소
dequeData - 꺼낸 데이터를 저장할 기억공간의 주소
Returns : 성공적으로 꺼내면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL dequeue(Queue * qp, int * dequeData)
{
Node *cur;
if (qp == NULL) { /* qp 포인터 NULL check */
return FALSE;
}
if (isQueueEmpty(qp)) /* 큐가 비어있으면 dequeue 불가 */
{
return FALSE;
}
else { /* head node 뒤에서 데이터를 꺼낸 후 데이터 노드 삭제 */
*dequeData = qp->head->next->data;
cur = qp->head->next;
qp->head->next = qp->head->next->next;
free(cur);
return TRUE;
}
}
/*--------------------------------------------------------------------------------------
Function name : printQueue - 큐 내의 모든 데이터를 출력 함
Parameters : qp - 큐 구조체의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void printQueue(const Queue * qp)
{
Node *cur;
if (qp == NULL) { /* qp 포인터 NULL check */
return;
}
if (isQueueEmpty(qp) == TRUE)
{
printf("Queue가 비어있습니다!!\n");
return;
}
/* dequeue 순서대로 출력하기 - 실제로 dequeue 되는 것은 아님 */
cur = qp->head->next;
while (cur != qp->tail) {
printf("%5d\n", cur->data);
cur = cur->next;
}
printf("\n\n");
}
/*--------------------------------------------------------------------------------------
Function name : destroyQueue - 큐 소멸 함수
Parameters : qp - 큐 구조체의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void destroyQueue(Queue * qp)
{
Node *cur;
if (qp == NULL) { /* qp 포인터 NULL check */
return;
}
/* 데이터 첫 노드부터 맨 뒤의 노드까지 모두 삭제 */
cur = qp->head->next;
while (cur != qp->tail) {
qp->head->next = qp->head->next->next;
free(cur);
cur = qp->head->next;
}
free(qp->head); /* 헤드노드 삭제 */
free(qp->tail); /* 테일노드 삭제 */
qp->head = qp->tail = NULL; /* head, tail 포인터를 NULL로 초기화 */
}
