Printing Pedigrees

Problem

  • You’ve been hired by Ancestry.com!
  • Many customers have been wanting a blank pedigree chart to take to family reunions to fill out as a family
  • Write a program to print 5 blank generations, with each blank labeled with the generation number
  • Don’t worry about drawing branch lines
  • Should look like this (but with one more generation):
			4. _______
		3. _______
			4. _______
	2. _______
			4. _______
		3. _______
			4. _______
1. _______
			4. _______
		3. _______
			4. _______
	2. _______
			4. _______
		3. _______
			4. _______
  • Don't worry about indentation initially, just get the right numbers on the right lines.

Part 2

  • How would you indent based on the function parameter?
  • Add a parameter explicitly for the label
  • How do I determine my parent's label from my label?

Part 3

  • Real pedigrees don’t label by generation, but by a genealogical numbering system called Ahnentafel numbers (the number means more than you might think).
  • “a father's number will be twice that individual's number, or a mother's will be twice plus one”
  • For example:
			8. _______
		4. _______
			9. _______
	2. _______
			10. _______
		5. _______
			11. _______
1. _______
			12. _______
		6. _______
			13. _______
	3. _______
			14. _______
		7. _______
			15. _______
  • How do we adapt to do this?
  • The code below demonstrates the result of all three parts.

Problem-Solving

  • Pretend that “someone else” has solved printing a tree for a mother/father (e.g., generation x-1)
  • Figure out how printing a tree for mother/father can be used to print a tree for me.
  • Decide the base case: what should happen for the last generation printed?

Solution

/*
Test cases:
Input: Print only one generation
Expected Output: a tree with just place for me
 
Input: Print a tree with 0 generations
Expected Output: no tree
 
Input: Print two generations
Expected Output: a tree with me and my parents
 
Input: Print three generations
Expected Output: a tree with room for me, my parents, and my grandparents
*/
 
#include <iostream>
 
using namespace std;
 
const int GENERATIONS_TO_PRINT = 5;
const int STARTING_LABEL = 1;
 
/*
	A recursive function to print a blank pedigree for an arbitrary number of generations
	@param generations_left number of generations printed by this function call
	@param label label to be printed for the root of this blank tree
*/
void print_blank_tree(int generations_left, int label)
{
	// base case
	if (generations_left == 0)
	{
		return;
	}
 
	// print father's tree (assume someone has figured out how to do that)
	print_blank_tree(generations_left-1, label * 2);
 
	// print myself indented based on how many generations have been printed
	for (int tab = 0; tab < GENERATIONS_TO_PRINT - generations_left; tab++)
	{
		cout << "\t";
	}
	cout << label << ". _______________________" << endl;
 
	// print mother's tree (assume someone has figured out how to do that)
	print_blank_tree(generations_left - 1, label * 2 + 1);
}
 
int main()
{
	// Invoke the function, assuming someone else has solved the problem
	print_blank_tree(GENERATIONS_TO_PRINT, STARTING_LABEL);
 
	system("pause");
	return 0;
}
cs-142/printing-pedigrees.txt · Last modified: 2015/05/28 19:22 by cs142ta
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0