精华内容
下载资源
问答
  • 算法设计四个要求

    千次阅读 2020-03-19 19:08:23
    算法设计四个要求 1. 正确性 2. 可读性:便于他人理解交流 3. 健壮性:当输入数据不合法,算法也能做出相应处理。 4. 时间效率高和存储量低

    算法设计的四个要求

    1. 正确性
    2. 可读性:便于他人理解交流
    3. 健壮性:当输入数据不合法,算法也能做出相应处理。
    4. 时间效率高和存储量低

    展开全文
  • 遗传算法

    万次阅读 多人点赞 2019-04-06 21:41:47
    使用遗传算法求解多峰函数的最大值,是我的一项课程作业,做完之后,顺便把文档整理出来做记录。全部内容如下: 1、问题描述 编程实现遗传算法,并求解多峰函数的最大值。多峰函数的表达式如下所示: 用MATLAB...

    使用遗传算法求解多峰函数的最大值,是我的一项课程作业,做完之后,顺便把文档整理出来做个记录。全部内容如下:

    1、问题描述

    编程实现遗传算法,并求解多峰函数的最大值。多峰函数的表达式如下所示:
    在这里插入图片描述
    用MATLAB做出函数的图像如下:
    在这里插入图片描述

    2、算法描述及实现

    2.1、遗传算法概述

    遗传算法(GA,Genetic Algorithm),也称为进化算法。遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。其主要特点是直接对结构对象进行操作,因此不同于其他求解最优解的算法,遗传算法不存在求导和对函数连续性的限定,采用概率化的寻优方法,不需要确定的规则就能自动获取和指导优化的搜索空间,自适应地调整搜索方向。

    以上是对遗传算法相对抽象的总结,为了更具体形象的解释遗传算法的一般原理,我们首先介绍一些生物学上的概念

    ①种群:不同生物个体形成的群体,生物的进化以群体的形式进行,这样的一个群体称为种群;

    ②个体:组成种群的单个生物;

    ③基因:带有遗传信息的DNA片段,可以通俗的将基因理解为一段信息,这段信息决定的生物个体的性状;

    ④表现型:根据基因形成的个体的外部表现;

    ⑤适应度:生物个体对于生存环境的适应程度,越适应那么其得以存活和繁衍的概率就越大;

    ⑥遗传:通过繁殖过程,子代将从父母双方各获取一部分基因,形成新的自己的基因,这个过程中,会发生基因的复制、交叉,也会以较低的概率发生基因突变;

    ⑦自然选择:物竞天择,适者生存的自然淘汰机制。具体为对环境适应度高的个体参与繁殖的机会比较多,后代就会越来越多。适应度低的个体参与繁殖的机会比较少,后代就会越来越少;

    ⑧进化:种群通过代际繁衍不断适应生存环境的过程,在这个过程中,以对外界环境的适应度为评判标准,生物的性状不断得到改良。

    了解了这些术语的含义,我们就可以进一步说说生物进化的过程了。由于自然选择是客观存在的,即生物只能改变自己去适应环境,那么在自然选择的过程中,适应度低的个体会被淘汰,适应度高的个体被保留,高适应度的父体与母体又有更高的概率繁衍出适应度高的子代,因此在一代又一代的繁衍之后,高适应度的个体在种群中所占的比例越来越大,种群就这样完成了进化。

    现在我们要参考生物进化的过程来设计算法解决求最优解的问题。对此,遗传算法的思路是,将要解决的问题模拟成一个生物进化的过程,通过进化来寻找最优解。以我们题目中寻找多峰函数的最大值这个问题为例

    将(x, y)这一可能的解作为一个个体;将多峰函数的函数值f(x, y)作为个体的适应度;对(x, y)进行编码作为个体的基因;以适应度为标准不断筛选生物个体;通过遗传算子(如复制、交叉、变异等)不断产生下一代。如此不断循环迭代,完成进化。最终,根据设定的迭代次数,可得到最后一代种群,该种群中的个体适应度都较高,而多峰函数的最大值就有比较大的概率存在于这一群解中,以种群中适应度最高的个体作为问题的解,则可以说该解有比较高的概率就是我们希望求得的最优解。

    文字述说终究还是不如图表好理解,因此还是看图吧(下图将本题与自然遗传联系了起来):
    在这里插入图片描述
    通过以上描述,我们不难看出,遗传算法不能保证一定能求得最优解,而只能以一定的概率求最优解。但是使用遗传算法时,我们可以不用关心具体如何去找最优解,要做的只是简单的否定一些表现不好的个体。这一优点也是遗传算法能够取得广泛应用的原因之一。

    2.2、算法的流程

    通过上文的阐述,对于如何模拟自然进化来求题中多峰函数的最优解已经比较明晰了。这里我将列出遗传算法的主要步骤,并一一解析:

    第一步:随机产生一个种群,作为问题的初代解(通常,初代解可能与最优解相差较大,这是可以容忍的,只要保证初代解是随机产生的,以确保个体基因的多样性即可);

    第二步:寻找一种合适的编码方案对种群中的个体进行编码,可以选择如浮点数编码或二进制编码等常用编码方案(需要指出的是,不同的编码方案直接影响后续遗传算子的实现细节);

    第三步:以多峰函数的函数值 作为个体的适应度,计算种群中每个个体的适应度(算出的适应度将为后续的个体选择提供依据);

    第四步:根据适应度的高低选择参与繁衍的父体与母体,选择的原则是适应度越高的个体越可能被选中(以此不断淘汰适应度低的个体);

    第五步:对被选出的父体与母体执行遗传操作,即复制父体与母体的基因,并采用交叉、变异等算子产生出子代(在较大程度保留优秀基因的基础上,变异增加了基因的多样性,从而提高找到最优解的概率);

    第六步:根据一定的准则判断是继续执行算法,还是找出所有子代中适应度最高个体作为解返回并结束程序(判断的准则可以是设定的解的阈值、指定的迭代次数等)。
    在这里插入图片描述

    2.3、算法的编码实现

    2.3.1、编码

    本文采用的是二进制编码方式,这种编码方式编解码过程简单易行,相应的交叉算子、变异算子等操作用位运算即可实现。当然,它也有一定的缺点,比如连续性不够强。为保证求解的精度,本文使用14个bit为 编码,使用11个bit为 编码,两者组合成25个bit的最终结果。不难算出,该方式的编码精度可达千分位。具体的编码操作可总结为,将 或 的取值区间映射到0~2n-1这一整数范围,其中n表示编码位数, 或 在其取值区间的某点,相应的映射到整数区间中的某点,改点即为 或 的基因编码。程序如下:

    /*
        基因编码
        gene1       输入型参数,待编码的基因段1
        gene2       输入型参数,待编码的基因段2
        gene_code   输出型参数,基因编码
    
        返回值:当输入的基因不符合要求时返回false,否则返回true
    */
    static bool gene_encode(const double gene1, const double gene2, unsigned int *gene_code)
    {
        /* 判断基因是否合法 */
        if (!is_gene_legal(gene1, gene2))
            return false;
    
        /* 若基因合法则对其进行编码 */
        unsigned int gene1_code = (gene1 - GENE1_RANGE_LEFT) * (GENE1_CODE_MAX - 1) / (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT);
        unsigned int gene2_code = (gene2 - GENE2_RANGE_LEFT) * (GENE2_CODE_MAX - 1) / (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT);
        
        /* 组合基因片段 */
        *gene_code = (gene1_code << 11) | gene2_code;
    
        return true;
    }
    

    2.3.2、解码

    解码是编码的逆过程,无需赘述,程序如下:

    /*
        基因解码
        gene_code   输入型参数,基因编码
        gene1       输出型参数,解码后的基因段1
        gene2       输出型参数,解码后的基因段2
    
        返回值:当输入的基因编码不符合要求时返回false,否则返回true
    */
    static bool gene_decode(const unsigned int gene_code, double *gene1, double *gene2)
    {
        /* 判断基因编码是否合法 */
        if (!is_gene_code_legal(gene_code))
            return false;
    
        /* 若基因编码合法则对其进行解码 */
        unsigned int gene1_code = GET_GENE1_CODE(gene_code);
        unsigned int gene2_code = GET_GENE2_CODE(gene_code);
    
        *gene1 = (double)gene1_code * (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT) / (GENE1_CODE_MAX - 1) + GENE1_RANGE_LEFT;
        *gene2 = (double)gene2_code * (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT) / (GENE2_CODE_MAX - 1) + GENE2_RANGE_LEFT;
    
        return true;
    }
    

    2.3.3、计算适应度

    适应度函数也称评价函数,通常用于区分群体中个体好坏的标准。适应度高的,也就是优秀的个体有更大的几率参与繁衍,遗传自己的基因。一般的,适应度函数根据目标函数来确定,有时候直接将目标函数值作为适应度。这里,考虑到待求解的多峰函数,尖峰分布密集而且峰的直径很窄,这不利于遗传算法的收敛,因此本文不直接将多峰函数值作为适应度,而是利用对数函数将多峰函数进行平缓,并将平缓后的函数值作为目标函数。具体做法是,将多峰函数进行两次求对数,因此,多峰函数与适应度的关系可如下表示:
    在这里插入图片描述
    用MATLAB做出适应度函数图像如下:
    在这里插入图片描述
    对比前文中的图不难看出,图像得到了有效的平缓,同时不同峰之间也保持着一定的高低之别。值得一提的是,这里更主要的是给出优化遗传算法的一个思路,即可以在适应度函数上做文章。本题的适应度函数只是对多峰函数本身做了一个简单的变换,读者不妨思考一下,就本题而言有没有什么非常好的适应度函数。

    据上文所述,适应度求值函数如下:

    /*
        多峰函数:z = 21.5 + x *sin(4 * 3.1415926 * x) + y * sin(20 * 3.1415926 * y)
        适 应 度:log(log(z))
        约    束:-3.0 <= x <= 12.1; 4.1 <= y <= 5.8
        精    度:精确到千分位
    */
    double get_fitness(const double x, const double y)
    {
        return log(log(21.5 + x * sin(4 * PI * x) + y * sin(20 * PI * y)));
    }
    

    2.3.4、选择算子

    本文的选择算法采用了非常常用的“轮盘赌算法”,赌盘算法的原理非常简单明了。创建赌盘时,我们将种群中所有个体的适应度求和,不妨将得到的结果称为总和适应度。然后,将每个个体的适应度除以总和适应度,然后将得到的商逐个累加,每加一次就得到赌盘的一个边界,累加完成后总和为1。如下的饼状图可以更形象的表明赌盘的原理:
    在这里插入图片描述
    由上文所述,赌盘创建函数可如下编写:

    /*
        创建赌盘
        ga      遗传算法器指针
    */
    static void create_roulette(GA *ga)
    {
        /* 计算赌盘中的概率 */
        ga->roulette[0] = ga->fitness[0] / ga->sum_fitness;
    
        for (int num = 1; num < ga->population_num - 1; num++)
        {
            ga->roulette[num] = ga->roulette[num - 1] + ga->fitness[num] / ga->sum_fitness;
        }
    
        ga->roulette[ga->population_num - 1] = 1.0;
    }
    

    再回到选择算子,选择算子需要赌盘作为基础,其运行时,会产生一个0到1的随机数,然后在赌盘中找到该数所在的区间,这个区间对应的个体即为被选中的个体。因此,适应度越高的个体被选中的几率越大,这是合理的。当然,也存在较小的概率选出适应度较低的个体,为了避免这种情况,本文引入了竞争机制,即一次选择的过程选出2个个体,再取其中适应度较高的那个个体,具体的程序如下:

    /*
        基因选择函数
        ga      遗传算法器指针
        返回值:返回使用轮盘赌的方式选出的个体(编号)
        说  明:选择策略为轮盘赌+随机竞争
    */
    static unsigned int select(GA *ga)
    {
        unsigned int index1 = 0, index2 = 0;
    
        /* 产生一个[0.0, 1.0]之间的浮点数 */
        double selector1 = rand() * 1.0 / RAND_MAX;
        double selector2 = rand() * 1.0 / RAND_MAX;
    
        /* 找出被选中的个体的索引 */
        for (; selector1 > ga->roulette[index1]; index1++);
        for (; selector2 > ga->roulette[index2]; index2++);
    
        return (ga->fitness[index1] > ga->fitness[index2] ? index1 : index2);
    }
    

    2.3.5、交叉算子

    遗传算法的交叉操作实质上是按某种方式交换父体和母体的部分基因,常见的交叉算子有单点交叉、两点交叉、多点交叉、均匀交叉及算术交叉等。本文选用两点交叉法,实现过程既不复杂,也有较好的随机性,该方法可由下图示意:
    在这里插入图片描述
    图中虚线指出的两个交叉点是随机产生的。具体程序如下:

    /*
        交叉函数
        ga          遗传算法器指针
        one         输出型参数,待交叉基因
        another     输出型参数,待交叉基因
        说明:
        1.对传入的基因编码执行两点交叉操作
    */
    static void cross(GA *ga, unsigned int *one, unsigned int *another)
    {
        /* 1.随机产生两个交叉点的位置 */
        unsigned char pos1 = rand() % GENE_CODE_LENGTH + 1;
        unsigned char pos2 = rand() % GENE_CODE_LENGTH + 1;
        unsigned char min_pos = min(pos1, pos2);
        unsigned char max_pos = max(pos1, pos2);
    
        /* 2.截出需要交换的基因段 */
        unsigned int one_gene_seg = get_bits(*one, min_pos, max_pos) << (min_pos - 1);
        unsigned int another_gene_seg = get_bits(*another, min_pos, max_pos) << (min_pos - 1);
        unsigned int mask = ~(get_bits(~(0U), min_pos, max_pos) << (min_pos - 1));
    
        /* 3.执行交叉操作 */
        *one = (*one & mask) | another_gene_seg;
        *another = (*another & mask) | one_gene_seg;
    }
    

    2.3.6、变异算子

    在自然界中,基因变异可以增加个体的多样性,这对于遗传算法来说是增加了个体的随机性,可以增加找到最优解的概率。本文采用的变异算子所做的操作是随机选择基因的某一位进行反转,程序如下:

    /*
        变异函数
        gene_code       输入型参数
        说明:
        1.对传入的基因编码执行变异操作
        2.随机选择基因编码中的一位做反转操作
    */
    static void mutate(unsigned int *gene_code)
    {
        unsigned int mutate_bit = 1 << (rand() % GENE_CODE_LENGTH);
        *gene_code ^= mutate_bit;
    }
    

    2.3.7、繁殖函数及进化函数

    遗传算法的主要算子都在上文中分析过了,下面要做的就是根据遗传算法的流程将这些算子整合起来以实现算法功能。在本文中,这其中涉及到两个关键的函数,即繁殖函数和进化函数。繁殖函数包括基因的复制、交叉及变异,同时本文还采用了子代竞争策略,即父代产生的两个子代个体仅保留适应度最高的,程序如下:

    /*
        繁殖函数
        ga       遗传算法器指针
        father   从种群中选出的父体
        mother   从种群中选出的母体
        返回值:  适应度最高的子代的基因编码
        说明: 
        1.一对父体与母体将繁殖出一对子代
        2.选择出适应性更好的子代返回
    */
    static unsigned int inherit(GA *ga, unsigned int father, unsigned int mother)
    {
        unsigned int son1 = ga->gene_code[father];
        unsigned int son2 = ga->gene_code[mother];
    
        /* 1.交叉 */
        cross(ga, &son1, &son2);
    
        /* 2.变异 */
        mutate(&son1);
        mutate(&son2);
    
        /* 3.子代竞争 */
        double son1_gene1, son1_gene2, son2_gene1, son2_gene2;
        gene_decode(son1, &son1_gene1, &son1_gene2);
        gene_decode(son2, &son2_gene1, &son2_gene2);
    
        return (ga->get_fitness(son1_gene1, son1_gene2) > ga->get_fitness(son2_gene1, son2_gene2)) ? son1 : son2;
    }
    

    进化函数则实现了遗传算法的一次完整的迭代过程,根据上文给出的遗传算法流程图,不难进行如下编码:

    /*
        进化函数
        ga      遗传算法器指针
    */
    static void evolve(GA *ga)
    {
        /* 1.申请暂存子代基因编码的内存 */
        unsigned int *descendants = (unsigned int *)calloc(ga->population_num, sizeof(unsigned int));
        
        /* 2.精英保留(将上一代中适应度最高的个体的基因编码保留) */
        descendants[0] = ga->gene_code[ga->best_individual];
        
        /* 3.选择合适的父体与母体 */
        unsigned int father = select(ga);
        unsigned int mother = select(ga);
    
        /* 4.繁殖(包含交叉与变异) */
        for (int num = 1; num < ga->population_num; num++)
            descendants[num] = inherit(ga, father, mother);
    
        /* 5.将子代记录到ga中并进行基因解码(使新一代的基因编码与基因对应) */
        for (int num = 0; num < ga->population_num; num++)
        {
            ga->gene_code[num] = descendants[num];
            gene_decode(ga->gene_code[num], &ga->gene[num].gene1, &ga->gene[num].gene2);
        }
        
        /* 5.更新种群适应度 */
        fit(ga);
        
        /* 6.更新赌盘 */
        create_roulette(ga);
    
        /* 7.释放之前申请的空间 */
        free(descendants);
    }
    

    3、运行结果及分析

    至此,本文已经给出了一个遗传算法的C语言实现的所有关键程序。下面就调用编写的遗传算法进行测试。本文将创建含有100个个体的种群,并进行100代迭代以求解多峰函数的最大值,一次完整的调用本文实现的遗传算法的程序如下所示:

    /* 创建遗传算法器 */
    GA *ga = create_ga(get_fitness, 100);
    
    /* 初始化遗传算法器 */
    ga->init(ga);
    
    /*迭代100代*/
    for (int i = 0; i < 100; i++)
    ga->evolve(ga);
    
    /*销毁遗传算法器*/
    delete_ga(ga);
    

    经多次调用测试,算法执行的结果较为稳定,所得的多峰函数最大值大多在38以上,多次运行结果中最好的解为38.849744,对应的坐标为(11.625331, 5.725256)。将迭代求得的最大值用MATLAB作图如下:
    在这里插入图片描述
    为验证是否找到了最优解,用MATLAB遍历求出该多峰函数在给定定义域内的最大值为38.8501,与本文求出的结果相差0.000356,可见本文实现的遗传算法表现还不算太差。

    文中给出的程序比较散,这里给出完整程序的下载链接

    展开全文
  • 算法版 课后习题答案

    万次阅读 多人点赞 2016-03-28 17:07:59
    算法版 Eclipse EOF


    如果你是与JAVA相关方向的,可以看看这篇文章,相信对你会有所帮助: 点击打开链接


    算法(第四版) 第12次印刷

    感觉我真的是良心博主。。。。

    注意!!! :书上的过程图有些是比较坑的(非错误问题),比如P525的NFA并不是只执行了构造函数后的结果而是将构造函数和该类中的一个方法一起运行后的结果,比较坑,如果对书中算法有什么不懂的可以看看我写的注释(在Algorithms中),如果没有注释的要么是没必要,要么就是我也不会(比如红黑树的删除部分)


    关于终止Console继续读入流:

    书上有一些题目需要从console读取流并进行处理(我之前的代码都是直接用In类和命令行参数代替了),从console读取有个问题就是如何终止流的输入,如果不手动终止输入StdIn.isEmpty始终是false,这样后面的代码始终无法执行,Eclipse默认的EOF是ctrl+Z(在console输入完内容按完回车以后按ctrl+z(在console中)就会终止当前输入,StdIn.isEmpty为true),有个尴尬的问题是ctrl+z经常是无效的即你按了ctrl+z也不能终止流的输入,一开始我以为是快捷键的冲突导致的,结果改了以后仍是无效的,但我发现每次第一次启动eclipse后用ctrl+z终止流输入时有效的再次运行那个类就失效了,因此我想到的就是每次运行过一次以后就刷新(eclipse最左边建工程的地方点鼠标右键)要注意一点,你刷新的时候一定要选定那个类不要点在别的类刷新,这样是没用的,再次运行时EOF有效(可能会出现刷新一次后EOF仍然失效,再次刷新一次即可,在刷新之前一定要把当前运行的类终止,即console中红色的小正方形点一下变灰色)


    参考代码:点击打开链接


    Eclipse从控制台直接读取文件:

    比如你运行的类当前需要读取一个.txt的文件,而你不向想通过将内容复制到concole中读取或者通过命令行参数读取,而是想直接通过控制台读取并使用相应的方法,则可以通过这样设置达到目的:Run---->Run configurations--->




    这样点击运行的时候控制台什么都不要输入,直接EOF(不会看第一条),在读取比特流的时候采用console读取具体数据和从控制台直接读取.txt文件时有区别的,具体区别见下面的参考代码里的注释,这是针对数据压缩那里的内容,前面的自行测试

    参考代码:点击打开链接


    针对第五章第五节数据压缩算法的测试,基本思路将output定向到一个.txt文件中(如何定向看第二条),将压缩后的比特流保存到一个.txt的文件中,验证解压缩算法时,从.txt文件中读取比特流然后在控制台打印解压后的内容,具体操作看下面的图:首先新建一个用于保存比特流的.txt文件,我这里是a.txt,将文件放入具体的包中,

    然后将输出定向到该文件(看第二条),输出路径的设置:


    首先先点inputfile通过workspace找到a.txt这个文件,这时候将inputfule的路径复制下来作为outputfile的路径,取消inputfile前面的勾,在outputfile前面打勾,然后apply,直接运行,这样压缩后的比特流就保存到了a.txt文件中(会提示你刷新,刷新一下就行了),验证解压缩算法的时候就是将inputfile定向到a.txt文件

    参考代码:点击打开链接



    eclipse命令行参数使用:

    Run---->Run configurations----->右边 arguments 里写

    用空白字符区别不同的命令行参数:

    如:1 2 3    args.length=3

    123    args.length=1

    在命令行参数中读取测试用例 xxx.txt ,使用作者提供的jar包,参考书中205   我写的Algorithms/Number_2/Multiway

    比如我把 测试用例 m1.txt  m2.txt  m3.txt拷到了包Number_2下  则只需修改 working directory 为Number_2

     

     

    贴上我的GitHub地址,习题答案就在里面:

    https://github.com/xiaoyuzdy/Algorithms

    过几个月打算去找实习,题目会一直写,如果对你有帮助,觉得还不错,并且有github账户,麻烦给我个Star,这对我找工作很有帮助,十分感谢

    其中 Algorithms 为书中的一些算法还有就是一些作者自己写的API的使用

    AlgorithmsTest 为书中课后习题

    TestCase.zip 为书中需要用到的测试用例可使用迅雷下载

    再贴上GitHub上一个人写的:

    https://github.com/aistrate/AlgorithmsSedgewick/tree/master/1-Fundamentals

     

     

    展开全文
  • 算法的定义通常,定义算法为"为解决某一特定任务而规定的一指令序列"。算法的5基本特性① 有输入。一个算法必须有0或多输入。它们是算法开始运算前给予算法的量。这些输入取自于特定的对象的集合。它们可以...

    算法的定义

    通常,定义算法为"为解决某一特定任务而规定的一个指令序列"

    算法的5个基本特性

    ① 有输入。一个算法必须有0个或多个输入。它们是算法开始运算前给予算法的量。这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供,也可以使用赋值语句在算法内给定。

    ② 有输出。一个算法应有一个或多个输出,输出的量是算法计算的结果。

    ③ 确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况,需要执行的动作都应严格地、清晰地规定。

    例1:

    void fa( )
    { 
    	int x=5,y=10; 
    	z=x+++y;//解释为:x+(++y)?(x++)+y?
    	printf("%d,%d,%d",x,y,z);
    }
    void fb( )
    { 
    	int x=5,y=10;
    	z=x+(++y); //x+++y解释为:x+(++y)
    	printf("%d,%d,%d",x,y,z);
    }
    void fc( )
    {
    	int x=5,y=10;
    	z=(x++)+y;	//x+++y解释为:(x++)+y
    	printf("%d,%d,%d",x,y,z);
    }

     有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。

    例2:

    void fa(  )
    {
          int i=0,s=0;
          while(i<10) //死循环
              s++;        //不满足有穷性
          i++;
          printf(“s=%d,i=%d\n“,s,i);
    }
    void fb(  )
    {
          int i=0,s=0;
          while(i<10) //i<10执行多少次
          {
              s++;  //s++执行?次
              i++; // i++ 执行?次
          }
          printf(“s=%d,i=%d\n“,s,i); 
    }

     有效性。算法中每一条运算都必须是足够基本的。就是说,它们原则上都能精确地执行,甚至人们仅用笔和纸做有限次运算就能完成。

    例3:

    求和:S=1+2+3+...+∽   //不可以实现。

    算法设计的要求

    1)正确性

           a.无语法错误;

           b.对n组输入产生正确结果;

           c.对特殊输入产生正确结果;

           d.对所有输入产生正确结果。

    2)可读性:算法主要是为了人的阅读与交流

    3)健壮性

    4)高效与低存储量


    来源:我是码农,转载请保留出处和链接!

    本文链接:http://www.54manong.com/?id=16

    '); (window.slotbydup = window.slotbydup || []).push({ id: "u3646208", container: s }); })();
    '); (window.slotbydup = window.slotbydup || []).push({ id: "u3646147", container: s }); })();
    展开全文
  • 文章目录1 算法的研究内容2 算法设计的两例子2.1 调度问题2.2 算法设计的步骤2.3 投资问题3 总结 在学习算法涉及与分析的内容之前,先了解一下算法所涉及的几大块的内容,方便以后学习。 1 算法的研究内容 算法...
  • 基于遗传算法的排课设计

    千次阅读 多人点赞 2019-07-03 00:48:34
    问题描述 在排课问题中,我们的主要任务是将班级、教室、课程、教师安排...学校有5班,13种课程,23名教师和5教室。 ●教室集合R(301-101,301-102,301-103,301-104,301-105),假设每间教室只可容纳...
  • 算法设计经典算法

    万次阅读 2018-12-04 10:35:37
    贪婪法又称贪心算法,是当追求的目标是一问题的最优解时,设法把整个问题的求解工作分成若干步骤来完成,是寻找最优解问题的常用方法。 贪婪法的特点是一般可以快速得到满意的解,因为它省去了为找最优解要穷尽...
  • 算法设计与分析基础(第3版)

    万次阅读 多人点赞 2018-08-20 18:42:40
    - 算法设计与分析基础 - Anany Levitin 著 (第三版) 序言 设计技术作为问题求解的一般性策略 分析算法效率(算法经验分析、算法可视化) 各种方法加习题练习 目录 1. 绪论 2. 算法效率分析基础 3. 蛮...
  • MATLAB智能算法30案例分析.史峰等

    万次阅读 2019-03-10 11:36:02
    《MATLAB智能算法30案例分析》是2011年由北京航空航天大学出版社出版的图书,作者是郁磊、史峰、王辉、胡斐… 《MATLAB智能算法30案例分析》是作者多年从事算法研究的经验总结。讲解了遗传算法、免疫算法、退火...
  • 算法设计与分析 (知识点总结)

    千次阅读 多人点赞 2021-03-03 23:08:42
        通过学习掌握算法设计的主要方法,算法的时、空复杂性有正确分析的能力,能够针对具体的应用问题选择合适的数据结构并设计结构清晰、正确有效的算法,为独立设计算法和算法进行复杂性分析奠定坚实的理论...
  • 目前互联网上的中文答案不是最新版的,题目不全,包括百度文库中的,这虽然是英文的,但是比较齐全。
  • DES算法详细设计

    万次阅读 多人点赞 2017-10-07 09:09:08
    明文按64位进行分组,密钥长64位,密钥事实上是56位参与DES运算(第8、16、24、32、40、48、56、64位是校验位, 使得每密钥都有奇数1)分组后的明文组和56位的密钥按位替代或交换的方法形成密文组的加密方法。...
  • 数据结构算法评价四个标准

    万次阅读 热门讨论 2015-08-30 23:52:35
    下面大致分了四个方面来评价算法。         一、四个标准   正确性    能正确地实现预定的功能,满足具体问题的需要。 处理数据使用的算法是否得当,能不能得到预想的结果...
  • 算法设计与分析】分治法与最近点问题

    千次阅读 多人点赞 2018-10-15 17:26:32
    说明:这是武汉理工大学计算机学院【算法设计与分析】课程的第一次实验第三题:分治法与最近点问题 >>点击查看WUTer计算机专业实验汇总 谨记:纸上得来终觉浅,绝知此事要躬行。 一、问题描述 设,,…...
  • 算法的特征及设计要求

    千次阅读 2016-03-24 12:58:23
    算法的特征及设计要求
  • 计算机算法分析与设计(第五版)

    万次阅读 2019-09-04 09:59:12
    ** 计算机算法分析与设计(第五版 ) ** #算法实现题1 1-1问题描述:一本书的页码从自然数1开始顺序编码直到自然数n。...算法设计:给定表示书的总页码的十进制整数n(1m≤10°),计算书的全部页码中...
  • 图像识别算法

    万次阅读 多人点赞 2019-08-15 17:36:40
    首先比较上下左右四个点的像素值关系,至少要有3个点的像素灰度值大于或小于,则为候选点,然后再进一步进行完整的判断。 为了加快算法的检测速度,可以使用机器学习ID3贪心算法来构建决策树。这里需要说明的是,...
  • 基于物品的协同过滤算法实现图书推荐系统

    万次阅读 多人点赞 2019-09-14 21:20:24
    本文旨在利用基于物品的协同过滤算法,来实现一图书推荐系统。 本文首先介绍了推荐系统的发展历史,及目前常用的几种推荐算法的介绍与比较,然后以基于物品的协同过滤算法为基础,详细介绍图书推荐系统的构建。在...
  • (一)人脸识别技术之人脸识别过程及识别算法简介

    万次阅读 多人点赞 2018-11-04 23:19:40
    人脸识别四个步骤,分别为人脸图像采集及检测,人脸图像预处理(对齐),人脸图像特征提取和人脸图像匹配与识别. 1 人脸图像采集及检测 人脸图像采集 即通过摄像镜头获取人脸的数字图像. 人脸检测(判断是否有人...
  • EAST算法详解

    万次阅读 多人点赞 2018-06-18 14:54:54
    EAST:高效而准确的场景文本检测 1. 摘要 以前的场景文本检测方法已经在各种基准测试中取得了良好的效果...这是因为文本检测的整体性能取决于pipelines中多阶段和各部分的相互作用,而简单的pipeline能够集中精...
  • 算法设计与分析学习心得

    千次阅读 2020-06-23 22:13:14
    计算机算法设计与分析主要通过介绍常见的算法设计策略及复杂性分析方法,培养学生分析问题和解决问题的能力,为开发高效的软件系统及参加相关领域的研究工作奠定坚实的基础。该课程理论与实践并重,内容具有综合性、...
  • 算法设计与分析重点总结

    千次阅读 多人点赞 2021-01-02 20:26:23
    考试题型: 选择 2* 10 填空2* 10 简答 3* 4 程序分析填空 4* 4 综合(代码)8* 4 第一章基础知识 1.算法的定义 算法就是解决问题的方法,是解决某一...输出:一个算法产生一或多输出,这些输出是同输入
  • 算法设计 - 概述

    千次阅读 2018-10-21 21:01:15
    本文作为一个对算法设计的概述,着眼于讨论如下几点:其一,算法界的知识图谱;其二,五类算法设计思路的引入;其三,枚举决策类算法的解空间树;其,枚举决策类算法的分类;其五,算法的递归实现和递推实现;其六...
  • 【优化算法】简述灰狼优化算法(GWO)原理

    万次阅读 多人点赞 2019-03-25 21:10:34
    系列优化算法简述: OP_1. 简述遗传算法(GA)原理 OP_2 简述灰狼优化算法(GWO)原理 前言: 灰狼优化算法(Grey Wolf Optimizer,GWO)由澳大利亚格里菲斯大学学者 Mirjalili 等人于2014年提出来的一种群智能...
  • 算法设计——五大算法总结

    千次阅读 多人点赞 2020-09-15 16:10:20
    算法设计总结一、【分治法】二、【动态规划法】三、【贪心算法】、【回溯法】1、回溯法的一般描述五、【分支限界法】 一、【分治法】 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,...
  • 运动目标跟踪算法

    万次阅读 多人点赞 2019-02-17 12:53:17
    本文介绍了一般的目标跟踪算法常用的算法进行对比,并详细介绍了粒子滤波算法和基于轮廓的目标跟踪算法。最后简单介绍了目标遮挡的处理、多摄像头目标跟踪和摄像头运动下的目标跟踪。 一、一般的目标跟踪...
  • 本文(所有排序算法代码+综合比较代码)链接: 一、比较目的:        由于《数据结构》课本中各种内部排序算法的时间复杂度分析结果...以下八种常用内部排序算法进行比较:直接插入排序、希...
  • 我们在《排序算法》系列的开头介绍了几种能在O(nlg⁡n)O(n\lg n)O(nlgn)时间内排序nnn数的算法。归并排序和堆排序达到了最坏情况下的上界;快速排序在平均情况下达到该...下文将证明包含nnn元素的输入序列来说
  • 算法设计需要达到的目标

    千次阅读 2020-04-19 11:47:40
    可读性:算法是易于理解的,这要求算法在逻辑上是清晰的、结构化的 健壮性:算法具有容错性,即异常处理,能够检测不合理的数据,保证程序不发生异常中断等 高效率低存储:效率是指算法的执行时间;存储是指算法执行...
  • 算法设计与分析基础 第章谜题

    千次阅读 多人点赞 2018-11-14 16:26:32
    习题4.1 1.摆渡的士兵 n士兵组成的分队必须越过一条又深...解答:每次只能容纳一名士兵,所以士兵一定是一过河,同时需要有小男孩将船划回来,那么每一次士兵过河之前,两小男孩先划船过去,然后一小男...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 477,030
精华内容 190,812
关键字:

对算法设计的四个要求