完成Python基础算法和数据结构练习。
Kempner series
def kempner(n):
—|—
As we have learned in various math courses, the n:th harmonic number equals to
the sum of the reciprocals of the first n positive integers, that is, Hn = 1/1
- 1/2 + 1/3 +… + 1/ n. As n approaches infinity, so does the harmonic number H
n without limit, although with mere logarithmic order of growth. It is not
even necessary to include all positive integers to this series to make it
diverge without bound, but various infinite subsets of positive integers such
as the prime numbers will still make this sum grow without limit.
A whimsical variation known as Kempner series adds up only those unit
fractions whose denominators do not contain the digit nine. This rule
eliminates enough terms from the infinite sum to make it converge to a finite
limit, since the included terms that do not contain the digit nine get
exponentially more rare as n increases. Your function should compute and
return K n, the n :th term of the Kempner series by adding up the reciprocals
of the first n positive integers that do not contain the digit nine. For
example, to compute K 10, you would need to add up 1/1 + 1/2 + 1/3 + 1/4 + 1/5 - 1/6 + 1/7 + 1/8 + 1/10 + 1/11, the first ten such reciprocals.
Instead of approximating the result inaccurately with fixed precision floating
point numbers, you must perform this computation with perfect accuracy using
Fraction objects from the fractions module. However, since the numerators and
denominators of these fractions grow pretty quickly as n increases, the result
should be returned as a Fraction object given by the approximation produced by
calling the methodlimit_denominator(1000)to approximate the true value
of the result as the nearest fraction whose denominator is less than one
thousand.n Expected result (as Fraction) 4 25/12 100 431/87 500 5743/914 1000 6723/985
Hippity hoppity, abolish loopity
def frog_collision_time(frog1, frog2):
—|—
A frog moving on the infinite two-dimensional grid of integers is represented
as a 4-tuple of the form (sx, sy, dx, dy) where (sx, sy) is its starting
position at time zero, and (dx, dy) is its constant direction vector for each
hop. Time advances in discrete integer steps 0, 1, 2, 3,… so that each frog
makes one hop exactly at every tick of the clock. At time t, the position of
that frog is given by the formula (sx + t*dx, sy + t*dy) that can be
nimbly evaluated even for large t.
Given two frogs frog1 and frog2 that are guaranteed to initially stand on
different squares, return the time when both frogs hop into the same square.
If these frogs never jump into the same square, return None.
This function should not contain any loops whatsoever, but the result should
be calculated using conditional statements and integer arithmetic. Perhaps the
best way to get cracking is to first solve a simpler version of this problem
with one-dimensional frogs restricted to hop along the one-dimensional line of
integers. Once you get that function working correctly, including all its
possible edge cases, use it to solve for t separately for the x - and y -
dimensions in the original problem. Combine those two one-dimensional answers
into your final answer.
| frog1 | frog2 | Expected result |
|---|---|---|
| (0, 0, 0, 2) | (0, 10, 0, 1) | 10 |
| (10, 10, -1, 0) | (0, 1, 0, 1) | None |
| (0, -7, 1, -1) | (-9, -16, 4, 2) | 3 |
| (-28, 9, 9, -4) | (-26, -5, 8, -2) | None |
| (-28, -6, 5, 1) | (-56, -55, 9, 8) | 7 |
Double trouble
def double_trouble(items, n):
—|—
Suppose for the sake of argument that you repeat the following operation n
times for the given list of items : remove the first element, and append that
same element twice to the end of items. Which one of the items would be
removed and copied in the last operation that we perform?
Sure, this problem could be solved by actually performing that operation n
times, but the point of this question is to come up with an analytical
solution to compute the result much faster than going through that whole
rigmarole. Of course, the automated tester is designed so that anybody trying
to brute force their way through this problem by actually performing all n
operations one by one will run out of time and memory long before receiving
the answer. To come up with this analytical solution, tabulate some small
cases (you can implement the brute force function to compute these) and try to
spot the pattern that generalizes to arbitrarily large values of n.
| items | n | Expected result |
|---|---|---|
| [‘joe’, ‘bob’, 42] | 10 | ‘joe’ |
| [17, 42, 99] | 1000 | 17 |
| [17, 42, 99] | 10**20 | 99 |
| (The real reason why you should pay attention in your courses on discrete math | ||
| and combinatorics is to familiarize you with techniques to derive symbolic | ||
| solutions to problems of this nature so that you don’t have to brute force | ||
| their answers in a time that would be prohibitively long to ever be feasible. | ||
| We met this same theme earlier back in the question asking how many blocks are | ||
| in a pyramid shape…) |
Nearest polygonal number
def nearest_polygonal_number(n, s):
—|—
Any positive integer s > 2 defines an infinite sequence of s - gonal
numbers whose i:th element is given by the formula ((s - 2) i^2 - (s - 4) i) / 2 , as explained on the Wikipedia page “ Polygonal Number “. In this
formula, positions start from 1, not 0, and we use the letter i for the
position since we will be using the letter n for something else. For example,
the sequence of “octagonal numbers” that springs forth from s = 8 starts with
1, 8, 21, 40, 65, 96, 133, 176…
Given the number of sides s and an arbitrary integer n, this function should
find and return the s - gonal integer that is closest to n. If n falls exactly
halfway between two s - gonal numbers, return the smaller one. As you can see
from the last row of the following table, this function must be efficient even
for gargantuan values of n.
| n | s | Expected result |
|---|---|---|
| 5 | 3 | 6 |
| 27 | 4 | 25 |
| 450 | 9 | 474 |
| 10**10 | 42 | 9999861561 |
| The simplest way to make this function efficient is to harness the power of | ||
| repeated halving to pull your wagon with a clever application of binary | ||
| search. Start with two integers a and b wide enough that they satisfy ` a <= i | ||
| <= b ` for the currently unknown position i that the nearest polygonal number | ||
| is stored in. (Just initialize these two with a = 1 and b = 2, and keep | ||
| squaring b until the number in that position gets too big. It’s not like these | ||
| initial bounds need to be accurate.) | ||
| From there, compute the midpoint position (a + b) // 2, and look at the | ||
| element in that position. Depending on how that midpoint element compares to | ||
| n, bring either b or a to the midpoint position. Continue this until the gap | ||
has become small enough so that b - a < 2 , at which point one more final |
||
| tells you which element is the correct answer. |
Postfix interpreter
def postfix_evaluate(items):
—|—
When arithmetic expressions are given in the familiar infix notation 2 + 3 *
4, we need to use parentheses to force a different evaluation order than the
usual PEMDAS order determined by precedence and associativity. Writing
arithmetic expressions in postfix notation (also known as Reverse Polish
Notation ) may look strange to us humans accustomed to the conventional infix
notation, but is computationally far easier to handle, since postfix notation
allows any evaluation order to be expressed unambiguously without using any
parentheses at all! A postfix expression is given as a list of items that can
be either individual integers or one of the strings ‘+’, ‘-‘, ‘*‘ and ‘/‘ for
the four possible arithmetic operators.
To evaluate a postfix expression using a simple linear loop, use a list as a
stack that is initially empty. Loop through the items one by one, in order
from left to right. Whenever the current item is an integer, just append it to
the end of the list. Whenever the current item is one of the four arithmetic
operations, remove two items from the end of the list, perform that operation
on those items, and append the result to the list. Assuming that items is a
legal postfix expression, which is guaranteed in this problem so that you
don’t need to do any error handling, once all items have been processed this
way, the one number that remains in the stack is returned as the final answer.
To avoid the intricacies of floating point arithmetic, you should perform the
division operation using the Python integer division operator // that
truncates the result to the integer part. Furthermore, to avoid the crash
caused by dividing by zero, in this problem we shall artificially make up a
rule that dividing anything by zero will simply evaluate to zero instead of
crashing.
| items | (Equivalent infix) | Expected result |
|---|---|---|
| [2, 3, ‘+’, 4, ‘*’] | (2+3) * 4 | 20 |
| [2, 3, 4, ‘*’, ‘+’] | 2 + (3*4) | 14 |
| [3, 3, 3, ‘-‘, ‘/‘] | 3 / (3 - 3) | 0 |
| [7, 3, ‘/‘] | 7 / 3 | 2 |
| (By adding more operators and another auxiliary stack, an entire programming | ||
| language can be built around the idea of postfix evaluation. See the Wikipedia | ||
| page “Forth”, if interested.) |
Fractran interpreter
def fractran(n, prog, giveup = 1000):
—|—
John Conway, who was quite a character among mathematicians, is best known for
The Game of Life, not to be confused with the classic board game that shares
the same name. That one achievement eclipsed basically all other wacky and
original creations of Conway, so perhaps we ought to give his less appreciated
creations at least an occasional turn in the flashing lights of red carpet
fame.
This lab asks you to write a simple interpreter for the esoteric programming
language called FRACTRAN, named as a pun of the word “fraction” and the
FORTRAN programming language. (Everything used to be in uppercase back in the
day, with occasional dollar signs interspersed as separators.) A program
written in such mysterious and hard-to-decipher form consists of nothing but a
list of positive integer fractions, in this problem given as tuples of the
numerator and the denominator. Of course, you are not merely allowed but
encouraged to use the Fraction data type of the Python fractions module to
simplify the computations inside your function.
Given a positive integer n as its start state, the next state is the product
nf for the first fraction listed in prog for which nf is an exact integer.
That integer then becomes the new state for the next round. Once n*f is not an
integer for any of the fractions f listed in prog, the execution terminates.
Your function should compute and return the sequence of integers produced by
the given FRACTRAN program, with a forced termina… sorry, forced halting
(after all, Conway was British) taking place after giveup steps, if the
execution has not halted by then.
| n | prog | giveup | Expected result |
|---|---|---|---|
| 2 | [(17, 91), (78, 85), (19, 51), (23, 38), (29, 33), (77, 29), (95, 23), | ||
| (77, 19), (1, 17), (11, 13), (13, 11), (15, 2), (1, 7), (55, 1)] | 20 | ||
| [2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, | |||
| 116, 308, 364, 68, 4, 30] | |||
| 9 | (same as above) | 20 | [9, 495, 435, 1155, 1015, 2695, 3185, 595, |
| 546, 102, 38, 23, 95, 385, 455, 85, 78, 66, 58, 154, 182] |
Permutation cycles
def permutation_cycles(perm):
—|—
Let us define a list of n elements to be a permutation if it contains every
integer from 0 to n - 1 exactly once. (Being computer scientists, we again
count from zero, whereas mathematicians count from one in this definition.)
For example, [5, 2, 0, 1, 4, 3] is one of the 6! possible permutations of n =
6. Every permutation perm encodes a function that maps each position from 0 to
n - 1 into another position. For example, the example permutation maps the
position 0 into position 5, position 1 into position 2, and so on.
A cycle in a permutation is a list of positions inside it so that each
position is mapped into the next position in the cycle, the last element
looping back to the beginning. For example, the example permutation contains
two cycles [0, 5, 3, 1, 2] and [4], the second cycle therefore a singleton.
This function should find all cycles in the permutation. Instead of returning
the result as a list of cycles. To make the result unique, each cycle starts
from its highest-numbered position, and the cycles should be listed in
increasing order of these starting positions. For example, the previous cycles
should be listed as [4] and [5, 3, 1, 2, 0], in this order.
Furthermore, instead of returning a list of cycles, the contents of these
cycles should be returned as the standard representation of the original
permutation, a flat list that contains these cycles listed in order. This way,
every permutation maps uniquely to its standard representation that is another
permutation without any separator characters between cycles, but still allows
these cycles to be extracted at will. (Think about how you would do this.)
| perm | Expected result |
|---|---|
| [0, 1, 2, 3] | [0, 1, 2, 3] |
| [3, 2, 1, 0] | [2, 1, 3, 0] |
| [5, 2, 0, 1, 4, 3] | [4, 5, 3, 1, 2, 0] |
| [2, 4, 6, 5, 3, 1, 0] | [5, 1, 4, 3, 6, 0, 2] |
| [5, 3, 0, 1, 4, 2, 6] | [3, 1, 4, 5, 2, 0, 6] |
| [0, 9, 7, 4, 2, 3, 8, 5, 1, 6] | [0, 7, 5, 3, 4, 2, 9, 6, 8, 1] |
Squaring off
def subtract_square(queries):
—|—
Two players play a game called “ Subtract a square “ with a positive integer.
On their turn to play, each player can subtract any square number (1, 4, 9,
16, 25, 36, 49,…) from the current number as long as the result would not
become negative. Under the normal play convention, the player who makes the
final move by moving to zero wins, leaving his opponent stuck with no possible
moves. (In the misre version of the game that has otherwise identical rules
but where you win by losing the original game, these definitions would be
adjusted accordingly.)
This and all other combinatorial games can be modelled with recursive
equations. This game is an example of an impartial game since the moves
available to both players are exactly the same, as opposed to “partisan games”
such as chess where each player can only move pieces of one colour. A game
state is therefore determined by the remaining number alone, but not on which
player has to make the next move. A state is called “hot” (“winning”) if it
allows at least one move that guarantees the win regardless of the opponent’s
response, under the natural assumption that the current player will then also
continue making the best moves until the opponent says uncle. The game state
is “ cold “ (“losing”) if no winning move exists.
Since the possible states of this game are the nonnegative integers, the base
case for the recursion is that zero is cold. The state n is hot if there
exists at least one move m so that n-m*m is cold, otherwise n is cold. Since
the heat of each state n depends on heats of states lower than n, we might as
well combine the computations of states to be as a “batch job”. Given a list
of queries so that each element is a state this function should return a list
of results for those queries so that True means hot and False means cold. You
should compute the heat values of states as a single list that you build up
from left to right, so that the computation of the heat value of each state
can simply read from this list the heat values of previous states that it
needs.
| queries | Expected result |
|---|---|
| [7, 12, 17, 24] | [False, False, False, True] |
| [2, 3, 6, 10, 14, 20, 29, 39, 57, 83, 111, 149, 220, 304, 455, 681] | |
| [False, True, True, False, True, False, True, False, False, True, True, True, | |
| True, True, True, True] |
ztalloc ecneuqes
def ztalloc(shape):
—|—
The famous Collatz sequence was used in the lectures as an example of a
situation that requires the use of a while -loop, since we cannot know
beforehand how many steps are needed to get to the goal from the given
starting value. The answer was given as the list of integers that the sequence
visits before terminating at its goal. However, we can also look at this
sequence in a binary fashion depending on whether each value steps up (3x + 1)
or down ( x // 2) from the previous value, denoting these steps with letter
‘u’ and ‘d’, respectively. For example, starting from n = 12, the sequence
[12, 6, 3, 10, 5, 16, 8, 4, 2, 1] would have the step shape ‘ddududddd’.
This function should, given the step shape as a string that is guaranteed to
consist of only letters u and d, determine which starting value for the
Collatz sequence produces that shape. However, this function must also
recognize that some shape strings are impossible as entailed by the transition
rules of Collatz problem, and correctly return None for all such shapes. You
should start from the goal state 1, and perform the given transitions in
reverse. Make sure that your function does not accept moves that would not be
legal in the original Collatz sequence in forward direction.
| shape | Expected result |
|---|---|
| ‘ududududddddudddd’ | 15 |
| ‘dudududdudddudddd’ | 14 |
| ‘uduuudddd’ | None |
| ‘d’ | 2 |
| ‘uuududdddduuuuuuudddddd’ | None |
| ‘duuudddddddd’ | None |
Reverse ascending sublists
def reverse_ascending_sublists(items):
—|—
Create and return a new list that contains the same elements as the argument
list items, but reversing the order of the elements inside every maximal
strictly ascending sublist. Note the modifier “strictly” used there to require
each element to be greater than the previous element, not merely equal to it.
As is the case with all functions unless otherwise specified, this function
should not modify the contents of the original list, but create and return a
brand new list object that contains the result, no matter how tempting it
might be to perform this operation right there in the original list to “save
some memory”.
In the table below, different colours highlight the strictly ascending
sublists for the reader, and are not part of the actual argument given to the
function. (It’s not like this is Mathematica or some other high level symbolic
computation system that deals directly with symbolic expressions in their
unevaluated forms, allowing you to do things like this…)
| items | Expected result |
|---|---|
| [ 1, 2, 3, 4, 5 ] | [ 5, 4, 3, 2, 1 ] |
| [ 5, 7, 10, 4, 2, 7, 8, 1, 3 ] | [10, 7, 5, 4, 8, 7, 2, 3, 1] |
| [ 5, 4, 3, 2, 1] | [ 5, 4, 3, 2, 1 ] |
