标签归档:算法

c语言算法设计策略–2 分治法


分治法的思想和特征

分治法是一种重要的算法。分治法的思想可以描述为:对于一个规模为n的问题,若该问题可以容易地解决,则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立与原问题相同,递归地解决这些子问题,然后将各问题的解合并到原问题的解中。


分治法所能解决的问题一般具有以下特征:
1 该问题的规模缩小到一定程序就很容易得到解决
2 该问题可以分解为若干个规模较小的相同问题
3 分解出的问题,最后可以通过合并解得到原问题的解
4 该问题分解出的各个子问题是相互独立,子问题之间不包含公共的子问题

c语言算法设计策略--1贪心法


一、贪心法的思想

例:假如有一个人手上有四种面值的硬币,三角、一角五分、五分、二角,此时我们需要找零6角五分时,如何才能使找零的个数最少?
这时,我们会不加思索的找出2个三角一个五分的硬币。
这种找零的方式;
1 选出一个面值不超过六角五分的最大硬币,即三角
2 我们从六角五分中减去三角,剩余三角五分,然后我们再从硬币里面找出一个面值不大于三角五分的硬币,依次寻找下去,直到找零结束。
我们把这种找零的方式,称之为贪心法。


上述找零的算法利用的硬币的特殊性。
如果上述找零1角五分 硬币种类为 一分 五分 一角一分三种。如果我们采用上述的贪心法,那么得到的结果是一个一角一分 和四个一分 总共五个硬币,同我们直接找3个五分硬币相比,明显不是最优结果。

贪心法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它能产生整体最优解。



二、贪心法的基本要素

使用贪心法需要具有两个重要的性质: 最优子结构性质和贪心选择性质
2.1 最优子结构性质
当一个问题的最优解一定包含其子问题的最优解时,称此问题具有最优子结构性质。

2.2 贪心选择性质
贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择获得,其中每次所作的选择可以依赖于以前的选择,但不依赖于将来所做的选择。贪心选择性质保证了问题存在从贪心选择开始的最优解。


三、贪心法的算法设计模式

function decimal[] zhaoLin(decimal LingQian,decimal[] n)
  {
     decimal[] t; 
     for(i=0;i < n.length;i++){
         if(n[i] < = LingQian){  //采用贪心算法进行比对
           t.push(n[i]);       //合并最优解
           LingQian -=n[i];
        }
     }
    return t;
 }


四、贪心法举例说明

4.1 问题描述
在漆黑的夜里,N位旅行者来到一座桥,如果过这座桥,必须借助手电筒,否则的话,无法过桥,但是这时,大家只有一把手电筒,而桥每次只能通过两个人
如果单独过桥的话,N位旅行者所需时间已知;而如果两人同时过桥,所需时间为两人之中比较慢的一个人的过桥时间,现在我们需要设计一种最快的过桥方案
4.2 问题分析
每次过桥只能两个人一起通过,并且还需要有人将手电筒送过来,则只有当每次有人过桥后,将手电筒送过来所花费的时间最少,才能保证总时间最少,设N个人每个人过桥的花费时间为
t[0...N-1],然后将N个人过桥所需时间从小到大依次排序。
产生以下两种方案:
4.2.1
速度最快的人t[0] 和速度次快的人t[1] 过桥,然后速度最快的人将手电筒送来,再由速度次慢的人t[N-2] 和t[N-1] 依次过桥,再由t[1]将手电筒送回,依次循环过桥
4.2.2
速度最快的人t[0]和速度最慢的人过桥t[N-1],然后由t[0]将手电筒送回,再由速度最快的人和速度次慢的人一起过桥,再由速度最快的人将手电筒送回,依次循环过桥

4.2.1 过桥时间 t[0]+2*t[1]+t[N-1]
4.2.2 过桥时间 2*t[0]+t[N-2]+t[N-1]
如果4.2.1 过桥时间比4.2.2过桥时间短,那么就应该存在以下关系
t[0]+2*t[1]+t[N-1] < 2*t[0]+t[N-2]+t[N-1] //简写 2*t[1] 4.3 算法描述

     void fun(int n,int t[])
       {
        int first= 0;
        int last = n-1;
        int sum=0;
        while(last >= 2){
          if(last >= 3){
            if(t[last-1]+t[first] > 2*t[first+1]){
                sum += t[last]+t[first]+t[first+1]*2;
              }else
              {
                sum += t[first]*2+t[last-1]+t[last];
              }
              last =last -2;
          }else if(last ==2)
               sum +=t[first]+t[last];
       }
	sum +=t[first+1];
       }

c语言算法重要性

在算法设计中,我们关心两个方面: 性能和资源消耗。


算法决定了程序的可行性

在一些实时的情况下(机器人 嵌入式设备),如果速度不够快,那么就没有意义
所以在决定采用计算机实现某一功能时,我们首先要分析一下算法是否可性。


算法是描述程序行为的通用语言

我们可以通过算法来描述程序的运行流程,在任何地方,它可以在实践中得到体现也可以在理论中得到证明。
例:关于用户体验,每个人都有自己的想法,不可能让所有人都满意某种设计,但是算法却可以做到让所有都满意,因为算法是通过运行来衡量算法的性能
算法为计算机世界构建一个纯净的世界,一个说一不二的世界。


算法拥有很强的趣味性

算法本身就具有很强的趣味性,它的速度和构思会产生不言而喻的美感。


算法与日常生活息息相关

在日常生活中,人们都在自觉的使用算法,例:超市购物,我们会按照一定的步骤依次来完成购物,这个购物的步骤我们也可以称之为算法。当然通过多次购物的比对,我们可以选择出最佳的购物路线,这个过程也是
我们改进算法的一种形式。


算法是程序设计的根基

在计算机技术快速发展的今天,新语言不断的涌现,编程工具不断的更新,语法知识不断的更新, 唯一不变的就是我们程序的设计步骤及算法


学习算法能够提高分析问题的能力

学习算法可以锻炼一个人的思维,提高解决和分析问题的能力,对日后的学习、生活、工作也会产生深远的影响。