0

From description:

The $n^\text{th}$ line of output is the relative lengths of the marks on a ruler subdivided in intervals of $({}^1/_2)^{n}$ of an inch. For example, the fourth line of the output gives the relative lengths of the marks that indicate intervals of one-sixteenth of an inch on a ruler."

So for the first line, the program prints "1" and for the second line it prints "1 2 1".

This is where I am lost, how does "1 2 1" represent subdivision of fourths when there are only 3 numbers. Why is it that to print the next line the recursive relation is $f(n) = f(n - 1) + n + f(n - 1)$ where $f(n)$ prints a string of numbers, and $f(1) = 1$?

shardulc
  • 4,562
Mutating Algorithm
  • 263

1 Answers1

4

I think the text is describing a ruler like this (from Clipart Kid):

enter image description here

The 1/16 mark, not labeled but pictured to the left of the 1/8 mark, is of length 1. Then the lengths of all the marks (ignoring the 0 and 1) are $$1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1$$ (Admittedly the 1/2 mark is not really 8 times as long as the 1/16 mark, but you get the idea.)

This is your $f(n)$. In my opinion, the text is not very clear in the description.

shardulc
  • 4,562
  • Yes, this makes a lot more sense in that the one inch mark is already given and we just have to produce the marks for everything before the 1 inch. – Mutating Algorithm Dec 26 '16 at 00:55