This lab will give you some practice with recursion (in the first question) and also processing file input (in the second one).
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.
?
HINT
?
HINT
?
TESTING IDEAS
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?
