CS50 (Computer Science 50) is an on-campus and online introductory course on computer science taught at Harvard University and, as of 2015, Yale University as well. In 2016, CS50 became available to high school students as an AP course. The course material is available online for free on EdX with a range of certificates available for a fee. The on-campus version is Harvard’s largest class with 800 students, 102 staff and up to 2,200 participants in their regular hackathons.
CS50, Wikipedia
* 此课程笔记根据 Harvard CS50 Spring 2020 完成。
第 6 周讲了 Python,把此前的诸多 C 程序转化为了 Python 实现,在此过程中介绍了 Python 的语法、特性及语言风格。最后见缝插针讲了很简短的正则的内容。我想在这里讲 Python,大概是稍后讲网页编程的时候,需要用到 Python 的 Flask 的缘故。
大部分内容引用自 CS50 课程官方的笔记。
目录
Python Basics
- Today we’ll learn a new programming language called Python, and remember that one of the overall goals of the course is not learning any particular languages, but how to program in general.
- Source code in Python looks a lot simpler than C, but is capable of solving problems in fields like data science. In fact, to print “hello, world”, all we need to write is:
print("hello, world")
- Notice that, unlike in C, we don’t need to import a standard library, declare a
main
function, specify a newline in theprint
function, or use semicolons. - Python is an interpreted language, which means that we actually run another program (an interpreter) that reads our source code and runs it top to bottom. For example, we can save the above as
hello.py
, and run the commandpython hello.py
to run our code, without having to compile it. - We can get strings from a user:
answer = get_string("What's your name?\n") print("hello, " + answer)
- We create a variable called
answer
, without specifying the type (the interpreter determins that from context for us), and we can easily combine two strings with the+
operator before we pass it intoprint
.
- We can also pass in multiple arguments to
print
, withprint("hello,", answer)
, and it will automatically join them with spaces for us too. print
also accepts format strings likef"hello, {answer}"
, which substitutes variables inside curly braces into a string.
- We create a variable called
- We can create variables with just
counter = 0
. To increment a variable, we can usecounter = counter + 1
orcounter += 1
. - Conditions look like:
if x < y: print("x is less than y") elif x > y: print("x is greater than y") else: print("x is equal to y")
- Unlike in C and JavaScript (whereby braces
{
}
are used to indicate blocks of code), the exact indentation of each line is what determines the level of nesting in Python.
- And instead of
else if
, we just sayelif
.
- Unlike in C and JavaScript (whereby braces
- Boolean expressions are slightly different, too:
while True: print("hello, world")
- We can write a loop with a variable:
i = 3 while i > 0: print("cough") i -= 1
- We can also use a
for
loop, where we can do something for each element in a list:
for i in [0, 1, 2]: print("cough")
- Lists in Python are like arrays in C, but they can grow and shrink easily with the interpreter managing the implementation and memory for us.
- This
for
loop will set the variablei
to the first element,0
, run, then to the second element,1
, run, and so on. - And we can use a special function,
range
, to get some number of values, as infor i in range(3)
. This will give us0
,1
, and2
, for a total of thee values.
- In Python, there are many data types:
bool
,True
orFalse
float
, real numbersint
, integersstr
, stringsrange
, sequence of numberslist
, sequence of mutable values, that we can change or add or removetuple
, sequence of immutable values, that we can’t changedict
, collection of key/value pairs, like a hash tableset
, collection of unique values
- docs.python.org is the official source of documentation, but Google and StackOverflow will also have helpful resources when we need to figure out how to do something in Python. In fact, programmers in the real world rarely know everything in the documentation, but rather how to find what they need when they need it.
Examples
- We can blur an image with:
from PIL import Image, ImageFilter before = Image.open("bridge.bmp") after = before.filter(ImageFilter.BLUR) after.save("out.bmp")
- In Python, we include other libraries with
import
, and here we’llimport
theImage
andImageFilter
names from thePIL
library. - It turns out, if we look for documention for the
PIL
library, we can use the next three lines of code to open an image calledbridge.bmp
, run a blur filter on it, and save it to a file calledout.bmp
. - And we can run this with
python blur.py
after saving to a file calledblur.py
.
- We can implement a dictionary with:
words = set() def check(word): if word.lower() in words: return True else: return False def load(dictionary): file = open(dictionary, "r") for line in file: words.add(line.rstrip("\n")) file.close() return True def size(): return len(words) def unload(): return True
- First, we create a new set called
words
. Then, forcheck
, we can just ask `if word.lower() in words
. Forload
, we open the file and usewords.add
to add each line to our set. Forsize
, we can uselen
to count the number of elements in our set, and finally, forunload
, we don’t have to do anything!
- It turns out, even though implementing a program in Python is simpler for us, the running time of our program in Python is slower than our program in C since our interpreter has to do more work for us. So, depending on our goals, we’ll also have to consider the tradeoff of human time of writing a program that’s more efficient, versus the running time of the program.
- In Python, we can too include the CS50 library, but our syntax will be:
from cs50 import get_string
- Notice that we specify the functions we want to use.
- Now we can get strings from a user:
from cs50 import get_string s = get_string("What's your name?:\n") print("hello, " + s)
- We can substitute expressions into our format strings, too:
from cs50 import get_int age = get_int("What's your age?\n") print(f"You are at least {age * 365} days old.")
- And we can demonstrate conditions:
from cs50 import get_int x = get_int("x: ") y = get_int("y: ") if x < y: print("x is less than y") elif x > y: print("x is greater than y") else: print("x is equal to y")
- To check conditions, we can say:
from cs50 import get_string s = get_string("Do you agree?\n") if s == "Y" or s == "y": print("Agreed.") elif s == "N" or s == "n": print("Not agreed.")
- Python doesn’t have chars, so we can check them as strings directly.
- We can also say
if s in ["Y", "y"]:
, orif s.lower() in ["y"]:
. It turns out that strings in Python are like structs in C, where we have not only variables but functions that we can call. For example, given a strings
, we can call itslower
function withs.lower()
to get the lowercase version of the string.
- We can improve versions of
cough
, too:
print("cough") print("cough") print("cough")
- We don’t need to declare a
main
function, so we just write the same line of code three times.
- But we can do better:
for i in range(3): cough() def cough(): print("cough")
- Notice that we don’t need to specify the return type of a new function, which we can define with
def
. - But this causes an error when we try to run it:
NameError: name 'cough' is not defined
. It turns out that we need to define our function before we use it, so we can either move our definition ofcough
to the top, or create a main function:
def main(): for i in range(3): cough() def cough(): print("cough") main()
- Now, by the time we actually call our
main
function, thecough
function will have been read by our interpreter.
- Our functions can take inputs, too:
def main(): cough(3) def cough(n): for i in range(n): print("cough") main()
- We can define a function to get a positive integer:
from cs50 import get_int def main(): i = get_positive_int() print(i) def get_positive_int(): while True: n = get_int("Positive Integer: ") if n > 0: break return n main()
- Since there is no do-while loop in Python as there is in C, we have a
while
loop that will go on infinitely, but we usebreak
to end the loop as soon asn > 0
. Then, our function will justreturn n
. - Notice that variables in Python have function scope by default, meaning that
n
can be initialized within a loop, but still be accessible later in the function.
- We can print out a row of question marks on the screen:
for i in range(4): print("?", end="") print()
- When we print each block, we don’t want the automatic new line, so we can pass a parameter, or named argument, to the
print
function. Here, we sayend=""
to specify that nothing should be printed at the end of our string. Then, after we print our row, we can callprint
to get a new line.
- We can also “multiply” a string and print that directly with:
print("?" * 4)
. We can print a column with a loop:
for i in range(3): print("#")
- And without a loop:
print("#\n" * 3, end="")
. We can implement nested loops:
for i in range(3): for j in range(3): print("#", end="") print()
- We don’t need to use the
get_string
function from the CS50 library, since we can use theinput
function built into Python to get a string from the user. But if we want another type of data, like an integer, from the user, we’ll need to cast it withint()
. - But our program will crash if the string isn’t convertable to an integer, so we can use
get_string
which will just ask again. - In Python, trying to get an integer overflow actually won’t work:
from time import sleep i = 1 while True: print(i) sleep(.01) i *= 2
- We call the
sleep
function to pause our program for a second between each iteration. - This will continue until the integer can no longer fit in your computer’s memory.
- Floating-point imprecision, too, can be prevented by libraries that can represent decimal numbers with as many bits as are needed. We can make a list:
scores = [] scores.append(72) scores.append(73) scores.append(33) print(f"Average: {sum(scores) / len(scores)}")
- With
append
, we can add items to our list, using it like a linked list. - We can also declare a list with some values like
scores = [72, 73, 33]
.
- We can iterate over each character in a string:
from cs50 import get_string s = get_string("Input: ") print("Output: ", end="") for c in s: print(c, end="") print()
- Python will get each character in the string for us.
- To make a string uppercase, too, we can just call
s.upper()
to get the uppercase version of the entire string, without having to iterate over each character ourselves.
More features
- We can take command-line arguments with:
from sys import argv for i in range(len(argv)): print(argv[i])
- Since
argv
is a list of strings, we can uselen()
to get its length, andrange()
for a range of values that we can use as an index for each element in the list.
- But we can also let Python iterate over the list for us:
from sys import argv for arg in argv: print(arg)
- We can return exit codes when our program exits, too:
from sys import argv, exit if len(argv) != 2: print("missing command-line argument") exit(1) print(f"hello, {argv[1]}") exit(0)
- We import the
exit
function, and call it with the code we want our program to exit with.
- We can implement linear search by just checking each element in a list:
import sys names = ["EMMA", "RODRIGO", "BRIAN", "DAVID"] if "EMMA" in names: print("Found") sys.exit(0) print("Not found") sys.exit(1)
- If we have a dictionary, a set of key:value pairs, we can also check each key:
import sys people = { "EMMA": "617-555-0100", "RODRIGO": "617-555-0101", "BRIAN": "617-555-0102", "DAVID": "617-555-0103" } if "EMMA" in people: print(f"Found {people['EMMA']}") sys.exit(0) print("Not found") sys.exit(1)
- Notice that we can get the value of of a particular key in a dictionary with
people['EMMA']
. Here, we use single quotes (both single and double quotes are allowed, as long they match for a string) to differentiate the inner string from the outer string. - And we declare dictionaries with curly braces,
{}
, and lists with brackets[]
.
- In Python, we can compare strings directly with just
==
:
from cs50 import get_string s = get_string("s: ") t = get_string("t: ") if s == t: print("Same") else: print("Different")
- Copying strings, too, works without any extra work from us:
from cs50 import get_string s = get_string("s: ") t = s t = t.capitalize() print(f"s: {s}") print(f"t: {t}")
- Swapping two variables can also be done by assigning both values at the same time:
x = 1 y = 2 print(f"x is {x}, y is {y}") x, y = y, x print(f"x is {x}, y is {y}")
Files
- Let’s open a CSV file:
import csv from cs50 import get_string file = open("phonebook.csv", "a") name = get_string("Name: ") number = get_string("Number: ") writer = csv.writer(file) writer.writerow((name, number)) file.close()
- It turns out that Python also has a
csv
package (library) that helps us work with CSV files, so after we open the file for appending, we can callcsv.writer
to create awriter
from the file and thenwriter.writerow
to write a row. With the inner parentheses, we’re creating a tuple with the values we want to write, so we’re actually passing in a single argument that has all the values for our row. - We can use the
with
keyword, which will helpfully close the file for us:
... with open("phonebook.csv", "a") as file: writer = csv.writer(file) writer.writerow((name, number))
New features (Regex)
- A feature of Python that C does not have is regular expressions, or patterns against which we can match strings. For example, its syntax includes:
.
, for any character.*
, for 0 or more characters.+
, for 1 or more characters?
, for something optional^
, for start of input$
, for end of input
- For example, we can match strings with:
import re from cs50 import get_string s = get_string("Do you agree?\n") if re.search("^y(es)?$", s, re.IGNORECASE): print("Agreed.") elif re.search("^no?$", s, re.IGNORECASE): print("Not agreed.")
- First, we need the
re
package, or library, for regular expressions. - Then, for
y
oryes
, we have the regular expression^y(es)?$
. We want to make sure that the string starts withy
, and optionally hases
immediately after they
, and then ends. - Similarly, for
n
andno
, we want our string to start, have the lettern
, and optionally the lettero
next, and then end. The regular expression for that would be^no?$
. - We pass in another argument,
re.IGNORECASE
, to ignore the casing of the letters in the string. - If neither regular expression matches, we wouldn’t print anything.
- On our own Mac or PC, we can open a terminal after installing Python, and use the microphone to convert our speech to text:
import speech_recognition recognizer = speech_recognition.Recognizer() with speech_recognition.Microphone() as source: print("Say something!") audio = recognizer.listen(source) print("Google Speech Recognition thinks you said:") print(recognizer.recognize_google(audio))
- It turns out that there’s another library we can download, called
speech_recognition
, that can listen to audio and convert it to a string.
- And now, we can match on the audio to print something else:
... words = recognizer.recognize_google(audio) # Respond to speech if "hello" in words: print("Hello to you too!") elif "how are you" in words: print("I am well, thanks!") elif "goodbye" in words: print("Goodbye to you too!") else: print("Huh?")
- We can even use regular expressions, to match on part of a string:
... words = recognizer.recognize_google(audio) matches = re.search("my name is (.*)", words) if matches: print(f"Hey, {matches[1]}.") else: print("Hey, you.")
- Here, we can get all the characters after
my name is
with.*
, and print it out.
- We run detect.py and faces.py, which finds each face (or even a specific face) in a photo.
- qr.py will also generate a QR code to a particular URL.
习题个人解答
很多之前写的 C 语言的程序被要求用 Python 重新实现,文艺复兴时间。
Hello
from cs50 import get_string name = get_string("What's your name?\n"); print(f"hello, {name}");
Mario
from cs50 import get_int def get_range_int(a, b): while True: ans = get_int("Height: ") if ans >= a and ans <= b: return ans height = get_range_int(1, 8) for i in range(1, height + 1): for left in range(height): if left < height - i: print(" ", end="") else: print("#", end="") print(" ", end="") for right in range(height): if right < i: print("#", end="") else: print(" ", end="") print()
Cash
from cs50 import get_float def get_non_negative_float(): while True: ans = get_float("Change owed: ") if ans >= 0: return ans total_coin = 0 denominations = [25, 10, 5, 1] dollar = get_non_negative_float() penny = int(dollar * 100) for i in range(4): total_coin += int(penny / denominations[i]) penny = penny % denominations[i] print(total_coin)
Credit
Python 果然清爽,我好了。
from cs50 import get_int def main(): table = { 'i': "INVALID", 'a': "AMEX", 'm': "MASTERCARD", 'v': "VISA" } card_number = get_int("Number: ") if luhn(card_number): print(table[check(card_number)]) else: print("INVALID") def check(number): if number >= 4000000000000000 and number < 5000000000000000: return 'v' elif number >= 4000000000000 and number < 5000000000000: return 'v' elif number >= 340000000000000 and number < 350000000000000: return 'a' elif number >= 370000000000000 and number < 380000000000000: return 'a' elif number >= 5100000000000000 and number < 5600000000000000: return 'm' else: return 'i' def luhn(n): s = str(n)[::-1] sum = 0 for i in range(len(s)): if i % 2 == 0: sum += int(s[i]) else: sum += int((int(s[i]) * 2) / 10) + (int(s[i]) * 2) % 10 if sum % 10 == 0: return True else: return False main()
Readability
from cs50 import get_string def main(): s = get_string("Text: ") l = count_letters(s) w = count_words(s) s = count_sentences(s) L = l / w * 100.0 S = s / w * 100.0 index = round(0.0588 * L - 0.296 * S - 15.8) if index < 1: print("Before Grade 1") elif index >= 16: print("Grade 16+") else: print(f"Grade {index}") def count_letters(s): length = len(s) letter = 0 for i in range(length): if s[i].isalpha(): letter += 1 return letter def count_words(s): length = len(s) word = 1 for i in range(length): if s[i].isspace(): word += 1 return word def count_sentences(s): length = len(s) sentence = 0 for i in range(length): if s[i] in ['.', '?', '!']: sentence += 1 return sentence main()
DNA
DNA 连续次数匹配,一个是读取文本,一个是读取 CSV 表格。记住一定是连续次数,审题啊。
The CODIS Unit manages the Combined DNA Index System (CODIS) and the National DNA Index System (NDIS) and is responsible for developing, providing, and supporting the CODIS Program to federal, state, and local crime laboratories in the United States and selected international law enforcement crime laboratories to foster the exchange and comparison of forensic DNA evidence from violent crime investigations. The CODIS Unit also provides administrative management and support to the FBI for various advisory boards, Department of Justice (DOJ) grant programs, and legislation regarding DNA.
https://www.fbi.gov/services/laboratory/biometric-analysis/codis
from sys import argv import csv if len(argv) != 3: print("Usage: python dna.py data.csv sequence.txt") exit(1) csvfile = open(argv[1], 'r') for row in csv.DictReader(csvfile): dna_select = list(row.keys())[1:] break csvfile.close() dna = {} dnafile = open(argv[2], 'r') dnadata = dnafile.readline() for dna_pair in dna_select: temp = 0 maxn = 0 i = 0 while i < len(dnadata): if dnadata[i:i+len(dna_pair)] == dna_pair: temp += 1 if temp > maxn: maxn = temp i += len(dna_pair) else: temp = 0 i += 1 dna[dna_pair] = maxn csvfile = open(argv[1], 'r') total = False for row in csv.DictReader(csvfile): flag = True for i in dna.keys(): if int(row[i]) != dna[i]: flag = False if flag: print(row['name']) total = True if not total: print("No match")
评论