烈焰中舞动的火花,将赐予邪恶异性交往以天罚。 收藏本站
登陆 / 注册 搜索

阅读:9.7K   回复: 2

程序的灵魂——算法!

[复制链接]
小执念 古黑浩劫论坛大牛 2015-11-25 23:16 |显示全部楼层

可遇不可求的事:故乡的云,上古的玉,随手的诗,十九岁的你。

管理员
    一、什么是算法

  算法是一系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

  算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模n 的函数f(n),算法执行的时间的增长率与f(n) 的增长率正相关,称作渐进时间复杂度(Asymptotic Time Complexity)。时间复杂度用“O(数量级)”来表示,称为“阶”。常见的时间复杂度有: O(1)常数阶;O(log2n)对数阶;O(n)线性阶;O(n2)平方阶。👩‌👚🖥👻👆
程序的灵魂——算法! 2015042829952615.jpg


  算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

  算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法,后者是操作实现的算法。

✌🏦🍊✔🦋‌


  一个算法应该具有以下五个重要的特征:

  1、有穷性: 一个算法必须保证执行有限步之后结束;
  2、确切性: 算法的每一步骤必须有确切的定义; 👨‍🚒‍🩲🧻😅👂
  3、输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件;
  4、输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
  5、可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。

  算法的设计要求
👃🌧🍭♾🐂‌
  1)正确性

  有4个层次:

✋🛩🍭🅾🦖‎  A.程序不含语法错误;
  B.程序对几组输入数据能够得出满足规格要求的结果;
  C.程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据能够得出满足规格要求的结果;
  D.程序对一切合法的输入数据都能产生满足规格要求的结果。

👄🛩🍚➡🦠‏

  2)可读性(Readability)

  算法的第一目的是为了阅读和交流;
  可读性有助于对算法的理解;
  可读性有助于对算法的调试和修改。 👨‍🚒‌🧥🛒🥰👊

  3)高效率与低存储量

  处理速度快;存储容量小
  时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。
👄⛄🥑⁉🐟‎
算法的描述
描述方式
类语言
类似高级语言的语言,例如,类PASCAL、类C语言。
自然语言👨‍⚕️‎💎📡🤩💅
.....
伪代码
包括程序设计语言的三大基本结构及自然语言的一种语言
流程图特定的表示算法的图形符号

👨‍🚒‍🧣🗝🤔👎


  算法的评价、算法评价的标准:时间复杂度和空间复杂度。

  1)时间复杂度 指在计算机上运行该算法所花费的时间。用“O(数量级)”来表示,称为“阶”

  常见的时间复杂度有: O(1)常数阶;O(logn)对数阶;O(n)线性阶;O(n^2)平方阶
🙌🥛🚷🦋‏  2)空间复杂度 指算法在计算机上运行所占用的存储空间。度量同时间复杂度。

  时间复杂度举例

  (a) X:=X+1 ; O(1)
🤞🌕🍊🅰🦜‍
  (b) FOR I:=1 TO n DO

  X:= X+1; O(n)

👏🏠🌶🚭🐅‎  (c) FOR I:= 1 TO n DO

  FOR J:= 1 TO n DO

  X:= X+1; O(n^2) 👩‏🥾🧻🤐🤛

  “算法”一词最早来自公元 9世纪 波斯数学家比阿勒·霍瓦里松的一本影响深远的著作《代数对话录》。20世纪的 英国 数学家图灵 提出了著名的图灵论点,并抽象出了一台机器,这台机器被我们称之为图灵机 。图灵的思想对算法的发展起到了重要的作用。

  算法是计算机 处理信息的本质,因为 计算机程序本质上是一个算法,告诉计算机确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。 一般地,当算法在处理信息时,数据会从输入设备读取,写入输出设备,可能保存起来以供以后使用。

👁🚂🎂®🐅‌
  这是算法的一个简单的例子。

  我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小可以将下面的算法形象地称为“捡豆子”:

  首先将第一颗豆子(数列中的第一个数字)放入口袋中。
🧠🛑🍊☯🦄‎
  从第二颗豆子开始检查,直到最后一颗豆子。如果正在检查的豆子比口袋中的还大,则将它捡起放入口袋中,同时丢掉原先的豆子。 最后口袋中的豆子就是所有的豆子中最大的一颗。

      下面是一个形式算法,用近似于编程语言的伪代码表示

👈🚠🍧🅱🦄‌给定:一个数列“list",以及数列的长度"length(list)" largest = list[1] for counter = 2 to length(list): if list[counter] > largest: largest = list[counter] print largest

      符号说明:

= 用于表示赋值。即:右边的值被赋予给左边的变量。 🧑‍💻‏👙💿😈👍

List[counter] 用于表示数列中的第 counter 项。例如:如果 counter 的值是5,那么 List[counter] 表示数列中的第5项。

<= 用于表示“小于或等于”。

🙌🛑🍟❌🦉‌

  二、算法设计的方法

  1.递推法

  递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解,当N=1时,解或为已知,或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质,即当得到问题规模为i-1的解后,由问题的递推性质,能从已求得的规模为1,2,…,i-1的一系列解,构造出问题规模为I的解。这样,程序可从i=0或i=1出发,重复地,由已知至i-1规模的解,通过递推,获得规模为i的解,直至得到规模为N的解。
👊🦼🍞❌🐻‌
  问题描述:编写程序,对给定的n(n≦100),计算并输出k的阶乘k!(k=1,2,…,n)的全部有效数字。

  由于要求的整数可能大大超出一般整数的位数,程序用一维数组存储长整数,存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a[ ]存储:

🖕🏠🥑🆒🐉‍  N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100

  并用a[0]存储长整数N的位数m,即a[0]=m。按上述约定,数组的每个元素存储k的阶乘k!的一位数字,并从低位到高位依次存于数组的第二个元素、第三个元素……。例如,5!=120,在数组中的存储形式为:

  3 0 2 1 ……
🦴🌡🥚♻🐋‎
  首元素3表示长整数是一个3位数,接着是低位到高位依次是0、2、1,表示成整数120。

  计算阶乘k!可采用对已求得的阶乘(k-1)!连续累加k-1次后求得。例如,已知4!=24,计算5!,可对原来的24累加4次24后得到120。

👳‎🩴✏🥲👂


  2.递归

  递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。

  能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 ‌💍🗑😶👈

       编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。

  斐波那契数列为:0、1、1、2、3、……,即:
👵‌👙🧬🤐🤛
  fib(0)=0;

  fib(1)=1;

  fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 👵‏👠📏🤡💅

  写成递归函数有:

  int fib(int n)

🤟🎢🥚✡🐅‌  { if (n==0) return 0;

  if (n==1) return 1;

  if (n>1) return fib(n-1)+fib(n-2); 👦‎👠🩺😆👂

  }

  递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n-2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。

👮‍♂️‌👒📞🥰🦴


  在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。

  在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。

  由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。
👊⛵☪🐤‍
      组合问题

  问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1
🧒‏👙🔑😰🤌
  (4)5、3、2 (5)5、3、1 (6)5、2、1

  (7)4、3、2 (8)4、3、1 (9)4、2、1

  (10)3、2、1

🧑‍🍳‍👜💊🤑💅



  分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。

【程序】
👨‍🎨‍🥾🔌💩🧠
  1.   # include <stdio.h>

  2.   # define MAXN 100

  3.   int a[MAXN];

    🧑‍🌾‏👓📟😰🤛



  4.   void comb(int m,int k)

  5.   { int i,j;
  6. 🧒‍💎🧬😥👍
  7.   for (i=m;i>=k;i--)

  8.   { a[k]=i;

  9.   if (k>1)

    👦‍👖🧻💩🦷



  10.   comb(i-1,k-1);

  11.   else
  12. 🧓‌🕶🪥🤮👆


  13.   { for (j=a[0];j>0;j--)

  14.   printf(“%4d”,a[j]);

  15.   printf(“\n”);
    👈🚐🍖🅾🐟‌

  16.   }

  17.   }

  18. 🤝🌕🍓💲🦉‌
  19.   }

  20.   void main()

  21.   { a[0]=3;🧒‌👗🗡😳✍

  22.   comb(5,3);

  23.   }
复制代码

👮‍♂️‍🩲📀😘👈



  3.回溯法

  回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前候选解的规模,以继续试探的过程称为向前试探。

👍🧳🥚❗🦚‎      组合问题

  问题描述:找出从自然数1,2,…,n中任取r个数的所有组合。

  采用回溯法找问题的解,将找到的组合以从小到大顺序存于a[0],a[1],…,a[r-1]中,组合的元素满足以下性质: 🧑‍💻‎👞🔭💀🤌

  (1) a>a,后一个数字比前一个大;

  (2) a-i<=n-r+1。
🧑‍🎤‌🎩📀🥲💪
  按回溯法的思想,找解过程可以叙述如下:

  首先放弃组合数个数为r的条件,候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件,扩大其规模,并使其满足上述条件(1),候选组合改为1,2。继续这一过程,得到候选组合1,2,3。该候选解满足包括问题规模在内的全部条件,因而是一个解。在该解的基础上,选下一个候选解,因a[2]上的3调整为4,以及以后调整为5都满足问题的全部要求,得到解1,2,4和1,2,5。由于对5不能再作调整,就要从a[2]回溯到a[1],这时,a[1]=2,可以调整为3,并向前试探,得到解1,3,4。重复上述向前试探和向后回溯,直至要从a[0]再回溯时,说明已经找完问题的全部解。按上述思想写成程序如下:

  【程序】 🧒‎🩲🧯☠🤞

  1.   # define MAXN 100

  2.   int a[MAXN];
  3. 🧑‍⚕️‍👗✒👍
  4.   void comb(int m,int r)

  5.   { int i,j;

  6.   i=0;🧓‍🩳📞😥✊

  7.   a=1;

  8.   do {

  9. 👌⛄🦀📵🐅‌

  10.   if (a-i<=m-r+1

  11.   { if (i==r-1)

  12.   { for (j=0;j<r;j++)
    🤳⛄🌶❓🦌‎

  13.   printf(“%4d”,a[j]);

  14.   printf(“\n”);

  15. ✊🗺♾🦖‎

  16.   }

  17.   a++;

  18.   continue;🧑‍⚕️‎👑😴👄

  19.   }

  20.   else

  21. 🖕🗺🍓🆎🐡‎
  22.   { if (i==0)

  23.   return;

  24.   a[--i]++;👨‍🎨‍👓✒😅👎

  25.   }

  26.   } while (1)
  27. 👩‌🪖💉😔✌
  28.   }

  29.   main()

  30.   { comb(5,3);
    👁🎠🥭🆚🐠‏

  31.   }
复制代码


  4.贪婪法

👏🗽🔪🚷🐠‏

  贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。

  例如平时购物找钱时,为使找回的零钱的硬币数最少,不考虑找零钱的所有各种发表方案,而是从最大面值的币种开始,按递减的顺序考虑各币种,先尽量用大面值的币种,当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种方法在这里总是最优,是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1、5和11单位的硬币,而希望找回总额为15单位的硬币。按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬币,共找回5个硬币。但最优的解应是3个5单位面值的硬币。

  【问题】 装箱问题
🤌🏫🈷🐂‏
  问题描述:装箱问题可简述如下:设有编号为0、1、…、n-1的n种物品,体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V,即对于0≤i<n,有0<vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。

  若考察将n种物品的集合分划成n个或小于n个物品的所有子集,最优解就可以找到。但所有可能划分的总数太大。对适当大的n,找出所有可能的划分要花费的时间是无法承受的。为此,对装箱问题采用非常简单的近似算法,即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中,该算法虽不能保证找到最优解,但还是能找到非常好的解。不失一般性,设n件物品的体积是按从大到小排好序的,即有v0≥v1≥…≥vn-1。如不满足上述要求,只要先对这n件物品按它们的体积从大到小排序,然后按排序结果对物品重新编号即可。装箱算法简单描述如下:
👩‌💄🖨🤐👃
  { 输入箱子的容积;

  输入物品种数n;

  按体积从大到小顺序,输入各物品的体积; 👦‎📥😍🦷

  预置已用箱子链为空;

  预置已用箱子计数器box_count为0;

🤳🌦🔪🆎🐒‌  for (i=0;i<n;i++)

  { 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j;

  if (已用箱子都不能再放物品i)
✍🗼🍧⚛🐶‎
  { 另用一个箱子,并将物品i放入该箱子;

  box_count++;
🧑‍🚀‏🧥🪓😋🖐
  }

  else

  将物品i放入箱子j; 👵‎🦺🏮🤪🖐

  }

  }
‎🧦🧬😂👂
  上述算法能求出需要的箱子数box_count,并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解,设有6种物品,它们的体积分别为:60、45、35、20、20和20单位体积,箱子的容积为100个单位体积。按上述算法计算,需三只箱子,各箱子所装物品分别为:第一只箱子装物品1、3;第二只箱子装物品2、4、5;第三只箱子装物品6。而最优解为两只箱子,分别装物品1、4、5和2、3、6。

  若每只箱子所装物品用链表来表示,链表首结点指针存于一个结构中,结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。以下是按以上算法编写的程序。

  }
👃🏠🥭ℹ🦋‏
  5.分治法

  任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算;n=2时,只要作一次比较即可排好序;n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。

🤙🚈🥭☪🦬‎  分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

  如果原问题可分割成k个子问题(1<k≤n),且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

  分治法所能解决的问题一般具有以下几个特征:
✍🏦🥛‼🐞‏
  (1)该问题的规模缩小到一定的程度就可以容易地解决;

  (2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
🧑‍🚀‍🥾📷😷💅
  (3)利用该问题分解出的子问题的解可以合并为该问题的解;

  (4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

  上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

👨‍🎨‎👞📷😡🤳



  分治法在每一层递归上都有三个步骤:

  (1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
👴‌👙📐😥🖕
  (2)解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;

  (3)合并:将各个子问题的解合并为原问题的解。

  6.动态规划法

🧒‌👚🪜🙃👈



  经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题。简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加。

  为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。以下先用实例说明动态规划方法的使用。

👈🎠🍌🉑🐠‎  【问题】 求两字符序列的最长公共字符子序列

  问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列<i0,i1,…,ik-1>,使得对所有的j=0,1,…,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。

  考虑最长公共子序列问题如何分解成子问题,设A=“a0,a1,…,am-1”,B=“b0,b1,…,bm-1”,并Z=“z0,z1,…,zk-1”为它们的最长公共子序列。不难证明有以下性质:

🏠🍏🔞🐺‍


  (1) 如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,…,zk-2”是“a0,a1,…,am-2”和“b0,b1,…,bn-2”的一个最长公共子序列;

  (2) 如果am-1!=bn-1,则若zk-1!=am-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列;
👳‌🛍⚒😅👀
  (3) 如果am-1!=bn-1,则若zk-1!=bn-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列。

  这样,在找A和B的公共子序列时,如有am-1=bn-1,则进一步解决一个子问题,找“a0,a1,…,am-2”和“b0,b1,…,bm-2”的一个最长公共子序列;如果am-1!=bn-1,则要解决两个子问题,找出“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列和找出“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列,再取两者中较长者作为A和B的最长公共子序列。

  代码如下:👵‏👓⚔😷✍

全屏查看
  1.   # include <stdio.h>

  2.   # include <string.h>
  3. 🧒‌👙🧲😴🤛
  4.   # define N 100

  5.   char a[N],b[N],str[N];

  6.   int lcs_len(char *a, char *b, int c[ ][ N])
    🤛🏠🫑♑🐢‍

  7.   { int m=strlen(a), n=strlen(b), i,j;

  8.   for (i=0;i<=m;i++) c[0]=0;

  9. ✋🌧🥄🈳🦬‏
  10.   for (i=0;i<=n;i++) c[0]=0;

  11.   for (i=1;i<=m;i++)

  12.   for (j=1;j<=m;j++)

    👂🛑🍪🆚🐕‍


  13.   if (a==b[j-1])

  14.   c[j]=c[j-1]+1;

  15. 👁🛩🥭🅿🐖‎
  16.   else if (c[j]>=c[j-1])

  17.   c[j]=c[j];

  18.   else🧒‎🦺🧻😶🤟

  19.   c[j]=c[j-1];

  20.   return c[m][n];

  21. 👍🗽🍞🚷🪰‏
  22.   }

  23.   char *buile_lcs(char s[ ],char *a, char *b)

  24.   { int k, i=strlen(a), j=strlen(b);👵‎🎒🧹😴🧠

  25.   k=lcs_len(a,b,c);

  26.   s[k]=’’;

  27. 👈🌕🌶🆘🐕‏

  28.   while (k>0)

  29.   if (c[j]==c[j]) i--;

  30.   else if (c[j]==c[j-1]) j--;
    🦷🚠🥣🈸🐺‏

  31.   else { s[--k]=a;

  32.   i--; j--;
  33. 👮‍♂️‏🎒💶😪


  34.   }

  35.   return s;

  36.   }

    👃💈🔪⚛🐤‏


  37.   void main()

  38.   { printf (“Enter two string(<%d)!\n”,N);
  39. 👩‌🧢📱😊✊


  40.   scanf(“%s%s”,a,b);

  41.   printf(“LCS=%s\n”,build_lcs(str,a,b));

  42.   }
复制代码
👩‍✈️‌🪖🖲😃🦴


  7.迭代法

  迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: 👴‍👑🖌😶👍

  (1) 选一个方程的近似根,赋给变量x0;

  (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0;
👮‍♂️‎🧢🪥😈🦴
  (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。

  若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为:

  程序如下:
✍🚂🫑🔞‏
  【算法】迭代法求方程组的根

  1.   { for (i=0;i<n;i++)
  2. 👩‍✈️‎🩳📥😒👆
  3.   x=初始近似根;

  4.   do {

  5.   for (i=0;i<n;i++)👳‏👠🪜😃🖕

  6.   y = x;

  7.   for (i=0;i<n;i++)
  8. 🧑‍🚀‏👚🏮😡👆


  9.   x = gi(X);

  10.   for (delta=0.0,i=0;i<n;i++)

  11.   if (fabs(y-x)>delta) delta=fabs(y-x); } while (delta>Epsilon);
    🧠🗽🔪☯🦠‍

  12.   for (i=0;i<n;i++)

  13.   printf(“变量x[%d]的近似根是 %f”,I,x);
  14. 👦‌🪖🔍😡👃
  15.   printf(“\n”);

  16.   }
复制代码



👌🪐🥚🔞🐞‏      具体使用迭代法求根时应注意以下两种可能发生的情况:

  (1)如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制;

  (2)方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。

‎🥾💶😤🤝



  8.穷举搜索法

  穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。

👨🦱‏👖📱😘🖕


  【问题】 将A、B、C、D、E、F这六个变量排成如图所示的三角形,这六个变量分别取[1,6]上的整数,且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。

  程序引入变量a、b、c、d、e、f,并让它们分别顺序取1至6的整数,在它们互不相同的条件下,测试由它们排成的如图所示的三角形三条边上的变量之和是否相等,如相等即为一种满足要求的排列,把它们输出。当这些变量取尽所有的组合后,程序就可得到全部可能的解。程序如下:

  按穷举法编写的程序通常不能适应变化的情况。如问题改成有9个变量排成三角形,每条边有4个变量的情况,程序的循环重数就要相应改变。 🧑‍🌾‎🧣💿😈👃

  (一)基本算法 :

  1.枚举
👴‍🧢💶😉🤌
  2.搜索:

  深度优先搜索

  广度优先搜索
🙌💈🍪📵🪰‍
  启发式搜索

  遗传算法

✊🪐🥣☪🦌‏

  (二)数据结构的算法

  (三)数论与代数算法

  (四)计算几何的算法:求凸包 🧑‍🎤‌🧢📬😰✊

  (五)图论算法:

  1.哈夫曼编码
👳‍👔📱😂🙌
  2.树的遍历

  3.最短路径 算法

  4.最小生成树 算法 🧓‌👞🩺😋

  5.最小树形图

  6.网络流 算法

🤟🚂🍍🈷🐺‎  7.匹配算法

  (六)动态规划

  (七)其他: 👦‎👓🗝🥰👊

  1.数值分析

  2.加密算法
🥷‍🦺🪓👻🤛
  3.排序 算法

  4.检索算法

  5.随机化算法

🤳🗺🍊⁉🐟‌



上一篇
下一篇
帖子热度 9735 ℃
小执念在网吧通宵,花了 2 个 金币.

屋顶,数星星 「出类拔萃」 2018-5-4 20:10 来自手机 |显示全部楼层

这个用户很懒,还没有填写自我介绍呢~

墙倒都不服,就服你
初晓微芒 「出类拔萃」 2018-4-30 23:23 来自手机 |显示全部楼层

这个用户很懒,还没有填写自我介绍呢~

非常好,顶一下
您需要登录后才可以回帖 登录 | 免费注册  

本版积分规则

快速回复 返回列表