Computer Science‎ > ‎

C Program: Source code to solve the Josephus Problem



 
The C++ Programming Language...
List Price: Rs.775
Our Price: Rs.736
Buy from FlipKart

The C++ Programming Language (Bjarne Stroustrup)

Beginning C++ Through Game Pr...
Our Price: Rs.2008
Buy from FlipKart

       
Beginning C++ through Game Programming 

 
C++ How to Program
List Price: Rs.695
Our Price: Rs.632
Buy from FlipKart

                               
 
The C Programming Language
List Price: Rs.175
Our Price: Rs.137
Buy from FlipKart

             
The C Programming Language (Kernighan)
 
C How To Program 6th  Edition
List Price: Rs.650
Our Price: Rs.624
            Buy from FlipKart


          
C How to Program (Deitel and Deitel)

 



C Program/source code to solve the Josephus Problem


/*The following program is an implementation of the Josephus Problem in C.
Consider a problem of a group of soldiers overpowered and surrounded by enemy forces. A single soldier can escape and all soldiers stand
in a circle and a number n is picked up and a soldier's name is picked up. Beggining with the soldier whose name is picked they begin to count clock wise
When count reaches n,the soldier is removed and count begins with next soldier. This countinues till only one soldier remains. Josephus Problem
is to determine the soldier which escapes.
*/
#include<stdio.h>
struct node
{
    struct node *next;//stroes address to next node
    char name[10];//stroes the name
}*start;//points to beginning of the list
typedef struct node *Nodeptr;
void add(char namePassed[])//add a node
{
Nodeptr temp=(struct node *)malloc(sizeof(struct node));//newly declared node
Nodeptr move;
move=start;//points to the start
if(temp==NULL)
{
    printf("OverFlow\n");
    return;//can not allocate space so return
}
while((move->next)!=NULL)
move=move->next;//move to appropriate place to add new node to end
strcpy(temp->name,namePassed);
temp->next=NULL;
move->next=temp;
}
int main()
{
char choice[20];
start=(Nodeptr)malloc(sizeof(struct node));
printf("\t\tJosephus Problem\n");
printf("Enter the name \n");//Enter the begining node
scanf("%s",start->name);
start->next=NULL;
printf("Enter end to stop entering data otherwise enter the name\n");
scanf("%s",choice);
while(strcmp(choice,"end")!=0)
{
add(choice);
printf("Enter end to stop entering data otherwise enter the name\n");
scanf("%s",choice);
}
Nodeptr move=start;
while((move->next)!=NULL)
move=move->next;
move->next=start;//Make the list circular by making the end point to start
move=start;
int count;//takes the count after which the soldier is removed
char begin[20];//stores name of soldier to begin with
printf("Enter the count after which deletion is to happen and Enter the name of starting soldier\n");
scanf("%d%s",&count,begin);
int ctr=0;
while(strcmp(move->name,begin)!=0)
move=move->next;//move to the soldier which user told to start with
int pass=1;
while(move->next!=move)//when move->next==move than we have only one soldier left
{
ctr++;
if(ctr==count-1)//delete next node
{
    Nodeptr temp=move->next;
    move->next=temp->next;
    printf("The soldier who eliminated in pass number %d is %s\n",pass,temp->name);
    free(temp);//free space
    ctr=0;
    pass++;
}
move=move->next;
}
printf("The soldier who escapes is %s\n",move->name);
getch();
}
/*A sample run of the program works as:-
        Josephus Problem
Enter the name
A
Enter end to stop entering data otherwise enter the name
B
Enter end to stop entering data otherwise enter the name
C
Enter end to stop entering data otherwise enter the name
D
Enter end to stop entering data otherwise enter the name
E
Enter end to stop entering data otherwise enter the name
end
Enter the count after which deletion is to happen and Enter the name of starting soldier
3
A
The soldier who eliminated in pass number 1 is C
The soldier who eliminated in pass number 2 is A
The soldier who eliminated in pass number 3 is E
The soldier who eliminated in pass number 4 is B
The soldier who escapes is D
*/









 















C Program to Reverse A String

C Program: Building an Expression Evaluator
C Program: Check for Armstrong Numbers
C Program: Check whether a string is a Palindrome or not
C Program: Common Operations on Sets - Union, Intersection, Difference, Cardinal Product
C Program: Computing exp(x), sin(x), cos(x), tan(x) using series expansions
C Program: Computing the Area of a Circle
C Program: Computing the Upper Triangular Matrix and Lower Triangular Matrix
C Program: Demonstrating File Handling Functions
C Program: Demonstrating Operations on Matrices - Addition, Subtraction, Multiplication, Inversion, Finding Determinants
C Program: Demonstrating the use of Bitwise Operators
C Program: Displaying a Histogram of word frequencies (unigram)
C Program: Distance Vector Routing Algorithm using Bellman Ford's Algorithm
C Program: Numerical Computing - The Gaussian Elimination Method
C Program: Numerical Computing - Implementing the Newton Raphson Method
C Program: Numerical Computing - the Bisection Method
C Program: Numerical Computing - The Gaussian Elimination Technique from Linear Algebra
C Program: Numerical Computing - the Jacobi Method
C Program: Printing the Pascal Triangle
C Program: Reversing the order of words in a sentence
C Program: Solving Simultaneous Equations in Two Variables
C Program: Source Code for computing the GCD(HFC) of two numbers
C Program: Source Code for Solving Quadratic Equations
C Program: Source code to solve the Josephus Problem
C Program: Sudoku Solver
C Program: The Usage of Command Line Arguments
C Program: Using the Sieve of Eratosthenes to print Prime Numbers