接上回。

程序设计语言基本概念

机器语言:以二进制代码的形式存在，不同cpu的机器语言不同。

汇编语言：用助记符表示机器指令，与cpu有关。

高级语言:接近于英语，与cpu无关

    C/C++  语言

    Java 语言

    Python 语言

C是面向过程的语言，C++,Java,Python是面向对象的语言。

“3+2 ”的各种表示

机器语言：1101101010011010

汇编语言：add 3 2

高级语言(Python为例）：

      >>>3+2

翻译系统

汇编语言：

    汇编程序----         ---机器语言表示文件

高级语言

   解释和编译两种方法

   源程序-----------显示结果

   源程序-------执行文件----显示结果

Python语言简介

Python是一种面向对象的解释型计 算机程序设计语言，由荷兰人

Guido van Rossum于1989年发明， 第一个公开发行版发行于1991年。

Python的设计哲学是“优雅” 、“ 明 确” 、“简单”

Python是自由软件之一，免费、开 源。

Python已经被移植到许多平台上。 这些平台包括Unix/Linux、

Windows 、Mac OS。

Python IDLE开发环境

Python ：https://www.python.org/downloads

选择Python版本

选择操作系统

运行程序:交互式解释器执行

3+5*6

33

print(“ hello world”)

hello world

运行程序: File |New,Save,Run

运行程序:命令行环境运行

d:>python hello.py

hello.py是python程序，放在d盘根目录

hello.py:

print(“hello world”)

标识符和变量

标识符是指用来标识某个实体的一个符号，在不同的应用环境下有不同的含义

标识符由字母、下划线和数字组成，且不能以数字开头

python中的标识符是区分大小写的， Andy与andy是不同的标识符

如：my_test _123

Python关键字

python一些特殊的组合，是所谓的关键字。 关键字不允许作为标识符。

*Python关键字：

raise

return

try

while

as

except

lambda

with

assert

finally

nonlocal

yield

break

for

not

class

from

or

continue

global

pass

常量和变量

常量就是不能改变的量，比如常用的数学 常数3. 14159就是一个常量

变量就是程序为了方便地引用内存中的值 而为它取的名称。Python变量名是大小 写敏感的

a=7 “=“是赋值号

a 7

7是一个对象，可以通过变量a 引用这个 对象

id函数

Python变量有一个非常重要的性质：变 量是将名字和对象关联起来。赋值操作并 不会实际复制值，它只是为数据对象取个 相关的名字。名字是对象的引用而不是对 象本身

id是Python的内置函数，显示对象的地址

id函数用法

输入及输出函数

输入函数：input()

input从键盘输入一个字符串。‘9’表示是 一个字符串,它的ASCII吗值是57

a=input() 9

a

‘9’

输入数字

用int()函数输入数字

a=int(input()) 9

a

9

一行输入多个值

m,n=input(“请输入多个值：”).split()

请输入多个值：3 5

m

‘3’

n

‘5’

input(“请输入多个值：”)函数中的参数是

输出提示字符串

输出函数：print()

print是输出函数，参数是输出值

print(3) #输出1个数字

3

print(3,7) #输出2个数字

3 7

b,c=3,4 #输出1个数字，两个变量

print(b, c, 5) 3 4 5

井号“# ”常被用作单行注释符号，在代码 中使用“# ”时，它右边的任何数据都会被 忽略，当做是注释

不换行输出

每行输出一个值

print(3)

print(4)

print(5)

用end参数，一行输出三个值,

print(3,end=’ ‘)

print(4,end=’ ‘)

print(5,end=’ ‘)

输入三角形的三边长度3,4,5，

求这个三角形的面积

import math #引入数学库

a=int(input())

b=int(input())

c=int(input())

s=(a+b+c)/2

‘*’表示乘，math.sqrt表示开根号

area=math.sqrt(s*(s-a)(s-b)(s-c))

print(“三角角形的边长：”,a,b,c,end=’ ‘)

print(“三角角形的面积：”,area)

画五角形

import turtle

turtle.forward(200)

turtle.right(144)

turtle.forward(200)

turtle.right(144)

turtle.forward(200)

turtle.right(144)

turtle.forward(200)

turtle.right(144)

turtle.forward(200)

turtle.done()

数字类型

计算机内部用位序列表示数据，类型为这些

位序列赋予了意义。

同时，类型限制了数据的取值范围。

整数

浮点数

整数

66 66

• 175 - 175

07

SyntaxError: invalid token

0

0

二进制，八进制，十六进制

0b或0B 代表二进制

0o或0O 代表八进制

0x 或0X 代表十六进制

0b 10 2

0o10 8

0x10 16

整数可以表示很大的数

google= 10**50

google

1000000000000000000000000000000000 00000000000000000

运算符

运算符

说明

示列

运算结果

+

加法

5+10

15

-

减法

100-5

95

*

乘法

8*9

72

/

浮点数除法

100/5

20.0

//

整除

100//5

20

%

模（求余）

9%4

1

**

幂

2**3

8

浮点数

浮点数也就是小数

1.23 ，3. 14 ，-9.01

科学计数法：前面决定精度 后面决 定范围

 1.23x109就是1.23e9，

 0.000012可以写成1.2e-5。

“e”的前后都不能空，“e” 的后面要整数。

浮点数运算

浮点数运算有误差

2. 1-2.0==0. 1

False

3.8/0.7

5.428571428571429

浮点数的整除还是浮点数

round(80.23456,2)

80.23

abs(-70.5)

70.5

数学模块(math)

math库是一个数学库，包含了很多的数学常数和数 学函数

要使用math库，先要用“ import math”语句引入math 库

import math

math.pi

3. 141592653589793 >>>math.sqrt(9)

3.0

dir(math) 查看math模块的函数

函数和方法

方法是与数据对象关联的函数，是在相对应 数据对象名字空间中定义的函数

用” .”记法调用的函数也称方法

math.cos(5)

cos()是函数，cos()也称为math对象的方法

练习：求sin 30度的值

字符串类型

字符串常量是以’’或””括起来的任意文本， 比如’abc’ ，”xyz”等等。请注意，’’或””本 身只是一种表示方式，不是字符串的一部 分

字符串常量又称字符串字面量

” hello world” ‘ hello world’

”” #空字符串

‘’

多行字符串常量

‘’’hello python

人身苦短

我用python’’’

‘hello python\n 人身苦短\n

可用这种方式表示多行注解

转义字符

转义字符 描述

\ \

' ’

\” ”

\a 响铃

\b 退格(Backspace)

\n 换行

\t 横向制表符

\r 回车

\f 换页

\ooo 最多三位八进制数，例如：\12代表换行

\xyy 两位十六进制数，例如：\x0a代表换行

转义字符举例

”\12 ” #八进制

‘\n ’

”\x0a ” #十六进制

‘\n ’

”\141 ” #八进制

‘a ’

print(“\“) \

“"“

‘“‘

字符串运算符：+ ，*

“人生苦短”+” 我用Python“ ‘人生苦短 我用Python’

‘2’*3 ‘222’

type 函数是一个内置的函数，调用它就能知道 想要查询对象的类型信息

type( 1) <class ‘ int’>

type(“ python” ) <class ‘str’>

布尔类型和列表类型

布尔类型的变量只有True 、False两种值， 要么是True ，要么是False（请注意大小 写）

布尔值可通过逻辑运算符和关系运算符计 算出来。关系运算符是 < 、 <= 、 > 、 >=、 ==和！= ， 逻辑运算符是and 、or和not。

关系运算符

比较法则：

1. 关系运算符的优先级相同

2. 两个数字的比较，关系运算符按照数字大小进行比较

3. 两个字符串比较，关系运算符比较字符串中字符的Unicode 码值，从左到右 一一比较：

首先比较两个字符串的第一个字符，其Unicode码值大的字符串大。 若第一个字符相等，则继续比较第二个字符

以此类推，直至出现不同的字符为止或字符串中字符都比较完成。

逻辑运算符

逻辑量1 逻辑量2 结果 逻辑

量

1 结果

False False False

        False	True

False True False

True False False

        True	False

True True True

and 运算

逻辑量1 逻辑量2 结果 not 运算

False False False

False True True

True False True

True True True

or 运算

关系运算符实例

1<3<5 #等价于1<3 and 3<5

True

3<5>2

True

1>6<8

False

import math #sqrt是math 模块下的函数，导入math

模块

1>6<math.sqrt(9)

False

‘ Hello’> ‘world’ # ascii(‘ H’) = 72 < ascii(‘w’) = 119

False

‘ Hello’> 3 #字符串和数字不能比较

TypeError: unorderable types: str()>int()

4

x+y, x-y

加，减

从左向右

优先级和结合性实例

3+5 * 4 #先乘后加 23

5 * 3/2 #从左向右 7.5

-232 #从右向左

-512

3<5 or a>3 #从左向右

True

列表

列表可以由零个或多个元素组成，元素之间用逗 号分开，整个列表被方括号所包裹

empty_list = [ ] #空列列表

weekdays = [‘Monday’, ‘Tuesday’, \ ‘Wednesday’, ‘Thursday’, ‘Friday’]

weekdays[2] #下标从0开始 ‘Wednesday’

列表运算

weekdays[4]=5

weekdays

[‘Monday’, ‘Tuesday’, ‘Wednesday’,

‘Thursday’, 5]

[ 1,2,3]<[ 1,2,4] #比较列表大小

True

[ 1,2,3]+[‘c’,‘java’ ,‘ python’] #加法 [ 1, 2, 3, ‘c’, ‘java’, ‘python’]

[ 1]* 10 #可以用作列表初始化 [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

内置转换函数

bool

根据传入的参数的逻辑值创建一个新的布尔值

int 根据传入的参数创建一个新的整数

float 根据传入的参数创建一个新的浮点数

str

创建一个字符串

ord 返回Unicode字符对应的整数

chr 返回整数所对应的Unicode字符

bin 将整数转换成2进制字符串

oct 将整数转化成8进制数字符串

hex 将整数转换成16进制字符串

list 根据传入的参数创建一个新的列表

内置转换函数实例

bool(‘str’) True

int(3.6) 3

float(3) 3.0

ord函数和chr函数

ord(‘a’) #ASCII码值 97

ord(‘ 中’) #汉字‘ 中’的Unicode码 20013

chr(97) #参数类型为整数

‘a’

8与”8”如何转换？

bin函数， oct函数， hex函数

bin(3) #0b为默认

‘0b 11‘

oct( 10) ‘0o12‘

hex( 15) ‘0xf’

str函数和list函数

str( 123) ‘ 123’

list(‘abcd’) #传入字符串，创建列表 [‘a’, ‘b’, ‘c’, ‘d’]

表达式和表达式语句

 表达式是可以计算的代码片段，由常量、变量和运算符或函数按规则构 成代码片段，返回运算结果

 >>>7       #表达式      7

 计算表达式 cos(a(x+1)+b)/2,a等于2 ，x等于5 ，b等于3

 >>> import math

 >>> math.cos(2*(5+1)+3)/2

 -0.37984395642941066

 计算表达式：当n是奇数时为1 ，偶数时为0

 >>> n=int(input())      5

 >>> 1 if n%2==1 else 0  #条件表达式      1

 表达式语句：调用的表达式直接变为语句，如print(“abc” )

                                                    一般在调用函数和方法的时候需要表达式语句

 表达式可以以语句形式出现（单独一行），但语句不能出现在表达式中， 如赋值语句没有结果，不能被嵌套

语句

Python语言常用的有赋值、if语句和for语句。语 句通常是一行一条语句。如一行中有多条语句， 则用分号（；）分开，如语句太长要跨行时，

可以用续行符（\）跨行表示一个语句。

赋值语句

赋值语句用于将名称绑定到特定对象（值）

基本形式是“变量=值”的形式

“= ”不是运算符，没有优先级和结合性

【例 3-1】 基本赋值语句

x=1

y=2

k=x+y

print(k)

程序输出：

3

多变量赋值

x,y=4,8

print(x,y)

4 8

赋值和“+ ” 、“- ” 、“ * ”和“\”组合

i=2

i*=3

i

6

j=5

j*=3+1 # j=j*(3+1)

j 20

if语句

if 逻辑表达式: 语句块1

else:

语句块2

x=int(input())

if x%2==0:

print(“偶数”)

else:

print(“奇数”)

计算水费

为鼓励居民节约用水，自来水公司采取按用水量阶梯

式计价的办法，居民应交水费y（元）与月用水量x

（吨）相关：当x不超过15吨时，y=4x/3；超过后，

y=2.5x− 17.5,小数部分保留2位。请编写程序实现水费

的计算。

x=float(input())

if x<=15:

y=4*x/3

else:

y=2.5*x-17.5

print(“水费 = {:.2f}”.format(y))

for语句

for variable in 列表:

语句块

for后面的变量先被赋于列表的第一个值，

并执行下面的代码块。然后变量被赋于列表 中的第二个值，再次执行代码块。该过程一 直继续，直到穷尽这个列表。语句块缩进表 示它是属于for代码块

【例 3-3】遍历列表

for i in [1,2,3,4]:

print(i)

输出：

1

2

3

4

range函数

range(start ，stop ，step)。

start:计数从start开始。默认是从0开始。 例如range（5）等价于range（0 ，5）

stop: 计数到stop结束，但不包括 stop。

例如：list(range（0 ，5）)是[0, 1, 2, 3, 4] 没有5

step：步长，默认为1 。例如：range（0， 5）等价于range(0, 5, 1)

用range函数产生列表

list(range(10)) # 从 0 开始到 10 ，不包括10

  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ] 

list(range(1,11)) # 从 1 开始到11

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

list(range(0, 30, 4)) # 步长为 4

[0, 4, 8, 12, 16, 20, 24, 28]

list(range(0, -10, -1)) # 步长为负数

[0, -1, -2, -3, -4, -5, -6, -7, -8, -9]

效果等价

Range前有没有list,对for语句是等价的

for i in list(range( 1,5)):

  print(i,end=" ")

print()

for i in range( 1,5):

  print(i,end=" ")

输出都是 ：1 2 3 4

sum函数

它可以求列表的和

如何求1+2+3+…+10的和？

sum([1,2,3,4,5,6,7,8,9, 10])

55

或：

sum(range( 1, 11))

【例 3-4】输入n（ n>=10）,求

1+2+…+n之和。

n=int(input())

s=sum(range(n+1))

print(s)

【例 3-5】输入n（ n>=5）求n!

n=int(input())

fac= 1

for i in range( 1,n+1) :

fac=fac*i

print(fac)

列表元素可以是表达式

a=3

b=7

lst=[a+2,b]

lst

[5,7]

for循环和列表结合新列表

lst=[i+5 for i in [1,2,3,4 ]]

它等价于下面语句块

for i in [1,2,3,4]:

lst=lst+[i+5]

lst

[6,7,8,9]

lst=[i+5 for i in [1,2,3,4] if  i%2==1]

它等价于下面语句块。

lst=[]

for i in [1,2,3,4]:

if i%2==1:

lst=lst+[i+5]

列表推导式

列表推导式是从一个或者多个列表快速简洁 地创建列表的一种方法，又被称为列表解析。 它可以将循环和条件判断结合，从而避免语 法冗长的代码，同时提高程序性能。

[ expression for item in 列表 ]

输出表达式   变量

nl = [2*number for number in [ 1,2,3,4,5]]

nl

[2, 4, 6, 8, 10]

带条件的列表解析

[expression for item in 列表 if condition]

nl=[number for number in range( 1,8) if number % 2 == 1] 可选

number_list [ 1, 3, 5, 7]

级数求和就变成如何写通项公式a i

【例 3-6】【例 3-7】求和

求1+1/2+…+1/20之和

print(sum([1/i for i in list(range(1,21))]))

通项公式: ai = 1/i

求 1-1/2+1/3-1/4+…之前n项和(n>= 10)

n=int(input())

print(sum([1/i if i%2== 1 else -1/i for i in \

range(1,n+1)]))

列表推导式的if条件和条件表达 式同时使用

【例 3-8】求 1- 1/3+1/5- 1/7+…- 1/47+1/49

[i if i%4== 1 else – i for i in range( 1,50) \

      if i %2== 1]

[ 1, -3, 5, -7, 9, - 11, 13, - 15, 17, - 19, 21, -23, 25, -27, 29, -31, 33, -35, 37, -39,41, -43, 45,

-47, 49]

print(sum([1/i if i%4== 1 else - 1/i for i in \

range( 1,50) if i%2== 1]))

求 6+66+666+…+666…666

生成5个6

int(‘6’*5) 66666

n=int(input())

print(sum([int(‘6’*i) for i in range( 1,n+1)]))

格式化输出

当输出计算结果时，经常需要控制它的显示形式

format()函数是Python的内置函数，用来设置输出 格式，返回值是字符串

一般形式：”需格式化字符串” .format(参数表）

name=“John”

“ Hello,{:>6s}” .format(name)

’ Hello, □□John’

{:6s}是格式限定符，描述参数name如何显示, 普通字符串原样输出，□表示空格

{}中不写格式，则原值输出

格式限定符举例

输出

“{:d}” .format(24)

“{:b}”.format(45)

“{:o}”.format(24)

“{:x}”.format(24)

“{:5d}”.format(24)

“{:4d}”.format(24879)

“{:.2f}”.format( 1.2449)

“{:.2e}”.format(53.2453)

“{:6.2f}”.format( 1.2449)

“{:9s}”.format(“hello”)

“{:>9s}”.format(“hello”)

多个参数格式化输出

x=3. 14159

y=2x3

print(“{0:.2f} {1:.2f}”.format(x,y))

3. 14 18.85

0和1表示format函数中的第一和第二个参 数，.2f表示小数部分保留两位，四舍五 入

a=3； b=4.56

print(“{} {}”.format(float(a),b))

字符串格式化

s=”hello”

“{}”.format(s)

‘hello’

“{:10s}”.format(s)

‘hello ‘

“{:^ 10s}”.format(s)

‘ hello ‘

“{:>10s}”.format(s)

‘ hello’

华氏-摄氏温度转换表

输入2个正整数lower和upper（lower<upper<100），请输出一张取值范围为[lower ，upper) 、且每次增加2华氏度的华氏-摄氏温度转换表，小数
部分保留一位。温度转换的计算公式：C=5×(F−32)/9 ，其中：C表示摄氏温度，F表示华氏温度。

lower,upper=input().split() # 一行输入两个数，是字符串类型
lower,upper=int(lower),int(upper) # 字符串变成整数
for i in range(lower,upper,2):
print(i,”{:5. 1f}”.format(5*(i-32)/9))
#print(“fahr={0:d} Celsius={ 1:5. 1f}”.format(i, 5*(i-32)/9))

程序输入：

30 40

程序输出：

30 - 1.1

32 0.0

34 1.1

36 2.2

38 3.3

问题求解与算法

Overview

算法的概念
算法的三种结构
算法的发现
常用算法
算法的方法学

4.1 问题求解过程

算法的概念

为解决问题而采用的方法和步骤就是算法。
算法的质量直接影响程序运行的效率。
根据图灵理论，只要能够被分解为有限步骤的问题就可以被计算机执行。
算法的正式定义：算法是求解问题步骤的有序集合，它能够产生结果并在有限时间内结束。

算法的特性

确定性：相同的输入，通过同一算法的计算，输出结果应该是相同的，即不会由于在不同时间、不同地点、采用不同计算机计算，会导致不同结果。
有穷性：算法中的步骤应该是有限的，否则计算机就会永远无休止地执行程序。但是，即便是在某台计算机上运行了长达数年，只要能够结束，也称为算法。
有效性：算法中的每一个步骤都应该被有效地执行
可有零个或多个输入
有一个或多个输出

算法的分类

数值计算：数值计算主要是针对特定数学模型求出数值解，而数学本身通常更关注的是解的存在性（和唯一性）。比如方程的求根、方程组的求解、概率与统计的计算、微分方程求数值解等，主要处理“连续数据”问题的解。
非数值计算：计算机处理符号、表格的能力使得计算机大大拓展了其应用领域，比如图书管理、物流管理等。这些问题的重要特征是用“离散数据” 描述问题。解决这类问题的算法归为非数值计算。
计算机的诞生，主要是为解决数值计算问题而设计，这大概也是“计算机”名称的由来。但是非数值计算的应用增长远远超过数值计算类的应用增长。

4.2 算法的三种结构

根据结构化程序设计，所有的程序都由三种结构构成：

顺序结构
最简单的一种结构，它使计算机按照命令出现的先后顺序依次执行
分支结构
在程序执行过程中 ，根据设定的条件来决定程序的执行方向，即有选择地执行部分命令
循环结构
使计算机按照设定的条件重复执行一组命令

8

顺序和分支结构

9

循环结构

10

while结构的Python实现

while 条件：

 语句块1    #书写缩进             

                

                 

11

do while 结构的Python实现

while True:
……
break
……

break语句跳出while语句

12

算法举例

求两个正整数A和B的最大公约数（GCD）
算法一：逐个验证方法
算法二：欧几里德（Euclid）方法

13

逐个验证方法举例

设A=6 B=9

①A=9 B=6

②i=B (i=6)

③A%i !=0

④i=i-1 (i=5)

⑤ A%i !=0

⑥i=i-1 (i=4)

⑦ A%i !=0

⑧ i=i-1 (i=3)

⑨ A%i==0 && B%i==0

⑩最大公约数就是i(=3)

第一步：比较A和B这两个数：

A设置为较大的数，B为较小的数；

第二步：i从B到1循环

执行第三步；

第三步：如果i能够整除A和B，则最大公约数就是i，程序结束;否则重复进行第二步、第三步。

14

算法一：逐个验证方法

a=int(input())
b=int(input())
if b>a:
a,b=b,a
for i in range(b,0,-1):
if b%i==0 and a%i==0:
print(“最大公约数是:”,i)
break #跳出for循环

15

欧几里德（Euclid）算法

第一步：比较A和B这两个数：A设置为较大的数，B为较小的数；

第二步：A除以B，得到余数C；

第三步：如果C等于0，则最大公约数就是B，程序结束; 否则将B赋值给A，C赋值给B；

重复进行第二步、第三步。

计算过程举例：

设A=18 B=30

①A=30 B=18

②C=A%B=12

③A=18 B=12

④C=A%B=6

⑤A=12 B=6

⑥C=A%B=0

⑦最大公约数就是B=6

16

Euclid 算法的Python实现

a=int(input())
b=int(input())
if b>a: a,b=b,a
c = a % b
while c > 0:
a, b = b, c
c = a % b
print(“最大公约数是“,b)

用while True结构求最大公约数

形式化的算法描述：
计算两个数m和n的余数r；
如果余数r不为0，则以n和r作为新的m和n，
回到1重复计算；
3. 否则n就是余数

m, n = input(“请输入两个整数：”).split()
m,n=int(m),int(n)
while True:
r = m % n
if r != 0:
m,n = n, r
else:
break
print(“最大公约数是{}”.format(n))

4.3 算法的表示和发现

算法的表示是为了把算法以某种形式加以表达，因此一个算法的表示可以有不同的方法，
本章算法表示用：
流程图
Python代码

19

流程图符号

含义
符号
说明
开始/结束 表示流程图的开始和结束
处理 用于描述需要执行的处理内容
条件分枝 表示if语句等条件分枝处理

在符号中描写具体的条件
循环 表示循环处理，使用上下框

围住需要循环处理的部分
输入/输出 输入和输出
预定义的处理 用于表示事先定义好的函数
流程指向 指向下一步动作

20

用Python语言描述求n!算法

n=int(input())
fac=1
for i in range(1,n+1):
fac=fac*i
print(“n!等于:”,fac)

算法的发现

发现算法具有很大的挑战性
“中国邮递员问题”：
不但要选择路径，而且要确保这个选择的路径是最短的。
解决问题的4个步骤：
理解问题
设计一个解决问题的方案
执行这个方案
检验这个方案

4.4算法举例

基本算法
迭代
递归
排序
查找

基本算法1——输入正整数，求它的值

解题思路：

不断减一，减一的次数加1

为零时，减一的次数就是它的值

n=int(input())

#如输入5

count=0

while n>0:

 n=n-1

 count=count+1

print(count)

n的值
减的次数 count
5
0
4
1
3
2
2
3
1
4
0
5

基本算法2—-求最小值 练习：求最大值

data=[6,15,4,2,8,5,11,9,7,13]

min_index=0
for i in range(1,len(data)):
if data[min_index]>data[i]:
min_index=i

print(min_index,data[min_index])

基本算法3—–累积,累加

输入 n,m(n<m)
求：
n*(n+1)(n+2)……m

练习，如何求：
n+(n+1)+(n+2)+…m

n=int(input())
m=int(input())
c=1
for i in range(n,m+1):
c=c*I
print(c)

基本算法4——-求正整数的各位之和

n=int(input())

lst=[]

while n>0:

lst=[n%10]+lst

n=n//10

print(sum(lst))

456=4102+5101+6*100
重复 n%10,n//10 运算
直到n为0
456%10=6 456//10=45
45%10=5 45//10=4
4%10=4 4//10=0
各位之和：
6+5+4=15

迭代

迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值
用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

计算log2x

例4-2 计算log2x
x = int(input())
count = 0
while x >1:
x //= 2
count += 1
print(count)
输入：32
输出：5
输入：31
输出：4  

正整数进制转换 n是迭代变量

n=int(input())

lst=[]

while n>0:

lst=[n%2]+lst

n=n//2

print(lst)

n
n%2

递归

函数调用自身的编程技巧称为递归

递归做为一种算法在程序设计语言中广泛应用。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要终止条件和递归条件。当终止条件不满足时，递归前进；当终止条件满足时，递归返回。编写递归函数时，必须告诉它何时停止递归，直接返回结果，从而避免形成无限循环。

Python函数的定义

内置函数

len(“hello”)
5
len([3, 7.8 ,”good”])
3
函数是完成特定功能的程序段。它们允许你给程序段命名一个名字，这是函数定义。然后你可以在你的程序的任何地方使用这个名称运行这个语句块，这被称为调用函数

自定义函数
def 函数名(参数表)：
函数体

如定义函数：y=x2+1
def f(x):
value=x**2+1
return value
n=int(input())
y=f(n)
print(y)

斐波那契数列

斐波那契数列是一个经常使用递归方式定义的常用数学函数.
fib(0)= 1 n=0 (1)
fib(1)= 1 n=1 (2)
fib(n)=fib(n-1)+fib(n-2) n>=2 (3)
公式（1）和公式（2）是终止条件，公式（3）是递归条件

例 6-17 斐波那契数列递归程序

def fib(n): #假定n是正整数返回第n+1个斐波那契数
if n == 0 or n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
print(fib(4))

fib(4)递归计算过程

                       fib(4)
            fib(3)      +          fib(2)
     fib(2)  +   fib(1)

fib(1) + fib(0)

fib(0)=fib(1)=1

排序

排序是将一组原始数据按照递增或递减的规律进行重新排列的算法。

选择法排序思想（从小到大）

在n个数的表中找到最小的数并与第一个位置的数交换，然后在余下的n-1个数中找到最小的数与第二个位置的数交换，直到对所有数据全部扫描过。

 冒泡法排序思想（从小到大）

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

选择排序流程图和程序

data=[6,15,4,2,8,5,11,9,7,13]

for i in range(len(data)-1):

minindex=i

for j in range(i+1,len(data)):

    if data[minindex]>data[j]:

        minindex=j

data[i],data[minindex]=data[minindex],data[i]

#print(data)

print(data)

冒泡排序算法

冒泡排序是一种简单的排序算法
冒泡排序算法（升序）：
在数据集中依次比较相邻的2个数的大小，如果前面的数大，后面的数小，则交换；n个数需要比较n-1次，其结果是将最大的数交换到最后位置（下标n-1）。
从剩下的未排序数据中（n-1个）重复上述步骤，n-1个数需要比较n-2次，其结果是将次大的数交换到倒数第2个位置（下标n-2）。
…
n-1.比较剩下2个数，如果前面的大，后面的小，则交换。
结束。
如果是降序排序的话，则只要将上述算法中的交换条件改成前面的数小，后面的数大即可。

冒泡排序过程

[6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
[6, 4, 2, 8, 5, 11, 9, 7, 13, 15]
[4, 2, 6, 5, 8, 9, 7, 11, 13, 15]
[2, 4, 5, 6, 8, 7, 9, 11, 13, 15]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
在比较交换过程中，大的数逐步往后移动，相对来讲小的数逐步向前移动；如同水中的气泡慢慢向上升。

例4-25 冒泡排序程序

data=[6,15,4,2,8,5,11,9,7,13]

#从0到8，外循环共len(data)-1次

for i in range(len(data)-1):

for j in range(len(data)-i-1): 

    if data[j]>data[j+1]:

        data[j],data[j+1]=data[j+1],data[j]

print(data)

练习:程序输出值

def bubble_sort(nums):

这个循环负责设置#冒泡排序进行的次数

for i in range(len(nums) - 1):
    for j in range(len(nums) - i - 1):  # j为列表下标
        if nums[j] > nums[j + 1]:
            nums[j], nums[j + 1] = nums[j + 1], nums[j]
    if(i==3):print(nums[4])
return nums

bubble_sort([45, 32, 8, 33, 12, 22, 19, 97])

查找

在一个列表中查找一个特定的数据，若找到则返回它所在的位置。对于列表数据简单的方法有两种：
顺序查找
从列表的第一个数据（或叫做元素）开始，但给定的数据和表中的数据匹配时，查找过程结束，给出这个数据所在表中的位置或明确表中没有该数据。
折半查找
也叫二分法，对已经大小有序的列表，可以进行折半查找。从列表的中间位置开始，比较要查找的的数据，判断是在前半部分还是后半部分。每次比较至少可以排除一半的范围，是效率很高的方法。
折半查找算法可以用迭代思想也可以用递归思想实现。

折半查找

例4-23 二分搜索代码

a=[5,16,39,45,51,98,100,202,226,321,368,444,501]

x = int(input())

found = -1

left = 0 #第一个元素下标

right = len(a)-1 #最后一个元素下标

while left<=right:

mid = (left + right) // 2

if a[mid] > x:

    right = mid - 1

elif a[mid] < x:

    left = mid + 1

else:                     # a[mid]==x

    found = mid

    break

print(found)

4.5 算法的方法学

贪心法
分治法
*动态规划

贪心法 （Greedy Algorithm）

贪心算法的基本思想是从小的方案推广到大的解决方法。它分阶段工作，在每一个阶段选择最好的方案，而不考虑其后的结果如何。
贪心法主要用于求解最优问题，但它已经发展成为一种通用的算法设计技术：核心是：
可行性——每一步选择必须满足问题的约束；
局部最优——它是当前可选择的方案中最优的；
不可取消性——选择一旦做出，在算法的其后步骤中不能被取消。
贪心法不能确定得到的最后解是最优的，也不能用于求解最大或最小问题。在算法的效率上，贪心法快速，程序实现需要的内存开销也较小。但遗憾的是，它们往往是不正确的。然而一旦被证明是正确的，其执行效率和速度有很大的优势。

找零钱问题

假设只有 1 分、 2 分、五分、 1 角、二角、 五角、 1元的硬币。在超市结账 时，如果 需要找零钱， 收银员希望将最少的硬币数找给顾客。那么，给定 需要找的零钱数目，如何求得最少的硬币数呢？
先用最大面值换
再用次大面值换
。。。。。。
最后用最小面值换

最少硬币的程序

coins=[100,50,20,10,5,2,1] #100表示100分，既1元
qty=[] #存放各类零钱的数量
money=int(input(“请输入要换零钱的数量，以分为单位：”))
for i in range(len(coins)):
qty=qty+[money//coins[i]]
money=money%coins[i]
print(sum(qty))

贪心策略失效

硬币种类=[25分,21分,10分,1分] , 换63分，要求硬币数最少

使用贪心策略，63 = 25 * 2 + 10 * 1 + 1 * 3 ， 共 2 + 1 + 3 = 6枚硬币
最优的策略是，63 = 21 * 3，共 3 枚硬币
贪心策略严重依赖于货币的币值设计。

补充：霍夫曼编码是一种贪心算法

假定下列6个字母A，B，C，D，E，F在文章中出现的频率分别是0.05，0.10，0.15，0.20，0.22，0.28.
（1）构建一颗霍夫曼树：将上述6个字母设为结点（叶子），并将频率作为各节点的权。选取权最小的两个结点构建一颗二叉树，新建二叉树的顶点的权为两个儿子的权之和。最后得到一颗具有最小带权路径长度的二叉树。
（2）将霍夫曼树从根开始沿着路径给节点进行左0右1编码。
（3）从根到各个叶子结点的0-1编码就是霍夫曼码。

分治法 （Divide and Conquer ）

基本思想就是，将一个较大规模的问题分解为若干个较小规模的子问题，找出子问题的解，然后把各个子问题的解合并成整个问题的解。
分治法的分（Divide）是指划分较大问题为若干个较小问题，递归求解子问题；分治法的治（Conquer）是指从小问题的解构建大问题的解。
分治法的实现很可能可以采用递归的形式

金块问题: （挑出最重和最轻的两个金块）
n=8时，普通方法需要的比较次数：(n-1)+(n-2) = 13。
分治法的比较次数：

               8

   4                     4

2 2 2 2

L H L H L H L H

 L  H                L  H

             L  H

比较次数

4

4

2

10

n=16时，普通方法需要的比较次数： (n-1)+(n-2) = 29。
分治法的比较次数：10+10+2 = 22

C(n) = 2 C(n/2) + 2 (当n>2) = 3n/2 -2 (当n为2的幂)

金块问题程序

def min_max(a):
if len(a)==1:
return (a[0],a[0])
elif len(a)==2:
return (min(a),max(a))
else:
m=len(a)//2
lmin,lmax=min_max(a[:m])
rmin,rmax=min_max(a[m:])
return (min(lmin,rmin),max(lmax,rmax))

a,b=min_max([3,8,9,4,10,5,1,17])
print(“最小值是”,a,”，最大值是”,b)

*动态规划法 (Dynamic Programming）

动态规划被描述为：如果一个较大问题可以被分解为若干个子问题，且子问题具有重叠，可以将每个子问题的解存放到一个表中，这样就可以通过查表解决问题。
核心思想是以空间换时间！

两个方向访问单个数据

用[ ]来访问序列中的一个元素。

比如访问字符串中的某个字符：

prompt = ‘hello’

print(prompt[0])

输出：

h

print(prompt[4])

输出：

o

假设序列中的元素个数是n，下标的有效范围是0到n-1，或者-1到-n。

如果下标的绝对值大于n-1，则会发生下标越界错误。

如果下标的值为负数，表示从序列的最后一个元素往前引用，比如：

prompt = ‘hello’

print(prompt[-1],prompt[-4])

输出

o e

访问一部分数据

如果要访问序列中的一部分元素，可以使用切片（slice）。切片通过冒号分隔两个下标来实现。比如访问列表中的一部分：
a = [2,3,5,7,11,13]
print(a[1:3])
输出
[3,5]
切片a[1:3] 表示包含从第1个下标（1）开始到第2个下标（3）前面的下标（2）为止的部分元素的子序列（列表）。

切片的其他表示方式

a = [2,3,5,7,11,13]

切片使用负的下标访问

a[1:-3]

结果：[3,5]

切片省略第2个下标，表示从第1个下标的元素开始到最后一个元素的切片。

a[2:]

结果：[ 5, 7, 11, 13]  

第1个下标为0时，可以省略。

a[:3]

结果：[2, 3, 5]

a[:-2]

结果：[2, 3, 5, 7]

切片使用第3个参数，该参数表示切片选择元素的步长。

a[0:5:2]

结果是: [2, 5, 11]

切片使用第3个参数为负数时，表示逆向取切片。

a[-1:0:-1]

结果是：[13, 11, 7, 5, 3]

a[::-1]

结果是：[13, 11, 7, 5, 3, 2]

*字典的创建、访问、增加、修改

直接用[ ]运算符，用<字典> [键]的形式，访问键所对应的数据。

score = {‘张三’:78, ‘李四’:92}
print(score[‘张三’]) #访问score中键为’张三’的数据

score[‘李四’] = 89 #把score中键为’李四’的数据修改为89

score[‘王五’] = 100 #score中没有键为‘王五’的元素，则增加一项，键为’王五’,数据为100。

print(score）

输出：

{‘张三’: 78, ‘李四’: 89, ‘王五’: 100}

*用动态规划求斐波那契数列

#用动态规划方法优化

pre={0:1,1:1}
def fib(n):
if n in pre: #可以用in检查字典中是否有n这个关键字
return pre[n]
else:
newvalue=fib(n-1)+fib(n-2)
pre[n]=newvalue #增加字典的条目
return newvalue
print(fib(100))