下载文档原格式
四个经典的算法案例案例1：辗转相除法，又名欧几里德算法，它是用来求两个正整数最大公因数的一种方法。
例：用辗转相除法求8251与6105的最大公约数∵ 8251÷6105＝1 余 21466105÷2146＝2 余 18132146÷1813＝1 余 3331813÷ 333＝5 余 148333 ÷ 148＝2 余 37148 ÷ 37＝4∴ 37是8251与6105的最大公约数程序框图如下：其中 r = mod（a, b） r表示a÷b的余数案例2：秦九韶算法，它是中国南宋时期数学家秦九韶提出的，用来解决多项式的求值问题，在西方被称作霍纳算法。
首先看一道例题：求多项式f(x)=2x5―5x4―4x3+3x2―6x+7当x=5时的值。
根据秦九韶算法：f(x)可表示为f(x)=（｛［（2x―5）x―4］x+3｝x―6）x+7于是令 V0=5则 V1=2V0―5=2×5―5=5V2=V1X―4=5×5―4=21V3=V2X+3=21×5+3=108V4=V3X―6=108×5―6=534V5=V4X+7=534×5+7=2677∴ f(5) = 2677秦九韶算法只用到乘法、加法两个简单运算，不需要乘方运算，它是多项式求值的简化算法。
下面看程序框图，其中a0、a1、a2、a3、a4、a5是f (x) 从右向左的系数。
案例3：排序：是一种基本并且常用的算法，排序的算法很多，可以参阅课本，这里不再叙述。
案例4：进位制例：画程序框图，表示把k进制数a（共有n位），转化为十进制数b的过程框图如下：其中：t = GET a│i│ t表示a右数第i位利用上面的算法，把2进制数110011化为十进制的数即：1×20+1×21+0×22+0×23+1×24+1×25= 51以上是四个经典算法，大家可以从中体会算法的基本思想和算法的基本结构，并尝试用算法的基本语句描述它。
算法练习题1. 斐波那契数列：1 1 2 3 5 8 13 21 …… 求第20个数；2. 今有雉兔同笼，上有三⼗五头，下有九⼗四⾜，问雉兔各⼏何？3. 求1000以内的⽔仙花数4. 求⼀个数的阶乘5. 求多个连续数的阶乘之和6. 如果今天是星期⼆，那么1000天后是星期⼏？⽤户输⼊⼀个天数，计算这个天数后是星期⼏？7. 苹果3元⼀个，鸭梨2元⼀个，桃⼦1元⼀个。
现在想⽤200元买100个⽔果，在控制台中列出所有可能性8. 求任意⼀个⼩于100000的正整数的位数，并逆序打印每⼀位数字⽐如：567，位数是3位，以此打印7 ，6 ，59. 有⼀分数序列：2/1，3/2，5/3，8/5，13/8，21/13...求出这个数列的前20项之和。
程序分析：请抓住分⼦与分母的变化规律。
10. 有⼀些苹果，每⼈分5个多1个，每⼈分6个多2个，每⼈分7个多3个，⼀共有多少个苹果11. 判断⼀个数字是不是素数12. 利⽤条件运算符的嵌套来完成此题：学习成绩>=90分的同学⽤A表⽰，60-89分之间的⽤B表⽰，60分以下的⽤C表⽰。
1.程序分析：(a>b)?a:b这是条件运算符的基本例⼦。
13. 求s=a+aa+aaa+aaaa+aa...a的值，其中a是⼀个数字。
例如2+22+222+2222+22222(此时共有5个数相加)，⼏个数相加由⽤户输⼊（prompt）14. ⼀球从100⽶⾼度⾃由落下，每次落地后反跳回原⾼度的⼀半；再落下，求它在第10次落地时，共经过多少⽶？第10次反弹多⾼？15. 求10000以内的完美数如果⼀个数恰好等于它的约数之和，则称该数位“完美数”。
16. 寻找丑数题⽬：我们把只包含因⼦2、3 和5 的数称作丑数（Ugly Number）。
例如6、8 都是丑数，但14 不是，因为它包含因⼦7。
习惯上我们把1 当做是第⼀个丑数。
求按从⼩到⼤的顺序的第1500 个丑数。
17. 猴⼦吃桃问题：猴⼦第⼀天摘下若⼲个桃⼦，当即吃了⼀半，还不瘾，⼜多吃了⼀个第⼆天早上⼜将剩下的桃⼦吃掉⼀半，⼜多吃了⼀个。
经典算法题范文1.冒泡排序算法冒泡排序是一种简单而常用的排序算法。
它通过重复地交换相邻的元素来对一个数组进行排序，直到没有可交换的元素为止。
冒泡排序的时间复杂度为O(n^2)，是一种效率较低的排序算法，但它非常容易理解和实现。
2.快速排序算法快速排序是一种高效的排序算法，它通过一趟排序将一个数组分成两个独立的部分，其中一部分的所有元素都比另一部分的所有元素小。
然后，继续对这两个部分递归地进行排序，直到整个数组有序。
快速排序的时间复杂度为O(nlogn)，是一种常用的排序算法。
3. Dijkstra算法Dijkstra算法是一种用于求解单源最短路径问题的经典算法。
它通过动态规划的思想，逐步确定每个顶点到源点的最短路径长度，并记录下最短路径。
Dijkstra算法的时间复杂度为O(ElogV)，其中E为边数，V为顶点数。
它在图论和网络路由等领域具有重要的应用。
4.红黑树算法红黑树是一种自平衡的二叉查找树，它在插入和删除元素时能够保持树的平衡性。
红黑树的主要特点是每个节点都有一个颜色属性，可以是红色或黑色，并且满足一些额外的条件确保树的平衡。
红黑树的时间复杂度为O(logn)，是一种高效的动态数据结构，广泛应用于数据库和操作系统等领域。
5.归并排序算法归并排序是一种稳定的排序算法，它通过将已经有序的子序列合并成一个有序的序列，从而实现排序功能。
归并排序的核心思想是将一个数组分成两个子数组，然后对这两个子数组分别进行归并排序，最后将两个有序的子数组合并成一个有序的数组。
归并排序的时间复杂度为O(nlogn)，是一种高效的排序算法。
总结起来，上面介绍的这几个经典算法题分别涉及排序、图论、数据结构等不同领域，它们是算法研究和实践中的重要问题。
掌握这些经典算法题，能够帮助我们理解算法设计的思想和方法，提高算法设计和分析的能力。
同时，这些经典算法题还具有广泛的应用，可以帮助我们解决日常生活和工作中的实际问题。
因此，学习和掌握这些经典算法题对于计算机科学和软件工程的学习和工作都具有重要意义。
本文由ｗａｎｇｆａｎｗｉｎｄｏｗｓ贡献 ｄｏｃ文档可能在ＷＡＰ端浏览体验不佳。
建议您优先选择ＴＸＴ，或下载源文件到本机查看。
Ｃ 语言经典算法 １００ 例（１） Ｃ 语言编程经典 １００ 例 Ａ：【程序 １】 题目：有 １、２、３、４ 个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ １．程序分析：可填在百位、十位、个位的数字都是 １、２、３、４。
组成所有的排列后再去掉 不满足条件的排列。
２．程序源代码： ｍａｉｎ（） ｛ ｉｎｔ ｉ，ｊ，ｋ； ｐｒｉｎｔｆ（“＼ｎ“）； ｆｏｒ（ｉ＝１；ｉ〈５；ｉ＋＋） ／＊以下为三重循环＊／ ｆｏｒ（ｊ＝１；ｊ〈５；ｊ＋＋） ｆｏｒ （ｋ＝１；ｋ〈５；ｋ＋＋） ｛ ｉｆ （ｉ！＝ｋ＆＆ｉ！＝ｊ＆＆ｊ！＝ｋ） ／＊确保 ｉ、ｊ、ｋ 三位互不相同＊／ ｐｒｉｎｔｆ（“％ｄ，％ｄ，％ｄ＼ｎ“，ｉ，ｊ，ｋ）； ｝ ｝ ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 【程序 ２】 题目：企业发放的奖金根据利润提成。
利润（Ｉ）低于或等于 １０ 万元时，奖金可提 １０％；利润 高于 １０ 万元，低于 ２０ 万元时，低于 １０ 万元的部分按 １０％提成，高于 １０ 万元的部分，可可 提成 ７．５％；２０ 万到 ４０ 万之间时，高于 ２０ 万元的部分，可提成 ５％；４０ 万到 ６０ 万之间时高 于 ４０ 万元的部分，可提成 ３％；６０ 万到 １００ 万之间时，高于 ６０ 万元的部分，可提成 １．５％， 高于 １００ 万元时，超过 １００ 万元的部分按 １％提成，从键盘输入当月利润 Ｉ，求应发放奖金总 数？ １．程序分析：请利用数轴来分界，定位。
注意定义时需把奖金定义成长整型。
２．程序源代码： ｍａｉｎ（） ｛ ｌｏｎｇ ｉｎｔ ｉ； ｉｎｔ ｂｏｎｕｓ１，ｂｏｎｕｓ２，ｂｏｎｕｓ４，ｂｏｎｕｓ６，ｂｏｎｕｓ１０，ｂｏｎｕｓ； ｓｃａｎｆ（“％ｌｄ“，＆ｉ）； ｂｏｎｕｓ１＝１０００００＊０．１；ｂｏｎｕｓ２＝ｂｏｎｕｓ１＋１０００００＊０．７５； ｂｏｎｕｓ４＝ｂｏｎｕｓ２＋２０００００＊０．５； ｂｏｎｕｓ６＝ｂｏｎｕｓ４＋２０００００＊０．３； ｂｏｎｕｓ１０＝ｂｏｎｕｓ６＋４０００００＊０．１５； ｉｆ（ｉ〈＝１０００００） ｂｏｎｕｓ＝ｉ＊０．１； ｅｌｓｅ ｉｆ（ｉ〈＝２０００００） ｂｏｎｕｓ＝ｂｏｎｕｓ１＋（ｉ－１０００００）＊０．０７５； ｅｌｓｅ ｉｆ（ｉ〈＝４０００００） ｂｏｎｕｓ＝ｂｏｎｕｓ２＋（ｉ－２０００００）＊０．０５； ｅｌｓｅ ｉｆ（ｉ〈＝６０００００） ｂｏｎｕｓ＝ｂｏｎｕｓ４＋（ｉ－４０００００）＊０．０３； ｅｌｓｅ ｉｆ（ｉ〈＝１００００００） ｂｏｎｕｓ＝ｂｏｎｕｓ６＋（ｉ－６０００００）＊０．０１５； ｅｌｓｅ ｂｏｎｕｓ＝ｂｏｎｕｓ１０＋（ｉ－１００００００）＊０．０１； ｐｒｉｎｔｆ（“ｂｏｎｕｓ＝％ｄ“，ｂｏｎｕｓ）； ｝ ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 【程序 ３】 题目：一个整数，它加上 １００ 后是一个完全平方数，再加上 １６８ 又是一个完全平方数，请问 该数是多少？ １．程序分析：在 １０ 万以内判断，先将该数加上 １００ 后再开方，再将该数加上 ２６８ 后再开方， 如果开方后的结果满足如下条件，即是结果。
经典算法试题及答案题目一：找出旋转排序数组中的最小值题目描述：假设按照升序排序的数组在预先未知的某个点上进行了旋转。
例如，数组 `[0,1,2,4,5,6,7]` 可能变为`[4,5,6,7,0,1,2]`。
请找出并返回数组中的最小元素。
说明：- 原数组是一个升序排序的数组- 数组中可能包含重复的元素- 你的算法应该具有 O(log n) 的时间复杂度答案解析：这个问题可以通过二分查找的方法来解决。
以下是详细的解题步骤：1. 初始化两个指针 `left` 和 `right` 分别指向数组的开头和结尾。
2. 当 `left` 小于 `right` 时，执行以下步骤：- 找到中间位置 `mid`。
- 如果 `nums[mid]` 大于 `nums[right]`，则最小值在 `mid+1` 到 `right` 之间，更新 `left = mid + 1`。
- 如果 `nums[mid]` 小于 `nums[right]`，则最小值在 `left` 到 `mid` 之间，更新 `right = mid`。
- 如果 `nums[mid]` 等于 `nums[right]`，则无法判断最小值的位置，需要减少 `right`。
3. 当 `left` 等于 `right` 时，返回 `nums[left]`。
代码实现：```pythondef findMin(nums):left, right = 0, len(nums) - 1while left < right:mid = left + (right - left) // 2if nums[mid] > nums[right]:left = mid + 1elif nums[mid] < nums[right]:right = midelse:right -= 1return nums[left]```题目二：合并两个有序链表题目描述：将两个有序链表合并为一个新的有序链表。
第四讲 算法典型例题1.下图是某算法的程序框图，则程序运行后输出的结果是 .2、某城市缺水问题比较突出，为了制定节水管理办法，对全市居民某年的月均用水量进行了抽样调查，其中n 位居民的月均用水量分别为x 1，…，x n (单位：吨)，根据图2所示的程序框图，若n =2,且x 1，x 2 分别为1,2，则输出地结果S 为 .3、某城市缺水问题比较突出，为了制定节水管理办法，对全市居民某年的月均用水量进行了抽样调查，其中4位居民的月均用水量分别为（单位：吨）。
根据下左图所示的程序框图，若1x ，2x ，3x ，4x 分别为1，1.5，1.5，2，则输出的结果s 为 .结束0=s ，1=nn s s n +-+=)1(1+=n n9>s输出s开始是否11222i i S S x S S x =+=+i<=n ?是开始 S 1=0，S 2=0，i=1i=i+1否 输出S 结束22111()S S S i i=-图2输入x 1,x 2,…,x n 11i S S x =+i<=4? 是开始 S 1=0，i=1i=i+1否 输出S 结束11S S i =图3输入x 1,x 2,…,x 44、求实数x 的绝对值的算法程序框图，则判断框①中可填 .5、如下图所示，程序框图(算法流程图)的输出值x = .6、执行下边的程序框图，输出的T= .7、程序框图（即算法流程图）如图下（中）所示，其输出结果是_______.8、如上右图是一个算法的流程图，最后输出的W = .开始 输入x ① 是 否 输出x 输出－x结束图4否 结束开始 x=1 x=x+2 x=x+1x 是奇数?x >8? 是 输出x 是否图5T >S ? 否开始S =0,T =0,n=0T =T +n n=n+2 S = S +5是 输出T 结束图6a >100否开始a=1a=2a+1 是 输出a 结束图7S >=10? 否开始S = 0 T =T +2是 输出W 结束T = 1S =T 2－S W = S +T 图8。
算法经典必刷题
以下是一些经典的算法必刷题目，供您参考：
1. 两数之和（LeetCode 1）：给定一个整数数组 nums 和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
2. 三数之和（LeetCode 498）：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有
满足条件且不重复的三元组。
3. 最长回文子串（LeetCode 5）：给定一个字符串 s，找到 s 中最长的回
文子串。
你可以假设 s 的最大长度为 1000。
4. 二分查找（LeetCode 7）：给定一个排序数组和一个目标值，在数组中
查找目标值，并返回其索引。
如果目标值不存在于数组中，则返回 -1。
5. 盛最多水的容器（LeetCode 11）：给定 n 个非负整数 a1，a2，...，an，每个数代表一个坐标点 (i, ai)。
在坐标内画 n 条垂直线，使得 i 垂直线的两
个端点分别为 (i, ai) 和 (i, 0)。
找出其中的一条线，使得该条线落在这 n 条
垂直线构成的区域内时，它到 x 轴的垂线段区域内的水最多。
6. 合并两个有序链表（LeetCode 20）：将两个升序链表合并为一个新的升序链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
这些题目都是经典的算法问题，对于提高算法和数据结构方面的能力非常有帮助。
当然，还有很多其他的经典算法必刷题目，您可以根据自己的实际情况选择题目进行练习。
经典算法练习题算法是计算机科学中的重要概念，它是解决问题的一系列步骤或规则。
在计算机编程中，经典算法是程序员经常使用的一种算法。
通过练习经典算法，可以增强程序员的逻辑思维能力，并提高解决问题的效率和准确性。
本文将介绍几个经典算法练习题。
题目一：冒泡排序算法实现冒泡排序是一种基本的排序算法，它通过多次比较和交换来实现排序。
具体步骤如下：1. 从待排序的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置；2. 继续比较下一对元素，直到没有任何一对元素需要交换为止；3. 重复上述步骤，直到所有元素都排好序为止。
题目二：二分查找算法实现二分查找算法也被称为折半查找算法，它是一种高效的查找算法。
它的前提是待查找的数据已经排好序。
具体步骤如下：1. 首先，确定待查找数据的左边界和右边界；2. 计算待查找数据的中间位置，并将中间位置数据与目标数据进行比较；3. 如果中间位置数据等于目标数据，查找成功；4. 如果中间位置数据大于目标数据，修改右边界为中间位置减1，并回到第二步继续查找；5. 如果中间位置数据小于目标数据，修改左边界为中间位置加1，并回到第二步继续查找；6. 重复上述步骤，直到找到目标数据或者左边界大于右边界为止。
题目三：递归算法实现递归算法是一种自己调用自己的算法。
它通常用于解决可以被分解为重复子问题的问题。
递归算法的实现包括两个关键要素：递归基和递归式。
1. 递归基：确定递归结束的条件，即最简单的情况；2. 递归式：将原问题转化为更小规模的问题，并通过调用自身解决该小规模问题。
题目四：动态规划算法实现动态规划算法是一种将复杂问题分解为多个重叠子问题的算法。
通过解决子问题并将结果保存在一个表中，可以避免重复计算，提高效率。
动态规划算法的实现包括以下步骤：1. 确定状态：将原问题分解为若干子问题，通过定义状态表示子问题；2. 确定状态转移方程：描述当前状态与下一个状态之间的关系；3. 确定初始条件：确定递归出口的初始情况。
决策树算法例题经典
案例1：购物产品推荐。
假设当前我们需要进行购物产品推荐工作，用户可以选择若干项属性，例如品牌、价格、颜色、是否有折扣等等，在已知一些样本的基础上，构
建一棵决策树，帮助用户快速得到最佳购买推荐。
如果用户选择的品牌为A，则直接推荐产品P3；如果选择品牌为B，
则继续考虑价格，如果价格低于100，则推荐产品P1，否则推荐产品P2。
如果用户选择的品牌为C，则直接推荐产品P4。
当然，这只是一个简单的例子，实际应用场景中可能会有更多的属性
和样本。
因此，在构建决策树时需要考虑选取最优特征，避免过度拟合等
问题。
案例2：疾病预测。
假设有一组医学数据，其中包括患者的年龄、性别、身高、体重、血
压等指标以及是否患有糖尿病的标签信息。
我们希望构建一个决策树来帮
助医生快速判断患者是否可能患有糖尿病。
如果患者年龄大于45岁，则进一步考虑体重，如果体重高于120kg，则判断为高风险群体；否则判断为低风险群体。
如果患者年龄不超过45岁，则直接判断为低风险群体。
当然，这只是一个简单的例子，实际应用场景中可能会有更多的指标
和样本。
因此，在构建决策树时需要考虑选取最优特征，避免过度拟合等
问题。
矩阵快速幂hrbust1140数字和问题Description定义一种操作为：已知一个数字，对其各位数字反复求和，直到剩下的数是一位数不能求和为止。
例如：数字2345，第一次求和得到2 + 3 + 4 + 5 = 14，再对14的各位数字求和得到1 + 4 = 5，得到5将不再求和。
现在请你求出对a^b进行该操作后，求最终得到的数字.Input第一行，包含两个数字a（0 <= a <= 2000000000）和b（1 <= b <= 2000000000）Output输出对a^b进行操作后得到的数字是什么#include <iostream>#include<cstring>#include<iomanip>#include<math.h>#include<stdio.h>#include<algorithm>using namespace std;int sum(int x){return ((x+8)%9+1);}int g(int a,int k){if(k==0) return 1;if(k==1) return a%9;if(k%2==0) return (g((a%9)*(a%9),k/2)%9);if(k%2==1) return (a%9)*(g((a%9),k-1)%9);}int main(){int a,k;while(scanf("%d%d",&a,&k)!=EOF){if(a==0)printf("0\n");elseprintf("%d\n",sum(g(a,k)));}}小乐乐喜欢很多明星，她总是喜欢在没事干的时候念叨自己喜欢的那些明星的名字。
有些明星她很喜欢，不自觉的就会念叨很多遍，有的明星则是偶尔想起，随便念叨而已。
给出她一天念叨的明星，请你帮我找出，她念叨最多的明星是哪个呢？（给你N个字符串,要求输出出现最多的名字以及其出现的次数）输入：第一行为一个整数N （1< N < 10000000)接下来为N行每行一个明星的名字 a (|a| <= 10)。
总共她所知道的明星不超过30000个。
输出：输出那个出现次数最多名字和其次数。
格式参照样例输出(保证结果唯一)#include <cstdio>#include <cstring>#define N 300007struct HB {int name;int num;}hashbox[N];int hash(int num) {return num%N;}int find(int num) {int key = hash(num);//得到Hash值while (1) {if (hashbox[key].name == -1 || hashbox[key].name == num) return key;//为空或找到num?}}int main() {int n;while (scanf("%d", &n) != EOF) {int i;int maxname = -1;int maxnum = 0;for (i = 0; i < n; i++) {int name;scanf("%d", &name);int key = find(name);HLG 1073 病毒某种病毒袭击了某地区，该地区有N(1≤N≤50000)人，分别编号为0,1,...,N-1，现在0号已被确诊，所有0的直接朋友和间接朋友都要被隔离。
例如：0与1是直接朋友，1与2是直接朋友，则0、2就是间接朋友。
那么0、1、2都须被隔离。
现在，已查明M个直接朋友关系。
如：0,2就表示0,2是直接朋友关系。
请你编程计算，有多少人要被隔离。
样例输入：100 40 11 23 44 5样例输出：3#include<cstdio>#include<cstring>using namespace std;const int N = 100010;int fa[N];void init(int n) {for (int i = 0; i <= n; ++i) fa[i] = i;}int find(int u) {return fa[u] == u ? fa[u] : fa[u] = find(fa[u]);}void unin(int u, int v) {fa[find(v)] = find(u);int main() {int n, m;while(scanf("%d%d", &n, &m) != EOF) {init(n);//并查集初始化while(m--) {int a, b;scanf("%d%d", &a, &b);unin(a, b);//a和b并到一个集合上}int ans = 0;for(int i = 0; i < n; ++i) {if(find(i) == find(0)) {//如果i和0号患病者是一个集合证明他也患病了ans++;}Description 编辑距离(hrbust oj 1284)俄罗斯科学家VladimirLevenshtein 在1965年提出了编辑距离概念。
编辑距离，又称Levenshtein 距离，是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。
许可的三种编辑操作包括插入一个字符、删除一个字符、将一个字符替换成另一个字符。
至今，编辑距离一直在相似句子检索的领域中发挥着不可忽视的作用。
我们不妨来设计一个程序，计算两个字符串的编辑距离。
Input输入数据的第一行是一个正整数，表示一共有几组数据。
每组数据有两行，每行一个字符串。
* 每个字符串长度不超过1000* 字符串中只含小写英文字母Output对于每组数据，请输出一个整数表示两个字符串的编辑距离。
每个答案占一行。
Sample Input2davidvivianabcaabbccSample Output43尝试用动态规划解决；第一步 尝试表示出状态：用指标函数 d[i][j] 表示 a 字符串的前i 个字符 和 b 字符串的前 j 个字符变成一致所需要的最少操作次数（即编辑距离）；则原问题的答案为d[len(a)][len(b)];第二步 尝试写出状态转移的方程：通过观察可以发现初始状态：d[0][i] = i; （ 0 <= i <= len(b) )d[i][0] = i; ( 0 <= i <= len(a) )d[i][j] 的状态可能由以下几种情况转移而来：d[i-1][j] ：a 串的前i-1个字符和b 串的前j 个字符已经一致，此时要得到d[i][j] 可以在a 串的末尾加上一个b 串末尾的字符 或者 将b串末尾的字符去掉，即可使的a 串的前i个字符和b 串的前j 个字符变成一致，此时有d[i][j] = d[i-1][j] + 1d[i][j-1]: a 串的前i-1个字符和b 串的前j 个字符已经一致，和上述情况类似，此时有d[i][j] = d[i][j-1] + 1d[i-1][j-1]: 这个时候要分两种状态讨论：a[i] == b[j] , 此时：d[i][j] = d[i-1][j-1]a[i] != b[j] , 此时：d[i][j] = d[i-1][j-1] + 1 （只要将a[i]变成b[j]即可)综上所述得到状态转移方程：d[i][j] = min{ d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+(a[i]==b[j]? 0:1) }实现如下int main(){int T;scanf("%d",&T);while (T--){scanf("%s %s",a+1,b+1);int la = strlen(a+1);int lb = strlen(b+1);for (int i = 1; i <= la; ++i) d[i][0] = i;for (int i = 1; i <= lb; ++i) d[0][i] = i;d[0][0] = 0;for (int i = 1; i <= la; ++i){for (int j = 1; j <= lb; ++j){if ( a[i] == b[j] ){d[i][j] = d[i-1][j-1];}else{d[i][j] = d[i-1][j-1] + 1;}d[i][j] = min( d[i][j], d[i-1][j]+1 );d[i][j] = min( d[i][j], d[i][j-1]+1 );}}printf("%d\n",d[la][lb]);}return 0;}#include <stdio.h>#include <string.h>const int maxn=10000;//提前估计好可能会开的节点的个数int tot; //节点编号，模拟申请新节点，静态申请int trie[maxn][26]; //假设每个节点的分支有26个bool isw[maxn]; //判断该节点是不是单词结尾void insert(char *s,int rt){for(int i=0;s[i];i++){int x=s[i]-'a';//假设单词都是小写字母组成if(trie[rt][x]==0){//没有，申请新节点trie[rt][x]=++tot;}rt=trie[rt][x];}isw[rt]=true;}bool find(char *s,int rt){for(int i=0;s[i];i++){int x=s[i]-'a';//假设单词都是小写字母组成if(trie[rt][x]==0){}rt=trie[rt][x];}return isw[rt];}char s[22];//单词读入int main(){tot=0;//一开始没有节点int rt=++tot;//申请一个根节点memset(trie[rt],0,sizeof(trie[rt]));//初始化根节点memset(isw,false,sizeof(isw));while(scanf("%s",s),s[0]!='#'){//新建字典，以一个'#'结束insert(s,rt);}while(scanf("%s",s),s[0]!='#'){//查单词，以一个'#'结束if(find(s,rt))HDU 1166 敌兵布阵[一维树状数组]Input第一行一个整数T，表示有T组数据。
