Monday, October 20, 2014

Josephus Problem Solvation code in C++

#include<iostream>
using namespace std;

struct node{

    int val;
    node *next;
};

void insert_node(int);
void print();
void josephus(int);
node *head,*nptr,*tptr;

int main(){

    head = NULL;
    int start,n;
    cout << "Enter node number: " << endl;
    cin >> n;
    insert_node(n);
    cout << "The persons are:" << endl;
    print();
    cout << "Enter start number: " << endl;
    cin >> start;
    josephus(start);
    return 0;
}

void josephus(int start){

    node *ptr,*qptr;
    qptr = ptr = head;
    for (int i = 1; i < start; i++){

            ptr = ptr->next;
            qptr = ptr;
    }
    while (ptr->next != ptr){

        qptr->next = ptr->next->next;
        ptr = qptr->next;
        qptr = ptr;
    }
    head =  ptr;
    cout << "The person survived is :" << ptr->val << endl;
}
void insert_node (int n){

    for(int i = 0; i < n; i++){

        nptr = new node;
        nptr->val = i+1;
        nptr->next = NULL;
        if (head == NULL){

            head = nptr;
            tptr = nptr;
        }
        else{

            tptr->next = nptr;
            tptr = nptr;
        }
    }
    tptr->next = head;
}
void print(){

    tptr = head;
    cout << tptr->val << "->";
    tptr = tptr->next;
    while (head != tptr){

        cout << tptr->val << "->";
        tptr = tptr->next;
    }
    cout<< endl;
}

No comments:

Post a Comment