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

 找回密码
 立即注册

QQ登录

只需一步,快速开始

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

第十二讲 算法及其描述

[复制链接]

281

主题

680

帖子

214748万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
2147483647
QQ
发表于 2019-12-8 16:03:35 | 显示全部楼层 |阅读模式
第十二讲 算法及其描述
学习目标
0 I( I# \  j0 f: }) p$ Q7 Q" d1.理解和概述算法的概念与特征;- O( h7 R) v4 T. X- Y& u
2.运用恰当的描述方法和控制结构表示简单算法。
# n" f$ T; i+ z& v- H+ U; C- M学习内容
2 [1 `1 z6 O$ |/ ~算法' \$ I8 g5 }; v1 @+ f' j7 }
算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说,算法就是用计算机求解某一问题的方法,是能被机械地执行的动作或指令的有穷集合。) f2 Z4 J, X$ s* a* H& l
例如,若要求方程6x+5y+4z=50的正整数解的个数,则解决问题的算法步骤如下:
7 y* v. Y. w! e①t=0;1 V) B& b9 P+ }4 Y  ]! R6 m
②x=1;" i  ^. R+ k- L6 }: R3 A
③y=1;
9 g  R9 b: s1 u7 L+ N/ s④z=1;
. Y# W0 p9 d: W⑤如果满足式子6x+5y+4z=50,则解的个数加1(即t=t+1,表示右边式子的值赋值给左边式子),并输出这个解(即输出t,x,y,z的值);) S+ h; C) N# Z; _( S, u7 R; V) @
⑥z=z+1;6 n0 I% E- M# A( N' P
⑦如果z≤12则转步骤⑤,否则继续步骤⑧;
4 `* t5 W6 p' Y6 e( q⑧y=y+1;$ x. v, G  H/ c
⑨如果y≤10则转步骤④,否则继续步骤⑩;6 M* |& L1 d' e) X
⑩x=x+1;0 R+ ?8 C' W, z2 Z1 f8 ]7 E, r$ b
⑪如果x≤8则转步骤③,否则继续步骤⑫
( g6 i" Z, C# _- |- ?2 p, n⑫结束。
1 `0 U/ U/ _9 O/ K% ]5 D3 P% q: M. ~+ O算法的特征/ W0 i0 o! H, ^. s) V
算法作为能确实解决某个问题的策略,具有五个方面的重要特征:5 g  O+ @! [9 h& U; _
(1)有穷性。一个算法在执行有穷步之后必须结束,即一个算法所包含的计算步骤是有限的。例如,在上面的算法中,x的值从1开始穷举,重复执行语句,直到x>8时终止执行。
* n2 P1 Z4 r  x( c& [(2)确定性。算法执行的每一个步骤必须有确切的定义,不能出现模棱两可的情况。例如,上面算法步骤⑤就明确规定:当满足式子6x+5y+4z=50时,则解的个数加1(即t=t+1),并输出这个解。! {6 D* e  t$ r
(3)数据输入。一个算法必须有零个或多个数据输入,以刻画运算对象的初始情况。例如,在上面的算法中,就没有数据输入。: Z3 q0 \2 @* B( n4 b# r' B
(4)数据输出。一个算法有一个或多个数据输出,以反映对输入数据加工后的结果,没有输出的算法是毫无意义的。例如,在上面的算法中,有两个输出,即步骤⑤的个数t和具体解(x,y,z的值)。
7 @* |( c$ P, L(5)可行性。算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步骤,即每个计算步骤都可以在有限时间内完成。例如,上面的算法中每一步都是可以在有限时间内完成的。
6 h. |8 a5 z; q- R% j0 j算法的描述
+ v3 `- i- o3 t5 ~. s2 g算法是对解题过程的精确描述,且需要使用某种方法将其表示出来。5 W  G) R5 B" |9 H4 ~4 I
1.描述算法的常用方法7 e2 P: t6 i0 c
描述算法的常用方法有自然语言描述算法、流程图描述算法和伪代码描述算法。; o$ @* t7 |+ H6 F5 `& f
(1)用自然语言描述算法。7 _' o) o5 ]$ X) J* V, J6 A! @+ G, e
用自然语言描述算法,就是用人们日常所用的语言,如汉语、英语等来描述算法。例如,从A市到B市耗时最少的旅行路线问题的算法描述,即使用了自然语言。
" C+ B  ^2 b' ~% E  _使用自然语言描述算法比较容易掌握,但也存在明显的缺点。例如,当算法中含有多分支或循环操作较多时,使用自然语言很难将其清晰地表示出来;并且由于自然语言的歧义性,也容易导致算法执行的不确定性。+ g: d% M6 }. N2 K+ V" t$ ~
(2)用流程图描述算法% R4 l( g# c" N4 X9 U$ i9 `2 I( a
用流程图捕述算法是用程序框图来描述算法的一种表示方法。使用流程描述算法,可使算法的流程描述得清晰、简洁。流程图的基本图形及其功能如下表所示。0 o5 t3 m$ t# W

2 e5 ~/ v, E7 _; a例如,用流程图描述求方程6x+5y+4z=50的正整数解的算法,如下图所示。4 N9 r" `7 s* |% I5 q% N6 w
+ a0 v. p5 p* H8 h$ \* h
(3)用伪代码描述算法。' G7 }/ P( O+ q3 i
用伪代码描述算法就是用介于自然语言和计算机语言之间的文字和符号来描述算法。它不用图形符号,书写方便,格式紧凑,易于理解,便于向计算机程序设计语言过渡。! Y1 ^! L+ z2 J- ^
例如,用伪代码描述求解方程6x+5y+4z=50的算法如下:1 ^, R& l& z1 ?( ^' F7 J' f# s
# W% E& ^0 f3 ?
在《几何原本》一书中,欧几里得阐述了关于求两个正整数的最大公约数的过程,这就是著名的欧几里得算法——辗转相除法,其具体过程如下:
. {# D: {$ i3 d* ?$ i8 s" }设给定的两个正整数为m和n,求它们的最大公约数的步骤为:
7 `& T) c' {, ?: S: m! }) `2 a$ l①以m除以n,令所得的余数为R。) V% H1 L: c2 T5 p
②若R=0,则输出结果n,算法结束;否则,继续步骤③。
, r* P; N1 s3 q( C8 ~③令m=n,n=R,并返回步骤①继续进行。7 H( i- Q. K! _9 n- j- i  ]
用流程图将上述算法表示出来,试探索欧几里得算法在现实生活中有哪些应用,举出两个应用实例。
5 c3 t! c0 z8 i% h. X$ p, \9 y1 d# m
2.三种基本控制结构3 f4 J- @' Y$ p
前面的算法描述中,我们用到了顺序结构,选择结构和循环结构这三种基本控制结构(其流程图如下图所示),而任何复杂的算法都可以用这三种基本控制结构组合来表示。
" [# N( S& H9 R' Z+ z8 o3 K
8 i# {' ^8 r+ K9 ]8 c, _) e; I4 x这三种基本控制结构的主要作用是:
4 `3 y7 G# t% Q# J, |(1)顺序结构表示程序中的各步操作按出现的先后顺序执行。2 z: R( z4 H- h" l7 m
(2)选择结构表示程序的处理步骤出现了分支,需要根据某一特定的条件选择其中的一个分支执行。选择结构有单选择、双选择和多选择三种。
& T, S: |! _7 z- q3 h(3)循环结构表示程序反复执行某个或某些操作,直到判断条件为假(或为真)时才可终止循环。
9 s; }1 @- E. x3 r使用三种基本控制结构的组合来描述算法,可以改善算法的清晰度,提高算法的可读性,原因如下:6 |& \$ e0 s, ]5 T
(1)以控制结构为单位,只有一个入口和一个出口,各单位之间接口简单,比较容易独立地理解每一单位。, W7 `* m, }# ~. Z* J" k: g
(2)缩小了算法的静态描述与动态执行过程之间的差异,使得两者容易对应,易于理解。) g9 Y6 m; Y" k& g/ E
课内任务:将最大公约数代码输入,运行,观察是否达到预期效果。
9 E( N6 N8 z/ X3 A; p
  1. num_1 = int(input("输入一个数:")); s/ v0 n; C" L: L' T0 ^, n
  2. num_2 = int(input("输入另一个数:"))+ u8 F& G3 a* A# I
  3. if num_1 > num_2:: B0 f, g9 B  K+ k3 N* m3 M! p2 V; B
  4.     min = num_2
    2 Y" @5 y4 \. F+ @$ f6 j
  5. else:
    5 [7 T7 w3 v& L8 f  H( {
  6.     min = num_1
    7 [. G8 j0 N* A4 I1 G% B
  7. for i in range(1, min+1):
    1 L, a6 d8 O8 R$ x
  8.     if (num_1 % i == 0) and (num_2 % i == 0):; r( c7 S8 x' w- V* ?* H
  9.         c = i
    ( K6 c( }! Y/ \* r
  10. print('这两个数的最大公约数为:%d' % c)
复制代码
) K1 V: f, M! Y  |5 W9 x( o3 k- l. s

本帖子中包含更多资源

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

x
楼主热帖




上一篇:第十一讲 体验计算机解决问题的过程
下一篇:第十三讲 计算机程序与程序设计语言
+1
1037°C
沙发哦 ^ ^ 马上

帖子地址: 

教书育人!
回复

使用道具 举报

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

本版积分规则

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

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

GMT+8, 2020-8-4 11:04 , Processed in 0.328902 second(s), 40 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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