조세 프 링 문제 (Josephus) 의 두 가지 해법 (소스 코드)
주의 점: 어떤 사람 이 원 을 탈퇴 한 후에 번호 의 작업 은 다음 사람 부터 계속 해 야 하기 때문에 나머지 사람 은 원 으로 둘러싸 여 있 기 때문에 순환 표를 사용 할 수 있 습 니 다. 원 을 탈퇴 하 는 작업 은 표 의 결점 삭제 작업 에 대응 하기 때문에 이런 삭제 작업 이 빈번 한 상황 에 대해 효율 이 높 은 링크 구 조 를 선택 할 수 있 습 니 다.프로그램 지침 은 매번 한 사람 을 대표 하 는 구체 적 인 결점 을 가리 키 기 위해 판단 할 필요 가 없고 체인 테이블 은 앞장 서지 않 는 결점 을 가리킨다.따라서 모든 사람 이 둘 러 싼 동그라미 에 대응 하 는 데이터 구 조 는 앞장 서지 않 는 순환 링크 로 설명 한다.헤드 포인 터 를 p 로 설정 하고 구체 적 인 상황 에 따라 이동 합 니 다.탈퇴 한 사람의 선후 순 서 를 기록 하기 위해 순서 표를 사용 하여 저장 합 니 다.프로그램 이 끝 난 후에 순서대로 종료 한 사람의 번호 순 서 를 출력 합 니 다.각 노드 의 number 값 만 기록 하면 되 기 때문에 전체 1 차원 배열 을 정의 합 니 다.int quit[n];n 은 실제 문제 에 따라 정 의 된 충분 한 정수 이다.
● 일반 해법:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
/* */
typedef struct _node_t
{
int n_num;
struct _node_t *next;
} node_t;
node_t *node_t_create(int n);
node_t *node_t_get(node_t **pn, int m);
/* */
/*
* name: node_t_create
* params:
* n [in]
* return:
*
* notes:
* n
*
*/
node_t * node_t_create(int n)
{
node_t *p_ret = NULL;
if (0 != n)
{
int n_idx = 1;
node_t *p_node = NULL;
/* n node_t */
p_node = (node_t *) malloc(n * sizeof(node_t));
if (NULL == p_node)
return NULL;
else
memset(p_node, 0, n * sizeof(node_t));
/* */
p_ret = p_node;
for (; n_idx < n; n_idx++)
{
p_node->n_num = n_idx;
p_node->next = p_node + 1;
p_node = p_node->next;
}
p_node->n_num = n;
p_node->next = p_ret;
}
return p_ret;
}
/*
* name: main
* params:
* none
* return:
* int
* notes:
* main function
*/
int main()
{
int n, m;
node_t *p_list, *p_iter;
n = 20; m = 6;
/* */
p_list = node_t_create(n);
/* Josephus */
p_iter = p_list;
m %= n;
while (p_iter != p_iter->next)
{
int i = 1;
/* m-1 */
for (; i < m - 1; i++)
{
p_iter = p_iter->next;
}
/* m */
printf("%d
", p_iter->next->n_num);
/* m */
p_iter->next = p_iter->next->next;
p_iter = p_iter->next;
}
printf("%d
", p_iter->n_num);
/* */
free(p_list);
}● int f(int n, int m)
{
int i, r = 0;
for (i = 2; i <= n; i++)
r = (r + m) % i;
return r+1;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.