算法题目基本思想

1. 动态规划算法的基本思想是什么

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

2. 基本算法思想之穷举法

穷举算法是最基本的算法思想，我们通过一个简单的例子来看看穷举算法的应用。鸡兔同笼问题：

通过分析我们可以知道鸡的数量应该为0~35之间的数。这样，我们可以使用穷举法来逐个判断是否符合，从而搜索答案。

3. 舍伍德算法的基本思想

设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在x∈Xn使得 tA(x)>>tA(n)的可能性。
希望获得一个概率算法B，使得对问题的输入规模为n的每一个实例均有
这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。
舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。

4. kmp算法的基本思想

主串：a
b
a
c
a
a
b
a
c
a
b
a
c
a
b
a
a
b
b，下文中我们称作T
模式串：a
b
a
c
a
b，下文中我们称作W
在暴力字符串匹配过程中，我们会从T[0]
跟
W[0]
匹配，如果相等则匹配下一个字符，直到出现不相等的情况，此时我们会简单的丢弃前面的匹配信息，然后从T[1]
跟
W[0]匹配，循环进行，直到主串结束，或者出现匹配的情况。这种简单的丢弃前面的匹配信息，造成了极大的浪费和低下的匹配效率。
然而，在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。
比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。
在第一次匹配过程中
T:
a
b
a
c
a
a
b
a
c
a
b
a
c
a
b
a
a
b
b
W:
a
b
a
c
ab
在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，现在T[0]~T[4]就是上文中说的已经匹配的模式串子串，现在移动找出最长的相同的前缀和后缀并使他们重叠：
T:
a
b
a
c
aab
a
c
a
b
a
c
a
b
a
a
b
b
W:
a
b
a
c
ab
然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。
然而，有些同学可能会问了，每次都要计算最长的相同的前缀会不会反而浪费了时间，对于模式串来说，我们会提前计算出每个匹配失败的位置应该移动的距离，花费的时间是常数时间。比如：
j012345W[j]abacabF(j)001012当W[j]与T[i]不匹配的时候，设置j
=
F(j-1)
文献中，朱洪对KMP算法作了修改，他修改了KMP算法中的next函数，即求next函数时不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]<>W[j]，他记修改后的next函数为newnext。显然在模式串字符重复高的情况下，朱洪的KMP算法比KMP算法更加有效。
以下给出朱洪的改进KMP算法和next函数和newnext函数的计算算法。

5. 动态规划算法的基本思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。

拓展资料：

动态规划的实质是分治思想和解决冗余，因此动态规划是一种将问题实例分析为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略
动态规划所针对的问题有一个显着的特征，即它对应的子问题树中的子问题呈现大量的重复。动态规划的关键在于，对于重复的子问题，只在第一次遇到时求解，并把答案保存起来，让以后再遇到时直接引用，不必要重新求解。

6. 常见算法思想6：回溯法

回溯法也叫试探法，试探的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

（1）针对所给问题，定义问题的解空间。
（2）确定易于搜索的解空间结构。
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。

下面是回溯的3个要素。
（1）解空间：表示要解决问题的范围，不知道范围的搜索是不可能找到结果的。
（2）约束条件：包括隐性的和显性的，题目中的要求以及题目描述隐含的约束条件，是搜索有解的保证。
（3）状态树：是构造深搜过程的依据，整个搜索以此树展开。

下面是影响算法效率的因素：

回溯法搜索解空间时，通常采用两种策略避免无效搜索，提高回溯的搜索效率:

为缩小规模，我们用显示的国际象棋8*8的八皇后来分析。按照国际象棋的规则，皇后的攻击方式是横，竖和斜向。
皇后可以攻击到同一列所有其它棋子，因此可推导出每1列只能存在1个皇后，即每个皇后分别占据一列。棋盘一共8列，刚好放置8个皇后。

为了摆放出满足条件的8个皇后的布局，可以按如下方式逐步操作：

把规模放大到N行N列也一样，下面用回溯法解决N皇后问题：

执行：

7. 什么是算法构造算法的基本思想是什么

1顺序结构
按从上到下的顺序进行
2选择结构
根据条件作判断,再决定执行哪一种操作的算法结构
必须包含判断框
3循环结构

8. 数据结构中图的克鲁斯卡尔算法的基本思想是

基本思想是：设有一个有n个顶点的连通网络N=｛V，E｝，最 初先构造一个只有n个顶点，没有边的非连通图 T=｛ V，￠｝，图中每个顶点自成一个 连通分量。当在E中选到一条具有最小权值的边时，若该边的两个顶点落在不同的连通 分量上，则将此边加人到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复 下去，直到所有顶点在同一个连通分量上为止。

9. 外部排序算法基本思想是什么

外部排序的基本思路

假设有一个72KB的文件，其中存储了18K个整数，磁盘中物理块的大小为4KB，将文件分成18组，每组刚好4KB。

首先通过18次内部排序，把18组数据排好序，得到初始的18个归并段R1~R18，每个归并段有1024个整数。

然后对这18个归并段使用4路平衡归并排序：

第1次归并：产生5个归并段

R11 R12 R13 R14 R15

其中

R11是由{R1,R2,R3,R4}中的数据合并而来

R12是由{R5,R6,R7,R8}中的数据合并而来

R13是由{R9,R10,R11,R12}中的数据合并而来

R14是由{R13,R14,R15,R16}中的数据合并而来

R15是由{R17,R18}中的数据合并而来

把这5个归并段的数据写入5个文件：

foo_1.dat foo_2.dat foo_3.dat foo_4.dat foo_5.dat

第2次归并：从第1次归并产生的5个文件中读取数据，合并，产生2个归并段

R21 R22

其中R21是由{R11,R12,R13,R14}中的数据合并而来

其中R22是由{R15}中的数据合并而来

把这2个归并段写入2个文件

bar_1.dat bar_2.dat

第3次归并：从第2次归并产生的2个文件中读取数据，合并，产生1个归并段

R31

R31是由{R21,R22}中的数据合并而来

把这个文件写入1个文件

foo_1.dat

此即为最终排序好的文件。

二 使用败者树加快合并排序

外部排序最耗时间的操作时磁盘读写，对于有m个初始归并段，k路平衡的归并排序，磁盘读写次数为

|logkm|，可见增大k的值可以减少磁盘读写的次数，但增大k的值也会带来负面效应，即进行k路合并

的时候会增加算法复杂度，来看一个例子。

把n个整数分成k组，每组整数都已排序好，现在要把k组数据合并成1组排好序的整数，求算法复杂度

10. 算法设计的基本思想与方法是什么

本书围绕算法设计技术组织素材，对每种算法技术选择了多个典型范例进行分析。本书将直观性与严谨性完美地结合起来。每章从实际问题出发，经过具体、深入、细致的分析，自然且富有启发性地引出相应的算法设计思想，并对算法的正确性、复杂性进行恰当的分析、认证。