Python代写：CS116 Accumulative Recursion

发表于   |   分类于

Introduction

这次需要代写的作业全部需要使用递归，最后一个问属于烧脑型的，五重递归。

Assignment Guidelines

  • This assignment covers material in Module 05.
  • Questions 1 and 2 must use accumulative recursion. Questions 3 and 4 can use any form of recursion.
  • Submission details:
    • Solutions to these questions must be placed in files a05q1.py, a05q2.py, a05q3.py, and
      a05q4.py, respectively, and must be completed using Python 3.
    • Download the interface file from the course Web page to ensure that all function names are spelled correctly and each function has the correct number and order of parameters.
    • All solutions must be submitted to MarkUs. No solutions will be accepted through email, even if you are having issues with MarkUs.
    • Verify using MarkUs and your basic test results that your files were properly submitted and are readable on MarkUs.
    • For full style marks, your program must follow the Python section of the CS116 Style Guide.
    • Be sure to review the Academic Integrity policy on the Assignments page
  • Download the testing module from the course web page. Include import check in each solution file.
    • When a function produces a floating point value, you must use check.within for your testing.
    • Unless told otherwise, you may use a tolerance of 0.00001 in your tests.
    • Test data for all questions will always meet the stated assumptions for consumed values.
  • Restrictions:
    • Do not import any modules other than math and check.
    • Do not use Python constructs from later modules (e.g. loops). Do not use any other Python functions not discussed in class or explicitly allowed elsewhere. See the allowable functions post on Piazza. You are always allowed to define your own helper functions, as long as they meet the assignment restrictions.
    • While you may use global constants in your solutions, do not use global variables for anything other than testing.
    • Read each question carefully for additional restrictions.
    • The solutions you submit must be entirely your own work. Do not look up either full or partial solutions on the Internet or in printed sources.

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,

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,

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

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:

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.)