Joseph ring problem (Josephus)

Original title:

The user inputs M, N value, from 1 to n, and outputs the value every number to m until all outputs. Write a C program. (Joseph ring problem josephus)

prompt:

Since after someone exits the circle, the number of reports will continue from the next person, the remaining people are still enricked into a circle, and the loop table can be used, since the work of exiting the circle corresponds to the deletion of the node in the table Operation, for this case where the delete operation is frequent, select a high efficiency of the chain table structure, and points to a specific representative of one person every time, the linked list does not need to take the header. Therefore, the data structure corresponding to the circle of all people is used to describe a loop chain list without header nodes. The head pointer is P and moves according to the specific situation. In order to record the order of the person who exits, a sequential table is stored. After the program is over, the output of the person who is in turn exiting sequentially. Since only the Number values ​​of each node are recorded, a integer one-dimensional array is defined. Such as: int quit [n]; n is a sufficiently large integer defined according to the actual problem.

Code:

/ ************************************************** ************************** CREATED: 2006/06/14 filename: c: / documents and settings / administrator / desktop /TMPP/josephus.c file path: c: / Documents and settings / Administrator / Deskttings / TMPP File Base: Josephus File Ext: C Author: a.tng version: 0.0.1 Purpose: Implementing the Josephus ring problem User input M, n value, from 1 to N starting sequential loop number, The value is output every to m until all outputs. Write a C program. (Joseph question josephus) ************************************************************* *********************************** / # include #include #include #include < Malloc.h>

/ * Structural and function declaration * / typef 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);

/ * Function function implementation * /

/ * * Name: node_t_create * params: * n [in] Number of linked lists to be constructed * Return: * Return to the construction successful ring-shaped one-way linked list pointer * notes: * Constructed Node Num-shaped ring-shaped linked list * * 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;

/ * Construct 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)); / * Memory space application success * / p_ret = p_node; for (; n_idx 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;

/ * Constructed annular single-way linked list * / p_list = node_t_create (n);

/ * Josephus loop number * / p_iter = p_list; m% = n; while (p_iter! = P_iter-> next) {INT i = 1;

/ * Take the m-1 node * / for (; i next;}

/ * Outputs the value of the mth node * / printf ("% d / n", p_iter-> next-> n_num);

/ * Remove the m m node from the list * / p_iter-> next = p_iter-> next-> next; p_itor = p_iter-> next;} printf ("% d / n", p_iter-> n_num);

/ * Release the space of the application * / free (p_list);

System ("pause");