How to resolve the algorithm Minimal steps down to 1 step by step in the XPL0 programming language

Published on 12 May 2024 09:40 PM
#Xpl0

How to resolve the algorithm Minimal steps down to 1 step by step in the XPL0 programming language

Table of Contents

Problem Statement

Given: The goal is find the minimum number of steps necessary to reduce N down to one. At any step, the number may be:

There may be many ways to reduce the initial N down to 1. Your program needs to:

No divisors, D. a single subtractor of 1. Single divisor of 2; single subtractor of 1: Divisors 2 and 3; subtractor 1: Using the possible divisors D, of 2 and 3; together with a possible subtractor S, of 1: Using the possible divisors D, of 2 and 3; together with a possible subtractor S, of 2:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Minimal steps down to 1 step by step in the XPL0 programming language

Source code in the xpl0 programming language

int     MinSteps,       \minimal number of steps to get to 1
        Subtractor;     \1 or 2
char    Ns(20000), Ops(20000), MinNs(20000), MinOps(20000);

proc Reduce(N, Step);   \Reduce N to 1, recording minimum steps
int  N, Step, I;
[if N = 1 then
    [if Step < MinSteps then
        [for I:= 0 to Step-1 do
            [MinOps(I):= Ops(I);
            MinNs(I):= Ns(I);
            ];
        MinSteps:= Step;
        ];
    ];
if Step >= MinSteps then return;        \don't search further
if rem(N/3) = 0 then
        [Ops(Step):= 3;  Ns(Step):= N/3;  Reduce(N/3, Step+1)];
if rem(N/2) = 0 then
        [Ops(Step):= 2;  Ns(Step):= N/2;  Reduce(N/2, Step+1)];
Ops(Step):= -Subtractor;  Ns(Step):= N-Subtractor;  Reduce(N-Subtractor, Step+1);
]; \Reduce

proc ShowSteps(N);      \Show minimal steps and how N steps to 1
int N, I;
[MinSteps:= $7FFF_FFFF;
Reduce(N, 0);
Text(0, "N = ");  IntOut(0, N);
Text(0, " takes ");  IntOut(0, MinSteps);  Text(0, " steps: N ");
for I:= 0 to MinSteps-1 do
        [Text(0, if extend(MinOps(I)) < 0 then "-" else "/");
        IntOut(0, abs(extend(MinOps(I))));
        Text(0, "=>");  IntOut(0, MinNs(I));  Text(0, " ");
        ];
CrLf(0);
]; \ShowSteps

proc ShowCount(Range);  \Show count of maximum minimal steps and their Ns
int  Range;
int  N, MaxSteps;
[MaxSteps:= 0;          \find maximum number of minimum steps
for N:= 1 to Range do
        [MinSteps:= $7FFF_FFFF;
        Reduce(N, 0);
        if MinSteps > MaxSteps then
                MaxSteps:= MinSteps;
        ];
Text(0, "Maximum steps: ");  IntOut(0, MaxSteps);  Text(0, " for N = ");
for N:= 1 to Range do   \show numbers (Ns) for Maximum steps
        [MinSteps:= $7FFF_FFFF;
        Reduce(N, 0);
        if MinSteps = MaxSteps then
                [IntOut(0, N);  Text(0, " ");
                ];
        ];
CrLf(0);
]; \ShowCount

int N;
[Subtractor:= 1;                \1.
for N:= 1 to 10 do ShowSteps(N);
ShowCount(2000);                \2.
ShowCount(20_000);              \2a.
Subtractor:= 2;                 \3.
for N:= 1 to 10 do ShowSteps(N);
ShowCount(2000);                \4.
ShowCount(20_000);              \4a.
]

You may also check:How to resolve the algorithm Loops/Do-while step by step in the dc programming language
You may also check:How to resolve the algorithm Mutex step by step in the Go programming language
You may also check:How to resolve the algorithm Summarize and say sequence step by step in the Clojure programming language
You may also check:How to resolve the algorithm Modular arithmetic step by step in the Go programming language
You may also check:How to resolve the algorithm Earliest difference between prime gaps step by step in the Rust programming language