This program is supposed to output the Calkin-Wilf tree. In other words it\'s su
ID: 3864232 • Letter: T
Question
This program is supposed to output the Calkin-Wilf tree. In other words it's supposed to show the fractions such as 1/1 and then next level is 1/2 and 2/1 ect
Please help with this thanks.
Please do not write it out I have a hard time reading other peoples hand writing please just type it out. thanks
write a c++ program that implements and tests the following two functions related to the Calkin-Wilf enumeration of the positive fractions:
The two functions below are supposed to be used in the c++ program. Please do not just copy the code below it is just used for an example. These two functions need to be in a new program and tested. Please HELP!!!
Fraction cwfrac(int p);
//Returns the fraction in position p in the Calkin-Wilf enumeration.
int cwpos(Fraction f);
//Returns the position of the fraction f in the Calkin-Wilf enumeration.
Here is an example of what I am talking about:
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Fraction
{
int numerator;
int denominator;
};
const int COLS = 10;
const int ROWS = 1024;
void calkin_wilf_tree(int, Fraction [][COLS]);
//Constructs the Calkin-Wilf tree of a given height
//in the specified two-dimensional array.
int main()
{
Fraction cw[ROWS][COLS]; //Two-dimensional array to hold the Calkin-Wilf tree.
int h;
cout << "This program computes and outputs the Calkin-Wilf tree of height h." << endl;
cout << "Enter an integer h between 0 and 9 (a negative value to quit): ";
cin >> h;
while (h >= 0)
{
calkin_wilf_tree(h,cw);
//Output the result as a table with 2^(h + 1) - 1 rows and h + 1 columns.
//The fractions at level k are in column k, 0 <= k <= h;
//a right child is in a row above its parent's row, while
//a left child is in a row below its parent's row.
for (int r = 0; r < pow(2,h + 1) - 1; r++)
{
for (int c = 0; c <= h; c++)
if (cw[r][c].numerator == 0)
{ //Replace any 0s with *.
cout << setw(3) << right << " ";
cout << "*";
cout << setw(3) << left << " ";
}
else
{
cout << setw(3) << right << cw[r][c].numerator;
cout << "/";
cout << setw(3) << left << cw[r][c].denominator;
}
cout << endl;
}
cout << endl << endl;
cout << "Enter the next value of h: ";
cin >> h;
};
system("pause");
return 0;
}
void calkin_wilf_tree(int h, Fraction cw[][COLS])
{
int initial_parent_row; //Row index of the first parent fraction in a given column.
int parent_row; //Row index of the current parent row.
int child_offset; //Used to locate the children of the parent fraction.
//Initialize the array to all 0s.
for (int r = 0; r < pow(2,h + 1) - 1; r++)
for (int c = 0; c <= h; c++)
{
cw[r][c].numerator = 0;
cw[r][c].denominator = 1;
}
//Place the fraction 1/1 - the root - in column 0.
initial_parent_row = pow(2,h) - 1;
cw[initial_parent_row][0].numerator = 1;
cw[initial_parent_row][0].denominator = 1;
child_offset = pow(2,h - 1);
for (int c = 1; c <= h; c++)
{ //Compute the fractions in column c.
parent_row = initial_parent_row;
for (int i = 1; i <= pow(2,c - 1); i++)
{ //Note that there are 2^c fractions in column c.
//Compute the right child.
cw[parent_row - child_offset][c].numerator = cw[parent_row][c - 1].numerator + cw[parent_row][c - 1].denominator;
cw[parent_row - child_offset][c].denominator = cw[parent_row][c - 1].denominator;
//Compute the left child.
cw[parent_row + child_offset][c].numerator = cw[parent_row][c - 1].numerator;
cw[parent_row + child_offset][c].denominator = cw[parent_row][c - 1].numerator + cw[parent_row][c - 1].denominator;
parent_row = parent_row + 4*child_offset;
}
//Initialize parent_row and child_offset for the next column.
initial_parent_row = (initial_parent_row + 1)/2 - 1;
child_offset = child_offset/2;
}
}
Explanation / Answer
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Fraction
{
int numerator;
int denominator;
};
const int COLS = 10;
const int ROWS = 1024;
void calkin_wilf_tree(int, Fraction [][COLS]);
//Constructs the Calkin-Wilf tree of a given height
//in the specified two-dimensional array.
int main()
{
Fraction cw[ROWS][COLS]; //Two-dimensional array to hold the Calkin-Wilf tree.
int h;
cout << "This program computes and outputs the Calkin-Wilf tree of height h." << endl;
cout << "Enter an integer h between 0 and 9 (a negative value to quit): ";
cin >> h;
while (h >= 0)
{
calkin_wilf_tree(h,cw);
//Output the result as a table with 2^(h + 1) - 1 rows and h + 1 columns.
//The fractions at level k are in column k, 0 <= k <= h;
//a right child is in a row above its parent's row, while
//a left child is in a row below its parent's row.
for (int r = 0; r < pow(2,h + 1) - 1; r++)
{
for (int c = 0; c <= h; c++)
if (cw[r][c].numerator == 0)
{ //Replace any 0s with *.
cout << setw(3) << right << " ";
cout << "*";
cout << setw(3) << left << " ";
}
else
{
cout << setw(3) << right << cw[r][c].numerator;
cout << "/";
cout << setw(3) << left << cw[r][c].denominator;
}
cout << endl;
}
cout << endl << endl;
cout << "Enter the next value of h: ";
cin >> h;
};
system("pause");
return 0;
}
void calkin_wilf_tree(int h, Fraction cw[][COLS])
{
int initial_parent_row; //Row index of the first parent fraction in a given column.
int parent_row; //Row index of the current parent row.
int child_offset; //Used to locate the children of the parent fraction.
//Initialize the array to all 0s.
for (int r = 0; r < pow(2,h + 1) - 1; r++)
for (int c = 0; c <= h; c++)
{
cw[r][c].numerator = 0;
cw[r][c].denominator = 1;
}
//Place the fraction 1/1 - the root - in column 0.
initial_parent_row = pow(2,h) - 1;
cw[initial_parent_row][0].numerator = 1;
cw[initial_parent_row][0].denominator = 1;
child_offset = pow(2,h - 1);
for (int c = 1; c <= h; c++)
{ //Compute the fractions in column c.
parent_row = initial_parent_row;
for (int i = 1; i <= pow(2,c - 1); i++)
{ //Note that there are 2^c fractions in column c.
//Compute the right child.
cw[parent_row - child_offset][c].numerator = cw[parent_row][c - 1].numerator + cw[parent_row][c - 1].denominator;
cw[parent_row - child_offset][c].denominator = cw[parent_row][c - 1].denominator;
//Compute the left child.
cw[parent_row + child_offset][c].numerator = cw[parent_row][c - 1].numerator;
cw[parent_row + child_offset][c].denominator = cw[parent_row][c - 1].numerator + cw[parent_row][c - 1].denominator;
parent_row = parent_row + 4*child_offset;
}
//Initialize parent_row and child_offset for the next column.
initial_parent_row = (initial_parent_row + 1)/2 - 1;
child_offset = child_offset/2;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.