How to resolve the algorithm Boustrophedon transform step by step in the ALGOL 68 programming language
How to resolve the algorithm Boustrophedon transform step by step in the ALGOL 68 programming language
Table of Contents
Problem Statement
A boustrophedon transform is a procedure which maps one sequence to another using a series of integer additions. Generally speaking, given a sequence:
(
a
0
,
a
1
,
a
2
, … )
{\displaystyle (a_{0},a_{1},a_{2},\ldots )}
, the boustrophedon transform yields another sequence:
(
b
0
,
b
1
,
b
2
, … )
{\displaystyle (b_{0},b_{1},b_{2},\ldots )}
, where
b
0
{\displaystyle b_{0}}
is likely defined equivalent to
a
0
{\displaystyle a_{0}}
. There are a few different ways to effect the transform. You may construct a boustrophedon triangle and read off the edge values, or, may use the recurrence relationship: The transformed sequence is defined by
b
n
=
T
n , n
{\displaystyle b_{n}=T_{n,n}}
(for
T
2 , 2
{\displaystyle T_{2,2}}
and greater indices). You are free to use a method most convenient for your language. If the boustrophedon transform is provided by a built-in, or easily and freely available library, it is acceptable to use that (with a pointer to where it may be obtained).
If your language supports big integers, show the first and last 20 digits, and the digit count of the 1000th element of each sequence.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Boustrophedon transform step by step in the ALGOL 68 programming language
Source code in the algol programming language
BEGIN # apply a Boustrophedon Transform to a few sequences #
# returns the sequence generated by transforming s #
PROC boustrophedon transform = ( []LONG INT s )[]LONG INT:
BEGIN
[]LONG INT a = s[ AT 0 ]; # a is s with lower bound revised to 0 #
[ 0 : UPB a, 0 : UPB a ]LONG INT t;
t[ 0, 0 ] := a[ 0 ];
FOR k TO UPB a DO
t[ k, 0 ] := a[ k ];
FOR n TO k DO
t[ k, n ] := t[ k, n - 1 ] + t[ k - 1, k - n ]
OD
OD;
[ 0 : UPB a ]LONG INT b;
FOR n FROM 0 TO UPB b DO b[ n ] := t[ n, n ] OD;
b
END # boustrophedon transform # ;
# prints the transformed sequence generated from a #
PROC print transform = ( STRING name, []LONG INT a )VOID:
BEGIN
[]LONG INT b = boustrophedon transform( a );
print( ( name, " generates:", newline ) );
FOR i FROM LWB b TO UPB b DO print( ( " ", whole( b[ i ], 0 ) ) ) OD;
print( ( newline ) )
END # print transform # ;
BEGIN # test cases #
print transform( "1, 0, 0, 0, ..."
, []LONG INT( 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 )
);
print transform( "1, 1, 1, 1, ..."
, []LONG INT( 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 )
);
print transform( "1, -1, 1, -1, ..."
, []LONG INT( 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1 )
);
print transform( "primes"
, []LONG INT( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 )
);
print transform( "fibnonacci numbers"
, []LONG INT( 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 )
);
[ 0 : 14 ]LONG INT factorial;
factorial[ 0 ] := 1;
FOR i TO UPB factorial DO factorial[ i ] := i * factorial[ i - 1 ] OD;
print transform( "factorial numbers", factorial )
END
END
You may also check:How to resolve the algorithm Parsing/Shunting-yard algorithm step by step in the zkl programming language
You may also check:How to resolve the algorithm Queue/Definition step by step in the Prolog programming language
You may also check:How to resolve the algorithm Quickselect algorithm step by step in the Raku programming language
You may also check:How to resolve the algorithm Menu step by step in the PHP programming language
You may also check:How to resolve the algorithm Fibonacci sequence step by step in the Mirah programming language