由于报告格式复杂，内容要求简要明确，很多人对写作报告，甚是感到苦恼。非常需要一份正确的报告格式范文。以下是小编精心整理的《遗传算法java实验报告》，希望对大家有所帮助。
第一篇：遗传算法java实验报告
JAVA实验报告 心得体会——密码攻击、遗传算法
JAVA实验报告
JAVA实验报告
一、 JAVA编程模拟密码攻击MimaGongji 1. 模拟密码攻击MimaGongji功能需求分析
编程模拟密码攻击的过程，实现下述功能：
(1)键盘输入12位密码，包括字母和数字;
(2)采用穷举法进行攻击，直到破解密码为止;
(3)屏幕输出试验的次数，并输出获得的密码。
2. MimaGongji基本设计思路
1) 基于对MimaGongji功能需求的分析，MimaGongji这个类作为主类，实现主要功能，包括密码的流输入，密码的穷举法破解和破解后密码的输出。 2) Java.io.*这个包主要实现数据的流输入和流输出。
3) public static void main(String[] args)这个方法是主要的方法，实现密码的键盘输入，采用穷举法进行攻击，并屏幕输出试验的次数和获得的密码。 4) .length()这个方法主要是计算一个字符串的长度
3. 实验步骤
1) Java程序代码(*.java)和详细的行注释 //文件名称为“MimaGongji.java” import java.io.*; //加入java的流输入和流输出包 class MimaGongji //定义主类 {
public static void main(String[] args)//引入主要方法 {
String s=""; try{ BufferedReader
mima=
new
BufferedReader(new InputStreamReader(System.in)); //定义密码的流输入
- 1
JAVA实验报告
//统计试验的次数
}
System.out.print(po);
} //输出破解之后的密码
} System.out.println();//换行 System.out.println("试验次数:"+g); //输出提示“试验的次数”
} }//类申明的结束
2)程序的运行(包括运行的过程、界面和结果图)
首先编写如上所示的源程序，保存文件名称为“MimaGongji.java”，然后编译源程序，编译完成后，生成一个字节码文件MimaGongji.class，执行这个程序，得到如下图所示的窗口：
- 345
JAVA实验报告
getContentPane().add(pb,BorderLayout.SOUTH);//把面板添加到窗口上
t1=new JTextField(50); //创建文本框
t2=new JTextField(50); //创建文本框
t3=new JTextField(50); //创建文本框 t4=new JTextField(5); //创建文本框 t5=new JTextField(5); //创建文本框 t6=new JTextField(5); //创建文本框
t2.setEditable(false); //定义文本框的不可书写
t4.setEditable(false); //定义文本框的不可书写
t5.setEditable(false); //定义文本框的不可书写
t6.setEditable(false); //定义文本框的不可书写
p.add(l3,BorderLayout.NORTH); //把标签添加到面板上 p.add(t3,BorderLayout.CENTER); //把文本框添加到面板上 p.add(l1,BorderLayout.NORTH); //把标签添加到面板上 p.add(t1,BorderLayout.CENTER); //把文本框添加到面板上 p.add(l2,BorderLayout.NORTH); //把标签添加到面板上 p.add(t2,BorderLayout.CENTER); //把文本框添加到面板上 p.add(l4,BorderLayout.NORTH); //把标签添加到面板上 p.add(t4,BorderLayout.CENTER); //把文本框添加到面板上 p.add(l5,BorderLayout.NORTH); //把标签添加到面板上 p.add(t5,BorderLayout.CENTER); //把文本框添加到面板上 p.add(l6,BorderLayout.NORTH); //把标签添加到面板上 p.add(t6,BorderLayout.CENTER); //把文本框添加到面板上 b0=new JButton("生成父母基因"); //创建父母基因生成按钮 pb.add(b0); //添加到面板上
b1=new JButton("100次交叉、变异"); //创建交叉、变异按钮 pb.add(b1); //添加到面板上 b2=new JButton("200次交叉、变异"); pb.add(b2); b3=new JButton("500次交叉、变异");
- 7
JAVA实验报告
Object s=e.getSource(); if(s==b0) //监听器实现功能 {
t3.setText(s1); //t3文本框输出s1
} t1.setText(s2); t4.setText(String.valueOf(H1)); t5.setText(String.valueOf(H2));
if(s==b1)time(100); //监听器实现功能
} if(s==b2)time(200); if(s==b3)time(500);
public void time(int r) //定义方法，实现函数的调用
{
int x,y,z,d1=0,d2=0,w,k,H3=0;
c=new int[23]; //定义一个数组
for(int j=1;j<=r;j++) //基因的交叉 {
x=1+(int)(Math.random()*23); //生成一个随机父亲基因位
y=1+(int)(Math.random()*23); //生成一个随机母亲基因位
z=f[x-1];f[x-1]=m[y-1];m[y-1]=z; //两个基因位的基因调换 }
for(int j=0;j<23;j++) //分别计算父母基因总和
{
d1+=f[j];
- 9
JAVA实验报告
2)程序的运行(包括运行的过程、界面和结果图)
首先编写如上所示的源程序，保存文件名称为“YichuanSuanfa.java”，然后编译源程序，编译完成后，生成一个字节码文件YichuanSuanfa.class，执行这个程序，得到如下图所示的窗口：
随机生成父母基因，得到如下图示：
- 11
JAVA实验报告
500次交叉、变异之后，得到如下图示：
4.实验心得
.java文件名要与主类名相同，JAVA对字
1.编写调试程序要注意程序编写的规则，母的大小写特别敏感，输入时要特捏注意大小写字母的定义，千万别犯主类名与.java文件名不同的错误。
2.在做图形界面时，注意设置图形界面的大小以及文本框、标签和按钮的位置。创建文本框的时候，可以设置文本框的可写性，以及文本框的颜色等等。在随机生成父母基因的时候，注意生成的随机数是什么范围，我们实验要求的范围是什么。监听器的响应，在文本框中输出的是一个基因整体还是一个数，都需要注意，因为这两种输出的方法不同。
3.为了简化程序，我们应该学会调用函数的方法。一开始做程序的时候，我没有注意到这一点，导致我的程序代码非常繁杂，而且容易出错。在同学的建议下，我把100次、200次、500次交叉、变异的实现使用调用函数的方法，这样我的程序代码变得简明多了。因此，在做程序的时候应该考虑到程序代码的简明扼要，不但美观，还能保证
JAVA实验报告
正确性的要求。
4.特别要注意的是一个变量的使用范围，在同一个方法中，同一变量是可以通用的，即不用重复定义，可以被系统认识，在不同的方法之间，同一变量是不能被对方所认识的，这就需要我们在定义变量时，注意变量的使用范围，如果需要在不同的方法中被引用，那就需要我们在所有的方法之外，同一类中进行定义。
第二篇：遗传算法学习心得体会
遗传算法
概念
遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它既能在搜索中自动获取和积累有关空间知识，并自适应地控制搜索过程以求得最优解遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近视最优方案。在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近视解。这个过程导致种群中个体的进化，得到的新个体比原个体更适应环境，就像自然界中的改造一样。
应用
遗传算法在人工智能的众多领域具有广泛应用。例如，机器学习、聚类、控制(如煤气管道控制)、规划(如生产任务规划)、设计(如通信网络设计、布局设计)、调度(如作业车间调度、机器调度、运输问题)、配置(机器配置、分配问题)、组合优化(如tsp、背包问题)、函数的最大值以及图像处理和信号处理等等。遗传算法多用应与复杂函数的优化问题中。 原理
遗传算法模拟了自然选择和遗传中发生的复制、交叉、和变异等现象，从任一初始种群出发，通过随机选择、交叉、变异操作，产生一群更适合环境的个体，使群体进行到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适合环境的个体求得问题的最优解。
算法流程 1. 编码：解空间中的解数据x，作为作为遗传算法的表现型形式。从表现
型到基本型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基本型串结构数据，这些串结构数据的不同的组合就构成了不同的点。 2. 初始种群的形成：随机产生n个初始串数据，每个串数据称为一个个体， n个串数据构成了一个群体。遗传算法以这n个串结构作为初始点开始迭代。设置进化代数计数器t 0;设置最大进行代数t;随机生成m个个体作为初始群体p(0)。 3. 适应度检测：适应度就是借鉴生物个体对环境的适应程度,适应度函数 就是对问题中的个体对象所设计的表征其优劣的一种测度。根据具体问题计算p(t)的适应度。
4. 选择：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到
下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
5. 交叉：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结
构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。 6. 变异：将变异算子作用于群体。即是对群体中的个体串的某些基因座上
的基因值作变动。
群体p(t)经过选择、交叉、变异运算之后得到下一代群体p(t+1)。 7. 终止条件判断:若t<=t,则t=t+1，转到第3步，否则以进化过程中所得
到的具有最大适应度个体作为最优解输出，终止计算。
遗传算法流程图如下图所示： 遗传算法
下几种：适应度比例方法、随机遍历抽样法、局部选择法。
其中轮盘赌选择法是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率，为遗传算法
2、交叉：在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。
交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法： b)二进制交叉(binary valued crossover) 1)单点交叉(single-point crossover) 2)多点交叉(multiple-point crossover) 3)均匀交叉(uniform crossover) 4)洗牌交叉(shuffle crossover) 5)缩小代理交叉(crossover with reduced surrogate)。
3、变异
变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法： a)实值变异 b)二进制变异。
一般来说，变异算子操作的基本步骤如下： a)对群中所有个体以事先设定的编译概率判断是否进行变异 b)对进行变异的个体随机选择变异位进行变异。
例：简单一元函数优化
求下面函数的最大值：
f(x)=xsin(10*pi*x)+2.0, -1<=x<=2; 程序： figure(1); fplot(variable.*sin(10*pi*variable)+2.0,[-1,2]); %画出函数曲线 %定义遗传算法参数
nind=40; %个体数目(number of individuals) maxgen=25; %最大遗传代数(maximum number of generations) preci=20; %变量的二进制位数(precision of variables) ggap=0.9; %代沟(generation gap) trace=zeros(2, maxgen); %寻优结果的初始值 fieldd=[20;-1;2;1;0;1;1]; %区域描述器(build field descriptor) chrom=crtbp(nind, preci); %初始种群 gen=0; %代计数器 variable=bs2rv(chrom, fieldd);
%计算初始种群的十进制转换
objv=variable.*sin(10*pi*variable)+2.0; %计算目标函数值 while gen
基本概念
遗传算法(genetic algorithms, ga)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 ga的组成: (1)编码(产生初始种群)
(2)适应度函数
(3)遗传算子(选择、交叉、变异)
(4)运行参数
编码
基因在一定能够意义上包含了它所代表的问题的解。基因的编码方式有很多，这也取决于要解决的问题本身。常见的编码方式有：
(1) 二进制编码，基因用0或1表示(常用于解决01背包问题) 如：基因a：00100011010 (代表一个个体的染色体) (2) 互换编码(用于解决排序问题，如旅行商问题和调度问题)
如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城市中，先经过城市2，再经过城市3，依此类推。
(3) 树形编码(用于遗传规划中的演化编程或者表示)
如,问题：给定了很多组输入和输出。请你为这些输入输出选择一个函数，使得这个函数把每个输入尽可能近地映射为输出。
编码方法：基因就是树形结构中的一些函数。
(4) 值编码 (二进制编码不好用时，解决复杂的数值问题)
在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他一些更复杂的东西。
适应度函数
遗传算法对一个个体(解)的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
如tsp问题，遍历各城市路径之和越小越好，这样可以用可能的最大路径长度减去实际经过的路径长度，作为该问题的适应度函数。
遗传算子——选择
遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。 sga(基本遗传算法)中采用轮盘赌选择方法。
轮盘赌选择又称比例选择算子，基本思想：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ，个体i 的适应度为 fi，则个体i 被选中遗传到下一代群体的概率为：
遗传算子——交叉
所谓交叉运算，是指对两个相互配对的染色体依据交叉概率按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算在ga中起关键作用，是产生新个体的主要方法。 1. 单交叉点法 (用于二进制编码)
选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。
如：交叉前：
00000|01110000000010000 11100|00000111111000101 交叉后：
00000|00000111111000101 11100|01110000000010000 2. 双交叉点法 (用于二进制编码)
选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因. 如：交叉前： 01 |0010| 11 11 |0111| 01 交叉后： 11 |0010| 01 01 |0111| 11 3. 基于“ 与/或 ”交叉法 (用于二进制编码) 对父代按位与”逻辑运算产生一子代a;按位”或”逻辑运算产生另一子代b。该交叉策略在解背包问题中效果较好 . 如：交叉前： 01001011 11011101 交叉后： 01001001 11011111 4. 单交叉点法 (用于互换编码)
选择一个交叉点，子代的从初始位置出发的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代中没有，就把它添加进去。 如：交叉前： 87213 | 09546 98356 | 71420 交叉后：
87213 | 95640 98356 | 72104 5. 部分匹配交叉(pmx)法(用于互换编码) 先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。
父代a：872 | 130 | 9546 父代b：983 | 567 | 1420 变为： temp a: 872 | 567 | 9546 temp b: 983 | 130 | 1420 对于 temp a、temp b中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1<——>5 3<——>6 7<——>0 子代a：802 | 567 | 9143 子代b：986 | 130 | 5427 6. 顺序交叉法(ox) (用于互换编码)
从父代a随机选一个编码子串，放到子代a的对应位置;子代a空余的位置从父代b中按b的顺序选取(与己有编码不重复)。同理可得子代b。 父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：
子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904 7. 循环交叉(cx)法(用于互换编码) cx同ox交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：ox中来自第一个亲代的编码子串是随机产生的，而cx却不是，它是根据两个双亲相应位置的编码而确定的。
父代a：1 2 3 4 5 6 7 8 9 | | | | | 父代a：5 4 6 9 2 3 7 8 1 可得循环基因：1->5->2->4->9->1 用循环的基因构成子代a，顺序与父代a一样 1 2 4 5 9 用父代b剩余的基因填满子代a： 1 2 6 4 5 3 7 8 9 子代b的编码同理。(循环基因 5->1->9->4->2->5)
遗传算子——变异 变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。ga中的变异运算是产生新个体的辅助方法，它决定了ga的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。
注：变异概率pm不能太小，这样降低全局搜索能力;也不能太大，pm > 0.5，这时ga退化为随机搜索。篇三：计算智能学习心得体会
计算智能学习心得体会
本学期我们水利水电专业开了“计算智能概论”这门课，有我们学院的金菊良教授给我们授课，据说这门课相当难理解，我们课下做了充分的准备，借了计算智能和人工智能相关方面的书籍，并提前了解了一点相关知识，我感觉看着有点先进，给我们以往学的课程有很大区别，是一种全新的概念和理论，里面的遗传算法、模糊集理论、神经网络更是闻所未闻，由于课前读了一些书籍，我以为课堂上应该能容易理解一点，想不到课堂上听着还是相当玄奥，遗传算法还好一点，因为高中学过生物遗传，遗传算法还能理解一点。像模糊集理论神经网络便不知所云了。虽然金老师讲课生动形象，幽默风趣，而且举了好多实际的例子，但有一些理论有点偏难。
多关于ci的解释。
虽然有好多计算智能理论还不太清楚，但是我对新知识还是相当渴望的，因为我本身比较爱学习，且喜欢读书。我感觉学到了许多知识：计算智能是一门经验科学，它研究自然的或人工的智能行为形成之原理以“推理即计算”为基本假设，开发某种理论、说明某项智能可以算法化，从而可以用机器模拟和实现;寻求和接受自然智能之启迪，但不企图完全仿制人类智能，其中心工程目标是研究设计和建立智能计算系统的方法。
由于我们只有16课时，所以我们学的面并不广，金老师主要教了一些计算智能方面的经典理论，我们所学的计算智能所涉及的领域主要包括以下三方面：遗传算法、人工神经网络方法和模糊集理论。
遗传算法最早由美国michigan大学john h. holland教授提出，
按照生物进化过程中的自然选择(selection)、父代杂交(crossover)和子代变异(mutation)的自然进化(natural evolution)方式，编制的计算机程序，能够解决许多复杂的优化问题，这类新的优化方法称之为遗传算法(genetic algorithm，ga)[7]。ga模拟生物进化过程中的主要特征有：(1)生物个体的染色体(chromosomes)的结构特征，即基因码序列(series of genetic code)决定了该个体对其生存环境的适应能力。(2)自然选择在生物群体(population)进化过程中起着主导作用，它决定了群体中那些适应能力(adaptability)强的个体能够生存下来并传宗接代，体现了“优胜劣汰”的进化规律。(3)个体繁殖(杂交)是通过父代个体间交换基因材料来实现的，生成的子代个体的染色体特征可能与父代的相似，也可能与父代的有显著差异，从而有可能改变个体适应环境的能力。
(4)变异使子代个体的染色体有别于其父代个体的染色体，从而也改变了子代个体对其环境的适应能力。(5)生物的进化过程，从微观上看是生物个体的染色体特征不断改善的过程，从宏观上看则是生物个体的适应能力不断提高的过程。 作为利用自然选择和群体遗传机制进行高维非线性空间寻优的一类通用方法，遗传算法(ga)不一定能寻得最优(optimal)点，但是它可以找到更优(superior)点，这种思路与人类行为中成功的标志是相似的。例如不必要求某个围棋高手是最优的，要战胜对手只需他(她)比其对手更强即可。因此，ga可能会暂时停留在某些非最优点上，直到变异发生使它迁移到另一更优点上。遗传算法随编码
方式、遗传操作算子的不同而表现为不同形式，因此难以象传统的共轭梯度法那样从形式上给以明确定义，它的识别标志在于它是否具有模拟生物的自然选择和群体遗传机理这一内在特征。目前国内外普遍应用的实施方案是标准遗传算法(simple genetic algorithm，sga)。 bp神经网络 bp神经网络是用反向传播学习算法(back-propagation algorithm，bp算法)训练的一种多层前馈型非线性映射网络，网络中各神经元接受前一级的输入，并输出到下一级，网络中没有反馈联接。bp神经网络通常可以分为不同的层(级)，第j层的输入仅与第j–1层的输出联接。由于输入层节点和输出层节点可与外界相连，直接接受环境的影响，所以称为可见层，而其它中间层则称为隐层(hidden layer)。决定一个bp神经网络性质的要素有三个：网络结构、神经元作用函数和学习算法，对这三个要素的研究构成了丰富多彩的内容，尤其是后者被研究得最多。bp算法是目前应用最为广泛且较成功的一种算法，它解决了多层前馈网络的学习问题，从而使该网络在各方面获得了广泛应用。它利用梯度搜索技术(gradient search technique)使代价函数(cost function)最小化。 bp算法把一组样本的输入输出问题归纳为一非线性优化问题，它使用了最优化方法中最常用的负梯度下降算法。用迭代运算求解网络权重和阈值对应于网络的学习记忆过程，加入隐层节点使得优化问题的可调参数增加，从而可得到更精确的解。
模糊集理论
模糊集理论(又称模糊数学，fuzzy mathematics)就是应用模糊集这一模拟人脑模糊思维的数学工具，来描述、分析、识别、分类、判断、推理、决策和控制各种模糊事物所形成的一门现代应用数学分支学科。经典数学仅考虑现实世界的数量而抛弃现实世界的质量，而模糊集理论则反映了现实世界数量与质量的统一性，是对经典数学的一种补充和完善。定义模糊集、模糊关系的不同运算(目前主要是代数运算)，就可得到相应的不同模糊数学方法。目前已研究成熟并广为应用的模糊数学方法主要有模糊模式识别、模糊聚类分析、模糊综合评价、模糊推理、模糊控制等方法。在现代科学技术体系中定性因素和主观因素定量化处理的方法至今仍很少，而模糊数学方法正是其中的典型代表，目前已在各科学和工程领域得到了广泛的成功应用，其主要原因在于它异于其它方法的一些显著特点：(1)模糊集的引入改善了二值逻辑中硬性的分类方法，是普通集合的推广，使模糊数学方法更加接近于广泛存在模糊性和不精确性的现实世界，也更加接近于人类思维方式。这些真实性使得模糊数学方法能很好地平衡系统的复杂性与描述系统的精确性，也有助于模糊数学方法充分提取各种专家经验信息和其它人类语言信息。(2)当系统为多输入多输出、强非线性、定性信息与定量信息混杂的动态系统时，系统的数学模型非常复杂或根本就不存在确定性数学模型，常规方法难以或不能有效处理这样的复杂系统，而模糊数学方法可以用建立在语言型经验之上的模糊集及其运算就可以简便有效地处理，有时甚至不需要辅以确定的数学模型。(3)模糊数学方法可以直接利用人类语言型概念及其运算，篇四：遗传算法总结
遗传算法总结
遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局自适应概率搜索算法。
一、遗传算法流程图
图1 遗传算法流程图
二、遗传算法的原理和方法 1) 染色体编码
把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。 de jong曾提出了两条操作性较强的实用编码原则：编码原则一：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案;编码原则二：应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。
编码方法主要有以下几种：二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法、参数级联编码方法、多参数交叉编码方法。 2) 适应值计算
由解空间中某一点的目标函数值f(x)到搜索空间中对应个体的适应度函数值 fit(f(x))的转换方法基本上有一下三种： a. 直接以待解的目标函数值f(x)转化为适应度函数值fit(f(x))，令 ?f(x) 目标函数为最大化函数 fit(fx())= ? ??f(x)目标函数为最小化函数 ?cmax?f(x) f(x)?cmax b. 对于最小值的问题，做下列转化fit(f(x))??，其中cmax是 0 其他? f(x)的最大输入值。
c. 若目标函数为最小值问题，fit(f(x))? 1 , c?0, c?f(x)?0 1?c?f(x) 1 , c?0, c?f(x)?0 1?c?f(x) 若目标函数为最大值问题，fit(f(x))?3) 选择、交叉、变异
遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：根据每个个体的适应度值大小选择。适应度较高的个体被遗传到下一代群体中的概率较大;适应度较低的个体的被遗传到下一代群体中的概率较小。其中选择的方法有：轮盘赌选择、随机竞争选择、最佳保留选择、无回放随机选择、确定式选择等。
遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉操作主要有单点交叉、两点交叉与多点交叉、均匀交叉和算数交叉四种。
遗传算法中的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他基因来替换，从而形成一个新的个体。主要有基本位变异、均匀变异、边界变异等几种变异操作方法。 4) 控制参数选择
交叉概率pcpm
三、算例
min f(x1,x2)?(x1?3)2?(x2?2)2 2 ?g1(x1,x2)?x12?x2?5? s.t.?h1(x1,x2)?x1?2x2?4?0?x,x?10，x?n 121? (1) 1)三种不同的遗传方法
方法一：原模型中x
1、x2均为决策变量，操作如下。 a. 采用混合整数编码，对x1进行十进制编码，x2进行二进制编码; b. 适应度函数值采用fit(f(x1,x2))? 1 计算，其中 c?f(x1,x2) c???max{0,g1(x1,x2)?5}???max{0,|h1(x1,x2)?4|}，?=?=10000; c. 采用赌轮盘选择、单点交叉和基本位变异; d. pc=0.8，pm=0.1，遗传代数为200，种群中个体数100; e. 终止条件为连续十次最优个体保持不变或遗传代数到达200。 方法二：已知等式约束h1(x1,x2)，可得x2?(4?x1)/2，则原问题可化为 min f(x1)?(x1?3)2?(( 4?x1 )?2)22 (2) 4?x12?2 g(x)?x?()?5111? 2?s..t?0?x1?10，x1?n?4?x1?0??10 2? x min f(x1)?(x1?3)2?(1)2 2 即等式约束简化后的模型为 4?x12?2 g(x)?x?()?5?1 s..t?112??0?x1?4，x1?n 其中a~b的操作如下，而c~e的操作同方法一。 a. 对x1进行十进制编码; b. 适应度函数值采用fit(f(x1,x2))? (3) 1 计算，其中 c?f(x1,x2) c???max{0,g1(x1,x2)?5}，?=10000 方法三：在方法二的基础上，改变x1的编码方法，对x1进行二进制编码。由于0?x1?4，且为自然数，则二进制编码至少为3位，但3位的二进制可以表示0~7的整数，所以存在冗余编码。则通过惩罚来排除冗余编码，即适应度函数值采用 fit(f(x1,x2))? 1 计算。 c?f(x1,x2) 其中c???max{0,g1(x1,x2)?5}???max{0,x1(i)?4}，?=10000。x1(i)表示个体解码后的x1。
2)三种方法的计算结果
方法一可得到三个不同的解：
解1：x1?2,x2?1, fit(f(x1,x2))?0.4646, f(x)?2.0000，适应度趋势图如下： 图2 方法一解1的适应度趋势图
解2：x1?0,x2?2, fit(f(x1,x2))?0.1075, f(x)?9.0000，适应度趋势图如下： 篇五：遗传算法学习作业
遗传算法学习总结 1.1 概述 遗传算法是一类借鉴生物界的进化规律(适者生存，优胜劣汰遗传机制)演化而来的自适应概率性随机化迭代搜索算法。1962年霍兰德(holland)教授首次提出了ga算法的思想，它的基本思想是基于darwin进化论和mendel的遗传演说。darwin进化论最重要的是适者生存的原理，它认为每一代种群总是向着前进方向发展，越来越适应环境。每一个个体都有继承前代的特性，但不是完全继承，会产生一些新特性。最终只有适应环境的特征才能被保留下来。mendel遗传学说最重要的是基因遗传原理，它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。一条染色体中存在很多基因，每个基因有自己的位置并控制着外部特征;基因的产生和变异直接影响到个体的特性是否能适应环境。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
遗传算法正是借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。
与自然界相似，遗传算法对求解问题的本身一无所知，从代表问题可能潜在解集的一个种群(population)开始，每一个种群则由经过基因(gene)编码(coding)的一定数目的个体 (individual)构成。每个个体实际上是染色体(chromosome)带有特征的实体。把问题的解表示成染色体，并基于适应值来选择染色体，遗传算法所需要的仅是对算法所产生的每个染色体进行评价，使适应性好的染色体有更多的繁殖机会。在算法中也就是以二进制编码的串。并且，在执行遗传算法之前，给出一群染色体，也就是假设解。然后，把这些假设解置于问题的“环境”中，也即在一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染色体进行复制，淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化，直到最适合环境的值。 1.2遗传算法的基本原理和特点 1.2.1 算法原理
在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群;通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群，再对这个新种群进行下一轮进化，这就是遗传算法的基本原理。
遗传算法的主要步骤如下： 1)随机产生一个由确定长度的特征串组成的初始群体; 2)对串群体迭代地执行步骤(1)和(2)，直到满足停止准则： (1)计算群体中每个个体的适应值。 (2)应用复制、杂交和变异算子产生下一代群体。 3)把在任一代中出现的最好的个体串指定为遗传算法的执行结果。这个结果可以表示问题的一个解(或近似解)。 基本遗传算法的流程图如图 1-1，其中gen是当前代数，m为每代种群中最大个体数。
图1-1 基本遗传算法的流程图 1.2.2 算法特点
遗传算法的特点如下： 1) 遗传算法中不包含待解决问题所持有的形态。它是从改变基因的配置来实现问题的整体优化的，因而属于自下而上的优化方法; 2) 类似于生物的进化过程，遗传算法处理的是变量集合的编码而非变量本身。它直接 对结构对象进行操作，不存在求导和函数连续性的限定; 3) 遗传算法具有内在的隐并行性和更好的全局寻优能力; 4) 遗传算法采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
遗传算法的这些特点已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。 1.3 基本遗传算法的步骤
1.3.1 染色体编码(chromosome coding)与解码(decode) 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值{0，1}所组成。初始群体中各个个体的基因可用均匀分布的随机数来生成。例如：x=100111001000101101就可表示一个个体，该个体的染色体长度是n=18。 (1)编码：变量x作为实数，可以视为遗传算法的表现型形式。从表现型到基因型的映射称为编码。设某一参数的取值范围为[u1，u2]，我们用长度为k的
二进制编码符号来表示该参数，则它总共产生2k种不同的编码，可使参数编码时的对应关系为：
000000?0000=0→u1 000000?0001=1→u1+? 000000?0010=2→u1+2? ? 111111?1111=2k-1→u2 u?u其中，?=2 k1。 2?1 (2)解码：假设某一个体的编码为bkbk-1bk-2?b2b1,则对应的解码公式为 x?u1?(?bi?2i?1)? i?1ku2?u1 ① k2?1 例如：设有参数x∈[2，4]，现用5位二进制编码对x进行编码，得25=32个二进制串(染色体)：
00000,00001,00010,00011,00100,00101,00110,00111 01000,01001,01010,01011,01100,01101,01110,01111 10000,10001,10010,10011,10100,10101,10110,10111 11000,11001,11010,11011,11100,11101,11110,11111 对于任一个二进制串，只要代入公式①，就可得到相应的解码，如x22=10101,它对应的十进制为?bi?2i?1=1+0*2+1*22+0*23+1*24=21,则对应参数 i?15 x的值为2+21*(4-2)/(25-1)=3.3548。 1.3.2 个体适应度的检测评估
基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到下一代群体中的机会多少。为了正确估计这个概率，要求所有个体的适应度
必须为非负数。所以，根据不同种类的问题，需要预先确定好由目标函数值到个体适应度之间的转换规律，特别是要预先确定好当目标函数值为负数时的处理方法。例如，可选取一个适当大的正数c，使个体的适应度为目标函数值加上正数c。 1.3.3 遗传算子
基本遗传算法使用下列三种遗传算子：
(1)选择运算使用比例选择算子。比例选择因子是利用比例于各个个体适应度的概率决定其子孙的遗传可能性。若设种群数为m，个体i的适应度为fi,则个体i被选取的概率为 pi?fi/?fk k?1m 当个体选择的概率给定后，产生[0，1]之间的均匀随机数来决定哪个个体参加交配。若个体的选择概率大，则能被多次选中，它的遗传基因就会在种群中扩大;若个体的选择概率小，则被淘汰。
我们经常采用的是轮盘赌的原理，个体的选择概率是基于它们的性能进行的一些计算。实值范围——总和是所有个体期望的选择概率的总和或当前种群中所有个体原始适应度值的总和。个体采用一对一方式
映像到范围[0，sum]的一连续区间，每一个体区间的 大小与对应个体的适应度值相匹配。如图1所示，轮
盘赌轮的周长是6个个体适应度值的总和，个体5 是最大适应度个体，它占有最大的区间。选择一个个
体，用在[0，sum]间产生随机数，看此随机数在哪个
个体的区间上，则此个体被选中。重复此过程，直到
所需数量个体被选中为止。
(2)交叉运算使用单点交叉算子。只有一个交叉点位置，任意挑选经过选择操作后种群中两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因码，形成两个子个体，如图2所示。
父个体1 父个体2 110 11 011 00 单点交叉 子个体1 子个体2 图2 单点交叉示意图
(3)变异运算使用基本位变异算子或均匀变异算子。为了避免问题 过早收敛，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即0变为1，而1变为0，如图3所示。
变异
图3 变异操作示意图 1.3.4 基本遗传算法的运行参数 基本遗传算法有下列4个运行参数需要预先设定，即m,t,pc,pm。 m为群体大小，即群体中所含个体的数量，一般取为20~100; t为遗传算法的终止进化代数，一般取为100~500; pc为交叉概率，一般取为0.4~0.99; pm为变异概率，一般取为0.0001~0.1。 1.4遗传算法的应用 进入90年代后，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。
遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。如工程结构优化、计算数学、制造系统、航空航天、交通、计算机科学、通信、电子学、材料科学等。 1)ga在数值优化上的应用
最优化问题是遗传算法经典应用领域，但采用常规方法对于大规模、多峰态函数、含离散变量等问题的有效解决往往存在许多障碍。对全局变化问题，目前存在确定性和非确定性两类方法。前者以brianin的下降轨线法、levy的隧道法和r.ge的填充函数为代表。该类方法虽然收敛快、计算效率高，但算法复杂，求得全局极值的概率不大。 遗传算法作为现代最优化的手段，实践证明，它应用于大规模、多峰多态函数、含离散变量等情况下的全局优化问题是合适的，在求解速度和质量上远远超过常规方法。 2)ga 在组合优化中的应用
3)遗传算法在机器学习中的应用
机器学习系统实际上是对人的学习机制的一种抽象和模拟，是一种理想的学习模型。基于符号学习的机器学习系统如监督型学习系统、条件反射学习系统、类比式学习系统、推理学习系统等，只具备一些较初级的学习能力。近年来，由于遗传算法的发展，基于进化机制遗传学习成为一种新的机器学习方法，它将知识表达为另一种符号形式—遗传基因型，通过模拟生物的进化过程，实现专门领域知识的合理增长型学习。 4)遗传算法在并行处理中的应用 遗传算法固有的并行性和大规模并行机的快速发展，促使许多研究者开始研究遗传算法的并行化问题，研究数量更加接近自然界的软件群体将成为可能。遗传算法与并行计算的结合，能把并行机的高速性和遗传算法固有的并行性两者的长处彼此结合起来，从而也促进了并行遗传算法的研究与发展。
第三篇：RSA算法实验报告
信息安全实验报告
题 目 RSA算法 姓 名 学 号
专业年级 计算机科学与技术2014级(1)班 指导教师
2016年 12 月 10日
一、 实验目的
了解非对称加密机制 理解RSA算法的加解密原理
熟悉Java的学习以及运用Java实现RSA算法的加解密过程
二、 实验背景
钥密码体制中，加密密钥(即公开密钥)PK是公开信息，而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存;另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。 RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在的这么多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。
三、 实验原理
1. 非对称密钥加解密概述
使用对称密钥加密体制进行保密通信时，任意不同的两个用户之间都应该使用互不相同的密钥。这样，如果一个网络中有n个用户，他们之间彼此都可能进行秘密通信，这时网络中将需要n(n-1)/2个密钥(其中，每个用户都需要保存n-1个密钥)，这样巨大的密钥量给密钥分配和管理带来了极大的困难。另外，随着计算机网络，特别是因特网的发展，网络上互不相识的用户可能需要进行保密的会话(例如，如果用户在进行电子商务活动时，需要保密的连接，这时的客户对象可能根本不是固定的对象)。最后，对称密钥加密机制难以解决签名验证问题。
非对称密钥加密也称为公开密钥加密，或者叫做公钥加密算法。使用公开密钥密码的每一个用户都分别拥有两个密钥：加密密钥和解密密钥，它们两者并不相同，并且由加密密钥得到解密密钥在计算机上是不可行的。每一个用户的加密密钥都是公开的。因此，加密密钥也称为公开密钥。所有用户的公开密钥都将记录在作用类似于电话号码薄的密钥本上，而它可以被所有用户访问，这样每一个用户都可以得到其他所有用户的公开密钥。同时，每一个用户的解密密钥将由用户保存并严格保密。因此，解密密钥也称为私有密钥。
非对称密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。公钥加密算法一般是将对密钥的求解转化为对数学上的困难问题的求解，例如RSA算法的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，已知两个大素数a和b，求出a*b是容易计算的，而已知a*b，想知道其是哪两个大素数的乘积目前还没有好的计算方法，另外也有一些非对称加密算法(如ELGamal算法)的安全性是基于求“离散对数”这个数学难题上的。
在公钥密码系统中每个实体都有自己的公钥和相应的私钥。公钥密码系统的加密变换和解密变换分别用E和D表示。任何实体B要向实体A发送信息m的步骤如下：实体B首先获得实体A的真实公钥的拷贝(eA)，实体B使用eA计算密文c=E(m)并发送给实体A，实体A使用自己的私钥dA，计算m=D(c)解密密文，恢复出明文m。这里公钥不需要保密，但要保证它的真实性，即eA确实是实体A掌握的私钥dA所对应的公钥。提供真实的公钥比安全地分配密钥实现起来要容易得多。这也是公钥密码系统的主要优点之一。
公钥密码系统的主要目的是提供保密性，它不能提供数据源认证(data origin authentication)和数据完整性(data integrity)。数据源认证是指：指定的数据是在以前的某个时间确实是由真正的源创建的。数据完整性是指：真正的源创建该数据后经过传输后存储没有发生改变。数据源认证和数据完整性要由其他技术来提供(如消息认证码技术、数字签名技术等)。
从本质上来看，公钥密码比对称密钥密码加密的速度要慢，粗略的说，公钥加密算法RSA硬件实现比分组加密算法DES硬件实现的速度慢1500倍，而软件实现的速度要慢100倍。
公钥解密也可以提供认证保证(如：在实体认证协议、带认证的密钥建立协议等)。公钥加密中必须有颁发让发送消息的人得到想要发送到的那个人的公钥的真实拷贝，否则就会受到伪装攻击。在实践中有很多方法分发真实的公钥，如：使用可信的公共文件，使用在线可信服务器，使用离线服务器和认证。
2. 公钥加解密的优缺点：
1) 大型网络中的每个用户需要的密钥数量少。
2) 对管理公钥的可信第三方的信任程度要求不高而且是离线的。 3) 只有私钥是保密的，而公钥只要保证它的真实性。 4) 多数公钥加密比对称密钥加密的速度要慢几个数量级。 5) 公钥加密方案的密钥长度比对称加密的密钥要长。 6) 公钥加密方案没有被证明是安全的。
公钥密码的概念本身就被公认为是密码学上的一块里程碑。三十多年来的研究表明，公钥密码成功地解决了计算机网络安全中的密钥管理，身份认证和数字签名等问题，已经成为信息安全技术中的重大核心技术。
四、 RSA算法 1. 概述
RSA加密算法于1977年由美国麻省理工学院的Ronal Rivest，Adi Shamir和Len Adleman三位年轻教授提出，并以三人的姓氏Rivest，Shamir和Adleman命名为RSA算法。这三位科学家荣获2002图灵奖，以表彰他们在算法方面的突出贡献。该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数的乘积却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。它无须收发双方同时参与加密过程，既可以用于保密也可以用于签名，因而非常适合于电子邮件系统的加密，互连网和信用卡安全系统。
算法概述：找两素数p和q，取n=p*q，取t=(p-1)*(q-1)，取任何一个数e，要求满足e
2. 算法设计
1) publicstaticvoid GetPrime() 说明：利用Java语言的中的java.math.BigInteger类的方法中随机产生大数。
2) public static boolean MillerRobin(BigInteger num) 参数说明：num是由GetPrime方法产生的大数。
说明：这个方法判断GetPrime方法传过来的是否是一个素数，是就返回true,否就返回false。
3) public static BigInteger powmod( BigIntegera，BigIntegert，BigInteger num ) 说明：这个方法对传入的大数进行幂运算。
4) public static BigInteger invmod(BigInteger a， BigInteger b) 说明：这个方法对大数进行取模运算。
5) public static String Encode(String inStr，BigInteger PrimeP，BigInteger PrimeQ，BigInteger n，int nLen，int m，JTextFieldd) 方法名称：加密算法。 参数说明：
inStr是从界面输入的明文。
PrimeP和PrimeQ是由GetPrime方法产生的两个大素数。 n是由PrimeP和PrimeQ得到的值。 nLen为n的长度。 d为公钥。
6) publicstatic String Decode(String inStr，BigInteger PrimeP，BigInteger PrimeQ， BigInteger n，int nLen，int m，JTextField e) 方法名称：解密算法。 参数说明：
inStr是从界面输入的明文。
PrimeP和PrimeQ是由GetPrime方法产生的两个大素数。 n是由PrimeP和PrimeQ得到的值。 nLen为n的长度。 e为私钥。
在对称加密中：n，d两个数构成公钥，可以告诉别人;n，e两个数构成私钥，e自己保留，不让任何人知道。给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。
RSA的安全性在于对于一个大数n，没有有效的方法能够将其分解从而在已知n，d的情况下无法获得e;同样在已知n，e的情况下无法求得d。
五、 实验结果
实验结果如下图所示：
六、 实验总结
本次实验对输入的任意一段明文字母，实现了输出对应密钥的密文字母。亲手实际编写RSA密码算法代码，更好的了解和掌握了RSA的相关内容。通过用Java对RSA密码体制进行编程，对RSA密码体制的加解密过程有了更深入的理解。通过这个实验更是让我获得了很多实际工作中所要具备的能力。
七、 代码附录
略
第四篇：《计算机算法》实验报告
1. 实验名称
本次实验的名称。
2. 问题描述
对本次实验要解决的问题的描述。
例子：处理汉诺塔问题时，描述什么是汉诺塔问题。
3. 解决思路
采用什么方法;为什么可以采用这个方法; 例子：处理棋盘覆盖问题时，
采用什么方法：采用递归分治的方法处理;
为什么可以采用递归分治方法的原因(P21页图2-6下面一段，理解之后用自己的话表述)：由于将棋盘横、纵各一分为二之后，特殊方格必然位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，如果采用某种L型骨牌覆盖没有特殊方格的三个小棋盘的中心相连部分(参见图2-6的b)，则三个小棋盘都各有1个特殊方格所覆盖。因此，这样处理之后，原来大棋盘覆盖的问题，就转化为四个小棋盘覆盖的问题，因此可以采用分治策略进行递归处理。
4. 算法设计与分析
给出算法设计的基本思想，如：伪算法描述，递归方程等。并分析算法的时间复杂度(空间复杂度)。注意，一定要有文字说明。 例子：快速排序 伪算法描述
QuickSort(int a[], int p, int r) { 如果待排序数组a[]中只有一个元素则直接返回; 如果待排序数组a[]中不止一个元素，则进行如下处理 {
对数组a[p:r]进行Partition划分，使得a[p:r]以a[p]为标准，划分为三个部分，即：
左半部分a[p:q-1];划分基准a[q]=a[p];右半部分a[q+1:r];
对左半部分快速排序QuickSort(a, p, q-1);
对右半部分快速排序QuickSort(a, q+1, r); } }
例子：0-1背包问题
递归关系或者递归方程。
给出P72页“2.递归关系”中的递归表达式，并给出文字说明。 注意：伪算法描述，或者递归方程不一定全部需要。根据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。
5. 程序实现
依据第4部分，给出C语言(其他语言亦可)的程序实现，并进行算法时间(空间)复杂度分析。
程序实现部分要包括：程序代码、程序注释、程序运行结果(或者截图)。
例子：快速排序的partition函数 int Partition (Type a[], int p, int r) {
int i=p, j= r+1;
int x = a[p]; //x=a[p]是对数组a进行划分的标准;
/* 以下循环将数组a[p:r]以a[p]为标准进行划分，在划分完毕之后，
* a[p]调整到数组a[p:r]的中间位置q，有a[q]=a[p];q左边所有的
* 元素均小于a[p]，即a[p:q-1]中的任意元素都小于a[p];q右边
* 所有的元素均大于a[p]，即a[q+1:r]中的元素都大于a[p]。
* /
while(true){ /* i用来从数组a[p:r]的左边向右边扫描，如果a[++i]中的元素总是 * 小于基准元素的，则是符合划分标准的，因此，不用额外处理， * 循环一直继续,直到第一个不满足划分标准的a[++i](即a[++i]>=i) * 出现，或者整个数组a[p:r]扫描完毕(即i
while(a[++i]
„„
6. 总结
不用每个实验写一个总结，可以在一次课作业的最后写一个总结。当然，如果需要，在每一个实验结尾都写一个总结也是可以的。总结的目的是自己知识学习的总结、解决问题的总结、编程的总结等等。
第五篇：用贪心算法求解Prim算法上机实验报告书
算法分析与设计
实验报告
班级：学号：姓名：上机时间：
一、实验目的与要求：
1、熟悉贪心算法的基本原理和适用范围;
2、使用贪心算法编程，求解最小生成树问题。
二、实验题目：
用贪心算法求解Prim算法
三、实验内容：
任选一种贪心算法(prim或Kruskal)，求解最小生成树。对算法进行
描述和复杂性分析。编程实现。
四、问题描述：
设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim
算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如
下的贪心选择：选取满足条件i∈s，j∈V-S，且c[i][j]最小的边，将顶
点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到
的所有边恰好构成G的一棵最小生成树。
五、问题分析与算法设计
六、实验结果及分析
七、实验总结
八、程序代码
#include
#include
#include
#include
#include
#define maxint 20
#define inf 700
int AllSelected(int n,int s[])
{
int i;
for(i = 1;i <= n;i++)
{
if(s[i] == 0)
return 0;
}
return 1;
}
void Prim(int n,int **c)
{
int lowcost[maxint];
int closest[maxint];
bools[maxint];s[1]=true;
for(int i=2;i<=n;i++)
{
lowcost[i]=c[1][i];
closest[i]=1;
s[i]=false;
}
for( i=1;i<=n;i++)
{
int min=inf;
int j=1;
for(int k=2;k<=n;k++)
{
if((lowcost[k]
{
min=lowcost[k];
j=k;
}
s[j]=true;
for(int k=2;k<=n;k++)
if((c[j][k]
{
lowcost[k]=c[j][k];closest[k]=j;
}
}
}
}
void main()
{
int n,i,j;
int **k;
printf("请输入顶点个数:");
scanf("%d",&n);
k= (int **)malloc(sizeof(int *)*(n + 1));
for(i = 1;i <= n;i++)
k[i] = (int *)malloc(sizeof(int)*(n+1));
printf("输入顶点间的权值(自己到自己为0，没有路的为大于其他任何值的数): ");for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
{
printf("k[%d][%d]=k[%d][%d]=",i,j,j,i);
scanf("%d",&k[i][j]);
k[j][i]=k[i][j];
}
printf(" ");
printf("顶点 ");
for(i=1;i<=n;i++)
{
printf("%d ",i);
}
printf(" ");
for(i=1;i<=n;i++)
{
printf("%d ",i);
for(j=1;j<=n;j++)
{
printf("%d ",k[i][j]);
}
printf(" ");
}
printf(" ");
Prim(n,k);
}