*Python Question* 1.Lagged Fibonacci Digits The Fibonacci sequence is a sequence

Question

*Python Question*

1.Lagged Fibonacci Digits

The Fibonacci sequence is a sequence of integer values, beginning with 0 and 1, in which each new term is equal to the sum of the two previous terms. For example, the first few terms of the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, etc.

This type of behavior can be used to develop a type of pseudorandom number generator called an Additive Lagged Fibonacci Generator (used in, among other things, the Soviet VIC cipher used in the 1950s). The generation process described below is often called "chain addition". In this case, each number or term in the sequence is a single digit. To generate the next term in the sequence, we add two adjacent digits from the sequence, modulo 10, and append the new digit to the end of the sequence. We always begin with the first two digits of the starting number.

For example, consider the starting number 729167. The first two digits are 7 and 2. 7 + 2 modulo 10 is 9, so we append 9 to the end of the number to get 7291679. The next two digits to be examined are the second and third digits. 2 + 9 is 11. 11 modulo 10 is 1, so we append 1 to the end of the sequence to get 72916791. The next two digits to be examined are the third and fourth digits. 9 + 1 is 10, which is 0 modulo 10. We append 0 to the existing sequence to get 729167910. Subsequent terms (digits) in the sequence follow the same general pattern.

Complete the alfg() function, which takes two arguments: a string containing an initial integer sequence of at least 2 digits, and a positive integer representing the number of rounds of chained addition to perform. The function returns a string: either the last five digits of the sequence after all of the requested rounds are complete, or the entire sequence if it has fewer than five terms (digits).

Hint: Use Python's list() command to break a string of digits into a list where each element is a single digit from the string (albeit still as a string rather than an integer). For example, list('12345') will return the list ['1', '2', '3', '4', '5'].

2. Constructing A Simple Text Index

Search engines like Google and Bing work by consulting an index of words found in each of the Web pages that they examine. This index identifies the document(s) that contain a particular word (like "dog" or "cat"), as well as the word's position(s) in those documents. For example, Google might record that the Web page "pets.html" contains the word "cat" at positions 22, 35, 100, and 209. Later, when a user searches for the word "cat", Google will return "pets.html" as a hit for that search term.

a.Start by completing the buildIndex() function. This function takes one argument: a string representing the text to be indexed. buildIndex() creates an empty dictionary to hold the final result. In this dictionary, each unique word becomes a key; its value is a list of integer positions where that word appears in the original text.

For each word in the source text, if the word is already present as a key in the dictionary, then the loop adds the current position/index of the word to the dictionary under that key. If the word is not already found in the dictionary, it is added as a new entry. Once the entire source text has been processed, buildIndex() returns the dictionary of word locations. Be sure to convert the input string to all lowercase and use strip() to remove any punctuation before you begin to process it!

Hint 1: Use the list operation append() to easily add a new value to the end of a list. For example, myList.append(5) would add the value 5 to the end of myList.

Hint 2: To create a new list from a single variable, just add square brackets around the variable's name:

anotherList = [ myVariable ]

Pseudocode:

procedure buildIndex (text)

indexempty dictionary

wordsresult of applying split() to text

position0

while position < length of words:

nextWordposition'th element of words

if nextWord is in the set of keys for index:

reflist of values associated with nextWord

Add position to the end of ref

Assign ref to the dictionary using nextWord as the key

else:

Assign a list containing position to the dictionary using nextWord as the key

return the new dictionary (index)

b. Next, complete the displayIndex() function, which takes a dictionary as its (only) argument. displayIndex() retrieves the list of keys from the dictionary that was passed in, sorts that list alphabetically, and then prints out each key, along with its associated value (a list of integer positions) on a separate line. This function does not return any value; it only prints the contents of its argument as a side effect.

Hint:

To sort a list, use the built-in Python function called sorted():

s = sorted(myList)

Sample Execution

(program output is initalics, and user input is in boldface)

Here is the required program skeleton:

import string

def alfg(sequence, rounds):
    return "None" # CHANGE OR REPLACE THIS STATEMENT

def buildIndex(text):
    index = {}

    # ADD YOUR CODE HERE

    return index

def displayIndex(myIndex):
    print() # print a blank line
    print("Index Contents:")
    # ADD YOUR CODE HERE

# DO NOT modify or remove the code below! We will use it for testing.

if __name__ == "__main__":
    # Problem 1: Lagged Fibonacci Digits
    seed = input("Enter the starting number: ")
    rds = int(input("Enter the number of rounds: "))

    print("Calling alfg("+seed+", "+str(rds)+") returns " + alfg(seed,rds))
    print()

    # Problem 2: Constructing A Simple Text Index
    data = input("Please enter some text to index: ")
    wordIndex = buildIndex(data)

    print("Results of buildIndex():", wordIndex) # Used to test your code from step 2a.

    displayIndex(wordIndex) # Used to test your code from step 2b

Explanation / Answer

nterms = 10

# uncomment to take input from the user
#nterms = int(input("How many terms? "))

# first two terms
n1 = 0
n2 = 1
count = 0

# check if the number of terms is valid
if nterms <= 0:
   print("Please enter a positive integer")
elif nterms == 1:
   print("Fibonacci sequence upto",nterms,":")
   print(n1)
else:
   print("Fibonacci sequence upto",nterms,":")
   while count < nterms:
       print(n1,end=' , ')
       nth = n1 + n2
       # update values
       n1 = n2
       n2 = nth
       count += 1

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.