You are not logged in.

#1 2020-09-13 21:53:32

MavisStitt
Member
From: Sweden, Hogland
Registered: 2020-09-13
Posts: 1

Click to share on Facebook (Opens in new window)

Implementation of a circular list for solving the problem of Josephus

Filed under:.

— Leave a comment        October 2

2010                 For the representation of individuals arranged in a circle, we create a circular linked list with a combination of each person to the person on his left in the circle.
The integer i represents the i-th person in the circle.
After you create a circular list of one node for 1, we insert its unique node to nodes 2 to N.
We end up with a cycle from 1 to N, with x indicating the node N.
Then.

Starting from 1 we omit M-1 nodes

we define the pointer of the (M-1)-th node to omit the M-th, and continue that way until only one node remains in the list.
You should know that the implementation of the algorithm does not take into account issues of data input validation or proper  management  of dynamic memory (e.g.
avoiding memory leaks) because it is only necessary to highlight the logic of the  algorithm .
#include <iostream> #include <cstdlib> using  namespace  std;  struct node {   int item; node * next;    node (int x, node * t) {     item = x; next = t;   } };  typedef node * plink;  int main (int argc, char *argv[]) {   int i, N, M;    if (!argv[1] || !argv[2])     return EXIT_FAILURE;    N = atoi (argv[1]);   M = atoi (argv[2]);    plink t = new node (1, 0);   t->next = t;   plink x = t;    for (i = 2; i <= N; i++)     x = (x->next = new node (i, t));    while (x != x->next) {     for (i = 1; i < M; i++)       x = x->next;      x->next = x->next->next;   }    cout << x->item << endl;    return EXIT_SUCCESS; }           Rate this:.
Share this:.
Click to share  on Facebook  (Opens in new window).

Click to share on LinkedIn (Opens in new window)
Click to share on Twitter (Opens in new window)
Click to print (Opens in new window)
Click to email this to a friend (Opens in new window)

Like this:.
Like   Loading.
Related.
Tags: , circular, Josephus problem,     .

Comments RSS feed                    Leave a Reply Cancel reply

Enter  your comment  here.
Fill in  your details  below or click an icon to log in:.
Email  (Address never made public)                 Name                 Website                                                            You are commenting using your  WordPress .com account.
( Log Out /     )                                                             You are commenting using your  Google account .
( Log Out /     )                                                             You are  commenting  using your Twitter account.
( Log Out /     )                                                             You are commenting using  your Facebook  account.
( Log Out /     )                             Cancel   Connecting to %s             Notify me of new comments via email.
Notify me of new posts via email.

« Implementation of algorithm for finding primes with the sieve of Eratosthenes

Implement simple reverse list iteratively.
».
(79).
(21).
(15).
(26).
(4).
(7).
(55).
(24).
(4).
(16).
(14).
(4).
(7).
(10).
(78).
(11).
(9).
(1).
October 2010      M  T  W  T  F  S  S           123      45678910      11121314151617      18192021222324      25262728293031        « Sep     Nov ».
(2).
(4).
(1).
(1).
(2).
(1).
(1).
(1).
(2).
(1).
(9).
(1).
(8).
(1).
(1).
(2).
(4).
(7).
(1).
(1).
(1).
(8).
(12).
(1).
(2).
(1).
(2).
(1).
(2).
(1).
(1).
(4).
(20).
(13).
(5).
(2).
(10).
(13).
(10).
(10).
(20).
287,006 hits.
Send to Email Address          Your Name       Your Email Address                              Cancel       Post was not sent - check your email addresses.
Email check failed.

Please try again          Sorry

your blog cannot share posts by email.
%d  bloggers like this:.

Offline

Board footer

Powered by FluxBB