Calkin-Wilf sequence: Difference between revisions
Added 3rd algorithm for calculating terms, and put all 3 algorithms into one program.
(Added 3rd algorithm for calculating terms, and put all 3 algorithms into one program.) |
|||
Line 946:
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
{-------------------------------------------------------------------------------
Line 952:
Calculates the Calkin-Wilf sequence up to the specified maximum index,
where the first term 1/1 has index 1.
Command line format is: CWTerms <max_index>
The program demonstrates 3 algorithms for calculating the sequence:
(1) Calculate term[2n] and term[2n + 1] from term[n]
(2) Calculate term[n + 1] from term[n]
(3) Calculate term[n] directly from n, without using other terms
Algorithm 1 is called first, and stores the terms in an array.
Then the program calls Algorithms 2 and 3, and checks that they agree
with Algorithm 1.
-------------------------------------------------------------------------------}
Line 970 ⟶ 971:
var
terms : array of TRational;
max_index
//
procedure CalcTerms_algo_1();
var
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;
end;
// Method to get each term from the preceding term.
//
function CheckTerms_algo_2() : boolean;
var
begin
a := 1;
while (index <= max_index) do begin
if (a <> terms[
temp := a + b - 2*(a mod b);
inc( index)
end;
end;
// Mathod to calcualte each term from its index, without using other terms.
function CheckTerms_algo_3() : boolean;
var
index, a, b, pwr2, idiv2 : integer;
begin
result := true;
for index := 1 to max_index do begin
idiv2 := index div 2;
pwr2 := 1;
while (pwr2 <= idiv2) do pwr2 := pwr2 shl 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;
if (a <> terms[index].Num) or (b <> terms[index].Den) then
result := false;
end;
end;
begin
// Read and validate maximum index
Line 1,060 ⟶ 1,050:
end;
// Calculate
CalcTerms_algo_1();
if not CheckTerms_algo_2() then begin
WriteLn
exit;
end;
if not CheckTerms_algo_3() then begin
WriteLn( 'Algorithm 3 failed');
exit;
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>
|