[Solved] CSCE 121 Lab 6-Recursion: Lucas numbers

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 L_i, his series begins thus: L₀=2, L₁=1, L₂=3, L₃=4, L₄=7, …The definition for a general element in the series is recursive, as follows:

1. Write a recursive function that computes the n^th element, L_n.
2. Now call your previous function to compute the value of L_n/L_n-1. Increase the value of n until this ratio changes by a factor less than 10^-4.

iii. If you try to compute L₅₀ 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?

1. 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 ‘
’, 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	Start by writing some code that will print the file sentence by sentence whilst respecting the constraint that you can’t store the whole thing in a single char[].
? HINT	Write a function that processes just one character. Also, this problem is a case where using global variables might be a good idea.

? TESTING IDEAS

Remember to test your code on an empty file, and also one with just a single punctuation mark. Finally, consider a file in which the final sentence in the file is missing its ending punctuation.

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?