完成Python基础算法和数据结构练习。
Giving back change
def give_change(amount, coins):
—|—
Given the amount of money (expressed as an integer as the total number of
cents, one dollar being equal to 100 cents) and the list of available
denominations of coins (similarly expressed as cents), create and return a
list of coins that add up to amount using the greedy approach where you use as
many of the highest denomination coins when possible before moving on to the
next lower denomination. The list of coin denominations is guaranteed to be
given in descending sorted order, as should your returned result also be.
| amount | coins | Expected result |
|---|---|---|
| 64 | [50, 25, 10, 5, 1] | [50, 10, 1, 1, 1, 1] |
| 123 | [100, 25, 10, 5, 1] | [100, 10, 10, 1, 1, 1] |
| 100 | [42, 17, 11, 6, 1] | [42, 42, 11, 1, 1, 1, 1, 1] |
| This particular problem with its countless variations is a classic when | ||
| modified so that you must minimize the total number of returned coins. The | ||
| greedy approach will then no longer produce the optimal result for all | ||
| possible coin denominations. For example, for simple coin denominations of | ||
| [50, 30, 1] kopecs and the amount of sixty kopecs to be exchanged, the greedy | ||
| solution [50, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] uses eleven coins, whereas the | ||
| optimal solution [30, 30] needs only two! A more advanced recursive algorithm | ||
| would be needed to make the “take it or leave it” decision for each coin and | ||
| explore which choice leads to a better final outcome. The intermediate results | ||
| of this recursion would then be memoized to avoid blowing up the running time | ||
| exponentially. |
Rooks on a rampage
def safe_squares_rooks(n, rooks):
—|—
On a generalized n - by- n chessboard, there are some number of rooks , each
one represented as a two-tuple (row, column) of the row and the column of the
square that the rook is in. (Since we are again being computer programmers
instead of normal people, these rows and columns are numbered from 0 to n -
1.) A chess rook covers all squares that are in the same row or in the same
column as that rook. Given the board size n and the list of rooks on that
board, count the number of empty squares that are safe, that is, are not
covered by any rook.
Hint: count separately how many rows and columns on the board are safe from
any rook. The result is simply the product of these two counts. (Permuting the
rows and columns does not change the answer to this question. We can therefore
imagine all the safe rows and columns to have been permuted in a way that has
all safe squares form a rectangle at the top left corner of the board, and the
area of a rectangle is of course the product of its width and height.)
| n | rooks | Expected result |
|---|---|---|
| 10 | [] | 100 |
| 4 | [(2, 3), (0, 1)] | 4 |
| 8 | [(1, 1), (3, 5), (7, 0), (7, 6)] | 20 |
| 2 | [(1, 1)] | 1 |
| 6 | [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)] | 0 |
| 100 | [(r, (r*(r-1))%100) for r in range(0, 100, 2)] | 3900 |
| 10**6 | [(r, r) for r in range(10**6)] | 0 |
Try a spatula
def pancake_scramble(text):
—|—
Analogous to flipping a stack of pancakes by sticking a spatula inside the
stack and flipping pancakes that rest on top of that spatula, a pancake flip
of order k done for the given text string reverses the prefix of first k
characters and keeps the rest of the string as it were. For example, the
pancake flip of order 2 performed on the string ‘ilkka’ would produce the
string ‘likka’ . The pancake flip of order 3 performed on the same string
would produce ‘klika’ .
A pancake scramble , as defined in the excellent Wolfram Challenges
programming problems site , consists of the sequence of pancake flips of order
2, 3, … , n performed in this exact sequence for the given n -character text
string. For example, the pancake scramble done to the string ‘ilkka’ would
step through the intermediate results ‘likka’ , ‘kilka’ , ‘klika’ and ‘akilk’
. This function should compute and return the pancake scramble of its
parameter text string.
| text | Expected result |
|---|---|
| ‘hello world’ | ‘drwolhel ol’ |
| ‘ilkka’ | ‘akilk’ |
| ‘pancake’ | ‘eanpack’ |
| ‘abcdefghijklmnopqrstuvwxyz’ | ‘zxvtrpnljhfdbacegikmoqsuwy’ |
| For those of you who are interested in this sort of stuff, the follow-up | |
| question “ How many times you need to pancake scramble the given string to get | |
| back the original string? “ is also educational, especially once the strings | |
| get so long that the answer needs to be computed analytically (note that the | |
| answer depends only on the length of the string but not the content, as long | |
| as all characters are distinct) instead of actually performing these scrambles | |
| until the original string appears. A more famous problem of pancake sorting | |
| asks for the shortest series of pancake flips whose application rearranges the | |
| elements of the given list in sorted order. |
Words with given shape
def words_with_given_shape(words, shape):
—|—
Let the shape of the given word of length n be a list of n - 1 integers, each
one either -1, 0 or +1, indicating whether the next letter following the
letter in that position comes later (+1), the same (0) or earlier (-1) in
alphabetical order of English letters. For example, the shape of ‘hello’ is
[-1, +1, 0, +1] , whereas the shape of ‘world’ is [-1, +1, -1, -1] . Find and
return a list of all words that have that particular shape , listed in
alphabetical order.
Note that your function, same as all the other functions specified in this
document that operate on lists of words, should not itself try to read the
wordlist file words_sorted.txt , even when Python makes this possible with
just a couple of lines of code. The tester script already reads in the entire
wordlist and builds the list of words from there. Your function should use
this given list of words without even caring which particular file it came
from.
| shape | Expected result (using wordlist words_sorted.txt ) |
|---|---|
| [1, -1, -1, -1, 0, -1] | [‘congeed’, ‘nutseed’, ‘outfeed’, ‘strolld’] |
| [0, 1, -1, 1] | [‘aargh’, ‘eeler’, ‘eemis’, ‘eeten’, ‘oopak’, ‘oozes’, |
| ‘sstor’] | |
| [1, 1, 1, 1, 1, 1, 1] | [‘aegilops’] |
| Motivated students can take on as an extra challenge for each possible word | |
| length n ranging from 3 to 20, find the shape of length n - 1 that matches the | |
| largest number of words. Alternatively, try to count how many possible shapes | |
| of length n - 1 do not match any words of length n at all. What is the | |
| shortest possible shape that does not match any words? How about the shortest | |
| such shape that does not contain any zeroes? |
Running median of three
def running_median_of_three(items):
—|—
Given a list of items that are all guaranteed to be integers, create and
return a new list whose first two elements are the same as they were in
original items , after which each element equals the median of the three
elements in the original list ending in that position. (If two out of these
three elements are equal, then that element is the median of those three.)
| items | Expected result |
|---|---|
| [5, 2, 9, 1, 7, 4, 6, 3, 8] | [5, 2, 5, 2, 7, 4, 6, 4, 6] |
| [1, 2, 3, 4, 5, 6, 7] | [1, 2, 2, 3, 4, 5, 6] |
| [3, 5, 5, 5, 3] | [3, 5, 5, 5, 5] |
| [22, 77] | [22, 77] |
| [42] | [42] |
The card that wins the trick
def winning_card(cards, trump = None):
—|—
Playing cards are again represented as tuples of (rank, suit) as in the
cardproblems.py example program. In trick-taking card games such as bridge ,
the players in turn each play one card from their hand to the trick. The
winner of the trick is determined by the following rules:
- If one or more cards of the trump suit have been played to the trick, the trick is won by the highest trump card, regardless of the other cards played.
- If no trump cards have been played to the trick, the trick is won by the highest card of the suit of the first card played to the trick. Cards of any other suits, regardless of their rank, are powerless to win that trick.
- Ace is the highest card in each suit.
Note that the order in which the cards are played to the trick greatly affects
the outcome of that trick. Given the list of cards played to the trick, return
the card that wins the trick.cards trump Expected result [(‘trey’, ‘spades’), (‘ace’, ‘diamonds’), (‘jack’, ‘spades’), (‘eight’, ‘spades’)] None (‘jack’, ‘spades’) [(‘ace’, ‘diamonds’), (‘ace’, ‘hearts’), (‘ace’, ‘spades’), (‘two’, ‘clubs’)] ’clubs’ (‘two’, ‘clubs’) [(‘two’, ‘clubs’), (‘ace’, ‘diamonds’), (‘ace’, ‘hearts’), (‘ace’, ‘spades’)] None (‘two’, ‘clubs’)
Boustrophedon
def create_zigzag(rows, cols, start = 1):
—|—
This function creates a list of lists that represents a two-dimensional grid
with the given number of rows and cols . This grid should contain the integers
counting the rows * cols numbers from start in ascending order. However, as in
the way that an ox plows a field somewhere back in ancient Greece, the
elements of every odd-numbered row must be listed in descending order. However
you choose to enforce that discipline is up to you.
In all of the examples of the following table, the keyword parameter start is
not given and therefore equals one. But your function must work correctly for
arbitrary values of start .
| rows | cols | Expected result |
|---|---|---|
| 3 | 5 | [[1,2,3,4,5], [10,9,8,7,6], [11,12,13,14,15]] |
| 10 | 1 | [[1], [2], [3], [4], [5], [6], [7], [8], [9], [10]] |
| 4 | 2 | [[1,2], [4,3], [5,6], [8,7]] |
Detab
def detab(text, n = 8, sub = ' '):
—|—
In the detabbing process of converting tab characters ‘\t’ to ordinary
whitespaces, each tab character is replaced by a suitable number of whitespace
characters so that the next character is placed at a position that is exactly
divisible by n . However, if the next character is already in a position that
is divisible by n , another n whitespace characters are appended to the result
so that at least one substitution character will appear to replace any tab
character.
For demonstration purposes, since whitespace characters might be difficult to
visualize during the debugging stage, the substitution character that fills in
the tabs can be freely chosen with the named argument sub that defaults to
whitespace. This function should create and return the detabbed version of its
parameter text .
| text | n | sub | Expected result |
|---|---|---|---|
| ‘Hello\tthereyou\tworld’ | 8 | ‘$’ | ‘Hello$$$thereyou$$$$$$$$world’ |
| ‘Ilkka\tMarkus\tKokkarinen’ | 4 | ‘-‘ | ‘Ilkka—Markus–Kokkarinen’ |
| ‘Tenser,\tsaid\tthe\ttensor’ | 5 | ‘+’ | ‘Tenser,+++said+the++tensor’ |
| People vary greatly on their preference for the value of n , which is why we | |||
| make it a named argument in this problem. Some people prefer n = 4, others | |||
| like the wider berth of n = 8, whereas your instructor likes the tight n = 2 | |||
| best. To each his or her own. |
Multidimensional knight moves
def knight_jump(knight, start, end):
—|—
An ordinary chess knight on a two-dimensional board of squares can make an
“L-move” into up to eight possible neighbours. However, we can generalize the
entire chessboard into k dimensions from our puny two. A natural extension of
the knight’s move to keep moves symmetric with respect to these dimensions is
to define the possible moves as some k - tuple of strictly decreasing
nonnegative integer offsets. Each one of these k offsets must be used for
exactly one dimension of your choice during the move, either as a positive or
a negative version.
For example, the three-dimensional (4, 3, 1) -knight makes its way by first
moving four steps along any one of the three dimensions, then three steps
along any other dimension, and then one step along the remaining dimension,
whichever of the original three that was. Once the knight has stepped along
some dimension, it can no longer step along that same dimension within the
same move. These steps are considered to be performed together as a single
jump that does not visit or is blocked by any of the intermediate squares.
Given the start and end positions as k - tuples of integer coordinates,
determine whether the knight can get from start to end in one jump.
| knight | start | end | Expected result |
|---|---|---|---|
| (2, 1) | (12, 10) | (11, 12) | True |
| (7, 5, 1) | (15, 11, 16) | (8, 12, 11) | True |
| (9, 7, 6, 5, 1) | (19, 12, 14, 11, 20) | (24, 3, 20, 11, 13) | False |
| A quick combinatorial calculation reveals that exactly k ! _2 k possible | |||
| neighbours are reachable in a single move, assuming that none of these moves | |||
| takes the knight outside the board. In this notation, the ordinary chess | |||
| knight is a (2, 1) -knight that can reach 2!_ 2 2 = 2 _4 = 8 possible | |||
| neighbouring squares in one jump. A 6-dimensional knight reaches a whopping | |||
| 6!_ 2 6 = 46080 different neighbours in one jump. Since the number of moves | |||
| emanating from each position to its neighbours grows exponentially with | |||
| respect to k , pretty much everything ends up being close to pretty much | |||
| everything else in high-dimensional spaces. (Density in general is known to | |||
| have both advantages and disadvantages in all walks of life.) |
Fulcrum
def can_balance(items):
—|—
Each item in the list of items is now considered to be a physical weight, and
therefore guaranteed to be a positive integer. Your task is to find and return
a fulcrum position in this list so that when balanced on that position, the
total torque of the items to the left of that position equals the total torque
of the items to the right of that position. The item on the fulcrum is assumed
to be centered symmetrically on both sides, and therefore does not participate
in the torque calculation.
As taught in any introductory textbook on physics, the torque of an item with
respect to the fulcrum equals its weight times its distance from the fulcrum.
If a fulcrum position exists, return that position, otherwise return -1 to
indicate that the given items cannot be balanced, at least not without
rearranging them. That one, by the way, would be an interesting but a more
advanced problem normally suitable for a third year computer science course…
but in Python, this algorithm could easily be built around this function by
using the generator permutations in the module itertools to try out all
possible permutations in an outer loop until you find one permutation that
works. (In fact, quite a few problems of this style can be solved with this “
generate and test “ approach without needing the fancy backtracking algorithms
from third year and up.)
| items | Expected result |
|---|---|
| [6, 1, 10, 5, 4] | 2 |
| [10, 3, 3, 2, 1] | 1 |
| [7, 3, 4, 2, 9, 7, 4] | -1 |
| [42] | 0 |
| Yes, I pretty much wrote this problem only to get to say “fulcrum”. What a | |
| cool word. And you know what is another really cool word? “ Phalanx “. That | |
| one even seems like something that could be turned into an interesting | |
| computational problem about lists of lists… and that’s the crux of that matte. |
