조세 프 링 문제 (Josephus) 의 두 가지 해법 (소스 코드)

알고리즘 설명: 번호 가 있 습 니 다. 1 부터 N 까지 N 명 이 한 바퀴 를 돌 고 M 에 게 보고 하 는 사람 이 아웃 되 고 다음 사람 은 1 부터 시작 합 니 다. 이렇게 지속 되 고 한 명 이 남 을 때 까지 이 사람의 번호 X 를 보고 합 니 다.N, M 을 입력 하고 X 를 구하 십시오.다음은 두 가지 해법 을 제시 하 겠 습 니 다. 앞 에 있 는 것 은 비교적 일반적인 해법 으로 '명문 정파' 에 비교적 적합 하고 뒤에 있 는 것 은 매우 교묘 합 니 다.
주의 점: 어떤 사람 이 원 을 탈퇴 한 후에 번호 의 작업 은 다음 사람 부터 계속 해 야 하기 때문에 나머지 사람 은 원 으로 둘러싸 여 있 기 때문에 순환 표를 사용 할 수 있 습 니 다. 원 을 탈퇴 하 는 작업 은 표 의 결점 삭제 작업 에 대응 하기 때문에 이런 삭제 작업 이 빈번 한 상황 에 대해 효율 이 높 은 링크 구 조 를 선택 할 수 있 습 니 다.프로그램 지침 은 매번 한 사람 을 대표 하 는 구체 적 인 결점 을 가리 키 기 위해 판단 할 필요 가 없고 체인 테이블 은 앞장 서지 않 는 결점 을 가리킨다.따라서 모든 사람 이 둘 러 싼 동그라미 에 대응 하 는 데이터 구 조 는 앞장 서지 않 는 순환 링크 로 설명 한다.헤드 포인 터 를 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;
}