CSC148H5 Lecture Notes - Lecture 11: American Broadcasting Company, Empty String, Erms
4 Feb 2017
School
Department
Course
Professor
Document Summary
Csc148h5s - introduction to computer science (winter 2017) Solving a problem by reducing it to subproblems, then combining the subproblem solutions to solve the original problem. Subproblems must have the same structure as the original problem and be easier to solve. Subproblems are so simple that they can be solve directly (without reducing them harm) # binary example from the previous class def codes (r): Return all binary codes of length r. if r == 0 : return [ "" ] small = codes(r -1 ) lst = [] for item in small: lst. append(item+ "0" ) lst. append(item+ "1" ) return lst. It does small = codes(1-1) so, small = [""] lst becomes ["0", "1"] codes(1) returns ["0","1"] What does codes(2) do? small becomes ["0","1"] lst becomes ["00","01","10",11"] so codes(2) is correct? yes. Example 2: finding the length of a string.
