Calkin-Wilf sequence: Difference between revisions
Added solution for Pascal.
(Added Sidef) |
(Added solution for Pascal.) |
||
Line 812:
The element 83116/51639 is at position 123456789 in the sequence.</pre>
=={{header|Pascal}}==
These programs were written in Free Pascal, using the Lazarus IDE and the Free Pascal compiler version 3.2.0. They are based on the Wikipedia article "Calkin-Wilf tree", rather than the algorithms in the task description.
<lang pascal>
program CWTerms1;
{-------------------------------------------------------------------------------
FreePascal command-line program.
Calculates the Calkin-Wilf sequence up to the specified maximum index,
where the first term 1/1 has index 1.
Command line format is
CWTerms1 <max_index>
e.g. for the Rosetta Code example
CWTerms1 20
This program stores the terms in an array. Each term after the first
is calculated from an earlier term in the array.
Cf. the alternative method in program CWTerms2.
-------------------------------------------------------------------------------}
uses SysUtils;
type TRational = record
Num, Den : integer;
end;
var
terms : array of TRational;
max_index, j, k : integer;
begin
// Read and validate maximum index
max_index := SysUtils.StrToIntDef( paramStr(1), -1); // -1 if not an integer
if (max_index <= 0) then begin
WriteLn( 'Maximum index must be a positive integer');
exit;
end;
// Calculate the array of terms.
// A dynamic array such as "terms" has zero-based indices.
// For convenience, we use indices [1..max_index] and ignore index [0].
SetLength( terms, max_index + 1);
j := 1; // index to earlier term, from which current term is calculated
k := 1; // index to current term
terms[1].Num := 1;
terms[1].Den := 1;
while (k < max_index) do begin
inc(k);
if (k and 1) = 0 then begin // or could write "if not Odd(k)"
terms[k].Num := terms[j].Num;
terms[k].Den := terms[j].Num + terms[j].Den;
end
else begin
terms[k].Num := terms[j].Num + terms[j].Den;
terms[k].Den := terms[j].Den;
inc(j);
end;
end;
// Display the terms
for k := 1 to max_index do
with terms[k] do
WriteLn( SysUtils.Format( '%8d: %d/%d', [k, Num, Den]));
end.
</lang>
{{out}}
Same as next program
<lang pascal>
program CWTerms2;
{-------------------------------------------------------------------------------
FreePascal command-line program.
Calculates the Calkin-Wilf sequence up to the specified maximum index,
where the first term 1/1 has index 1.
Command line format is
CWTerms2 <max_index>
e.g. for the Rosetta Code example
CWTerms2 20
This program calculates each term directly from its index,
without making use of previously calculated terms.
Cf. the alternative method in program CWTerms1.
-------------------------------------------------------------------------------}
uses SysUtils;
// Subroutine to calculate the term at the passed-in index.
procedure CalculateTerm( index : integer; out num, den : integer);
var
a, b, pwr2, idiv2 : integer;
begin
idiv2 := index div 2;
pwr2 := 1;
while (pwr2 <= idiv2) do pwr2 := pwr2 shl 1;
a := 1;
b := 1;
while (pwr2 > 1) do begin
pwr2 := pwr2 shr 1;
if (pwr2 and index) = 0 then
inc( b, a)
else
inc( a, b);
end;
num := a;
den := b;
end;
// Main routine
var
max_index : integer;
k, num, den : integer;
begin
// Read and validate maximum index
max_index := SysUtils.StrToIntDef( paramStr(1), -1); // -1 if not an integer
if (max_index <= 0) then begin
WriteLn( 'Maximum index must be a positive integer');
exit;
end;
// Calculate and display the terms individually
for k := 1 to max_index do begin
CalculateTerm( k, {out} num, den);
WriteLn( SysUtils.Format( '%8d: %d/%d', [k, num, den]));
end;
end.
</lang>
{{out}}
<pre>
1: 1/1
2: 1/2
3: 2/1
4: 1/3
5: 3/2
6: 2/3
7: 3/1
8: 1/4
9: 4/3
10: 3/5
11: 5/2
12: 2/5
13: 5/3
14: 3/4
15: 4/1
16: 1/5
17: 5/4
18: 4/7
19: 7/3
20: 3/8
</pre>
<lang pascal>
program CWIndex;
{-------------------------------------------------------------------------------
FreePascal command-line program.
Calculates index of a rational number in the Calkin-Wilf sequence,
where the first term 1/1 has index 1.
Command line format is
CWIndex <numerator> <denominator>
e.g. for the Rosetta Code example
CWIndex 83116 51639
-------------------------------------------------------------------------------}
uses SysUtils;
var
num, den : integer;
a, b : integer;
pwr2, index : qword; // 64-bit unsiged
begin
// Read and validate input.
num := SysUtils.StrToIntDef( paramStr(1), -1); // return -1 if not an integer
den := SysUtils.StrToIntDef( paramStr(2), -1);
if (num <= 0) or (den <= 0) then begin
WriteLn( 'Numerator and denominator must be positive integers');
exit;
end;
// Input OK, calculate and display index of num/den
// The index may overflow 64 bits, so turn on overflow detection
{$Q+}
a := num;
b := den;
pwr2 := 1;
index := 0;
try
while (a <> b) do begin
if (a < b) then
dec( b, a)
else begin
dec( a, b);
inc( index, pwr2);
end;
pwr2 := 2*pwr2;
end;
inc( index, pwr2);
WriteLn( SysUtils.Format( 'Index of %d/%d is %u', [num, den, index]));
except
WriteLn( 'Index is too large for 64 bits');
end;
end.
</lang>
{{out}}
<pre>
Index of 83116/51639 is 123456789
</pre>
=={{header|Perl}}==
| |||