八年级上册¶

第一单元 用计算机程序解决问题¶

第4节 迭代算法及应用¶

一、迭代算法¶

In [1]:
# 现场赛计分程序-求评委计分总和
lst = ['78.5', '77.3', '79.1', '78.0', '77.0']
s = 0
for num in lst:
    s = s + float(num)
print(s)
389.9

【体验活动】迭代算法生成分形图¶

  • 1)运行单元格内容,根据提示输入迭代次数,等待运行结果。
  • 2)多运行几次,每次输入不同的迭代次数,比较生成图像的差别(图片可用“右击-另存为”保存下来)。
  • 3)思考与交流:
  • ○查看源代码的注释,找出该表示迭代过程的语句。
In [7]:
# 分形叶子
import numpy as np
import matplotlib.pyplot as pl
import time

# 蕨类植物叶子的迭代函数和概率
eq1 = np.array([[0,0,0],[0,0.16,0]])
p1 = 0.01
eq2 = np.array([[0.2,-0.26,0],[0.23,0.22,1.6]])
p2 = 0.07
eq3 = np.array([[-0.15, 0.28, 0],[0.26,0.24,0.44]])
p3 = 0.07
eq4 = np.array([[0.85, 0.04, 0],[-0.04, 0.85, 1.6]])
p4 = 0.90

def ifs(p, eq, init, n):
    # 迭代向量的初始化
    pos = np.ones(3, dtype=np.float64)
    pos[:2] = init # pos=[x,y,1]

    # 通过函数概率,计算函数的选择序列
    p = np.add.accumulate(p) # 累加,[p1,p1+p2,p1+p2+p3,...]
    rands = np.random.rand(n) # array,0~1的随机数,长度为10
    select = np.ones(n, dtype=np.int64) # 想要得到的效果:select[i]=m表示第i个序列为m(0<=m<=len(p)-1)
    for i,x in enumerate(p[::-1]): # p[x:y:z]表示从x遍历到y,间隔为z。p[::-1]表示将前两个省略,间隔为-1,前两个默认为p[len(p)-1]到p[0]
        select[rands<x] = len(p)-i-1 # i=0时,x=p[len(p)-1]一定为1,因此第一步所有位置都赋为 len(p)-1。i=1时,x小于1,有一部分会满足rands<x。这一部分被赋值为 len(p)-2。这两次迭代的差集会永远被赋值为 len(p)-1不会变,则这个差集上的所有序列永远选择了第 len(p)-1 个迭代函数。

    # 结果的初始化
    result = np.zeros((n,2), dtype=np.float64)
    c = np.zeros(n, dtype=np.float64)

    for i in range(n):
        eqidx = select[i] # 所选函数的下标
        temp = np.dot(eq[eqidx], pos) # 迭代关系
        pos[:2] = temp # 更新迭代向量

        # 保存结果
        result[i] = temp # 第i次的结果:[x,y]
        c[i] = eqidx # 第i次的选择

    return result[:,0],result[:,1],c

times =int(input('输入迭代次数(1000-500000):'))
start = time.time()
x, y, c = ifs([p1,p2,p3,p4],[eq1,eq2,eq3,eq4], [0,0], times)
print(time.time() - start)
pl.figure(figsize=(6,6))
pl.subplot(121)
pl.scatter(x, y, s=1, c="g", marker="s", linewidths=0) # s=1表示散列点大小为1,c="g"表示点的颜色为green,marker="s"表示点的形状为正方形(速度最快)
pl.axis("equal")
pl.axis("off")
pl.subplot(122)
pl.scatter(x, y, s=1,c = c, marker="s", linewidths=0) # c=c表示按照每次迭代选择的序列来作为颜色,方便知道四个函数产生的点的大概位置
pl.axis("equal")
pl.axis("off")
pl.subplots_adjust(left=0,right=1,bottom=0,top=1,wspace=0,hspace=0)
pl.gcf().patch.set_facecolor("white")
pl.show()
输入迭代次数(1000-500000):500000
1.7313306331634521

二、迭代算法应用¶

In [9]:
# 1.空地填砖问题
a = int(input('输入整数a:'))
b = int(input('输入整数b:'))
while a % b != 0:
    a, b = b, a % b
print('最大公因数是{}。'.format(b))
输入整数a:12
输入整数b:68
最大公因数是4。

实践活动:输出斐波那契数列¶

In [21]:
# 也是兔子繁殖问题
# 月份: 1    2     3     4     5     6    7    8
# 兔子: 1    1     2     3     5     8   13   21
a, b = 1, 1
n = int(input('n:'))
while n > 2:
    a, b = b, a + b
    n = n - 1
print(b)
n:10000
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
In [ ]: