山东省高中信息技术学业水平考试试题网 - 数据与计算|信息系统与社会|数据与数据结构|网络基础|数据管理与分析|移动应用设计|三维设计与创意|开源硬件项目设计|算法初步|智能系统初步

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 578|回复: 0
收起左侧

第十一讲 体验计算机解决问题的过程

[复制链接]

273

主题

672

帖子

214748万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
2147483647
QQ
发表于 2019-12-3 20:50:28 | 显示全部楼层 |阅读模式
第十一讲 体验计算机解决问题的过程
学习目标8 q! [' F7 a" y) I2 ?" L
体验计算机解决问题的过程。7 z$ _# l0 l3 d  t9 M. w# u" {
学习内容/ Y( j) ^! H/ W* F' a: O, M; u* e( ^
      在现实生活中,我们经常需要对数据进行统计,分析。当数据量不多时,我们可以采用人工方法来处理;然而,当数据量变多时,我们运用计算机来解决问题将是一种更高效,更便捷的方法。
# {" J3 S7 e+ \) }$ t# ?0 y人工解决问题的过程6 i/ n. w: x7 K4 c5 F+ g7 J$ `. R& t1 g
      采用人工方法来解决问题,首先需要明确所要解决的问题和给出的条件,然后再根据已有的经验和知识确定解决问题的方法,从而解决问题。- }. Y) W$ t9 F6 A  }1 u) C$ u
探究活动$ ]- Y/ `( b$ K4 r5 C  H/ ~- n" `+ m
      如何设计从A市到B市耗时最少的旅行路线方案呢?我们从铁路公司、各航空公司和汽车客运公司网站得知,直达B市的交通工具只有火车和汽车两种,出发地有B1,B2,…,Bk市(没有A市),从A市出发到B1,B2,…,Bk市的交通工具有飞机、火车和汽车三种,这样从A市经B1,B2,…,Bk市到B市的交通情况如下图所示。8 U7 `; H, L* }% k1 w; i

, P4 Q+ A7 z4 z      由于从A市到B1,B2,…,Bk市有不同的交通工具,每一种交通工具又有不同的班次,因此从A市出发到中转城市B1,B2,…,Bk市就有M1、M2,…,Mk种班次。同样,从中转城市B1,B2,…,Bk市到B市也有不同的交通工具,每一种交通工具有不同的班次,因此从中转城市B1,B2,…,Bk市到B市就有N1,N2,…,Nk种班次。于是从A市经B1,B2,…,Bk市到B市的交通班车(班机)数共有:, t$ c+ N( q, A
S=M1×N1+M2×N2+…+Mk×Nk
) _* [  L  I- o4 x& D6 r4 g      寻找从A市到B市耗时最少的旅行路线问题就转化为在S种联运班次中找到一种耗时最少的联运班次。这样就需要遍历每一个班次进行比较,人工方式找到能够中转且等待时间和行驶时间最少的班次,工作量极其浩大!
; o; ~) l$ S& ]' w  X" [$ Q6 b假设从A市到B市的中转城市只有B1,B2市,从A市经B1,B2市到B市的交通情况如表3-2和表3-3所示。4 O! w! O0 ], {9 O  g

3 X) t8 ~! y4 L. k( i- O6 L      于是,从A市经B1市到B市的联运班次有7×9=63班;从A市经B2市到B市的联运班次有12×9=108班,合计为S=63+108=171班。然后在171班次中找到能够中转且等待时间加上行驶时间最少的联运班次,如下图所示。
9 v, t1 x+ ^! |  w! O" s: o, q" N0 S
      采用以下的思路求解耗时最少的联运班次问题:
: i" o' R6 y$ |0 I9 @5 y4 p: g      (1)找出能够中转的从A市经B1市到达B市的联运班次,并计算所用的时间。
) t: B/ f9 q& f! ~  o      (2)找到能够中转的从A市经B1市到达B市的联运班次中耗时最少的联运班次.
0 A3 p& Y7 a- _      (3)找出能够中转的从A市经B2市到达B市的联运班次,并计算所用的时间。% ~6 w5 k% S( \  M
      (4)找到能够中转的从A市经B2市到达B市的联运班次中耗时最少的联运班次。4 o. F7 y' f* g# I0 Y
      (5)取两条线路中耗时最少的联运班次为最佳旅行路线。
8 v# |1 _% o- H1 h      上述问题中,假如中转城市很多,交通班次也很多,找出耗时最少路线的工作量会非常大,若用人工穷举遍历,其效率就会很低。0 ?, D6 O& r/ c
计算机解决问题的过程
9 e' V& T5 i& W; S% g* T      当数据量很大,人工处理效率很低时,我们可以借助计算机,通过编写计算机程序解决问题。编写计算机程序解决问题要经过分析问题,设计算法,编写程序,调试运行程序等若干个步骤。4 R% B) T! ~! M! g6 }+ z* s: L! `
      1.分析问题: s0 z5 x4 S0 a' d7 H/ L
      在利用计算机解决问题之前,我们首先要分析问题的需求情况、已知条件和需要解决的问题。7 X4 O+ m0 h: p8 R) E$ L+ K4 M& D
      在从A市到B市耗时最少的旅行路线问题中,在不知道有多少个中转城市和每个城市有多少班车(或飞机)的情况下,我们可以利用大数据挖掘技术中的爬虫程序(参见配套学习资源包“第三章\课本素材\程序3-1”)到铁路网站、各航空公司和汽车客运公司网站获取从A市经中转城市B1,B2,…,Bk市到达B市的交通班次信息,经过数据清洗,形成结构化的数据存储为Excel文件。
+ {& l0 I) @0 G  S8 ~; s" w
( b  t% b; a& M+ {3 u' l: d! H! x7 i" K: \$ z8 g3 O
      2.设计算法- ~3 x* i7 X. h# O- ~, f
      问题分析清楚后,需要给出解决问题的详细方法和步骤,这一过程称为设计算法。
/ e8 ~( q! D) z3 P' F0 _5 L      例如,对于从A市到B市耗时最少的旅行路线问题,根据获取的从A市到B市的中转城市B1,B2,…,Bk的班次,以及各城市各交通班次的发车时间和行驶时间等信息,采用以下的思想找出耗时最少的联运班次问题,即算法如下:
) ^0 Q4 \9 f& l5 E( y2 q1 N      (1)分别找出能够中转且中转等待时间不小于1小时的从A市经B1,B2,…,Bk市到达B市的联运班次,并计算所用的时间。- f- t/ H: `; O
      (2)分别找到能够中转的从A市经B1,B2,…,Bk市到达B市的联运班次中耗时最少的联运班次,共k条线路。$ f" J: Q0 }) T4 F5 b1 r0 H
      (3)取k条线路中耗时最少的联运班次为最佳旅行路线。
* `& p3 e8 h8 s) e# i      3.编写程序
7 u, s5 ?2 Z6 @6 z/ Z8 w      有了清晰可操作的算法描述,就可以选择一种计算机语言工具来编写程序,实现算法。一般来说,只要算法确定,对计算机程序设计语言的选择没有特别的限定,通常根据问题的特性和编程人员对语言的熟悉程度来选定编写程序。
- s4 }! w7 ]3 p4 w' Z: V      Python语言编写从A市到B市耗时最少的旅行路线问题的算法的程序可参见配套学习资源包“第三章\课本素材\程序3-1”。其中,找出能够从A市经Bi(i=1,2,…,k)市到达B市的中转联运班次,并计算所用的时间以及找到耗时最少的联运路线的关键程序段如下。3 Z: D  h# v* b% N! ?. e
( q* \! U) g9 P1 M' J! P
      4.调试运行程
: t: d% B' l, v; c! q3 k) i      程序编写完成以后,再通过键盘把程序输入计算机中运行,检查程序能否按预想的效果行,这一过程称为程序的调试运行。计算机只能识别程序设计语言中所规定的语法规,如果编写程序时与规则不一致,哪怕是一个标点符号出错,也会因程序出错而中断运行。此时,我们可以根据计算机提示的出错信息修改程序,重新调试运行。由于 Python是解标程序,因此它的调试是在运行过程中逐行进行的。
0 t9 |( G6 x* N1 x! k      当程序能够顺利运行以后,我们还需要对程序运行的结果进行检查。因为如果程序语句符合语法规则,而程序中却有逻辑或计算方法等错误,计算机是检查不出来的。因此,如果结果不合理,还要对程序甚至算法进行修改,直到程序的功能符合设计要求为止。; {9 }% U& f- s3 F: e/ P+ z
      打开配套学习资源包“第三章课本素林程序3-1”,调试并运行程序3-1,找出从A市到B市耗时最少的旅行路线问题的结果,如图3-7所示
) A' F3 A  z- k3 C9 a5 k3 {/ n, |+ b9 ~& U
耗时最少的旅行路线问题的python代码:
0 T$ B7 a$ g) P+ D' \3 a0 z! z  Z
  1. import xlrd
    . C" Q- w3 o* j
  2. ms=[]3 b" O4 F9 D; S
  3. ra=[]. }& ^$ K4 z5 n. ^) }
  4. rb=[]+ F& o7 c. H. |, B
  5. for k in range(1,4):
    6 q7 |3 G0 I: ^6 n) U3 n- Q
  6.     data = xlrd.open_workbook("./data/B"+str(k)+".xlsx")+ x8 u5 }! y7 S( M
  7.     table_1 = data.sheet_by_name("Sheet1")
    ! k. ?1 a1 t! `1 H: ?# {
  8.     table_2 = data.sheet_by_name("Sheet2")
    3 \4 p$ s9 E! T5 w! y
  9.     rs1 = table_1.nrows
    * j+ o( w" X/ C
  10.     rs2 = table_2.nrows, L3 Z4 {$ y0 ^1 n+ F
  11.     m= 99
    1 @3 K9 }1 R* {" A% n4 @( F
  12.     for i in range(1,rs1):- X7 y& A  \8 U' c$ c/ ]7 R
  13.         t14 = table_1.cell(i,4).value) u( H. T* X* c- |. i7 }
  14.         t12 = t14-table_1.cell(i,2).value# f; R7 I: i2 m: D7 C+ s
  15.         for j in range(1,rs2):
    8 T, W- \  M& S$ ~" L8 ^1 ~
  16.             t22 = table_2.cell(j,2).value
    & j4 n( ]: |, _0 a3 L
  17.             if t22-t14>=1/24 :! F+ L* o+ |3 X8 d7 }4 u" U% F
  18.                 m1=t12+(t22-t14)+(table_2.cell(j,4).value-t22)
    . T1 N/ ]: a4 C( A7 v2 @$ l
  19.                 if m>m1:3 w! D& K, i  a1 I$ @; J! y3 ]8 V
  20.                     m=m1
    " Z5 ^' p4 g1 U: Y3 v0 v
  21.                     r1=i
    8 j6 x2 y! @& _
  22.                     r2=j# b! k$ `+ |: T( S
  23.     ms.append(m)
    + M: Y% X2 G) l5 Z5 O6 \4 M' I
  24.     ra.append(r1)
    2 a5 x% g6 U( v: X( j/ t8 g# Q% d
  25.     rb.append(r2)
    - N, p; r' Z  s/ J. D  }6 X! u
  26. ms0=min(ms)
    ) f( O6 `6 b- |: _2 O, O, X
  27. ms1=ms.index(ms0)
    7 A/ M# f# \2 l; V& Q' J0 x4 s+ ]
  28. print("从A地出发经B",ms1+1,"到达B地,最少耗时为:",ms0*24,"小时。具体行程请查看文件ZHXC.XLS。")
    8 @, |& i- t3 t  j: D/ s
  29. data = xlrd.open_workbook("./data/B"+str(ms1+1)+".xlsx")( a) q, \- s5 I, E& q; Z% d, g
  30. table_1 = data.sheet_by_name("Sheet1")
    . ?3 h2 g" ]. t7 s# ]$ ?
  31. table_2 = data.sheet_by_name("Sheet2")- k1 f2 o# G/ Q( L1 A
  32. import xlwt
    2 H+ [& y9 S& r# |. O2 f9 e
  33. wbk = xlwt.Workbook()
    ) p4 K* V! `" X, n4 L4 L
  34. sheet = wbk.add_sheet('sheet 1')/ W- e4 A# E7 Q
  35. for l in range (5):. w4 U- W5 }/ M9 Y# u% ^" \
  36.     sheet.write(0,l, table_1.cell(0,l).value)
    8 g& O8 ]/ Z" g4 w
  37.     sheet.write(1,l, table_1.cell(ra[ms1],l).value)
    / G& p- I& W/ S" _2 I& S, M
  38.     sheet.write(2,l, table_2.cell(rb[ms1],l).value)
    ( y. @1 w& U9 ?! r
  39. wbk.save('./data/zjxc.xls')
复制代码
课内任务:将99乘法表代码输入,运行,观察是否达到预期效果。+ g! V4 ^! r5 K5 |* g8 o2 @
  1. for i in range(1,10):
    6 M# Z  l7 ]: z% [. s. s0 P# a& V
  2.      for j in  range(1,i+1):
    + b% N0 A; O& V9 u, q0 E# v9 U
  3.         print("%d*%d=%2d"%(j,i,j*i),end=' ')
    1 |" T( q% ]/ f5 L% N) X
  4.      print("")
复制代码

" ^# L& {$ ^6 w- x

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
楼主热帖




上一篇:第十讲 从A市到B市耗时最少的旅行路线方案设计报告
下一篇:第十二讲 算法及其描述
+1
578°C
沙发哦 ^ ^ 马上

帖子地址: 

教书育人!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

百度一下 百度二下 百度三下 开门大吉

QQ|Archiver|手机版|小黑屋|山东省高中信息技术学业水平考试试题网 ( 鲁ICP备16049757号 )|网站地图

GMT+8, 2020-1-29 07:50 , Processed in 0.341965 second(s), 40 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表
潍坊行知学校信息技术QQ交流群:
潍坊行知学校信息技术
潍坊行知学校复读官方招生QQ群:
潍坊行知学校复读招生