第九章算法

点评：套用公式求值问题是传统数学求值问题的一种， 它是一种典型的顺序结构，也就是说只通过输入、输出和赋 值语句就可以完成任务．解决这类问题的关键是先分析这种
问题的解法，即构造计算的过程，再写出算法步骤和程序框
图，再翻译成算法语句即可．
【例 2】
下列程序
INPUT a，b，c a ＝b b ＝c c＝a PRINT a，b，c
若输入10,20,30，则输出结果是( A．10,20,30 B．20,30,20
)
C．20,20,30
D．30,20,10
解析 ：先把 b 的值 20 赋给 a ， ∴ a ＝ 20. 再把 c 的值 30 赋给 b ， ∴b＝30.然后把a的值20赋给c，∴c＝20.故选B.
答案：B
【例3】 交换两个变量A和B的值，并输出交换后的值． 思路点拨：引入一个中间变量X，将A的值赋予X，又将 B 的值赋予 A，再将X的值赋予B，从而达到交换 A，B的值( 比如 交换装满水的两个水桶里的水需要再找一个空桶)．
点评：(1) 条件语句的主要功能是用来实现算法中的条件
结构，在使用计算机时，经常需要按照条件进行分析、比较、 判断，并且按照判断后的不同情况进行不同的操作和处理. 如
果是要解决像“判断一个数的正负”、“比较数之间的大
小”，“对一组数进行排序”、“求分段函数的函数值”等 很多问题，计算机就需要用到条件语句； (2) 条件语句的嵌套 可多于两层，可以表达算法步骤中的多重限制条件，在使用 条件语句的嵌套时要注意IF与ELSE的配对关系．
解析：程序的功能是求分段函数
2 x ＋ 2 ，x<0，
即 y＝(2－|x|)2 的函数值， 4，x＝0， x－22，x>0，

A．k<n? C．k≥n?
B．k>n? D．k≤n?
解析 执行程序框图，输入的 a＝2，s＝0×2＋2＝2，k＝1；输入的 a ＝2，s＝2×2＋2＝6，k＝2；输入的 a＝5，s＝2×6＋5＝17，k＝3，此时 结束循环，又 n＝2，所以判断框中可以填“k>n？”。故选 B。
答案 B
9．执行如图所示的程序框图，若输入 m＝1，n＝3，输出的 x＝1．75， 则空白判断框内应填的条件为( )
A．1 C．3
B．2 D．4
解析 依据程序框图可知，程序运行如下：初始化数据：n＝0，x＝1132π， 第一次循环：a＝sinx＝sin1132π≠ 23，n＝n＋1＝1，x＝x－2n1－2 1π＝π；第二 次循环：a＝sinx＝sinπ≠ 23，n＝n＋1＝2，x＝x－2n1－2 1π＝π－132π＝192π； 第三次循环：a＝sinx＝sin91π2≠ 23，n＝n＋1＝3，x＝x－2n1－2 1π＝192π－152π
答案 B
14．执行如图所示的程序框图，若输出的结果为 4，则输入的实数 x 的 取值范围是( )
A．－217，89 C．－2，19
B．－89，217 D．－19，2
解析 第一次循环：n＝1，x＝3x＋1，n＝2；第二次循环：x＝(3x＋1)×3 ＋1＝9x＋4，n＝3；第三次循环：x＝(9x＋4)×3＋1＝27x＋13，n＝4，x≥12， 循环结束。可得不等式组29x7＋x＋4<131≥2，12， 解得－217≤x<89，所以若输出的
解析 根据程序框图进行运算：a＝0，S＝0，i＝1，a＝1，S＝1，i＝2； a＝4，S＝1＋4，i＝3；a＝9，S＝1＋4＋9，i＝4；a＝16，S＝1＋4＋9＋16， i＝5……依次写出 S 的表达式，发现规律，满足 C。

不朽的古代数学名著——《九章算术》每当提起中国古代数学，肯定会提到《九章算术》。

《九章算术》是流传至今的我国一部古代数学典籍，根据考证，大约成书于东汉初期，作者姓名不详。

《九章算术》是中国古典数学的一部最重要的经典著作。

它总结了我国先秦至西汉的数学成果，形成以问题为中心的算法体系。

它是我国传统文化的一部分，有着鲜明的特色，对世界数学宝库作出了重要贡献。

我国杰出的古代数学家刘徽于魏景元四年（263年）首次注释《九章算术》；唐初，数学家李淳风于显庆元年（656年）奉命对《九章算术》也作了注释。

刘徽在《九章算术注序》中说：“往昔暴秦焚书，经术散坏，自时厥后，汉北平侯张苍、大司农中丞耿寿昌皆以善算命世。

苍等因旧文之遗残，各称删补。

”可见，在秦朝以前已有算书流传，但因受秦始皇焚书而散失，后来张苍和耿寿昌等收集了旧算书的残篇，进行了删补。

他们删补校订旧算书的目的显然是为了培养行政官吏，或教习官家子弟，以实用为宗旨。

1983年从湖北江陵张家山出土的西汉早年（约公元前180年左右）的竹简算书《算数书》，也是采用问题集的形式，并按算法将问题分类。

其中大部分算法术语，都出现在以后的《九章算术》之中，因此，《算数书》可能是《九章算术》的取材来源之一。

《九章算术》就是在这类算书的基础上，经过多人之手，不断补充、修改、增订而逐步形成的。

由于《九章算术》是我国古代数学教材之一，在民间流传较为广泛，所以，对我国古代数学的影响十分巨大。

《九章算术》对分数、正负数的记载是世界上早而有系统的论述。

这不仅早于欧洲，也比印度的有关记载早五、六世纪。

我国古代虽然没有无理数的明确记载，但是，《九章算术》里早有这一概念的萌芽。

刘徽意识到有一种开不尽方的数，为了近似地表示这种开不尽方的数，便创造了十进制分数。

刘徽十分重视比例算法，当比例算法传到欧洲时，欧洲人对比例算法也很重视，不但称为“黄金算法”，而且往往还把简单的问题化为比例问题去研究。

《九章算术》里提出的方程组的解法是“直除”法。

Step 3 用加权平均法计算各路段当前交通量
（8-1）
Step 4 如果
相差不大，则停止计算。即
为最终分配结果。否则返回 Step1 。
实践中 Step 4停止计算的判断即可用误差大小，也可以用循环次数的多少来进 行运算的控制 ；用的比较多的是循环次数。在 Step 3中权重系数 a由计算者给 定。a即可定为常数，也可定为变数。通常定为常数时a=0.5；定为变数时a=1/n， n是循环次数。
◦ 原理理论上合理，实际求解非常困难。
◦ Beckmann（1956）等价数理最优化模型（有约束非线性最优 化问题）
◦ 其中：
，表示路段a上的交通流量；
◦ ：路段 - 径路相关变量，即 0-1 变量。如果路段a属于从
出发地为r目的地为s的OD间的第k 径路 ，则其值为1 ，否则 为0 ；
◦ f；krs ：出发地为r ，目的地为s的 OD 间的第k条径路上的流量
一、用户平衡分配模型及其求解算法
◦ （1） 模型化
◦ 其中，hkrs：OD对rs间第k条径路的交通量。 tkrs ：OD对rs间第k条径路的行驶时间。 trs：OD对rs间最短径路的行驶时间。 qrs ：OD对rs的分布交通量。
【例9-3】 如图表示了一对由两条可选路径连接的起终点， t1,t2分别表示路段1,2上的交通时间，用x1, x2表示相应的交通流 量，q表示总的OD流量，则q=x1+x2。
◦ 对于完全满足Wardrop原理定义的平衡状态，则称为平衡 分配方法；对于采用启发式方法或其他近似方法的分配模 型，则称为非平衡分配方法。
交通分配模型
均衡模型 非均衡模型
用户均衡模型扩展 标准用户均衡模型 系统优化均衡模型