算法设计
⑴ 计算机算法设计的关键是什么
刚看到有人答鸵鸟算法，的确是个很重要的算法。
然后就想到了下面这个sorting算法，虽然不怎么重要，但是挺有意思的。
我觉得这有可能是我这辈子最喜欢的算法了：
Sleep Sort
英语差不多的同学可以看一下Quora上的简介
https://www.quora.com/What-is-sleep-sort
这套算法是4chan上的某个精神病提出的
以下是代码：
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int main(int c, char **v)
{
while (--c > 1 && !fork());
sleep(c = atoi(v[c]));
printf("%d\n", c);
wait(0);
return 0;
}
用GCC编译，运行的时候把你想要sort的东西当成command line arguments送给可执行文件就行了
代码来源：https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
=====以下原答案=====
计算机科学里最重要的算法就是你觉得最重要的算法以外的所有算法。←这是玩笑话
算法是一整个体系，从divide and conquer,dynamic programming,greedy这样的基本分类到randomized, linear programming这种奇怪的东西都是算法体系里重要的一环。算法里还有一个大类就是data structure，这些东西环环相关。
初学算法的同学就是要不断的接触，了解，分析这些乱七八糟的东西，最终达到看到不同的结构，不同的需求能够选择正确的工具。我的第一个算法老师曾经这样说过：there isn't a best algorithm for everything, choose the best tool for your problem
就拿你说的hash来看，你觉得key value pair到处都有用到，就觉得这个算法最重要，O(1)的best case看起来也很诱人。可是能用的地方到底有多少？database天天用range query你告诉我你库只有hash index？不能吧，所以B tree是不是很重要？算法和优化是计算机科学里的一个大项，多少代人的研究成果让你一个hash最重要给概括了，这样是不是有种钦定的感觉？
算法导论多看看，没事的时候上leetcode做做题，多见识见识不同的算法是如何应用的，每次选择一个算法/数据结构就问问自己为什么这样？是hash，是hash先，明明都是hash先来的……key value也好，O(1)也好，还是universal那家伙也好...怎么就做不了sssp呢？以后遇上奇怪的程序也不至于懵逼到：我一个linear programming，怎么就跑maximum cardinality bipartite matching来了呢
至于到底什么算法最重要，能用到的都是最重要的，谢谢
⑵ 算法设计-流程制作
我觉得这样可能比较好理解一点 有三根柱子，标记为A, B, C 先要理解函数hanoi(n,A,B,C) 的意思是借助于B柱子将A上面的n个盘子移到C上面，必须充分对应到各个参数。 如果想将n个盘子从A柱子移动到C柱子 可以分为这样几个步骤 （1）必须将A最下面也就是最大的那个盘子移动到C最下面 首先需要借助C柱子将A上面的n-1个盘子移动到B上面 就是hanoi(n-1,A,C,B) 。 此时A上面只有一个最大的盘子，B上面按序放着n-1个盘子，C上面有0个盘子。 （2）将A上面的盘子移动到C上面，只需要1步。 此时A上面有0个盘子，B上面按序放着n-1个盘子，C上面只有一个最大的盘子。 （3）最后借助于A柱子将B上面n-1个盘子移到C上面即可 就是hanoi(n-1,B,A,C) 。 所以实际上数学推导公式为f(n)=2f(n-1)+1，其中f(1)=1，f(n)表示将n个盘子从A柱子移到C柱子的步数
⑶ 算法指什么，算法设计有什么指标
通俗讲就是解决问题的方法，用到计算机里，一般指程序设计中用到算法比较多。专也是考研属的时候计算机系的一个重点。
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
一个算法应该具有以下五个重要的特征：
有穷性： 一个算法必须保证执行有限步之后结束；
确切性： 算法的每一步骤必须有确切的定义；
输入：一个算法有0个或多个输入，以刻画运算对象的初始情况；
输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
http://www.cqzxzx.cn/it/noi/shuanfa/001.htm
⑷ 算法设计有哪些方法
算法设计常用的几种方法是
1. 穷举法
2. 贪心法
3. 分治法
4. 回溯法
5. 分枝限界法
6. 动态规划法
⑸ 算法设计的步骤不包含什么
一、学习内容
1. 算法设计中五大常用算法
1) 分治法
设计思想：将一个难以直接解决的大问题分解成规模较小的相同问题，以便分而治之。
实际的应用：快速排序、归并排序
分治法在每一层递归上的基本步骤：
①分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
②解决：若子问题规模较小就直接解决，不然就递归解决各个子问题
③合并：将各个子问题的解合并为原问题的解
以快速排序为例理解分治法：
快速排序代码：
public static void quickSort(int a[],int low,int high){
if(low < high){
int pivotpos = partition(a,low,high);
quickSort(a,low,pivotpos-1);
quickSort(a,pivotpos+1,high);
}
}
public static int partition(int a[],int low,int high){
int pivot = a[low];
while (low < high){
while (low < high && a[high] >= pivot){
--high;
}
a[low] = a[high];
while (low < high && a[low] <= pivot){
++low;
}
a[high] = a[low];
}
a[low] = pivot;
return low;
}
①分解:选取基准元素，将左右两侧进行划分
②解决:分别将两个子序列进行快速排序
③合并:将排好的子序列合并
以两路合并排序为例理解分治法：（分治法中的合并在归并排序中体现得更加清楚）
归并排序代码：
public static void merge(int a[],int low,int mid,int high){
int[] temp = new int[high-low+1];
int i = low;
int j = mid+1;
int k = 0;
while (i <= mid && j <= high){
if(a[i] < a[j]){
temp[k++] = a[i++];
}else {
temp[k++] = a[j++];
}
}
//把左边剩下的移到数组中
while (i <= mid){
temp[k++] = a[i++];
}
//把右边剩下的移到数组中
while (j <= high){
temp[k++] = a[j++];
}
//更新原数组
for (int x = 0;x <temp.length;x++){
a[x+low] = temp[x];
}
}
public static int[] mergeSort(int a[],int low,int high){
int mid = (low+high)/2;
if(low < high){
mergeSort(a,low,mid);
mergeSort(a,mid+1,high);
//左右合并
merge(a,low,mid,high);
}
return a;
}
①分解:将一个数组一刀切两半，递归切，直到切成单个元素
②解决:单个元素合并成有序的小数组
③合并:小数组合并成大数组，最终合并完成
2) 动态规划法
设计思想：最优化原理，即一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略
动态规划法所要满足的条件：
①问题中的状态满足最优化原理
②问题中的状态必须满足无后效性，无后效性指的是下一时刻的状态只与当前的状态 有关而与当前状态的之前状态无关。
动态规划三要素：
①问题的阶段
②每个阶段的状态
③从前一个阶段转换到后一个阶段的递推关系
实际的应用：0/1背包问题 最长公共子串问题
以最长公共子串问题为例理解动态规划法：
定义dp[i][j]表示以A中第i个字符结尾的子串和B中第j个字符结尾的子串的最大公共子串，dp 的大小也为 (n + 1) x (m + 1) ，这多出来的一行和一列是第 0 行和第 0 列，初始化为 0，表示空字符串和另一字符串的子串的最长公共子串。
当我们要求dp[i][j]时，我们要先判断A的第i个元素B的第j个元素是否相同即判断A[i - 1]和 B[j -1]是否相同，如果相同它就是dp[i - 1][j- 1] + 1，相当于在两个字符串都去掉一个字符时的最长公共子串再加 1；否则最长公共子串取0。所以整个问题的初始状态为：
dp[i][0]=0,dp[0][j]=0
相应的状态转移方程为：
实现代码：
public static int findLongest(String A,String B){
int n = A.length();
int m = B.length();
if(m == 0 || n == 0){
return 0;
}
int result = 0;
int[][] dp = new int[n+1][m+1];
//初始状态
for(int i = 0; i <= n;i++){
dp[i][0] = 0;
}
for(int i = 0; i <= m;i++){
dp[0][i] = 0;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(A.charAt(i-1) == B.charAt(j-1)){
dp[i][j] = dp[i-1][j-1]+1;
result = Math.max(result,dp[i][j]);
}else {
dp[i][j] = 0;
}
}
}
return result;
}
⑹ 算法设计一般采用的是______方法。
A 粗到细 抽象到具体
⑺ 算法设计的过程一般是什么样子
和你做数学题目的过程一样，已知条件是什么？已知量是什么？要求什么？需要输出一个什么结果？
算法设计就是把问题解决步骤用计算机编程语言来表示出来
⑻ 算法设计和编码之间的区别是什么哪种更难
算法设计更难，编码只是根据算法的伪代码去实现算法。需要一些写代码的功底。
算法设计更注重的是想法。基本上算法设计出来了，写程序就不难了。
算法设计的工资比编码的工资高得多，一个高中生就能编码了。
在印度，程序员基本上是高中生。而中国的计算机本科生出来基本上做了程序员。