随机蛙跳算法和NSGA2算法
《智能算法及应用技术》
结课综述
Name: Moonlightran
Email: randolphingwp@https://www.wendangku.net/doc/f18955256.html,
目录
1. 随机蛙跳（SFLA）算法 (1)
1.1 SFLA理论基础 (1)
1.2 SFLA 的基本原理 (3)
1.3 SFLA 的基本概念 (4)
1.4 SFLA 的参数设置 (4)
1.5 SFLA 的运算流程 (5)
1.6 SFLA函数优化中实例 (10)
1.7 粒子群算法（PSO）函数优化 (14)
2. 多目标优化算法(NSGA—II) (19)
2.1多目标优化问题描述 (19)
2.2 基本概念 (19)
2.3 非支配排序算法(NSGA) (20)
2.4 带精英策略的非支配排序遗传算法(NSGA—II) (22)
2.5 NSGA-II函数优化实例 (27)
单目标和多目标优化算法介绍
——随机蛙跳算法和带精英策略的非支配排序算法
通常的优化问题可以分为单目标优化问题和多目标优化问题。针对这两类问题，分别介绍随机蛙跳算法（SFLA）和带精英策略的非支配排序算法（NSGA—II），并且给出这两类算法在函数优化中的应用实例。
1.随机蛙跳（SFLA）算法
随机蛙跳算法是由Kevin Lanes和Mustafa Eusuff于2003 年共同提出，该算法结合了基于遗传特性的模因算法和基于行为的粒子群算法的优点，适合解决各类组合优化问题。混合蛙跳算法具有设置参数少、简单易于理解、鲁棒性强等特点，已在语音情感识别、作业车间调度、复杂函数优化问题求解等领域得到成功应用。
1.1 SFLA理论基础
SFLA 是一种群体仿生类启发式进化计算方法，该算法将模因算法和粒子群优化算法的思想相结合，并经过适度扩展，因而兼具二者的优点。作为SFLA 的理论基础，模因算法和粒子群优化算法有必要进行简要介绍。
1.1.1模因算法
Moscato受Dawkin提出的meme概念的启示，于1989年首次提出了模因算法。该算法源于文化进化理论中的隐喻思想，结合了全体成员参与搜索的思想和有选择性的特定个体搜索的机制，可以通过启发式搜索解决优化问题。模因算法在原理上与遗传算法很相似，不同的是该算法在原始遗传算法步骤中的交叉和变异步骤之后增加了一个小范围的局部进化过程，故模因算法也曾被叫做增加了局部搜索功能的遗传算法。给出模因算法的运算流程如图1.1所示。
图1.1模因算法流程
1.1.2粒子群算法
Kennedy和Eberhart受鸟群的群体飞行特性启发于1995年提出粒子群优化
算法，该算法是一种基于群体智能的自适应优化计算方法。假设有一群鸟，其中的所有个体均被称作一个“粒子”，这样的“粒子”被赋予速度和位置两种属性，在可行域中按照一定的规则飞行，目标是经过一定的进化次数找出待解问题的最佳参考方案。进化过程中，所有个体不断追随两个关键的极值以调整自己的位置和速度。其中一个极值是该粒子本身搜索到的最佳位置best P ，即粒子自身的最优值；另外一个是粒子群中的所有成员中当前最优个体所在的位置best G ，即全局最优解。
粒子群优化算法中个体的速度、位置更新公式如下：
)()()()(2111k i k
best k i k ibest k i k k i X G rand c X P rand c V V -+-+=-+ω（1.1）
11+++=k i k i k i V X X （1.2）
其中，k i V 为第k 次迭代中第i 个粒子的速度。
k i X 为第 k 次迭代中第i 个粒子的位置。
k
ibest P 为第 k 次迭代中第i 个粒子的自身最优位置。 k
best
G 为第 k 轮进化中的全局最优位置。 Rand ()为位于范围[0,1]之间的随机数。
ω为粒子的惯性因子，1c 为粒子的认知因子，控制k i P 移动的幅度。 2c 为粒子的社会因子，控制k G 移动的幅度。
粒子群优化算法的运算流程为： Step1：初始化粒子的速度和位置。 Step2：计算所有粒子的适应值。
Step3：比较各个粒子的当前适应值与其历史最优位置best P 的适应值，如果前者优，则置此粒子当前最佳位置为best P 。
Step4：比较各个粒子的当前适应值与其全局最优位置best G 的适应值，若前者优，则置此粒子当前全局最佳位置为best G 。
Step5：采用式（1.1）和式（2.1）更新种群中个体的速度和位置。 Step6：判断：若满足停止准则，则算法终止，否则转Step2。
上述两种算法核心思想的有机结合，即形成了所研究的混合蛙跳算法。
1.2 SFLA 的基本原理
SFLA 是基于群体智能的仿生类优化算法，种群（解集）由一些具有相同结构的青蛙（解）组成。SFLA模仿了青蛙群体的集体觅食活动。
为了寻找当前有限的食物源，在空间受限的一块区域内，一群青蛙首先按一定规则找准各自的初始位置。位置确定后，每只青蛙开始利用各自携带的个性化信息在自己所在位置附近寻找食物更丰富的位置，并通过跳跃更新自己的位置。寻找的规则是，蛙群通过充分发挥自身的自组织性，分别由个数基本相同的青蛙组团搜索，形成局部范围内的小团体，即为子种群。子种群内部，由局部精英个体带领其它个体进行搜索。每个子群搜索结束之后，所有个体重新组织起来，混合后重新按照规则分组，再执行组内搜索。组团搜索和群体混合迭代执行，直至找到最丰富的食物源。
对于SFLA，每只青蛙被看作一个候选解，确定初始位置即为青蛙种群的初始化过程。组团搜索对应于种群的划分并执行局部搜索，此过程是SFLA 最核心的步骤，本质上青蛙个体的位置更新发生于此阶段。子群的混合形成算法的混合运算，即全局信息交换。全局信息交换与局部深度搜索相互作用，为SFLA跳出局部极值提供了保证。
1.3 SFLA 的基本概念
1．青蛙：承载思想与信息的个体，构成种群的元素。
2．种群：由一定数量的青蛙组成的集合。
3．子种群：种群的子集。由所有青蛙构成的群体根据相应规则被划分为多个并行、独立的子集，这些子集被称为子种群，即局部小团体。
4．适应度：用来评价青蛙个体好坏的度量标准。
5．局部搜索：子种群内部个体的更新操作。按照一定的更新机制，子群内部的青蛙个体执行跳跃操作，从而消息得以在小团体内部传播和扩散。
6．混合运算：将各个子种群合并为一个种群的操作。将各个局部小团体进行合并，形成一个统一的群体，便于个体间的信息交流，为下一轮进化提供条件。
7．控制参数：SFLA 执行需要的控制参数，主要有：所有青蛙个体总数（种群规模），最大混合迭代次数，局部小团体（子种群）的个数，子种群内部进化代数，各局部团体中青蛙的个数，青蛙个体的维数，青蛙最大跳动步长等。
8．执行终止条件：
（1）在若干连续进化代数内，全局最优解没有得到刷新；
（2）算法执行到初始设定的最大混合迭代次数。
满足二者之一，算法即被强制终止。
1.4 SFLA 的参数设置
SFLA 的参数设置对算法的搜索性能具有非常重要的影响。SFLA 主要包括五个关键的参数，具体为：群体中青蛙个体数量F，算法的最大混合迭代次数G，子种群数量m ，各子种群的局部进化代数N，青蛙的最大允许跳跃距离
D。
max SFLA 的参数设置具体解释如下：
（1）群体中青蛙个体数量F：又称种群规模，指所有青蛙个体总数。一般而言是算法最重要的参数。青蛙个体数量越多，算法搜索到全局最优值的可能性也相应越大，但太大的种群规模会对搜索速度造成不利影响。
（2）算法的最大混合迭代次数G：此参数需要合理设置，如果G 过大，则导致算法复杂度增加；相反，如果G太小，将造成青蛙种群之间缺乏交流，影响青蛙向最优个体靠近。该参数的选取一般与问题的规模相关，规模越大，G的取值也相应越大。
（3）子种群数量m：此参数也需要合理地选择，m如果过小，导致每个子种群内部青蛙个数过多，参与局部搜索的个体相应过少，因此信息难以在子种群间充分交换，失去局部搜索的优势；但当m太大时，会造成每个子种群规模太小，因此会削弱局部模因搜索的优势，造成算法易于早熟收敛。
（4）各子种群的局部进化代数N：此参数也需要合理设置，过小的N会造成子种群内部青蛙个体频繁跳跃，减少了局部个体信息交流的机会；反之，若N 过大，将会增加局部区域内算法早熟的可能性。
（5）青蛙的最大允许跳跃距离
D：此参数可在一定程度上控制算法的全
max
局寻优能力。若
D太小，青蛙将在局部小范围跳动，容易陷入局部最优，削弱max
算法的全局搜索能力；而如果
D过大，青蛙将在可行域内大步跳跃，又容易造
max
成错过最佳寻优位置。
SFLA 的研究起步相对较晚，就算法的参数设置而言，学术界尚未形成可遵循的指导性原则，多数情况下通过仿真实验测试得到一组设置。这也给不同学者针对经典SFLA的改进效果对比造成了一定困难。
1.5SFLA 的运算流程
SFLA 首先从可行域中随机地产生一组初始解构成初始种群，每个解对应于一只青蛙；接着计算各个青蛙的适应度值，按照适应度降序排列；然后以某种规则把整个青蛙种群划分为一定数量的子种群，在每个子种群内执行局部搜索，即根据指定的策略更新子种群内的最差青蛙，促使被更新个体向局部最优位置靠近。子种群进化结束后，各子种群之间进行信息交换实现混合运算。交替执行局部搜索和混合运算直至满足停止条件。
为说明SFLA 的算法机理，以函数优化问题为例进行研究，问题如下：
]
,[)
(..min u l x x f t s ∈??
?（1.3） 其中},2,1,|{:],[S k u x l x u l k k k S =≤≤?∈=。利用混合蛙跳算法求解该问题时，分为四个步骤：
1.初始化
2.子种群划分
3.局部搜索
4.其种群混合 1.
5.1初始化
从可行域中随机产生F 个解},{21F x x x 作为初始种群，问题的纬数为S ，
},{21i
S i i i x x x x =为S 纬空间的一个解),2,1(F i =。经典的SLFA 初始化过程是
随机初始化的，种群分布不均匀，不利于算法在整个可行域空间上进行均匀搜索，进而有影响了算法的全局寻优的缺点，算法的初始化过程如图2中的伪代码所示：
图1.2经典SFLA 的初始化过程
1.5.2子种群划分
计算每个解的目标函数值),2,1)((F i x f i =，将目标函数值按照降序排列，并且将目标函数的最优值记为g x 作为整个种群的最优解。将整个种群划分为m 个子种群m Y Y Y ,,21，每个子种群包含n 个解，即满足n m F *=。其中，第一个解进入1Y ，第二个解进入2Y ，直到第m 个解进入m Y ，然后将第1+m 个解进入1Y ，以此类推，直至所有的解分配完毕。每个子种群中，目标函数最好和最差的解分别记为b x 和w x 。经典混合蛙跳算法中子种群的划分如图1.3中伪代码所示：
图1.3 经典SFLA 的子种群划分过程
1.5.3局部搜索
在迭代过程中，各子种群只更新目标函数值最差的解w x ，其更新公式为：
;,2,1),
(*()m i x x rand D w b i =-=（1.4） m i D D D D x x i i w w ,2,1,
,
max max =≤≤-+=（1.5）
其中，rand()为0到1之间的随机数，i D 为青蛙的移动步长，max D 表示允许青蛙移动的最大距离。式(5)对目标函数值最差的青蛙w x 执行更新，即修改解的位置。
如果更新后得到比w x 更好的解，则用更新后的解替代最差解；否则用g x 代替式(4)中的b x ，重新利用公式(4)、(5)计算新解；若仍得不到比w x 更优的解，则随机产生一个新解去替换最差解，子种群中最差青蛙的位置就得到了更新。在指定迭代次数内重复执行以上操作，就完成了一轮子种群的局部搜索。经典混合蛙跳算法的局部搜索过程见图1.4所示。
图1.4 经典混合蛙跳算法的局部搜索过程
1.5.4子种群混合
将各子种群m Y Y Y 21,重新合并为X ，即}{321m Y Y Y Y X ????= ，然后将X 重新按目标函数值降序排列，并用整个种群中最好的青蛙（即目标函数值最小）及时更新g x ，重新划分子种群，进行下一轮的局部搜索。
经过上述四步即种群初始化、子种群划分、局部搜索、子种群混合，完成了SFLA 的一次迭代，解的位置也得到了更新。混合蛙跳算法的算法流程如图1.5所示。
图1.5 混合蛙跳算法流程
1.6 SFLA 函数优化中实例
利用SFLA 算法寻优实例函数如下：
71289.2sin )(2
2cos 2cos 2
2
2
2-+++=
+y
x e y
x y x x f ππ（1.6）
用matlab 绘制出函数图像如图1.6所示，绘制图形代码如图1.7中所示。
图1.6 SFLA 寻优函数图形
图1.7绘制函数图形matlab 代码
从图中可以看出，该函数有很多的极大值点和极小值点，在(0,0)附近，极值估计在1左右。如果用普通的方法，很难准确的求到函数极值点。
接下来使用SFLA 算法的来求解这个函数的极大值。为了和SFLA 算法有一个对比。同时也用粒子群算法（PSO ）来求这个函数的极大值。
一个完整的SFLA 程序分为：参数设置、种群初始化、迭代寻优和结果显示几个部分，以下代码按照这几部分安排。
1.6.1 SFLA 算法参数设置
SFLA参数设置程序如下所示：
close all;clc;clear all; %清空运行环境m=4; %种群分组数
n=50; %t每组青蛙包含的个数
Ne=50; %组内迭代数
smax = 50; %最大步长
MAXGEN=300; %种群总进化代数d=2; %优化问题维数
pmax = 2; %d维最大值
pmin = -2;%d维最小值
1.6.2SFLA种群初始化
SFLA初始化程序如下所示：
适应度函数代码如下所示：
1.6.3 SFLA迭代寻优
end
%排序，找最好的，并分组
[fitsort,index]=sort(fitness);
fitsort=fitsort(end:-1:1);
index=index(end:-1:1);
for i3=1:F
x(i3,:)=p(index(i3),:);
end
gx=x(1,:);%种群内最好的青娃
yy(ii)=fitsort(1);
% yy(ii)=fun(x(1,:));
% local=zeros(n,d);
for i4=1:m
local = p(i4:m:end,:);
for j=1:Ne %每组青蛙迭代次数
pb=local(1,:);%组内最优
pw=local(n,:);%组内最差
s1=rand.*(pb-pw);%采用组内最优更新
s1(find(s1>smax))=smax;
temp= pw+s1;
temp(find(temp>pmax))=pmax;
temp(find(temp if fun(temp) > fun(pw) s1=rand.*(gx-pw);%采用全局最优更新 s1(find(s1>smax))=smax; temp=pw+s1; temp(find(temp>pmax))=pmax; temp(find(temp end if fun(temp)>fun(pw) s1=pmax*rands(1,d);%随机更新 s1(find(s1>smax))=smax; temp=pw+s1; temp(find(temp>pmax))=pmax; temp(find(temp end local(n,:) = temp; for loc=1:n fitlocal(loc)=fun(local(loc,:)); end [localsort,indexlocal]=sort(fitlocal); localsort=localsort(end:-1:1); indexlocal=indexlocal(end:-1:1); for loc=1:n localnew(loc,:) = local(indexlocal(loc),:); end local=localnew; end %结束Ne p(i4:m:end,:) =local; end %结束m %最好的青娃适配值 end %结束MAXGEN toc 1.6.4 结果分析 SFLA算法反复迭代300次，画出每一代最优个体适应度值变化图形，代码如下： 最优个体适应度值变化如图1.8所示，图1.9中给出所求极值的位置、还有程序运行所消耗的时间。 图1.8 最优个体适应度值曲线 图1.9 SFLA算法所求极值位置和消耗时间 从图1.8和1.9中可以看出，蛙跳算法运行300代，消耗14.7S时间。最终求得的最优个体适应度值为1.004737，对应的位置为（0.003306，0.003652），SFLA 寻优值接近函数实际值，证明了SFLA算法具有较强的寻优能力。为了和SFLA 算法对比，接下来我们使用粒子群算法对上述相同问题求解。 1.7 粒子群算法（PSO）函数优化 基于PSO算法函数优化的流程如下图1.10所示。 图1.10 PSO算法函数优化流程 其中，随机初始化粒子的速度和粒子的位置，速度和位置按照1.1和1.2中的公式更新。选择粒子种群大小为20，迭代次数为300次。适度函数和SFLA 算法中适度函数相同，程序代码如下： %% 清空环境 close all; clc clear tic; %% 参数初始化 %粒子群算法中的两个参数 c1 = 1.49445; c2 = 1.49445; maxgen=300; % 进化次数 sizepop=20; %种群规模 Vmax=0.5; Vmin=-0.5; popmax=2; popmin=-2; %% 产生初始粒子和速度 for i=1:sizepop %随机产生一个种群 pop(i,:)=2*rands(1,2); %初始种群 V(i,:)=0.5*rands(1,2); %初始化速度 %计算适应度 fitness(i)=fun1(pop(i,:)); %染色体的适应度 end %% 个体极值和群体极值 [bestfitnessbestindex]=max(fitness); zbest=pop(bestindex,:); %全局最佳 gbest=pop; %个体最佳 fitnessgbest=fitness; %个体最佳适应度值 fitnesszbest=bestfitness; %全局最佳适应度值 %% 迭代寻优 for i=1:maxgen for j=1:sizepop %速度更新 V(j,:) = V(j,:) + c1*rand*(gbest(j,:) - pop(j,:)) + c2*rand*(zbest - pop(j,:)); V(j,find(V(j,:)>Vmax))=Vmax; V(j,find(V(j,:) %种群更新 pop(j,:)=pop(j,:)+V(j,:); pop(j,find(pop(j,:)>popmax))=popmax; pop(j,find(pop(j,:) %适应度值 fitness(j)=fun1(pop(j,:)); end for j=1:sizepop %个体最优更新 if fitness(j) >fitnessgbest(j) gbest(j,:) = pop(j,:); fitnessgbest(j) = fitness(j); end %群体最优更新 if fitness(j) >fitnesszbest zbest = pop(j,:); fitnesszbest = fitness(j); end end yy(i)=fitnesszbest; end toc %% 结果分析 figure(1); plot(yy); title('最优个体适应度','fontsize',12); xlabel('进化代数','fontsize',12); ylabel('适应度','fontsize',12); fprintf('%f\n',zbest); 适应度函数如下所示： 使用PSO算法最优个体适应度值变化如图1.11所示，图1.12中给出所求极值的位置、还有程序运行所消耗的时间。 图1.11 PSO算法最优个体适应度值 图1.12 PSO算法所求极值位置和消耗时间 从图1.11和1.12中可以看出，蛙跳算法运行300代，消耗0.096644S时间。最终求得的最优个体适应度值为1.005375，对应的位置为（0.000792，0.00044），单从结果上看，PSO比SFLA效率高很多。 接下来，我们简单使SFLA算法和PSO算法分别对上述问题求解10次，结果如图1.13所示。 从结果中可以看到，PSO算法运行效率高，SFLA算法消耗时间大，从结果精度来看，PSO算法有些高于SFLA算法，有些低于SFLA算法结果。可见PSO 求解问题非常不稳定。在实际问题的求解过程中，不仅仅要追求算法的精度，而且算法的稳定性也是至关重要的，在这方面，SFLA算法明显要优于PSO算法。 (a) SFLA 算法求解结果(b) PSO 算法求解结果 图1.13SFLA 算法和PSO 算法对比 数据结构课程设计报告 实验一：计算器 设计要求 1、问题描述：设计一个计算器，可以实现计算器的简单运算，输出并检验结果的正确性，以及检验运算表达式的正确性。 2、输入：不含变量的数学表达式的中缀形式，可以接受的操作符包括+、-、*、/、%、(、)。 具体事例如下： 3、输出：如果表达式正确，则输出表达式的正确结果；如果表达式非法，则输出错误信息。 具体事例如下： 知识点：堆栈、队列 实际输入输出情况： 正确的表达式 对负数的处理 表达式括号不匹配 表达式出现非法字符 表达式中操作符位置错误 求余操作符左右出现非整数 其他输入错误 数据结构与算法描述 解决问题的整体思路： 将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。 解决本问题所需要的数据结构与算法： 用到的数据结构是堆栈。主要算法描述如下： A．将中缀表达式转换为后缀表达式： 1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况： 1）数字 2）小数点 3）合法操作符+ - * / % 4）左括号 5）右括号 6）非法字符 2. 首先为操作符初始化一个map 《智能算法及应用技术》 结课综述 Name: Moonlightran Email: randolphingwp@https://www.wendangku.net/doc/f18955256.html, 目录 1. 随机蛙跳（SFLA）算法 (1) 1.1 SFLA理论基础 (1) 1.2 SFLA 的基本原理 (3) 1.3 SFLA 的基本概念 (4) 1.4 SFLA 的参数设置 (4) 1.5 SFLA 的运算流程 (5) 1.6 SFLA函数优化中实例 (10) 1.7 粒子群算法（PSO）函数优化 (14) 2. 多目标优化算法(NSGA—II) (19) 2.1多目标优化问题描述 (19) 2.2 基本概念 (19) 2.3 非支配排序算法(NSGA) (20) 2.4 带精英策略的非支配排序遗传算法(NSGA—II) (22) 2.5 NSGA-II函数优化实例 (27) 单目标和多目标优化算法介绍 ——随机蛙跳算法和带精英策略的非支配排序算法 通常的优化问题可以分为单目标优化问题和多目标优化问题。针对这两类问题，分别介绍随机蛙跳算法（SFLA）和带精英策略的非支配排序算法（NSGA—II），并且给出这两类算法在函数优化中的应用实例。 1.随机蛙跳（SFLA）算法 随机蛙跳算法是由Kevin Lanes和Mustafa Eusuff于2003 年共同提出，该算法结合了基于遗传特性的模因算法和基于行为的粒子群算法的优点，适合解决各类组合优化问题。混合蛙跳算法具有设置参数少、简单易于理解、鲁棒性强等特点，已在语音情感识别、作业车间调度、复杂函数优化问题求解等领域得到成功应用。 1.1 SFLA理论基础 SFLA 是一种群体仿生类启发式进化计算方法，该算法将模因算法和粒子群优化算法的思想相结合，并经过适度扩展，因而兼具二者的优点。作为SFLA 的理论基础，模因算法和粒子群优化算法有必要进行简要介绍。 1.1.1模因算法 Moscato受Dawkin提出的meme概念的启示，于1989年首次提出了模因算法。该算法源于文化进化理论中的隐喻思想，结合了全体成员参与搜索的思想和有选择性的特定个体搜索的机制，可以通过启发式搜索解决优化问题。模因算法在原理上与遗传算法很相似，不同的是该算法在原始遗传算法步骤中的交叉和变异步骤之后增加了一个小范围的局部进化过程，故模因算法也曾被叫做增加了局部搜索功能的遗传算法。给出模因算法的运算流程如图1.1所示。 2011-1-12 收稿日期：2010-10-20 基金项目：国家自然科学基金资助项目(the National Natural Science Foundation of China under Grant No.60974082);商洛学院科研基金项目(Scientific Research Foundation of Shangluo University under Grant No. 09SKY011,10SKY024) 作者简介：赵鹏军 (1979－)，男，陕西渭南人，硕士，讲师，主要研究方向：最优化理论与方法，智能计算及其应用；邵泽军 (1981－)，男，山 东临沂人，硕士，助教，主要研究方向：智能交通管理. 一种新的改进的混合蛙跳算法 赵鹏军1，邵泽军2 1.商洛学院 数学与计算科学系，商洛 726000 2.北京化工大学北方学院 三河 065201 1.Department of Mathematics and Computational Science, Shangluo University, Shangluo 726000, China 2.North College of Beijing University of Chemical Technology, Sanhe 065201,China ZHAO Peng-Jun 1, SHAO Ze-Jun 2. Novel Improved Shuffled Frog Leaping Algorithm Abstract: To overcome the drawbacks of local optima and instability involved in Shuffled Frog Leaping Algorithm (SFLA), an improved SFLA is proposed. The proposed algorithm employs opposition based learning (OBL) to generate the initial population, which can obtain fitter initial candidate solutions. During the course of evolvement, the differential evolution (DE) is embedded in SFLA organically to maintain the population diversity, Numerical results show that the proposed SFLA has a better capability to solve complex functions than other algorithms. Keywords: shuffled frog leaping algorithm(SFLA); opposition; differential evolution(DE) 摘 要: 针对混合蛙跳算法在优化过程中受初始值影响较大且容易陷入局部最优的缺陷，提出了一个改进的混合蛙跳算法，该算法利用基于对立学习的策略产生初始种群，提高了产生解的质量；在进化过程中，将差分进化有机地嵌入其中，维持了种群的多样性。数值结果表明，改进的混合蛙跳算法对复杂函数优化问题具有较强的求解能力。 关键词：混合蛙跳算法；对立策略；差分进化 中图法分类号：TP18 文献标识码：A 1 引言 混合蛙跳算法[1] (Shuffled Frog Leaping Algorithm, SFLA)最早是由Eusuff 和Lansey 于2000年提出，源于对青蛙觅食行为的研究，具有概念简单，参数少，计算速度快，全局寻优能力强，易于实现等特点，并且简单易用，已在多个领域取得了成功[1-4]。然而，和其他智能优化算法一样，SFLA 同样存在易收敛到局部最优，在求解部分函数优化问题时效果不够理想的缺陷。 对立策略是提高算法优化性能的一种新方法[5]，文献[6]将其应用于差分进化(Differential Evolution, DE)算法中，数值结果验明了其有效性。文献[7]将其引入进化计算，提出一种基于对立策略的种群初始化方法，即用种群对立产生方式来取代传统的种群随机生成方式。在进化过程中同时考虑随机点和其对立点，比单纯地使用随机方法更有效。DE 算法[6]最初由Store 和Price 于1995年提出，该算法通过变异、杂交、选择操作来更新随机产生的初始种群，经过逐步迭代，不断进化，可实现全局最优解的搜索。 SFLA 和DE 算法都是基于群体智能和随机策略、并依据各自的搜索机制进行寻优。为提高SFLA 的性能，本文利用对立策略和DE ，提出了一种基于对立策略和差分进化的混合蛙跳算法（记为ODSFLA ），可有效改善SFLA 的求解效率，为求解优化问题提供一种新的优化工具。 2 混合蛙跳算法 SFLA 是通过个体间的协作与竞争来实现在多维空间中对最优解的搜索。下面以函数最小化为例，说明SFLA 的基本步骤。设青蛙种群规模为P ，其中第i 个个体在n 维空间中的坐标为12(,,,)i i i ni x x x x ，计算个体的适应度()i f x ，根据适应度将其按递减顺序排列。然后将整个种群划分为S 个子群，每个子群中包含N 个个体，即满足关系P S N ，在进化过程中，第一个解放入第一个子群，第二个解放入第二个子群，一直分配下去，直到第S 个解放入第S 个子群。然后，第1S 个解又放入到第一个子群，第2S 个解放入到第二个子群，这样循环分配下去，直到所有解分配完毕。 在每一个子群中，适应度最优和最差的解分别记为 12(,,,)b b b nb x x x x 和12(,,,)w w w nw x x x x ；种群中适应度 最优的解记为12(,,,)g g g ng x x x x 。在每次进化中，对w x 进行更新操作，其更新策略为： ()j b w D r x x ! (1) ' w w j x x D （max max j D D D !??） (2) 其中r 为[0,1]之间的均匀随机数，1,2,,j S ，max D 为最 大移动步长。如果'w x 的适应度优于w x 的适应度，则用' w x 代 替w x ；如果没有改进，则用g x 替换b x 重复执行式(1)、(2)； 如果仍没有改进，则从搜索空间中随机产生一个新解取代原来的w x ，在指定迭代次数It 内继续执行以上操作，这样也就完成了SFLA 的一次进化。 3 改进的混合蛙跳算法 3.1 对立策略 对立策略同时考虑当前点和其对立点，从中选择较优点。文献[6]已经证明了利用对立点的信息比利用随机信息能更快找到最优解，同时实验也表明对立搜索可比随机搜索更有效。对立点定义[5]如下： 设12(,,)n P x x x ，[,]i i i x l u #，1,2,,i n ，为n 维搜索空间中的一个点，,i i l u 分别为i x 的下界和上界，其对立点 可表示为12 (,,)n P x x x ???? ，其中 网络出版时间：2011-5-19 14:35 网络出版地址：https://www.wendangku.net/doc/f18955256.html,/kcms/detail/11.2127.tp.20110519.1435.001.html 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 设计过程在硬件与软件方面进行同步设计。硬件方面从功能考虑，首先选择内部存储资源丰富的AT89C51单片机，输入采用4×4矩阵键盘。显示采用3位7段共阴极LED动态显示。软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C 语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C51芯片、汇编语言、数码管、加减乘除 目录 摘要 (01) 引言 (01) 一、设计任务和要求............................. 1、1 设计要求 1、2 性能指标 1、3 设计方案的确定 二、单片机简要原理............................. 2、1 AT89C51的介绍 2、2 单片机最小系统 2、3 七段共阳极数码管 三、硬件设计................................... 3、1 键盘电路的设计 3、2 显示电路的设计 四、软件设计................................... 4、1 系统设计 4、2 显示电路的设计 五、调试与仿真................................. 5、1 Keil C51单片机软件开发系统 5、2 proteus的操作 六、心得体会.................................... 参考文献......................................... 附录1 系统硬件电路图............................ 附录2 程序清单.................................. 微机课程设计报告 题目简易计算器仿真 学院（部）信息学院 专业通信工程 班级2011240401 学生姓名张静 学号33 12 月14 日至12 月27 日共2 周 指导教师（签字）吴向东宋蓓蓓 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C52芯片、汇编语言、数码管、加减乘除 安卓应用程序设计 ——简易计算器的实现院（系）名称 专业名称 学生姓名 学生学号 课程名称 2016年6月日 1.系统需求分析 Android是以Linux为核心的手机操作平台，作为一款开放式的操作系统，随着Android 的快速发展，如今已允许开发者使用多种编程语言来开发Android应用程序，而不再是以前只能使用Java开发Android应用程序的单一局面，因而受到众多开发者的欢迎，成为真正意义上的开放式操作系统。计算器通过算法实行简单的数学计算从而提高了数学计算的效率，实现计算器的界面优化，使界面更加友好，操作更加方便。基于android的计算器的设计,系统具有良好的界面；必要的交互信息；简约美观的效果。使用人员能快捷简单地进行操作，即可单机按钮进行操作，即时准确地获得需要的计算的结果，充分降低了数字计算的难度和节约了时间。 2.系统概要设计 2.1计算器功能概要设计 根据需求，符合用户的实际要求，系统应实现以下功能：计算器界面友好，方便使用，，具有基本的加、减、乘、除功能，能够判断用户输入运算数是否正确，支持小数运算，具有清除功能。 图2.1系统功能图 整个程序基于Android技术开发，除总体模块外主要分为输入模块、显示模块以及计算模块这三大部分。在整个系统中总体模块控制系统的生命周期，输入模块部分负责读取用户输入的数据，显示模块部分负责显示用户之前输入的数据以及显示最终的计算结果，计算模块部分负责进行数据的运算以及一些其他的功能。具体的说，总体模块的作用主要是生成应用程序的主类，控制应用程序的生命周期。 输入模块主要描述了计算器键盘以及键盘的监听即主要负责读取用户的键盘输入以及 响应触屏的按键，需要监听手机动作以及用指针事件处理方法处理触屏的单击动作。同时提供了较为直观的键盘图形用户界面。 显示模块描述了计算器的显示区，即该区域用于显示用户输入的数据以及最终的计算结 算法和流程图 一、学习目的和学习内容 学习各种软件的使用——>让运算机按照我们的意图去完成一件事——>编程序（软件）给别人用； 国际信息学（运算机）奥林匹克竞赛——全国中学生信息学奥赛——江苏省中学生信息学奥赛； 竞赛的内容确实是编程竞赛；这也是我们的学习目的和内容； 运算机程序设计语言：人类语言——>用程序设计语言（如Pascal语言）表示——>再翻译成机器语言； 二、运算机解决问题的步骤 做任何一件事都要有一定的的步骤，如求1+2+3+4+5+6+7+8+9+10； 运算机解题步骤：分析问题 ——>确定解决问题的方法和步骤（即算法） ——>选择一种运算机语言，依照算法编写运算机程序 ——>让运算机执行那个程序获得结果 三、算法的概念 1、为解决某一个问题而采取的方法和步骤，称为算法。或者说算法是解决一个问题的方法的精确描述。 如：已知半径，运算圆的面积的算法。 算法读入半径R的值——>运算圆的面积S=π*R*R——>输出圆的面积S。 注意：算法不一定唯独，如求1+2+3+4+5+6+7+8+9+10的算法。 2、算法的特点： ①有穷性：必须在执行了有穷个运算步骤后终止； ②确定性：每一个步骤必须是精确的、无二义性的； ③可行性：能够用运算机解决、能在有限步、有限时刻内完成； ④有输入： ⑤有输出： 四、算法举例 例一：交换两个大小相同的杯子中的液体（A水、B酒）。 算法1： 1、再找一个大小与A相同的空杯子C； 2、A——>C； 3、B——>A； 4、C——>B；终止。 或（B——>C、A——>B、C——>A） 算法2： 1、再找两个空杯子C和D； 2、A——>C、B——>D； 3、C——>B、D——>A；终止。 VB应用程序的设计方法 ——“简易计算器”教学设计 揭阳第一中学卢嘉圳 教学内容：利用所学知识制作Visual Basic程序“简易计算器” 教学目标：能熟练运用CommandButton控件及TextBox控件进行Visual Basic(以下简称VB)程序的设计，能熟练运用条件语句编写代码 教学重点:运用开发VB程序一般过程的思路来开发“简易计算器” 教学难点:分析得出实现“简易计算器”各运算功能的算法。 教材分析： 当我刚开始进行程序设计的教学时，便感觉比较难教。这是因为程序设计本身枯燥、严谨，较难理解，而且学生大多数都是初学者，没有相应的知识基础。对于《程序设计实例》，我们选用的教材是广东教育出版社出版的《信息技术》第四册，该书采用的程序设计语言是VB，而学生是仅学过了一点点简单的QB编程之后就进入《程序设计实例》的学习的。 教材为我们总结了设计VB程序的一般步骤：创建用户界面；设置控件属性；编写事件程序代码；运行应用程序。我总结了一下，其实VB程序设计可分为设计用户界面及编写程序代码两个环节。 教学过程： 一、引入新课 任务：让学生按照书上提示完成一个非常简单的VB程序——“计算器”（仅包含开方、平方、求绝对值功能）的制作。 目的：加强对CommandButton控件及TextBox控件的掌握，复习对开方、求绝对值函数的使用。 引入本节课的学习任务：设计一个简易计算器，包含加、减、乘、除、开方、平方等运算。程序界面可参考下图。 具体功能为：在Text1中输入一个数值，然后单击代表运算符的按钮则运算结果会在text2中显示出来；比如在text1中输入一个2，然后按“+”按钮，再输入一个3按“-”按钮，再输入一个-4按“*”按钮，则实际为(2-3)*(-4)；最后在text2中显示结果为4。 模拟计算器 学生姓名：**** 指导老师：**** 摘要本课程设计的课题是设计一个模拟计算器的程序，能够进行表达式的计算，并且表达式中可以包含Abs()和Sqrt()运算。在课程设计中，系统开发平台为Windows ，程序设计设计语言采用C++，程序运行平台为Windows 或*nix。本程序的关键就是表达式的分离和处理，在程序设计中，采用了将输入的中缀表达式转化为后缀表达式的方法，具有可靠的运行效率。本程序做到了对输入的表达式（表达式可以包含浮点数并且Abs()和Sqrt()中可以嵌套子表达式）进行判定表达式是否合法并且求出表达式的值的功能。经过一系列的调试运行，程序实现了设计目标，可以正确的处理用户输入的表达式，对海量级数据都能够通过计算机运算快速解决。 关键词C++程序设计；数据结构；表达式运算；栈；中缀表达式；后缀表达式；字符串处理；表达式合法判定； 目录 1 引言 (3) 1.1课程设计目的 (3) 1.2课程设计内容 (3) 2 设计思路与方案 (4) 3 详细实现 (5) 3.1 表达式的合法判定 (5) 3.2 中缀表达式转化为后缀表达式 (5) 3.3 处理后缀表达式 (7) 3.4 表达式嵌套处理 (8) 4 运行环境与结果 (9) 4.1 运行环境 (9) 4.2 运行结果 (9) 5 结束语 (12) 参考文献 (13) 附录1：模拟计算器源程序清单 (14) 1 引言 本课程设计主要解决的是传统计算器中，不能对表达式进行运算的问题，通过制作该计算器模拟程序，可以做到快速的求解表达式的值，并且能够判定用户输入的表达式是否合法。该模拟计算器的核心部分就在用户输入的中缀表达式的转化，程序中用到了“栈”的后进先出的基本性质。利用两个“栈”，一个“数据栈”，一个“运算符栈”来把中缀表达式转换成后缀表达式。最后利用后缀表达式来求解表达式的值。该算法的复杂度为O(n)，能够高效、快速地求解表达式的值，提高用户的效率。 1.1课程设计目的 数据结构主要是研究计算机存储，组织数据，非数值计算程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 模拟计算器程序主要利用了“栈”这种数据结构来把中缀表达式转化为后缀表达式，并且运用了递归的思想来解决Abs()和Sqrt()中嵌套表达式的问题，其中还有一些统计的思想来判定表达式是否合法的算法。 1.2课程设计内容 本次课程设计为计算器模拟程序，主要解决表达式计算的问题，实现分别按表达式处理的过程分解为几个子过程，详细的求解过程如下：1 用户输入表达式。 2 判定表达式是否合法。 3 把中缀表达式转化为后缀表达式。 4 求出后缀表达式的结果。 5 输出表达式的结果。通过设计该程序，从而做到方便的求出一个表达式的值，而不需要一步一步进行运算。 摘要 随机蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)是进化计算领域中一种新兴、有效的亚启发式种群算法，它的基本思想来源于文化基因传承,其显著特点是具有局部搜索与全局信息混合的协同搜索策略，寻优能力强，易于编程实现，由Eusuff和Lansey于2003年正式提出，近几年来逐渐受到学术界和工程优化领域的关注。 本文从蛙跳算法的基本概念开始，分析算法的工作过程总结其基本原理与算法流程，然后对其关键参数进行说明并采用测试函数测试，最后将蛙跳算法应用于解决0-1背包问题，并与相关文献的结果进行对比，验证了算法解决此类问题的可行性。 关键词：蛙跳算法，函数优化，背包问题 ABSTRACT Shuffled Frog Leaping Algorithm (SFLA) is an emerging effective sub-heuristic in the field of evolutionary computation. Its basic idea comes from the cultural genetic inheritance and notable feature is a collaborative search strategy that is a mixture of local search and global information. SFLA has strong local search and global search ability, so it is good at searching for the best and is easy to be programmed. It is raised formally by Eusuff and Lansey in 2003 and become gradually popular the field of academic and optimization in recent years. Firstly, this paper describes the concept of SFLA, and summarizes its basic principle. Then, we draw the flowsheet, describe the key parameters and verify the algorithm by use of the test function. At last, we solve problems about the application on packing bags and prove its feasibility. Key words:S huffled Leaping Frog Algorithm，Function optimization ， Knapsack problem 算法与程序框图 一、程序框图与算法基本逻辑结构： 1.程序框图符号及作用： 程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形. 例：解一元二次方程：2 0(0)ax bx c a ++=≠ 2.画程序框图的规则： 为了使大家彼此之间能够读懂各自画出的框图，必须遵守一些共同的规则，下面对一些常用的规则做一简要介绍. （1）实用标准的框图符号. （2）框图一般按从上到下、从左到右的方向画. （3）一个完整的程序框图必须有终端框，用于表示程序的开始和结束. （4）除判断框外，大多数框图符号只有一个进入点和一个退出点，判断框是具有超过一个退出点的唯一符号，另外，一种判断框是“是”与“不是”两分支的判断，而且有且仅有两个结果；还有一种是多分支判断，有几个不同的结果. 3.算法的三种基本逻辑结构： （1）顺序结构 顺序结构是最简单的算法结构，语句与语句之间， 框与框之间是按从上到下的顺序进行的，它是由 若干个依次执行的处理步骤组成的，它是任何一 个算法离不开的基本结构.如图，只有在执行完步 骤n 后，才能接着执行步骤n+1. 例：.已知梯形的上底、下底和高分别为5、8、9，写出求梯形的面积的算法，画出流程图. 解：算法如下： S1 a ←5； S2 b ←8； S3 h ←9； S4 S ←（a +b ）×h /2； S5 输出S . 流程图如下： （2）条件结构 一些简单的算法可以用顺序结构来实现，顺序结构中所表达的逻辑关系是自然串行，线性排列的.但这种结构无法描述逻辑判断，并根据判断结果进行不同的处理的操作，（例如遇到十字路口看信号灯过马路的问题）因此，需要另一种逻辑结构来处理这类问题. 条件结构的结构形式如图，在此结构中含有一个判断框，算法执行到此判断框给定的条件P 时，根据条件P 是否成立，选择不同的执行框（步骤A ，步骤B ），无论条件P 是否成立，只能执行步骤A 或步骤B 之一，不可以两者都执行或都不执行.步骤A 和步骤B 中可以有一个是空的. 例：某铁路客运部门规定甲、乙两地之间旅客托运行李的费用为 0.53,50, 500.53(50)0.85, 50, c ωωωω?≤?=? ?+-?>?其中ω（单位：kg ）为行李的重量． 试给出计算费用c （单位：元）的一个算法，并画出流程图． 1S 输入行李的重量ω； 2S 如果50ω≤，那么0.53c ω=?， 否则500.53(50)0.85c ω=?+-?； 3S 输出行李的重量ω和运费c ． 步骤n 步骤n+1 ↓ ↓ ↓ 开始结束b h a 5 89 S (+)×/2a b h 输出S 满足条件？ 步骤A 步骤B 是否 满足条件？ 步骤A 是否 课题：用计算器计算 教学内容：三年级下册第48—51页内容 教学目标： 1、在运算中了解计算器的结构和基本功能；能正确、熟练地运用计算器进行一、两步的式题运算。 2、能运用计算器解决一些简单的实际问题，探索一些基本的数学规律。 3、培养观察、比较、分析、归纳、概括等能力。 教学过程： 一、尝试运用 师：开学到现在，我们一直在学习计算，下面这些题，哪些你一眼能看出来答案的，直接说的得数。 1、初步尝试 90＋56= 45×99≈ 87546—3469= 42×30= 2102÷30≈ 43×365= 师：最后两道看来有困难，列竖式算算。 师：先不报答案，要你自己检验做的对不对，你准备怎么样？试一试用计算器来验算，你们会吗？ 师：谁愿意带上你的竖式计算上来展示意下，向大家演示一下你用计算器验算的过程可以吗？（鼓励和表扬） 师：看来，大家还真的会用计算器！想不想“再显身手”？ 2、再次尝试：探索用计算器进行混合运算的方法 ①546×28－4276 ②2940 ÷28＋763 ③15021-87×99 ④25120÷（449－289） （1）这4题与上面4题相比，有什么不一样？会做吗？请试一试。 （2）交流操作方法。 （3）你有没有感觉到这4道题在计算过程中有什么不一样？ （4）用计算器计算③、④该怎么操作呢？我们以第③题为例，谁来介绍介绍？ （突出“记住中间数”、“使用MR键”、倒减等方法。） （①、②两题只要按顺序依次输入，③、④题要先算后一步，③④可以“记住过程得数”，③还可以倒减等） （5）介绍用存储键计算，尝试用“MR键”计算③④题。 二、解决生活问题 师：通过这几道题计算，你感觉计算器怎么样？你们喜欢用计算器吗？下面我们就发挥计算器的作用，用它来完成一个非常有价值的问题。 1、出示：一个水龙头滴水的动态画面。据统计一个没有关紧的水龙头，每天大约滴18千克的水，这些水就这样白白流掉了。 （1）照这样计算一年(按365天计算)要浪费多少千克水？ （2）把这些水分别装在饮水桶中(每桶约重15千克)算算大约能装多少桶？ （3）你家每月用几桶水？算算这些水够你家用几个月？大约合多少年？ 师：目前我国西南大旱，一些地区粮食因为缺水绝收。云南山区的孩子们喝脏水解渴。联系我们刚才的这些计算数据，你想到什么？ 三、探索计算规律： 师：既然人们发明了这么好的计算器，我们就应该更好地运用它。让我们来挑战一下自己，探索计算的规律好不好？ 1、找出规律后再填写每组的后2题得数，并用计算器检验。 19+9×9= 118+98×9= 1117+987×9= 11116+9876×9= 111115+98765×9= 学生汇报自己的发现。按这样一种规律写下去，下一题该是什么样的？ 2、自己探索规律。 1122÷34= 111222÷334= 11112222÷3334= …… 111…1222…2÷333…34= 2001个1 2001个2 2000个3 循环算法流程图： 1．若输入a ＝18，b ＝3， 那么输出结果为_____． 2．执行如图所示的流程图， 则输出S ＝_______． 3．下图所示的流程图的输出结果为____． 4．下图所示的流程图的输出结果为____． 5．如图所示的流程图输出的第 2010个数为________． 6．下图所示流程图输入n ＝4， 输出的结果为 5 ． 7．下图流程图，当输入n ＝6时，输出的结果为35． 8．某一计算机运算程序的工作步骤如下： S1 输入数据n ； S2 变量A 与k 的初始值为A ＝3，k ＝1； S3 若k ＜n ，执行S4； 若k ＝n ，执行S7； S4 执行运算B ＝1 1－A S5 将B 的值赋给A ； S6 将k ＋1的值赋给k 后执行S3； S7 输出A ． 若输入n ＝2010，则计算机将输出A ＝__． 9．如下流程图，循环体执行的次数为49． 10．下图流程图所给的运行结果为S ＝90，那么判断框中应填入的判断条件为____． 11．下图流程图输出结果为S＝132，则判断框中应填_____ 12．以下给出的是计算1 2 ＋ 1 4 ＋ 1 6 ＋…＋ 1 20 的 值的一个流程图，判断框内应填入的条件为___． 13．下图流程图是计算1＋1 3 ＋ 1 5 ＋…＋ 1 99 的 流程图，请你补充完整． 14．下图所示的流程图的功能为____．15．下图流程图的执行中依次输入72，91， 58，63，84，88，90，17，55，61，73，64，77，82，94，60．该流程图的功能为___． 算法及算法的表示检测 一、选择题（题型注释） 1．某算法要实现0到100的偶数之和，流程图如图所示。则i i+2被执行的次数是 A．50 B．51 C．100 D．101 2．某算法的部分流程图如右图所示，执行这部分流程后，变量x的值是 A.0 B.1 C.2 D.3 3．某商品团购优惠策略的流程图如图所示 当n为100、p为10时，实付金额s的值是( )。 A. 1000 B. 950 C. 850 D.750 4．写出下面流程图所表述的算法的功能▁▁▁▁ A. 降序排序 B. 求最大值 C. 交换输出 D. 判断是否是偶数5．以下流程图的运行结果是_______。 A．4 9 B．5 9 C．4 5 D．9 5 6．若输入两数1，-4，输出结果_______ A．-5 B．-3 C．5 D．3 7．如图所示，是求绝对值的算法，其描述方式分别是（） A．自然语言、流程图 B．伪代码、流程图 C．自然语言、伪代码D．流程图、自然语言 8．将两位同学的身高放入变量a和b中，比较这两个变量的大小，最后把其中较大的数放到变量c中并输出，流程图如图所示。①中应填（） A．ab C．a=b D．a<>b 9．求[0,100]之间所有偶数之和s的算法流程图如图所示。 为了实现此算法，图中判断框①和处理框②处可填入的是（） A.① x ≤ 100？② x←x+2 B. ① x ≤ 100？② x←x+1 C.① x ≥ 100？② x←x+2 D. ① x ≥ 100？② x←x+1 10．某算法流程图如图所示，执行该算法后，“s←s+i”共被执行的次数是（） 开始 A．0 B．6 C．7 D．8 11．某算法的流程图如下所示： 当输入a、b、c的值分别为5、2、8时，该算法的输出结果为（） A. 8 B. 2 C. 5 D. 7 “移动应用开发”实验报告 1 而受至到众多开发者的欢迎，成为真正意义上的开放式操作系统。计算器通 过算法实行简单的或学计算从而提高了数学计算的效率，实现计算器的界面 优化，使界面更加友好，操作更加方便。基于android的计算器的设计系统具 有良好的界面；必要的英互信息：简约美观的效票，使用人员能快捷简单地 进行操作，即可单机按钮进行操作，即时准确地获得需要的计算的结果，充 分降低了数字计算的难度和节约了时间。 2.系统概要设计 2.1计算器功能概要设计 根据需求，符合用户的实际需求，系统应实现以下功能：计算器界面友好， 方便使用，具有基本的加，减，乘，除功能。能够判断用户输入运算数是否 正确，支持小数运算，具有清除功能。 整个程序基于Android 技术开发，除总体模块外主要分为输入模块、显 示模块以及计算模块这三大部分。在整个系统中总体模块控制系统的生命周期，输入模块部分负责读取用户输入的数据，显示模块部分负责显示用户之 前输入的数据以及显示最终的计算结果，计算模块部分负责进行数据的运算 以及一些其他的功能。具体的说，总体模块的作用主要是生成应用程序的主类，控制应用程序的生命周期。 输入模块主要描述了计算器键盘以及键盘的监听即主要负责读取用户的 键盘输入以及响应触屏的按键，需要监听手机动作以及用指针事件处理方法 处理触屏的单击动作。同时提供了较为直观的键盘图形用户界面。 显示模块描述了计算器的显示区，即该区域用于显示用户输入的数据以 及最终的计算结果，同时负责显示一些其他的信息。 计算器模块主要描述了计算器的整体，实现了计算器的界面，负责用户 2 输入数据，计算，显示，清零等功能。 2.2输入模块设计 系统如果想完成计算器中各种功能，首先用户要能进行数据输入，由于 是在触屏手机上开发计算器程序，所以要求输入可以直接使用触屏进行，所 以在设计的时候就要充分的考虑这一点。正是由于考虑到这个特殊的地方， 所以在进行模块设计中，选择编写输入模块类的时候会特意选取使用可以支 持触屏输入的特殊增强型图形用户界面类。 输入模块主要的任务是描述计算器键盘以及实现键盘的监听，即当用户 点击按键或者屏幕的时候监听会去调用相应的处理办法，本模块还需要为系 统提供一个较为直观的键盘图形用户界面。输入模块的功能图如图 2.3显示模块设计 作为手机计算器系统，显示部分也是必不可少的一部分。没有显示部分 就没有办法显示用户输入的数字是否正确，甚至不能显示计算出的结果，由 此可见显示模块即包括输入的部分（因个人技术原因不能显示表达式的形式）也包括输出的部分。 显示模块主要完成的任务是描述计算器的显示区，该区域用于显示用户 输入的数据以及最终的计算结果和一些其他信息。同时本模块还将提供调用 和设置显示的具体方法。 3 算法与程序框图 【学习目标】 1.初步建立算法的概念； 2.让学生通过丰富的实例体会算法的思想； 3.让学生通过对具体问题的探究，初步了解算法的含义； 4.掌握程序框图的概念； 5.会用通用的图形符号表示算法，掌握算法的三个基本逻辑结构； 6.掌握画程序框图的基本规则，能正确画出程序框图. 【要点梳理】 要点一、算法的概念 1、算法的定义： 广义的算法是指完成某项工作的方法和步骤，那么我们可以说洗衣机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等等. 在数学中，现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成. 2、算法的特征： （1）确定性：算法的每一步都应当做到准确无误、“不重不漏”.“不重”是指不是可有可无的、甚至无用的步骤，“不漏”是指缺少哪一步都无法完成任务. （2）逻辑性：算法从开始的“第一步”直到“最后一步”之间做到环环相扣，分工明确，“前一步”是“后一步”的前提，“后一步”是“前一步”的继续. （3）有穷性：算法要有明确的开始和结束，当到达终止步骤时所要解决的问题必须有明确的结果，也就是说必须在有限步内完成任务，不能无限制的持续进行. （4）不唯一性：求解某一个问题的算法不一定是唯一的，对于一个问题可以有不同的算法． 3、设计算法的要求 （1）写出的算法，必须能解决一类问题（如：判断一个整数35是否为质数；求任意一个方程的近似解……），并且能够重复使用． （2）要使算法尽量简单、步骤尽量少． （3）要保证算法正确．且计算机能够执行，如：让计算机计算1×2×3×4×5是可以做到的． 4、算法的描述： （1）自然语言：自然语言就是人们日常使用的语言，可以是汉语、英语或数学语言等.用自然语言描述算法的优点是通俗易懂，当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和转向，并且操作步骤较多时，就不那么直观清晰了. （2）程序框图：所谓框图，就是指用规定的图形符号来描述算法，用框图描述算法具有直观、结构清晰、条理分明、通俗易懂、便于检查修改及交流等特点. （3）程序语言：算法最终可以通过程序的形式编写出来，并在计算机上执行. 要点诠释： 算法的特点:思路简单清晰，叙述复杂，步骤繁琐，计算量大，完全依靠人力难以完成，而这些恰恰就是计算机的特长，它能不厌其烦地完成枯燥的、重复的繁琐的工作，正因为这些，现代算法的作用之一就是使计算机代替人完成某些工作，这也是我们学习算法的重要原因之一. 事实上，算法中出现的程序只是用基本的语句把程序的主要结构描述出来，与真正的程序还有差距，所以算法描述的许多程序并不能直接运行，要运行程序，还要把程序按照某种语言的严格要求重新改写才行. 要点二、程序框图 1、程序框图的概念：数据结构课程设计计算器
随机蛙跳算法和NSGA2算法【精品文档】(完整版)
一种新的改进的混合蛙跳算法
简易计算器
微机课设简易计算器
基于安卓的计算器的设计与实现
算法和流程图
计算器制作
模拟计算器程序-课程设计
蛙跳算法的研究及应用
算法与程序框图汇总
用计算器计算(教案)
算法流程图
算法流程图练习
移动应用开发实验---简单计算器
算法与程序框图知识讲解