完成Python基础算法和数据结构练习。
Ryerson letter grade
1 | 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
1 | 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
1 | 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
1 | 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
1 | 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
1 | 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
1 | 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
1 | 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
1 | 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
1 | 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.”