CSCE 121: Introduction to Program Design and Concepts
Lab Exercise Six
Objective
This lab will give you some practice with recursion (in the first question) and also processing file input (in the second one).
How far must I get?
There are fewer questions this week to make it easier for everyone to finish. Please try your best to do so!
Recursion: Lucas numbers
No doubt you'll have heard of the Fibonacci series.
François Lucas
was the person who made them famous and a closely related series of
numbers were named for him. With the elements denoted
Li,
his series begins thus:
L0=2,
L1=1,
L2=3,
L3=4,
L4=7, …
The definition for a general element in the series is recursive, as follows:
i. Write a recursive function that computes the nth element, Ln.
ii. Now call your previous function to compute the value of Ln/Ln-1. Increase the value of n until this ratio changes by a factor less than 10-4.
iii. If you try to compute L50 with your function, you'll probably find that it takes an unreasonably long time to return a result. An important question is: for a particular n, how many times is the function called? Modify your code from the first part, instrumenting it so that it also counts the number of function calls. Can you figure out how to express this count (i.e., the total number of function calls) in terms of n?
iv. Rather than merely calling your recursive function, what is a more efficient way to compute large Lucas numbers?
Sentences of moderate length please!
Some students have said they find my questions too wordy. This question involves writing some code that will help me examine my writing style, by selecting only those sentences that are of moderate length.
Write a program that prints out all the sentences in a text file where:
min ≤ length ≤ max.
Assume that a sentence ends in either a period, question mark, or
exclamation point. Count all the blanks and punctuation in computing
length, with the exception of any spaces separating one sentence
from the next. (All end-of-line characters, i.e. the '\n', should simply be ignored.)
You can also assume that every line in the file has fewer than 200 characters.
However, you can't assume any bound on the length of the sentences
in the file—so you shouldn't try store it all in a single
char array. Nor should you assume any maximum on the
total number of sentences.
Request the filename and also min and max values as inputs from the user.
Ensure that they are positive integers with
min ≤ max < 1000.
|
|
|
|
|
|
Puzzling*
Here's a question to think about:
Is it possible to fill an 8×8 grid with dominoes (2×1 in size) such that no two dominoes form a 2×2 square?
Acknowledgements
The program for outputting sentences of a given length was the original idea of John Dalbey. The puzzle is from Anany Levitin and Maria Levitin, "Algorithmic Puzzles", Oxford University Press, 2011.