CS2312编程语言代写、代做Programming程序设计、Python程序代写

日期：2020-11-29 10:31

Lab 13 CS2312 Problem Solving and Programming (2020/2021 Semester A)

Introduction to Functional Programming using Python

This lab is based on the materials from Dr LI Shuaicheng (2018-19B)

Introduction

We will use a handy Python console (PythonAnywhere on www.python.org) to

learn Functional Programming in Python.

In each part of this lab, please

- Listen to the explanation,

- Study the given guideline,

- Study the given code in the code boxes in this word document and/or add your code in the code

boxes (or in a text editor, or Jupyter notebook etc. of your choice) *,

- Then copy and paste the code to run it in the Python console.

* You will need to submit the finished word document (or the text file or notebook file) onto Canvas=>Assignment.

* Ref: Avoid smart quotes: https://www.windowscentral.com/change-smart-quotes-straight-quotes-microsoft-office-word-outlook-powerpoint

^ Alternatives: vscode: https://code.visualstudio.com/docs/python/python-tutorial, repl: https://repl.it/languages/python3 , etc.

Reference: https://docs.python.org/3/library/, https://docs.python.org/3/library/functions.html

[Preparation]

1. Knowing Functional Programming

Please read the following paragraphs (From https://docs.python.org/3/howto/functional.html ) :

2, Online console from PythonAnywhere

Alternatives: Feel free to use any other shell or environment if you prefer

Enter www.python.org and run the interactive shell ==>

? You will see the prompt “>>>” at where you

will type the code and run it.

? “Clear” the screen : Ctrl-L

? Change font size: Ctrl--, Ctrl-+

Functional programming decomposes a problem into a set of functions.

Ideally, functions only take inputs and produce outputs, and

don’t have any internal state that affects the output produced for a given input.

Functional programming can be considered the opposite of object-oriented programming.

Objects are little capsules containing some internal state

along with a collection of method calls that let you modify this state, and

programs consist of making the right set of state changes.

Functional programming wants to avoid state changes as much as possible and works with data

flowing between functions.

Lab 13 CS2312 Problem Solving and Programming (2020/2021 Semester A) | www.cs.cityu.edu.hk/~helena

- 2 -

Lab Tasks

?inside code boxes in the tasks

Part A: We will first learn selected features of python step by step. <== Your code in the submission can be anything

Part B: We will move onto problem solving with Functional Programming. <== Your code has to be correct

Part A: Selected Features of Python

A.1 Variable and List, comments, input

The following creates two variables and a list.

No prior declaration is needed.

-The first assignment to a variable creates it.

Comment: #

Input: x = input()

Count of elements in a list: len(myList)

A.2 Printing – using the print function in Python 3

A.3 Define a function

About defining a function:

- def: define a function

- “global” is need to mean a global variable

- note the indentations (e.g. 3 spaces)

- when you finish, hit one more <enter> to exit

- default return value: None

print("Testing", x, y, myList) >>> print("Testing", x, y, myList)

Testing apple pear ['apple', 3.14]

>>>

sum=0

def addValue(x):

>>> sum=0

>>>

>>> def addValue(x):

... global sum

... sum += x

...

>>> addValue(1)

>>> addValue(2)

>>> addValue(3)

>>>

>>> sum

6

x = "apple"

y = 'pear'

myList = ["apple",3.14] #like array

x

y

myList

Given code box

(Please add your own code to do more test(s),

copy and paste to the Python console for running)

>>> x = "apple"

>>> y = 'pear'

>>> myList = ["apple",3.14] #like array

>>> x

'apple'

>>> y

'pear'

>>> myList

['apple', 3.14]

>>>

Lab 13 CS2312 Problem Solving and Programming (2020/2021 Semester A) | www.cs.cityu.edu.hk/~helena

- 3 -

A.4 and, or, not; True, False

A.5 Control of Flow, Multiple assignment

if ..:, elif ..:, else:

a, b, c = 1, 2, 3

To delete a variable, use del. E.g. del mx_1

A.6 List: + and slicing – provide the start and end (element excluded) index

A.7 The list() function

– creates a list by iterating through the contents of the given parameter

>>> s = [1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16]

>>> s

[1, 2, -3, 4, 5, -6, 7, 8, -9, 10, -11, -12, 13, -14, 15, -16]

>>> s = s[1:6]

>>> s

[2, -3, 4, 5, -6]

>>> s1 = s[:3]

>>> s2 = s[3:]

>>> s1

[2, -3, 4]

>>> s2

[5, -6]

True and False

True or False

not False

[Your work] Add your testing code in the code box below:

s = [1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16]

list("hello")

>>> True and False

False

>>> True or False

True

>>> not False

True

>>>

>>> list("hello")

['h', 'e', 'l', 'l', 'o']

>>>

x, y = 4, 4 #assign values to two variables

if x>y:

mx_1 = x

elif y>x: # try change to else:

mx_1 = y

mx_1

x, y = y+1, x-1

mx_2 = x if x>y else y

mx_2

Lab 13 CS2312 Problem Solving and Programming (2020/2021 Semester A) | www.cs.cityu.edu.hk/~helena

- 4 -

A.8 Lambda function, function variable

W3schools: A lambda function is a small anonymous function.

A lambda function can take any number of arguments, but can only have one expression.

Function variables: _is_equal, _is_small, _is_large, _append

One more example: f = lambda x,y: x if x>y else y

f(3,4) #gives 4

A.9 map function: map(f, [x1, x2, ..]) - means the execution of f on each element xi in the list

- f may be a one-parameter-function to take on each xi

- map returns a map object that can be iterated to execute f on each element xi in the list

To run, type list( map(f, [x1, x2, ..]) )

Default return value: None

Try:- add return sum inside the function

- list(map(list,["apple","pear","banana"])) # [['a', 'p', 'p', 'l', 'e'], ['p', 'e', 'a', 'r'], ['b', 'a', 'n', 'a', 'n', 'a']]

A.10 filter function (https://docs.python.org/3/library/functions.html#filter)

Filter a collection according to some conditions

Note: The object returned by filter / map

can be iterated only once.

It doesn't work for the second time.

a = filter(lambda x: x>0, [1, -2, 3, 6, -9, 20, 13, 16])

list(a) # gives [1, 3, 6, 20, 13, 16]

list(a) # gives []

sum=0

def addValue(x):

global sum

sum += x

>>> sum=0

>>> def addValue(x):

... global sum

... sum += x

...

>>> list(map(addValue, [1,2,3]))

[None, None, None]

>>> sum

6

>>> _is_equal = lambda x,y : x==y _is_equal = lambda x,y : x==y

>>> _is_small = lambda x,y : x<y

>>> _is_large = lambda x,y : x>y

>>> _append = lambda x,y: x+y

>>> _is_equal(1,2)

False

>>> _is_small(1,2)

True

>>> _is_large(1,2)

False

>>> _append([1,2],[3,4,5])

[1, 2, 3, 4, 5]

>>> a = filter(lambda x: x>0, [1, -2, 3, 6, -9, 20, 13, 16])

>>> b = filter(lambda x: x<0, [1, -2, 3, 6, -9, 20, 13, 16])

>>> list(a)

[1, 3, 6, 20, 13, 16]

>>> list(b)

[-2, -9]

a = filter(lambda x: x>0, [1, -2, 3, 6, -9, 20, 13, 16])

Lab 13 CS2312 Problem Solving and Programming (2020/2021 Semester A) | www.cs.cityu.edu.hk/~helena

- 5 -

Part B: Problem Solving

B.1 my_max: The balanced and imbalanced versions

What is the max of values in [1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16]?

The balanced version The imbalanced version

What should be A and B? Please complete them below:

(B1.1) The balanced version:

Hint: A is the maximum of the left-side sublist: my_max(x[:len(x)//2])

B is the maximum of the right-side sublist: ____________________

For x[:..], review A.6

//: floor division – give the same result as int(x/2)

(B1.2) The imbalanced version:

>>> def my_max(x):

... if len(x)==1:

... return x[0]

... elif len(x)==2:

... if x[0]>x[1]: return x[0]

... else: return x[1]

... else:

... return my_max([my_max(x[:len(x)//2]), my_max(x[len(x)//2:])])

...

>>> my_max([1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16])

15

>>>

def my_max(x):

if len(x)==1:

return x[0]

elif len(x)==2:

if x[0]>x[1]: return x[0]

else: return x[1]

else:

return my_max([_______, _______])

my_max([1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16])

def my_max(x):

if len(x)==1:

return x[0]

elif len(x)==2:

if x[0]>x[1]: return x[0]

else: return x[1]

else:

return my_max([_______, _______])

my_max([1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16])

OR

Lab 13 CS2312 Problem Solving and Programming (2020/2021 Semester A) | www.cs.cityu.edu.hk/~helena

- 6 -

B.2 my_reverse: The balanced and imbalanced versions

Reverse the list of values [1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16]

The balanced version The imbalanced version

What should be A and B? Please complete them below:

(B2.1) The balanced version:

Hint: my_reverse(x[len(x)//2:]), ?

For x[:..], review A.6

//: floor division – give the same result as int(x/2)

(B2.2) The imbalanced version:

>>> def my_reverse(x):

... if len(x)==1:

... return x

... return my_reverse(x[len(x)//2:])+my_reverse(x[:len(x)//2])

...

>>> my_reverse([1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16])

[-16, 15, -14, 13, -12, -11, 10, -9, 8, 7, -6, 5, 4, -3, 2, 1]

>>>

OR

def my_reverse(x):

if len(x)==1:

return x

return A + B

my_reverse([1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16])

def my_reverse(x):

if len(x)==1:

return x

return A + B

my_reverse([1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16])

Lab 13 CS2312 Problem Solving and Programming (2020/2021 Semester A) | www.cs.cityu.edu.hk/~helena

- 7 -

B.3 m, n problem (with map and lambda)

[LI Lecture 10 Slide 34-35]

Please complete the code below:

Hint: A' is the result of the subproblem m_n(n-1,m-n)

A is a lambda function that puts together A' and [n]

B is the result of the subproblem m_n(n-1,m)

For lambda, review A.8

For list(map(..,..)), review A.9

def m_n(n,m):

if m<0:

return []

elif n*(n+1)/2 < m:

return []

elif n*(n+1)/2 == m:

return [list(range(1,n+1))]

else:

return list(map( A , A' )) + B

m_n(4,4)

>>> def m_n(n,m):

... if m<0:

... return []

... elif n*(n+1)/2 < m:

... return []

... elif n*(n+1)/2 == m:

... return [list(range(1,n+1))]

... else:

... return list(map(lambda x:x+[n], m_n(n-1,m-n))) + m_n(n-1,m)

...

>>> m_n(4,4)

[[4], [1, 3]]

>>>

Lab 13 CS2312 Problem Solving and Programming (2020/2021 Semester A) | www.cs.cityu.edu.hk/~helena

- 8 -

B.4 Quick-Sort (with filter and lambda)

Please complete the code below:

Hint: A is the list of elements smaller than the bench_mark

B is the list of elements larger than the bench_mark

For lambda, review A.8

For list(filter(..,..)), review A.10

def quick_sort(myList):

if len(myList)==0:

return myList

bench_mark = myList[0]

equal = list(filter(lambda x: x==bench_mark, myList)) # the list of elements equal to the bench_mark

small = quick_sort( A )

large = quick_sort( B )

return small + equal + large

data_set=[1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16]

file:///I:\www\cs23022009B_Hide_074\08Sorting.ppt

myList

>>> def quick_sort(myList):

... if len(myList)==0:

... return myList

... bench_mark = myList[0]

... equal = list(filter(lambda x: x==bench_mark, myList))

... small = quick_sort(list(filter(lambda x: x<bench_mark, myList)))

... large = quick_sort(list(filter(lambda x: x>bench_mark, myList)))

... return small + equal + large

...

>>> data_set=[1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16]

>>> quick_sort(data_set)

[-16, -14, -12, -11, -9, -6, -3, 1, 2, 4, 5, 7, 8, 10, 13, 15]

>>>

Approach:

myList[0] is selected to be the bench_mark

Divide the items based on the bench_mark:

(1) left partition: the smaller ones

(2) items equal to bench_mark

(3) right partition: the larger ones

Next: Solve (1) and (3) in a recursive way.

The "Quick-sort" discussed here is simplified,

and only gives a very basic idea.

The actual Quick-sort algorithm performs in-place

sorting that achieves good run-time efficiency

Lab 13 CS2312 Problem Solving and Programming (2020/2021 Semester A) | www.cs.cityu.edu.hk/~helena

- 9 -

[https://docs.python.org/3/library/functools.html#functools.reduce]

B.5 Reduce function – Solve the max problem using Functional Programming (yet non-recursive)

Your task: Learn the reduce function and see how it is used.

reduce : replace simple recursive logics with the Reduce function: reduce a list of elements to one element

Note: f = lambda x,y: x if x>y else y is to set a function variable (review A.8)

B.6 Reduce function – Solve the reverse problem using Functional Programming (yet non-recursive)

Your task: Complete the code below:

Hint: A is appendR

B is map(toList,myList) means to turn the list of items to a list of one-item-lists

>>> f = lambda x,y: x if x>y else y

>>>

>>> from functools import reduce

>>> def my_max(myList):

... return reduce(f,myList)

...

>>> data_set=[1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16]

>>> my_max(data_set)

15

>>>

f = lambda x,y: x if x>y else y

from functools import reduce

def my_max(myList):

return reduce(f,myList)

data_set=[1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16]

my_max(data_set)

OR

OR

>>> def appendR(list1, list2):

... return list2+list1;

...

>>> def toList(item):

... return [item]

...

>>> def reverse(myList):

... return reduce( A , B )

...

>>> data_set=[1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16]

>>> reverse(data_set)

[-16, 15, -14, 13, -12, -11, 10, -9, 8, 7, -6, 5, 4, -3, 2, 1]

>>>

def appendR(list1, list2):

return list2+list1;

def toList(item): # turn each item into a list

return [item]

def reverse(myList):

return reduce( A , B )

data_set=[1,2,-3,4,5,-6,7,8,-9,10,-11,-12,13,-14,15,-16]

reverse(data_set)