How to resolve the algorithm Josephus problem step by step in the MATLAB programming language

Published on 12 May 2024 09:40 PM
#Matlab

How to resolve the algorithm Josephus problem step by step in the MATLAB programming language

Table of Contents

Problem Statement

Josephus problem is a math puzzle with a grim description:

n

{\displaystyle n}

prisoners are standing on a circle, sequentially numbered from

0

{\displaystyle 0}

to

n − 1

{\displaystyle n-1}

.
An executioner walks along the circle, starting from prisoner

0

{\displaystyle 0}

, removing every

k

{\displaystyle k}

-th prisoner and killing him.
As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed. > For example, if there are

n

5

{\displaystyle n=5}

prisoners and

k

2

{\displaystyle k=2}

, the order the prisoners are killed in (let's call it the "killing sequence") will be 1, 3, 0, and 4, and the survivor will be #2.

Given any

n , k

0

{\displaystyle n,k>0}

,   find out which prisoner will be the final survivor.
In one such incident, there were 41 prisoners and every 3rd prisoner was being killed   (

k

3

{\displaystyle k=3}

).
Among them was a clever chap name Josephus who worked out the problem, stood at the surviving position, and lived on to tell the tale. Which number was he?

The captors may be especially kind and let

m

{\displaystyle m}

survivors free, and Josephus might just have

m − 1

{\displaystyle m-1}

friends to save.
Provide a way to calculate which prisoner is at any given position on the killing sequence.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Josephus problem step by step in the MATLAB programming language

Source code in the matlab programming language

function [indAlive] = josephus(numPeople,count)
% Josephus: Given a circle of numPeople individuals, with a count of count,
% find the index (starting at 1) of the survivor [see Josephus Problem]

%% Definitions:
%   0 = dead position
%   1 = alive position
%   index = # of person

%% Setting up
arrPeople = ones(1, numPeople);
currInd = 0;

%% Counting
while (length(arrPeople(arrPeople == 1)) > 1)     % While more than 1 person is alive
    counter = 0;
    while counter ~= count                       % Counting until we hit the count
        currInd = currInd + 1;                  % Move to the next person
        
        if currInd > numPeople                  % If overflow, wraparound
            currInd = currInd - numPeople;
        end
        
        if arrPeople(currInd)                   % If the current person is alive
            counter = counter + 1;                % Add 1 person to the count
            %fprintf("Index: %d \t| Counter: %d\n", currInd, counter)           % Uncomment to display index and counter location
        end

    end
    
    arrPeople(currInd) = 0;                     % Kill the person we reached
    %fprintf("Killed person %d \n", currInd)                                   % Uncomment to display order of killing
    %disp(arrPeople)                                                           % Uncomment to display current status of people
end

indAlive = find(arrPeople);

end

You may also check:How to resolve the algorithm Numerical integration/Gauss-Legendre Quadrature step by step in the Java programming language
You may also check:How to resolve the algorithm Probabilistic choice step by step in the Rust programming language
You may also check:How to resolve the algorithm Möbius function step by step in the jq programming language
You may also check:How to resolve the algorithm Averages/Mode step by step in the Erlang programming language
You may also check:How to resolve the algorithm Anagrams/Deranged anagrams step by step in the Sidef programming language