数据结构与算法--Python实现 课课后习题(1)

​ 数据结构与算法——Python实现,第一章课后习题

第一章

R - 1.1

编写一个Python函数is_multiple(n,m),用来接收两个整数值n和m,如果n是m的倍数,即存在整数i使得n = mi,那么函数返回True,否则返回False

1
2
3
4
5
6
7
def is_multipe(n,m):
if n % m == 0:
return True
else:
return False

print(is_multipe(100,20))

R - 1.2

编写一个Python函数 is_even(k),用来接收一个整数 k,如果 k 是偶数返回 True,否则返回 False。但是,函数中不能使用乘法、除法或取余操作.

1
2
3
4
5
6
7
8
9
def is_even(k):
if not isinstance(k,int):
raise TypeError('k must be numeric')
if k % 2 == 0:
return True
else:
return False

print(is_even(10))

R - 1.3

编写一个Python函数 minmax(data),用来在数的序列中找出最小数和最大数,并以一个长度为 2 的元组的形式返回。注意:不能通过内置函数 min 和 max 来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
def minmax(data):
minnumer = data[0]
maxnumer = data[0]
for i in data:
if i > maxnumer:
maxnumer = i
elif i < minnumer:
minnumer = i

return minnumer,maxnumer

num = [2,3,5,6,8,7,9,4]
print(minmax(num))

R - 1.4

编写一个Python函数,用来接收正整数 n,返回 1 ~ n 的平方和。

1
2
3
4
5
6
7
8
def power(n):
sum = 0
result = [k*k for k in range(1,n+1)]
for i in result:
sum += i
return sum

print(power(2))

R - 1.5

基于Python的解析语法和内置函数 sum,写一个单独的命令来计算练习R-1.4中的和。

1
2
3
4
def sumer(n):
return sum(k*k for k in range(1,n+1))

print(sumer(2))

R - 1.6

编写一个Python函数,用来接收正整数n,并返回 1 ~ n 中所有的奇数的平方和。

1
2
3
4
5
6
7
8
9
def summer(n):
sum = 0
result = []
for i in range(1,n+1):
if i % 2 != 0:
sum += i*i
return sum

print(summer(3))

R - 1.7

基于Python的解析语法和内置函数 sum,写一个单独的命令来计算练习R-1.6中的和。

1
2
3
4
def summer(n):
return sum(k*k for k in range(1,n+1) if k % 2 !=0 )

print(summer(3))

R - 1.8

Python 允许负整数作为序列的索引值,如一个长度为 n 的字符串 s,当索引值 -n ≤ k < 0 时,所指的元素为 s[k],那么求一个正整数索引值 j ⩾ 0,使得 s[j] 指向的也是相同的元素。

1
j = n + k

R - 1.9

要生成一个值为 50, 60, 70, 80 的排列,求 range构造函数的参数.

1
2
result = [i for i in range(50,90,10)]
print(result)

R - 1.10

要生成一个值为 8, 6, 4, 2, 0, -2, -4, -6, -8 的排列,求 range 构造函数中的参数。

1
2
result = [k for k in range(8,-10,-2)]
print(result)

R - 1.11

演示怎样使用 Python 列表解析语法来产生列表 [1, 2, 4, 8, 16, 32, 64, 128, 256].

1
2
result = [2**k for k in range(9)]
print(result)

R - 1.12

Python 的 random 模块包括一个函数 choice(data),可以从一个非空序列返回一个随机元素。Random模块还包含一个更基本的 randrange 函数,参数化类似于内置的 range 函数,可以在给定范围内返回一个随机数。只使用 randrange 函数,实现自己的 choice 函数。

1
2
3
4
5
from random import randrange
def choice(data):
return data[randrange(len(data)-1)]

print(choice([2**k for k in range(9)]))

C - 1.13

编写一个函数的伪代码描述,该函数用来逆置 n 个整数的列表,使这些以相反的顺序输出,并将该方法与可以实现相同功能的 Python 函数进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
def resort(data):
for i in data:
if not isinstance(i,(int,float)):
raise TypeError('elements must be numeric')
#data.reverse()
#return data
#return data[::-1]
return list(reversed(data))

data = [k for k in range(5)]
print(data)
print(resort(data))

C-1.14

编写一个 Python 函数,用来接收一个整数序列,并判断该序列中是否存在一对乘积是奇数的互不相同的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
def is_odd(data):
for item in data:
if not isinstance(item,int):
raise TypeError('element must be numeric')
a = []
for i in data:
for j in data[data.index(i)+1:]:
if i*j % 2 == 1 and i != j:
a.append((i,j))
return a

a = [k for k in range(10)]
print(is_odd(a))

C-1.15

编写一个 Python 函数,用来接收一个数字序列,并判断是否所有数字都互不相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
def is_different(data):
for item in data:
if not isinstance(item,(int,float)):
raise TypeError('element must be numeric')
for i in data:
for j in data[data.index(i) + 1:]:
if i == j :
return False

return True

a = [1,5,4,6,5,4,7]
print(is_different(a))

C-1.16

在1.5.1节 scale 函数的实现中,循环体内执行的命令 data[j] *= factor。我们已经说过这个数字类型是不可变的,操作符 *= 在这种背景下使用是创建一个新的实例(而不是现有实例的变化)。那么 scale 函数是如何实现改变调用者发送的实际参数呢?

通过极端data[j] = data[j] * factor 对data[j]重新赋值


C-1.17

1.5.1节 scale 函数的实现如下。它能正常工作吗?请给出原因。

1
2
3
def  scale(data, factor):
for val in data:
val = val * factor

不能,只改变了val的值,没有改变形参


C-1.18

演示如何使用 Python 列表解析语法来产生列表 [0, 2, 6, 12, 20, 30, 42, 56, 72, 90]。

1
2
a = [k*(k-1) for k in range(1,11)]
print(a)

C-1.19

演示如何使用 Python 列表解析语法在不输入所有 26 个英文字母的情况下产生列表 [‘a’, ‘b’, ‘c’,…, ‘z’]。

1
2
a = [chr(k) for k in range(97,123)]
print(a)

C-1.20

Python 的 random 模块包括一个函数 shuffle(data),它可以接受一个元素的列表和一个随机的重新排列元素,以使每个可能的序列发生概率相等。 random 模块还包括一个更基本的函数 randint(a, b),它可以返回一个 a 到 b (包括两个端点)的随机整数。只使用 randint 函数,实现自己的 shuffle 函数。

1
2
3
4
5
6
7
8
9
10
11
12
from random import *
def my_shuffle(data):
new =[]
while len(data) > 0:
a = randint(0,len(data)-1)
new.append(data[a])
data.pop(a)

return new

data = [1,2,3,4,5]
print(my_shuffle(data))

C-1.21

编写一个Python程序,反复从标准输入读取一行直到抛出 EOFError 异常,然后以相反的顺序输出这些行(用户可以通过键按 Ctrl + D 结束输入)。

1
2
3
4
5
6
7
8
9
def function():
a = []
while True:
try:
response = input("Please input:")
a.append(response)
except EOFError:
for val in a[::-1]:
print(val)

C-1.22

编写一个Python程序,用来接收长度为 n 的两个整型数组 a 和 b 并返回数组 a 和 b 的点积。也就是返回一个长度为 n 的数组 c,即 c[i] = a[i] ⋅ b[i], for i = 0, …, n-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def dot_product(data1,data2):
for i in data1:
if not isinstance(i,int):
raise TypeError("element must be numeric")

for j in data2:
if not isinstance(j,int):
raise TypeError("element must be numeric")

if len(data1) != len(data2):
raise KeyError("Their must have same length!")

new = [data1[i] * data2[i] for i in range(len(data1))]

return new
a = [1,2,3,4,4]
b =[2,3,9,8,4]
print(dot_product(a,b))

C-1.23

给出一个 Python 代码片段的例子,编写一个索引可能越界的元素列表。如果索引越界,程序应该捕获异常结果并打印以下错误消息:“Don’t try buffer overflow attacks in Python!”

1
2
3
4
5
6
7
def function23(data, i):
try:
return data[i]
except IndexError:
print("Don't try buffer overflow attacks in Python!")
data = [1, 2, 3 ]
function23(data, 3)

C-1.24

编写一个 Python 函数,计算所给字符串中元音字母的个数。

1
2
3
4
5
6
7
8
9
10
def is_Yuan(data):
a = ['a','e','i','o','u']
number = 0
for i in data:
if i in a:
number += 1
return number
data = 'wdefiojawn'
num = is_Yuan(data)
print(num)

C-1.25

编写一个 Python函数,接收一个表示一个句子的字符串 s,然后返回该字符串的删除了所有标点符号的副本。例如, 给定字符串 “Let’s try, Mike.”,这个函数将返回 “Lets try Mike”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import string
def remove_mark():
pieces = []
reply = input("Please input something:")
for k in reply:
pieces.append(k)
punctuation = string.punctuation
for i in pieces:
if i in punctuation:
pieces.remove(i)
a = ''.join(pieces)
return a

print(remove_mark())

C-1.26

编写一个程序,需要从控制台输入 3 个整数 a、b、c,并确定它们是否可以在一个正确的算术公式(在给定的顺序)下成立,如“a + b = c” “a = b - c” 或 “a * b = c”。

1
2
3
4
5
6
7
def threeIntegers():
a = int(input("Please input three integers: "))
b = int(input("b:"))
c = int(input("c:"))
print('a+b=c 成立') if a+b ==c else print('a+b=c 不成立')

threeIntegers()

C-1.27

在 1.8 节中,我们对于计算所给整数的因子时提供了 3 种不同的生成器的实现方法。 1.8 节末尾处的第三种方法是最有效的,但我们注意到,它没有按递增顺序来产生因子。修改生成器,使得其按递增顺序来产生因子,同时保持其性能优势。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def factors(n):
k = 1
temp = []
while k*k < n:
if n % k == 0:
yield k
temp.append(n//k)
k+=1
if k * k == n:
yield k
for i in temp[::-1]:
yield i

print(list(factors(100)))

C-1.28

1

1
2
3
4
5
6
7
8
9
10
def norm(v,p=2):
i,temp = 0,0
while i < len(v):
temp += pow(v[i],p)
i += 1
result = pow(temp,1/p)
return result

v = [4,3]
print(norm(v))

P-1.29

编写一个 Python 程序,输出由字母 ‘c’,‘a’,‘t’,‘d’,‘o’,‘g’ 组成的所有可能的字符串(每个字母只使用1次)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution():
def solve(self,str):
self.allstr(str,[])

def allstr(self,str,solution):
if len(str) == 0:
print(solution)
return
for i in range(len(str)):
newsolution = solution + [str[i]]
new_str = str[:i]+str[i+1:]
self.allstr(new_str,newsolution)

str = ['c','a','t','d','o','g']
Solution().solve(str)

P-1.30

编写一个 Python 程序,输入一个大于 2 的正整数,求将该数反复被 2 整除直到商小于 2 为止的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution():

def solve(self,number):
if number <= 2:
raise ValueError("The number must bigger than 2!")
if not isinstance(number,int):
raise TypeError("The number must be an integer")
self.division_num(number,0)

def division_num(self,number,num):
if number < 2:
print(num)
return
newNumber = number / 2
num+=1
self.division_num(newNumber,num)

Solution().solve(6)

P-1.31

编写一个可以“找零钱”的 Python 程序。程序应该将两个数字作为输入,一个是需要支付的钱数,另一个是你给的钱数。当你需要支付的和所给的钱数不同时,它应该返回所找的纸币和硬币的数量。纸币和硬币的值可以基于之前或现在政府的货币体系。试设计程序,以便返回尽可能少的纸币和硬币。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class change_Money():

def judge(self):
a = float(input("You need to pay :"))
b = float(input("Your money:"))
if a == b:
print("The business is finished !")
elif a > b:
raise ValueError("You don't have enough money!")
else:
self.change(b - a)

def change(self,number):
par = [0.05,0.1,0.2,0.5,1.0,2.0,5.0,10.0,20.0,50.0,100.0]
sum = float(number)
i = len(par)-1
while i >= 0:
if sum >= par[i]:
n = int(sum // par[i])
change_m = n* par[i]
sum = float("%.6f" %(sum-change_m))
if par[i] > 1:
print("用了%d张%1.2f元纸币" %(n,par[i]))
else:
print("用了%d个%1.2f元硬币" %(n,par[i]))
i -= 1

if __name__ == '__main__':

change_Money().judge()

P-1.32

编写一个 Python 程序来模拟一个简单的计算器,使用控制台作为输入和输出的专用设备。也就是说,计算器的每一次输入做一个单独的行,它可以输入一个数字(如1034或12.34)或操作符(如 + 或 = )。每一次输入后,应该输出计算器显示的结果并将其输出到 Python 控制台。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def function():
temp = input("Please input Number1 operation Number2:").split(" ")
number1 = float(temp[0])
number2 = float(temp[2])
oper = str(temp[1])
if oper == '+':
result = number1 + number2
elif oper == '-':
result = number1 - number2
elif oper == '*':
result = number1 * number2
elif oper == '/':
result = number1 / number2
else:
raise EOFError("Error Input!")
print(result)

function()

P-1.33

编写一个 Python 程序来模拟一个手持计算器,程序应该可以处理来自 Python 控制台(表示 Push 按钮)的输入,每个操作执行完毕后内容输出到屏幕。计算器至少应该能够处理基本的算术运算和复位/清除操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class hand_held_calculator():

def Inuput(self):
sequence =[]
while 1:
for i in range(len(sequence)):
print(sequence[i],end='')
print()
print('*' * 20,end='\n')
while 1:
try:
num = input("Please input with sapce (a + b):").split(" ")
if num[0] == 'esc':
# 用于清屏
sequence = self.clear(sequence)
num = self.clear(num)
elif num[0] == '=':
result = self.calculate(sequence[0],sequence[1],sequence[2])
sequence = self.clear(sequence)
num = self.clear(num)
num += str(result)
else:
f = float(num[0])
k = float(num[2])
except ValueError:
print("It's not a number!Please enter again!")
else:
break
sequence = sequence + num

def clear(self,data):
# 用于清屏
data = []
return data

def calculate(self,num1,mark,num2):
num1 = float(num1)
num2 = float(num2)
if mark == '+':
return num1+num2
elif mark == '-' :
return num1-num2
elif mark == '*' :
return num1*num2
elif mark == '-' :
return num1/num2


if __name__ == '__main__':
hand_held_calculator().Inuput()

P-1.34

一种惩罚学生的常见方法是让他们将一个句子重复写很多次。编写独立的 Python 程序,将以下句子 “I will never spam my friends again.” 写 100 次。程序应该对句子进行计数,另外,应该有 8 次不同的随机输入错误。

1
2
3
4
5
6
7
8
def random_mistake():
count = 1
string = "I will never spam my friends again."
while count < 11:
temp = input("Now : {} Please write phrase: \n".format(count))
if temp == string:
count +=1
print("Finished!")

P-1.35

生日悖论是说,当房间中人数 n 超过 23 时,那么该房间里有两个人生日相同的可能性是一半以上。这其实不是一个悖论,但许多人觉得不可思议。设计一个 Python 程序,可以通过一系列随机生成的生日的实验来测试这个悖论,例如可以 n = 5, 10, 15, 20, …, 100 测试这个悖论.

1
2
3
4
5
def function352(num):
import math
prop = 1 - math.pow((364/365), (num*(num-1)/2))
print("在%d个人中至少有两人生日相同的概率为%.6f" %(num,prop))
function352(365)

P-1.36

编写一个 Python程序,输入一个由空格分隔的单词列表,并输出列表中的每个单词出现的次数。在这一点上,你不需要担心效率,因为这个问题会在本书后面的部分予以解决。

1
2
3
4
5
6
7
8
9
def function():
str = input("Please input something :").split(" ")
keys = list(set(str))
result = dict(zip(keys,[0]*len(keys)))
for i in str:
result[i] += 1
return result

print(function())

重点难点

  1. 使用两个print打印一行数据,更改print结尾参数:

    print(‘’,end = ‘ ‘)

  2. 1
    2
    3
    print (str.split( ))       # 以空格为分隔符
    print (str.split('i',1)) # 以 i 为分隔符
    print (str.split('w')) # 以 w 为分隔符

split()通过指定分隔符对字符串进行切片,如果参数 num 有指定值,则仅分隔 num+1 个子字符串

  1. 1
    str.join(sequence)
    • sequence – 要连接的元素序列。

    • 返回值:返回通过指定字符连接序列中元素后生成的新字符串。

    • 1
      2
      3
      4
      str = "-";
      seq = ("a", "b", "c"); # 字符串序列
      print str.join( seq );
      >>> a-b-c
  2. chr() 用一个范围在 range(256)内的(就是0~255)整数作参数,返回一个对应的字符。

  3. combinations(iterable, r) 创建一个迭代器,返回iterable中所有长度为r的子序列,返回的子序列中的项按输入iterable中的顺序排序:

    1
    2
    3
    4
    5
    6
    >>> list(combinations(range(3),2))
    [(0, 1), (0, 2), (1, 2)]
    >>> list(combinations(range(3),3))
    [(0, 1, 2)]
    >>> list(combinations(range(3),1))
    [(0,), (1,), (2,)]
  4. product(iterables[, repeat]) 创建一个迭代器,生成表示iterables*中的项目的笛卡尔积的元组,repeat表示重复生成序列的次数。

    1
    2
    3
    4
    5
    6
    >>> list(product(range(3),repeat=1))
    [(0,), (1,), (2,)]
    >>> list(product(range(3),repeat=2))
    [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
    >>> list(product(range(3),repeat=3))
    [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2), (2, 0, 0), (2, 0, 1), (2, 0, 2), (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 2, 0), (2, 2, 1), (2, 2, 2)]
  5. filter()函数:filter() 函数用于过滤序列,过滤掉不符合条件的元素,返回一个迭代器对象,如果要转换为列表,可以使用 list() 来转换。

1
filter(function, iterable)

参数

  • function – 判断函数。
  • iterable – 可迭代对象。

返回值:返回一个迭代器对象

1
2
3
4
5
6
7
8
def is_odd(n):
return n % 2 == 1

tmplist = filter(is_odd, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
newlist = list(tmplist)
print(newlist)
输出结果 :
[1, 3, 5, 7, 9]
  1. strip()函数:移除字符串头尾指定的字符(默认为空格或换行符)或字符序列。

    1
    2
    3
    4
    5
    6
    7
    8
    str = "00000003210Runoob01230000000"; 
    print str.strip( '0' ); # 去除首尾字符 0

    str2 = " Runoob "; # 去除首尾空格
    print str2.strip();
    以上实例输出结果如下:
    3210Runoob0123
    Runoob
  2. zip()函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的对象,这样做的好处是节约了不少的内存。

    我们可以使用 list() 转换来输出列表。

    如果各个迭代器的元素个数不一致,则返回列表长度与最短的对象相同,利用 * 号操作符,可以将元组解压为列表。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    >>>a = [1,2,3]
    >>> b = [4,5,6]
    >>> c = [4,5,6,7,8]
    >>> zipped = zip(a,b) # 返回一个对象
    >>> zipped
    <zip object at 0x103abc288>
    >>> list(zipped) # list() 转换为列表
    [(1, 4), (2, 5), (3, 6)]
    >>> list(zip(a,c)) # 元素个数与最短的列表一致
    [(1, 4), (2, 5), (3, 6)]

    >>> a1, a2 = zip(*zip(a,b)) # 与 zip 相反,zip(*) 可理解为解压,返回二维矩阵式
    >>> list(a1)
    [1, 2, 3]
    >>> list(a2)
    [4, 5, 6]
  3. set() 函数创建一个无序不重复元素集,可进行关系测试,删除重复数据,还可以计算交集、差集、并集等。

1
2
3
4
5
6
7
8
9
10
11
>>>x = set('runoob')
>>> y = set('google')
>>> x, y
(set(['b', 'r', 'u', 'o', 'n']), set(['e', 'o', 'g', 'l'])) # 重复的被删除
>>> x & y # 交集
set(['o'])
>>> x | y # 并集
set(['b', 'e', 'g', 'l', 'o', 'n', 'r', 'u'])
>>> x - y # 差集
set(['r', 'b', 'u', 'n'])
>>>
  1. replace() 方法把字符串中的 old(旧字符串) 替换成 new(新字符串),如果指定第三个参数max,则替换不超过 max 次。

str.replace(old, new[, max])

参数

  • old – 将被替换的子字符串。
  • new – 新字符串,用于替换old子字符串。
  • max – 可选字符串, 替换不超过 max 次

返回值:返回字符串中的 old(旧字符串) 替换成 new(新字符串)后生成的新字符串,如果指定第三个参数max,则替换不超过 max 次。

1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/python3

str = "www.w3cschool.cc"
print ("菜鸟教程旧地址:", str)
print ("菜鸟教程新地址:", str.replace("w3cschool.cc", "runoob.com"))

str = "this is string example....wow!!!"
print (str.replace("is", "was", 3))
以上实例输出结果如下:
菜鸟教程旧地址: www.w3cschool.cc
菜鸟教程新地址: www.runoob.com
thwas was string example....wow!!!
  1. shuffle() 方法将序列的所有元素随机排序。
1
2
3
4
5
6
7
8
9
10
11
import random

list = [20, 16, 10, 5];
random.shuffle(list)
print ("随机排序列表 : ", list)

random.shuffle(list)
print ("随机排序列表 : ", list)
以上实例运行后输出结果为:
随机排序列表 : [20, 5, 16, 10]
随机排序列表 : [5, 20, 10, 16]
  1. lstrip()方法用于截掉字符串左边的空格或指定字符。
1
2
3
4
5
6
7
str = "     this is string example....wow!!!     ";
print( str.lstrip() );
str = "88888888this is string example....wow!!!8888888";
print( str.lstrip('8') );
以上实例输出结果如下:
this is string example....wow!!!
this is string example....wow!!!8888888

rstrip()删除 string 字符串末尾的指定字符(默认为空格).

1
2
3
4
5
6
7
str = "     this is string example....wow!!!     "
print (str.rstrip())
str = "*****this is string example....wow!!!*****"
print (str.rstrip('*'))
以上实例输出结果如下:
this is string example....wow!!!
*****this is string example....wow!!!