原題：

?用戶輸入M,N值，從1至N開始順序循環(huán)數(shù)數(shù)，每數(shù)到M輸出該數(shù)值，直至全部輸出。寫出C程序。（約瑟夫環(huán)問題 Josephus）

提示：

??? 由于當(dāng)某個(gè)人退出圓圈后，報(bào)數(shù)的工作要從下一個(gè)人開始繼續(xù)，剩下的人仍然是圍成一個(gè)圓圈的，可以使用循環(huán)表，由于退出圓圈的工作對(duì)應(yīng)著表中結(jié)點(diǎn)的刪除操作，對(duì)于這種刪除操作頻繁的情況，選用效率較高的鏈表結(jié)構(gòu)，為了程序指針每一次都指向一個(gè)具體的代表一個(gè)人的結(jié)點(diǎn)而不需要判斷，鏈表不帶頭結(jié)點(diǎn)。所以，對(duì)于所有人圍成的圓圈所對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)采用一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表來描述。設(shè)頭指針為p，并根據(jù)具體情況移動(dòng)。
??? 為了記錄退出的人的先后順序，采用一個(gè)順序表進(jìn)行存儲(chǔ)。程序結(jié)束后再輸出依次退出的人的編號(hào)順序。由于只記錄各個(gè)結(jié)點(diǎn)的number值就可以，所以定義一個(gè)整型一維數(shù)組。如：int? quit[n];n為一個(gè)根據(jù)實(shí)際問題定義的一個(gè)足夠大的整數(shù)。

代碼：

/********************************************************************
??? created:??? 2006/06/14
??? filename:?? C:\Documents and Settings\Administrator\桌面\tmpp\josephus.c
??? file path:? C:\Documents and Settings\Administrator\桌面\tmpp
??? file base:? josephus
??? file ext:?? c
??? author:???? A.TNG
??? version:??? 0.0.1
???
??? purpose:??? 實(shí)現(xiàn) Josephus 環(huán)問題
??????????????? 用戶輸入M,N值，從1至N開始順序循環(huán)數(shù)數(shù)，每數(shù)到M輸出該數(shù)值，
??????????????? 直至全部輸出。寫出C程序。（約瑟夫環(huán)問題 Josephus）
*********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

/* 結(jié)構(gòu)體和函數(shù)聲明 */
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);

/* 功能函數(shù)實(shí)現(xiàn) */

/*
?*? name: node_t_create
?*? params:
?*??? n???????? [in]??????? 輸入要構(gòu)造的鏈表的個(gè)數(shù)
?*? return:
?*??? 返回構(gòu)造成功的環(huán)形單向鏈表指針
?*? notes:
?*??? 構(gòu)造節(jié)點(diǎn)數(shù)量為 n 的環(huán)形單向鏈表
?*
?*? author: A.TNG 2006/06/14 17:56
?*/
node_t * node_t_create(int n)
{
??? node_t *p_ret?? = NULL;

??? if (0 != n)
??? {
??????? int???? n_idx?? = 1;
??????? node_t *p_node? = NULL;

??????? /* 構(gòu)造 n 個(gè) 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));

??????? /* 內(nèi)存空間申請(qǐng)成功 */
??????? 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
?*
?*? author: A.TNG 2006/06/14 18:11
?*/
int main()
{
??? int???? n, m;
??? node_t *p_list, *p_iter;

??? n = 20; m = 6;

??? /* 構(gòu)造環(huán)形單向鏈表 */
??? p_list = node_t_create(n);

??? /* Josephus 循環(huán)取數(shù) */
??? p_iter = p_list;
??? m %= n;
??? while (p_iter != p_iter->next)
??? {
??????? int i?? = 1;

??????? /* 取到第 m-1 個(gè)節(jié)點(diǎn) */
??????? for (; i < m - 1; i++)
??????? {
??????????? p_iter = p_iter->next;
??????? }

??????? /* 輸出第 m 個(gè)節(jié)點(diǎn)的值 */
??????? printf("%d\n", p_iter->next->n_num);

??????? /* 從鏈表中刪除第 m 個(gè)節(jié)點(diǎn) */
??????? p_iter->next = p_iter->next->next;
??????? p_iter = p_iter->next;
??? }
??? printf("%d\n", p_iter->n_num);

??? /* 釋放申請(qǐng)的空間 */
??? free(p_list);

??? system("PAUSE");
}