完成Python基础算法和数据结构练习。
Ryerson letter grade
def ryerson_letter_grade(pct):
—|—
Given the percentage grade for the course, calculate and return the letter
grade that would appear in the Ryerson grades transcript, as defined on the
page Ryerson Grade Scales . The letter grade should be returned as a string
that consists of the uppercase letter followed by the possible modifier ‘+’ or
‘-‘ . The function should work correctly for all values of pct from 0 to 150.
Same as all other programming problems that follow this problem, this can be
solved in various different ways. At this point of your studies, the simplest
way to solve this problem would probably be just to use an if-else ladder .
The file labs109.py given in the repository ikokkari/PythonProblems already
contains an implementation of this function so that you can run the tester
script tester109.py and verify that it is working correctly.
| pct | Expected result |
|---|---|
| 45 | ‘F’ |
| 62 | ‘C-‘ |
| 89 | ‘A’ |
| 107 | ‘A+’ |
| As you learn more Python and techniques to perform computations within it, you | |
| may think up other ways to solve this problem. Some of these would be | |
| appropriate for actual productive tasks done in a professional coding | |
| environment, whereas others are intended to be taken in jest as a kind of | |
| conceptual performance art. A popular genre in all programming languages is to | |
| solve some straightforward problem with an algorithmic equivalent of a | |
| needlessly complicated Rube Goldberg machine , to demonstrate the universality | |
| and unity of all computation. |
Ascending
list def is_ascending(items):
—|—
Determine whether the sequence of items is strictly ascending so that each
element is strictly larger (and not just merely equal to) than the element
that precedes it. Return True if that is the case, and return False otherwise.
Note that the empty sequence is ascending, as is also every one-element
sequence, so be careful that your function returns the correct answers in
these seemingly insignificant edge cases of this problem. (If these sequences
were not ascending, pray tell, what would be the two elements that violate the
requirement and make that particular sequence not be ascending?)
| items | Expected result |
|---|---|
| [] | True |
| [-5, 10, 99, 123456] | True |
| [2, 3, 3, 4, 5] | False |
| [-99] | True |
| [4, 5, 6, 7, 3, 7, 9] | False |
| [1, 1, 1, 1] | False |
| In the same spirit, note how every possible universal claim made about the | |
| elements of an empty sequence is trivially true. For example, if seq is the | |
| empty sequence, the two claims “All elements of seq are odd” and “All elements | |
| of seq are even” are both equally true, as is also the claim “All elements of | |
| seq are colourless green ideas that sleep furiously “. For some reason, many | |
| people find this highly counterintuitive, even paradoxical, but it is a | |
| consequence of the fact that any logical formula “ A implies B “ is | |
| automatically true whenever A is false. |
Riffle
def riffle(items, out = True):
—|—
Given a list of items that is guaranteed to contain an even number of elements
(note that the integer zero is an even number), create and return a list
produced by performing a perfect riffle to the items by interleaving the items
of the two halves of the list in an alternating fashion.
When performing a perfect riffle, also known as the Faro shuffle , the list of
items is split in two equal sized halves, either conceptually or in actuality.
The first two elements of the result are then the first elements of those
halves. The next two elements of the result are the second elements of those
halves, followed by the third elements of those halves, and so on up to the
last elements of those halves. The parameter out determines whether this
function performs an out shuffle or an in shuffle that determines which half
the alternating card is first taken from.
| items | out | Expected result |
|---|---|---|
| [1, 2, 3, 4, 5, 6, 7, 8] | True | [1, 5, 2, 6, 3, 7, 4, 8] |
| [1, 2, 3, 4, 5, 6, 7, 8] | False | [5, 1, 6, 2, 7, 3, 8, 4] |
| [] | True | [] |
| [‘bob’, ‘jack’] | True | [‘bob’, ‘jack’] |
| [‘bob’, ‘jack’] | False | [‘jack’, ‘bob’] |
Only odd digits
def only_odd_digits(n):
—|—
Check that the given positive integer n contains only odd digits (1, 3, 5, 7
and 9) when it is written out. Return True if this is the case, and False
otherwise. Note that this question is not asking whether the number n itself
is odd or even. You therefore will have to look at every digit of the given
number before you can proclaim that the number contains no odd digits.
Hint: to extract the lowest digit of a positive integer n , use the expression
n % 10 . To chop off the lowest digit and keep the rest of the digits, use the
expression n // 10 . Or, if you don’t want to be this fancy, convert the
number into a string first and work from there with string operations.
| n | Expected result |
|---|---|
| 8 | False |
| 1357975313579 | True |
| 42 | False |
| 71358 | False |
| 0 | False |
Cyclops numbers
def is_cyclops(n):
—|—
A nonnegative integer is said to be a cyclops number if it consists of an odd
number of digits so that the middle (more poetically, the “eye”) digit is a
zero, and all other digits of that number are nonzero. This function should
determine whether its parameter integer n is a cyclops number, and return
either True or False accordingly.
| n | Expected result |
|---|---|
| 0 | True |
| 101 | True |
| 98053 | True |
| 777888999 | False |
| 1056 | False |
| 675409820 | False |
| As an extra challenge, you can try to solve this problem using only loops, | |
| conditions and integer arithmetic operations, without first converting the | |
| integer into a string and working from there. Dividing an integer by 10 | |
| effectively chops off its last digit, whereas the remainder operator % can be | |
| used to extract that last digit. These operations allow us to iterate through | |
| the digits of an integer one by one almost as if it were some kind of lazy | |
| sequence. | |
| (Even better, this operation doesn’t work merely for the familiar base ten, | |
| but it works for any base by using that base as the divisor. Especially using | |
| two as the divisor allows you to iterate through the bits of the binary | |
| representation of that same integer…) |
Domino cycle
def domino_cycle(tiles):
—|—
A single domino tile is represented as a two-tuple of its pip values , such as
(2, 5) or (6, 6). This function should determine whether the given list of
tiles forms a cycle so that each tile in the list ends with the exact same pip
value that its successor tile starts with, the successor of the last tile
being the first tile of the list since this is supposed to be a cycle instead
of a chain. Return True if the given list of domino tiles form such a cycle,
and False otherwise.
| tiles | Expected result |
|---|---|
| [(3, 5), (5, 2), (2, 3)] | True |
| [(4, 4)] | True |
| [] | True |
| [(2, 6)] | False |
| [(5, 2), (2, 3), (4, 5)] | False |
| [(4, 3), (3, 1)] | False |
Count dominators
def count_dominators(items):
—|—
An element of items is said to be a dominator if every element to its right
(and not just the one that is immediate to its right) is strictly smaller than
it. This function should count how many elements in items are dominators, and
return that count. By this definition, the last item of the list is
automatically a dominator. For example, in the list [42, 7, 12, 9, 13, 5] ,
the elements 42, 13 and 5 are dominators.
Before starting to write any code for this function, please read and think
about the tale of “ Shlemiel the painter “ and how this seemingly silly little
tale from a far simpler time might relate to today’s computational problems
for lists, strings and other sequences. This problem will be the first of many
that you will encounter during and after this course to illustrate the
important principle of using only one loop to achieve in a tiny fraction of
time the same end result that Shlemiel needs two nested full loops to achieve,
your workload therefore increasing only linearly with respect to the number of
items instead of quadratically (that is, as a function of the square of the
number of items), the same way that Shlemiel’s painting and running task will
increase as the fence gets longer.
| items | Expected result |
|---|---|
| [42, 7, 12, 9, 2, 5] | 4 |
| [] | 0 |
| [99] | 1 |
| [42, 42, 42, 42] | 1 |
| range(10**7) | 1 |
| range(10**7, 0, -1) | 10000000 |
Extract increasing integers from digit string
def extract_increasing(digits):
—|—
Given a string of digits guaranteed to consist of ordinary integer digit
characters 0 to 9 only, create and return the list of increasing integers
acquired from reading these digits in order from left to right. The first
integer in the result list is made up from the first digit of the string.
After that, each element is an integer that consists of as many following
consecutive digits as are needed to make that integer strictly larger than the
previous integer. The leftover digits at the end of the digit string that do
not form a sufficiently large integer are discarded.
This problem can be solved elegantly with only one for-loop through the digits
and looking at each digit exactly once, regardless of whether that digit is in
the beginning, end or middle of the string. Keep track of the current number
(initially zero) and the previous number to beat (initially minus one). Each
digit d is processed by saying current = 10*current + d .
| digits | Expected result |
|---|---|
| ‘045349’ | [0, 4, 5, 34] |
| ‘77777777777777777777777’ | [7, 77, 777, 7777, 77777, 777777] |
| ‘122333444455555666666’ | [1, 2, 23, 33, 44, 445, 555, 566, 666] |
| ‘1234567890987654321’ | [1, 2, 3, 4, 5, 6, 7, 8, 9, 98, 765, 4321] |
| ‘3141592653589793238462643383279502884’ | [3, 14, 15, 92, 653, 5897, 9323, |
| 84626, 433832, 795028] | |
| ‘123456789’ * 100 | A list that contains 75 elements, the last one of which |
| equals | |
| 34567891234567891234567891 |
Words that contain given letter sequence
def words_with_letters(words, letters):
—|—
This might be a good place to bring in some general discrete math terminology
that makes our problem specifications less ambiguous. A substring of a string
consists of characters taken in order from consecutive positions. Contrast
this to the similar concept of subsequence made of characters picked in order
but not necessarily from consecutive positions. For example, the strings “” ,
“e” , “put” , “ompu” and “computer” are both substrings and subsequences of
“computer” , whereas “cper” and “ out “ are subsequences but not substrings of
that word.
Note that the empty string is automatically a substring of every possible
string. Every string is its own substring, although not a proper substring the
same way how all other substrings are proper. Concepts of sublist and
subsequence are defined for lists in an analogous manner. Since sets have no
internal order on top of the element membership in that set, sets can
meaningfully have both proper and improper subsets. However, the concept of
subsequence would be nonsensical for sets and dictionaries.
Now that you know all that, given a list of words sorted in alphabetical
order, and a string of required letters , find and return the list of words
that contain letters as a subsequence.
| letters | Expected result (using the wordlist words_sorted.txt ) |
|---|---|
| ‘klore’ | [‘booklore’, ‘booklores’, ‘folklore’, ‘folklores’, ‘kaliborite’, |
| ‘kenlore’, ‘kiloampere’, ‘kilocalorie’, ‘kilocurie’, ‘kilogramme’, | |
| ‘kilogrammetre’, ‘kilolitre’, ‘kilometrage’, ‘kilometre’, ‘kilooersted’, | |
| ‘kiloparsec’, ‘kilostere’, ‘kiloware’] | |
| ‘brohiic’ | [‘bronchiectatic’, ‘bronchiogenic’, ‘bronchitic’, ‘ombrophilic’, |
| ‘timbrophilic’] | |
| ‘azaz’ | [‘azazel’, ‘azotetrazole’, ‘azoxazole’, ‘diazoaminobenzene’, |
| ‘hazardize’, ‘razzmatazz’] |
Taxi zum zum
def taxi_zum_zum(moves):
—|—
A Manhattan taxicab starts at the origin point (0, 0) of the two-dimensional
integer grid, initially heading north. It then executes the given sequence of
moves , a string made up of characters ‘L’ for turning 90 degrees left (while
standing in place), ‘R’ for turning 90 degrees right (ditto), and ‘ F ‘ for
moving one step forward according to its current heading. This function should
return the final position of the taxicab in the integer grid coordinates of
Manhattan.
| moves | Expected result |
|---|---|
| ‘RFRL’ | (1, 0) |
| ‘LLFLFLRLFR’ | (1, 0) |
| ‘FR’ * 1000 | (0, 0) |
| ‘FFLLLFRLFLRFRLRRL’ | (3, 2) |
| As an aside, why do these problems always seem to take place in Manhattan | |
| instead of, say, Denver where the street grid is rotated 45 degrees from the | |
| main compass axes to equalize the amount of daily sunlight on streets heading | |
| towards both orientations? That should make an interesting variation to many | |
| problems of this spirit. (Then again, diagonal moves always maintain the total | |
| parity of the coordinates, which makes it impossible to reach any coordinates | |
| of the opposite parity, somewhat like in that old joke with the punchline | |
| “Gee… I don’t think that you can get there from here.” |
