Python代写:CS116-Accumulative-Recursion

request Guidelines

This request covers material in Module 05.

Questions 1 and 2 must use accumulative recursion. Questions 3 and 4 can use any form of recursion.

Q1

In the game Racko, players attempt to build a strictly increasing sequence of cards (in which a number is less than the number that comes after it). At the end of the game, five points are awarded for each number in the increasing sequence that starts with the first card in the list. Note that any further increasing sequences in the list do not earn any points. For example, there are 20 points awarded for the values 5,10,12,16,15,43, because it begins with the strictly increasing sequence 5,10,12,16.
Use accumulative recursion to complete the Python function racko_points, that consumes seq, a list of distinct integers between 1 and 60, inclusive, and produces the score for seq.
For example,

1
2
3
racko_points([]) => 0
racko_points([9,2,20,40,60]) => 5
racko_points([5,10,48,2,9,17,40,60]) => 15

Note that you cannot reorder seq. Determine the number of earned points for the seq in the order given.

Q2

Consider Xtreme Racko, a variation of Racko® (as described in Question 1) that allows a player to score points for each number in their longest increasing sequence, regardless of where that sequence begins. Use accumulative recursion to complete the Python function xtreme_racko_points, that consumes seq, a list of distinct numbers between 1 and 60, inclusive, and produces the score for seq.
For example,

1
2
3
4
xtreme_racko_points([]) => 0
xtreme_racko_points([5,2,22,40,60]) => 20
xtreme_racko_points([5,50,46,2,9,17,1,60]) => 15
xtreme_racko_points([60,50,40,30]) => 5

Hint: You may find it helpful to use more than one accumulator for this question.

Q3

Write a Python function histogram that consumes marks, a list of integer marks between 0 and 100,

inclusive. The function produces None, and prints a histogram for marks. The histogram consists of one row for each distinct mark. The i th row has the form:

vvv: row where vvv is the i th smallest value (right justified over 3 places) and row is a string containing k copies of the string ‘X’, where k is the number of times vvv occurs in marks. That is, the first row contains information about the smallest value in marks, the second row contains information about the second smalles distinct value in marks, and so on. The consumed list may not be mutated. If marks is empty, nothing is printed.

For example, calling histogram([77,78,77,90,0,88,84,83,88,88,77,76,92,100,100]) prints

1
2
3
4
5
6
7
8
9
10
0: X
76: X
77: XXX
78: X
83: X
84: X
88: XXX
90: X
92: X
100: XX

The mark before the ‘:’ can be right justified using the rjust string method. There must be exactly one space after the colon, and no spaces after the string of ‘X’ values. No blank lines are printed.

Q4

A palindrome is a string that is the same forwards and backwards. For example, “madam” and “hannah” are palindromes, but “abcc b a” and “abcdba” are not.
Write a Python function generate_palindromes that consumes a natural number n and produces a list (in alphabetical order) of all the palindromes of length n consisting of a combination of the characters ‘X’ and ‘Y’. For example:

1
2
3
4
generate_palindromes(0) => ['']
generate_palindromes(1) => ['X', 'Y']
generate_palindromes(4) => ['XXXX', 'XYYX', 'YXXY', 'YYYY']
generate_palindromes(5) => ["XXXXX","XXYXX","XYXYX","XYYYX","YXXXY","YXYXY","YYXYY","YYYYY"]

Notes:

  • The order of the produced list is important. You may use sort or sorted, as appropropriate.
  • Think carefully about this problem before you start coding it. There is a short, somewhat elegant solution, but you must really think about what subproblem solution would assist you with finding the set of palindromes you need. (Hint: the solution of n-1 is unlikely to be helpful when solving n.)