程序基本算法

㈠ 算法和软件的关系，程序员应该学习哪些算法

一.基本算法:

枚举. (poj1753,poj2965)

贪心(poj1328,poj2109,poj2586)

递归和分治法.

递推.

构造法.(poj3295)

模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

图的深度优先遍历和广度优先遍历.

最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓扑排序 (poj1094)

二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)

最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

串 (poj1035,poj3080,poj1936)

排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)

简单并查集的应用.

哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼树(poj3253)

堆

trie树(静态建树、动态建树) (poj2513)

四.简单搜索

深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

背包问题. (poj1837,poj1276)

型如下表的简单DP(可参考lrj的书 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学

组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.

几何公式.

叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中级（校赛压轴及省赛中等难度）:
一.基本算法:

C++的标准模版库的应用. (poj3096,poj3007)

较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

差分约束系统的建立和求解. (poj1201,poj2983)

最小费用最大流(poj2516,poj2516,poj2195)

双连通分量(poj2942)

强连通分支及其缩点.(poj2186)

图的割边和割点(poj3352)

最小割模型、网络流规约(poj3308)

㈡ 程序设计常见的算法

常用的算法有：递推法、贪心法、列举法、递归法、分治法和模拟法。
建议你去看看《算法导论》，上面很全的。

㈢ 作为程序员提高编程能力的几个基础算法

一：快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环（innerloop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divideandconquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

1从数列中挑出一个元素，称为“基准”（pivot），

2重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

二：堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

创建一个堆H[0..n-1]

把堆首（最大值）和堆尾互换

3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4.重复步骤2，直到堆的尺寸为1

三：归并排序

归并排序（Mergesort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4.重复步骤3直到某一指针达到序列尾

5.将另一序列剩下的所有元素直接复制到合并序列尾

四：二分查找算法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

五：BFPRT(线性查找算法)

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，五位算法作者做了精妙的处理。

1.将n个元素每5个一组，分成n/5(上界)组。

2.取出每一组的中位数，任意排序方法，比如插入排序。

3.递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。

4.用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。

5.若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。

终止条件：n=1时，返回的即是i小元素。

六：DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

深度优先遍历图算法步骤：

1.访问顶点v；

2.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

3.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

上述描述可能比较抽象，举个实例：

DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

七：BFS(广度优先搜索)

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。

BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

1.首先将根节点放入队列中。

2.从队列中取出第一个节点，并检验它是否为目标。

如果找到目标，则结束搜寻并回传结果。

否则将它所有尚未检验过的直接子节点加入队列中。

3.若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

4.重复步骤2。

八：Dijkstra算法

戴克斯特拉算法（Dijkstra’salgorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

该算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E表示G中所有边的集合，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负权重（weight）。边的权重可以想象成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。

1.初始时令S=,T=，T中顶点对应的距离值

若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

若不存在<V0,Vi>，d(V0,Vi)为∞

2.从T中选取一个其距离值为最小的顶点W且不在S中，加入S

3.对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

九：动态规划算法

动态规划（Dynamicprogramming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

关于动态规划最经典的问题当属背包问题。

1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

十：朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。

朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。

尽管是带着这些朴素思想和过于简单化的假设，但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

通过掌握以上算法，能够帮你迅速提高编程能力，成为一名优秀的程序员。

㈣ 计算机程序语言包括哪几个基本算法

冒泡排序、选择排序、、插入排序、希尔排序、归并排序、堆排序

Java版代码：

package com.kevin;

/**
* 七种排序算法Java版
*
* @author Administrator
*
*/
public class Sort {

/**
* 打印数组
*
* @param data
*/
public static void displayData(int[] data) {
for (int d : data) {
System.out.print(d + " ");
}
System.out.println();
}

/**
* 冒泡排序算法，时间复杂度O(n2)，算法具有稳定性，堆排序和快速排序算法不具有稳定性，即排序后相同元素的顺序会发生变化
*
* @param src
*/
public static void bubbleSort(int[] src) {
if (src.length > 0) {
int length = src.length;
for (int i = 1; i < length; i++) {
for (int j = 0; j < length - i; j++) {
if (src[j] > src[j + 1]) {
int temp = src[j];
src[j] = src[j + 1];
src[j + 1] = temp;
}
}
}
}
}

/**
* 快速排序，时间复杂度O(nlogn)，最坏时间复杂度O(n2)，平均时间复杂度O(nlogn)，算法不具稳定性
*
* @param src
* @param begin
* @param end
*/
public static void quickSort(int[] src, int begin, int end) {
if (begin < end) {
int key = src[begin];
int i = begin;
int j = end;

while (i < j) {
while (i < j && src[j] > key) {
j--;
}
if (i < j) {
src[i] = src[j];
i++;
}
while (i < j && src[i] < key) {
i++;
}
if (i < j) {
src[j] = src[i];
j--;
}
}

src[i] = key;

quickSort(src, begin, i - 1);
quickSort(src, i + 1, end);
}

}

/**
* 选择排序，分为简单选择排序、树形选择排序(锦标赛排序)、堆排序 此算法为简单选择排序
*
* @param a
*/
public static void selectSort(int[] a) {
int length = a.length;
for (int i = 0; i < length; i++) {
int minIndex = i;

for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}

if (minIndex != i) {
int temp = a[minIndex];
a[minIndex] = a[i];
a[i] = temp;
}
}
}

/**
* 插入排序，适用于少量数据的排序，时间复杂度O(n2)，是稳定的排序算法，原地排序
*
* @param a
*/
public static void insertSort(int[] a) {
int length = a.length;

for (int i = 1; i < length; i++) {
int temp = a[i];
int j = i;
for (; j > 0 && a[j - 1] > temp; j--) {
a[j] = a[j - 1];
}
a[j] = temp;
}
}

/**
* 归并排序算法，稳定排序，非原地排序，空间复杂度O(n)，时间复杂度O(nlogn)
*
* @param a
* @param low
* @param high
*/
public static void mergeSort(int a[], int low, int high) {
if (low < high) {
mergeSort(a, low, (low + high) / 2);
mergeSort(a, (low + high) / 2 + 1, high);
merge(a, low, (high + low) / 2, high);
}
}

/**
* 归并排序辅助方法，合并
*
* @param a
* @param low
* @param mid
* @param high
*/
private static void merge(int[] a, int low, int mid, int high) {
int[] b = new int[high - low + 1];
int s = low;
int t = mid + 1;
int k = 0;
while (s <= mid && t <= high) {
if (a[s] <= a[t])
b[k++] = a[s++];
else
b[k++] = a[t++];
}
while (s <= mid)
b[k++] = a[s++];
while (t <= high)
b[k++] = a[t++];
for (int i = 0; i < b.length; i++) {
a[low + i] = b[i];
}
}

/**
* 希尔排序的一种实现方法
*
* @param a
*/
public static void shellSort(int[] a) {
int temp;
for (int k = a.length / 2; k > 0; k /= 2) {
for (int i = k; i < a.length; i++) {
for (int j = i; j >= k; j -= k) {
if (a[j - k] > a[j]) {
temp = a[j - k];
a[j - k] = a[j];
a[j] = temp;
}
}
}
}
}

/**
* 堆排序，最坏时间复杂度O(nlog2n)，平均性能接近于最坏性能。由于建初始堆所需的比较次数多，故堆不适合记录较少的比较 堆排序为原地不稳定排序
*
* @param array
*/
public static void heapSort(int[] array) {
for (int i = 1; i < array.length; i++) {
makeHeap(array, i);
}

for (int i = array.length - 1; i > 0; i--) {
int temp = array[i];
array[i] = array[0];
array[0] = temp;
rebuildHeap(array, i);
}
}

/**
* 堆排序辅助方法---创建堆
*
* @param array
* @param k
*/
private static void makeHeap(int[] array, int k) {
int current = k;
while (current > 0 && array[current] > array[(current - 1) / 2]) {
int temp = array[current];
array[current] = array[(current - 1) / 2];
array[(current - 1) / 2] = temp;
current = (current - 1) / 2;
}

}

/**
* 堆排序辅助方法---堆的根元素已删除，末尾元素已移到根位置，开始重建
*
* @param array
* @param size
*/
private static void rebuildHeap(int[] array, int size) {
int currentIndex = 0;
int right = currentIndex * 2 + 2;
int left = currentIndex * 2 + 1;
int maxIndex = currentIndex;
boolean isHeap = false;
while (!isHeap) {
if (left < size && array[currentIndex] < array[left]) {
maxIndex = left;
}
if (right < size && array[maxIndex] < array[right]) {
maxIndex = right;
}
if (currentIndex == maxIndex) {
isHeap = true;
} else {
int temp = array[currentIndex];
array[currentIndex] = array[maxIndex];
array[maxIndex] = temp;
currentIndex = maxIndex;
right = currentIndex * 2 + 2;
left = currentIndex * 2 + 1;
}
}
}

public static void main(String[] args) {
int data[] = { 2, -1, 5, 4, 6, 8, 7, -3 };
Sort.displayData(data);

Sort.bubbleSort(data);
Sort.displayData(data);
}

}

㈤ 程序设计与基本算法的内容提要

全书共分10章。第1章介绍了Pascal语言程序开发环境；第2～9章介绍了’Pascal语言的各种基本知识，体现了Pascal语言自身的描述能力和编程方法；第10章介绍了程序设计中的基本算法；书末附有部分习题参考答案。为了使学生尽快掌握竞赛的内容和范围，除前两章和第10章外，其余各章特意从近年来全国青少年信息学奥林匹克竞赛试题中精选了若干题目，组成了“典型试题分析”一节的内容。这些试题应用本章所讲内容完全可以解答。
本书深入浅出，思路清晰，不仅能帮助刚刚迈进信息学奥林匹克竞赛大门的选手掌握程序设计的基本知识，还能从启迪思维、开发智力的角度引导他们如何使用计算机来分析问题和解决问题。
本书既可以作为全国青少年信息学奥林匹克竞赛的培训教材和自学用书，也可以作为ACM大学生程序设计竞赛及大专院校相关专业教师和学生的参考书。

㈥ 程序算法的介绍

程序算法是对特定问题求解过程的描述，是指令的有限序列，每条指令完成一个或多个操作。通俗地讲，就是为解决某一特定问题而采取的具体有限的操作步骤。

㈦ C语言基本算法

1.输入语句:scanf("控制格式",接受值列表),其中控制格式常用的有:%d,%c,%s,%f,分别
表示整型,字符型,字符串和浮点型.
例如int
a;char
c;scanf("%d
%c",&a,&c);表示向a和c输入值
2.赋值语句:=号,如将b赋值为10,为b=10
3.条件:if(布尔表达式){程序}else{程序}(注:此结构可嵌套)
switch(离散量){case
常量:...;case
常量:...}
例:int
a;scanf("%d",&a);
if(a>10)
{printf("大于10");}
else
{printf("小于10")}
例:switch(months)
{
case
1:printf("1月有31天");break;
case
3:printf("3月有31天");break;
....
default:break;
}
4.循环:for结构,while结构,do-while结构
for(初始化;判断;变化)
{
}
while(条件)
{
}
do
{
}while(条件)

㈧ 什么是程序算法

算法是对特定问题求解过程的描述，是指令的有限序列，每条指令完成一个或多个操作。通俗地讲，就是为解决某一特定问题而采取的具体有限的操作步骤。

算法具有以下特性：

（1）有穷性：在有限的操作步骤内完成。有穷性是算法的重要特性，任何一个问题的解决不论其采取什么样的算法，其终归是要把问题解决好。如果一种算法的执行时间是无限的，或在期望的时间内没有完成，那么这种算法就是无用和徒劳的，我们不能称其为算法。

（2）确定性：每个步骤确定，步骤的结果确定。算法中的每一个步骤其目的应该是明确的，对问题的解决是有贡献的。如果采取了一系列步骤而问题没有得到彻底的解决，也就达不到目的，则该步骤是无意义的。

（3）可行性：每个步骤有效执行，得到确定的结果。每一个具体步骤在通过计算机实现时应能够使计算机完成，如果这一步骤在计算机上无法实现，也就达不到预期的目的，那么这一步骤是不完善的和不正确的，是不可行的。

（4）零个或多个输入：从外界获得信息。算法的过程可以无数据输入，也可以有多种类型的多个数据输入，需根据具体的问题加以分析。

（5）一个或多个：算法得到的结果就是算法的输出（不一定就是打印输出）。算法的目的是为解决一个具体问题，一旦问题得以解决，就说明采取的算法是正确的，而结果的输出正是验证这一目的的最好方式。