完成Python基础算法和数据结构练习。
Kempner series
1 | 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 method limit_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
1 | 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
1 | 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
1 | 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
1 | 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
1 | 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 n*f for the first fraction listed in prog for which n*f 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
1 | 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
1 | 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
1 | 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
1 | 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 ] |