程序员算法每日一练第三题

㈠ 程序员必须掌握哪些算法

一.基本算法:

枚举. (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)

三.数据结构.

线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)

静态二叉检索树. (poj2482,poj2352)

树状树组(poj1195,poj3321)

RMQ. (poj3264,poj3368)

并查集的高级应用. (poj1703,2492)

KMP算法. (poj1961,poj2406)

四.搜索

最优化剪枝和可行性剪枝

搜索的技巧和优化 (poj3411,poj1724)

记忆化搜索(poj3373,poj1691)

五.动态规划

较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
记录状态的动态规划. (POJ3254,poj2411,poj1185)

树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
随机化算法(poj3318,poj2454)
杂题(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.

坐标离散化.

扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多边形的内核(半平面交)(poj3130,poj3335)

几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级（regional中等难度）:
一.基本算法要求:

代码快速写成,精简但不失风格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保证正确性和高效性. poj3434

二.图算法:

度限制最小生成树和第K最短路. (poj1639)

最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最优比率生成树. (poj2728)

最小树形图(poj3164)

次小生成树.

无向图、有向图的最小环

三.数据结构.

trie图的建立和应用. (poj2778)

LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法(RMQ+dfs)).(poj1330)
双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)
左偏树(可合并堆).

后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)
四.搜索

较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)
四边形不等式理论.

较难的状态DP(poj3133)

六.数学

组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.

半平面求交(poj3384,poj2540)

可视图的建立(poj2966)

点集最小圆覆盖.

对踵点(poj2079)

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

一：快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序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.子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

十：朴素贝叶斯分类算法

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

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

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

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

㈢ 求编程领域上一些经典算法同时也是程序员必须掌握的算法

这是我在一个论坛里看到的，你也参考参考吧。C++的虚函数
======================
C++使用虚函数实现了其对象的多态，C++对象的开始四个字节是指向虚函数表的指针，其初始化顺序是先基类后派生类，所以该虚函数表永远指向最后一个派生类，从而实现了相同函数在不同对象中的不同行为，使得对象既有共性，又有其个性。

内存池分配、回收之伙伴算法
=======================
伙伴算法是空闲链表法的一个增强算法，依次建立2^0\2^1\2^2\2^3...2^n大小的 内存块空闲链表，利用相邻内存块的伙伴性质，很容易将互为伙伴的内存块进行合并移到相应的空闲链表或将一块内存拆分成两块伙伴内存，一块分配出去，另一块挂入相应空闲链表，使得内存的分配和回收变得高效。

AVL树
=======================
AVL树是一个平衡二叉树，其中序遍历是从小到大排序的，该结构插入节点和检索非常高效，被广泛应用

快速排序
=======================
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。效率非常高

密码学之非对称加密协议（公钥、私钥加密协议）
======================
非对称加密算法需要两个密钥，用其中一个加密产生的密文，只能通过另外一个密钥解密，密钥持有者A可以将其中一个公开，称为公用密钥，另外一个秘密保存称为私钥，这样当某人B想给A传一封秘信时，只要将密信使用A的公钥加密后，就可以放心使用各种信道将迷信传给A了，因为该密信只有A可以解密，第三者截取因为无法解密而毫无意义。
该算法很好地解决了密钥的安全传递的问题，因为公钥和加密算法都是公开的，私钥不需要传输。

密码学之数字签名协议（身份鉴别、防抵赖）
======================
数字签名也是建立在非对称加密基础之上的，如果A君用它的私钥将文件加密后在发布，A君就无法抵赖该文件是其发布的，因为其他人能通过A君的公钥将文件解密就说明，如果算法可靠，该文件一定是A君用其私钥加密的。
由于非对称加密算法的加密和解密很慢，现在的数字签名并非是将其要发布的信息用其私钥加密，而是先用一个单项散列算法如（MD5）产生一个该信息的比较短的指纹（hash值），对其指纹用其私钥加密后和信息一并发布，同样达到了防抵赖的作用。

无回溯字符串模式匹配-kmp算法
======================
他是根据子串的特征，当匹配失败时，不需要回溯，而是直接将字串向后滑动若干个字节，继续匹配，极大提高了匹配速度。该算法被广泛使用。详细请参考数据结构教程。

最小路径选路-迪杰斯特拉算法、弗洛伊德算法
======================
学习数据结构的时候，印象最深的就要算kmp算法和最小路径算法了，因为理解他们比较费脑子，我是不可能发明这些算法了，发明他们的都是天才，呵呵。
使用最短路径的算法曾经帮人写过一个小东西，还是很有效的，记得是使用的弗洛伊德算法的一个变种，要详细了解的朋友可以查找相关资料，想将他们使用在你的项目中，代码直接从教科书上抄就可以了，不需要理解。

tcp协议之-nagle算法
======================
tcp、ip中令人叫绝的想法很多，印象最深的要算nagle算法了。
tcp出于效率和流量控制的考虑，发送端的数据不是产生多少就马上发送多少，一般是等到数据集聚到发送缓冲区长度的一半或者数据达到最大tcp数据包数据部分长度（好像是65515）才启动发送，而且还要看接受端可用缓冲区的大小，如果接受端产生一个回应报文通知发送端没有接受空间了，发送端哪怕缓冲区已经满了，也不会启动发送，直到接受端通告发送端其已经有了接受数据的空间了。
这样就有一个问题，假如发送端就是要发送一个小报文（比如10个字节），然后等待对方的回应。按照上面的方案，tcp会一直等数据收集到一定量才发送，于是矛盾就产生了。应用层不再发数据，tcp等不到足够的数据不会将10个字的数据发送到网卡，接收端应用层收不到数据就不会回应发送端。
你也可能说，可以让修改发送端发送条件，不一定要等到足够的数据再发送，为了效率考虑，可以考虑延时一定的时间，比如说1秒，如果上层还没有数据到来，就将发送缓冲中的数据发出去。当然这样也是可行的，尽管应用端白白等了1秒钟啥也没干，呵呵。
其实nagle算法很好解决了该问题，它的做发是链接建立后的第一次发送不用等待，直接将数据组装成tcp报文发送出去，以后要么等到数据量足够多、要么是等到接受方的确认报文，算法及其简单，而且很好解决了上面的矛盾。

socket之io模型设计
======================
windows下socket有两种工作方式：
1）同步方式
2）异步方式

同步socket又有两种工作模式：
1）阻塞模式
2）非阻塞模式

阻塞模式是最简单的工作模式，以tcp的发送数据为例，如果发送缓冲区没有空间，send调用就不会返回，一直要等到能够发出一点数据为止，哪怕是一个字节，但是send返回并不表示我要发送的数据已经全部提交给了tcp，所以send返回时要检查这次发送的数量，调整发送缓冲指针，继续发送，直到所有数据都提交给了系统。
由于其阻塞的特性，会阻塞发送线程，所以单线程的程序是不适合使用阻塞模式通信的，一般使用一个连接一个线程的方法，但是这种方式对于要维护多个连接的程序，是个不好的选择，线程越多，开销越大。

同步非阻塞模式的socket不会阻塞通信线程，如果发送缓冲区满，send调用也是立刻返回，接受缓冲区空，recv也不会阻塞，所以通信线程要反复调用send或recv尝试发送或接收数据，对cpu是很大的浪费。
针对非阻塞的尴尬，接口开发人员发明了三种io模型来解决该问题：
1）选择模型（select）
2）异步选择模型（AsyncSelect）
3）事件选择模型（EventSeselect）
其思想是根据io类型，预先查看1个或n个socket是否能读、写等。
其select本身来说，select是阻塞的，可以同时监视多个socket，只要所监视的其中一个socket可以读、写，secect调用才返回
异步选择模型其select是异步的（异步是不会阻塞的），是将监视任务委托给系统，系统在socket可读、写时通过消息通知应用程序。有一点需要说明，假如应用程序已经有很多数据需要发送，当收到可写通知时，一定要尽量多地发送数据，直到发送失败，lasterror提示“将要阻塞”，将来才可能有新的可写通知到来，否则永远也不会有。
事件选择模型也是将监视socket状态的工作委托给系统，系统在适当的时候通过事件通知应用程序socket可以的操作。

除了同步工作方式外，还有一种叫异步工作方式
异步工作方式是不会阻塞的，因为是将io操作本身委托给系统，系统在io操作完成后通过回调例程或事件或完成包通知应用程序
异步工作方式有两种io模型和其对应，其实这两种模型是window是异步io的实现：
1）重叠模型
2）完成端口

重叠模型通过事件或回调例程通知应用程序io已经完成
完成端口模型比较复杂，完成端口本身其实是一个io完成包队列。
应用程序一般创建若干个线程用来监视完成端口，这些线程试图从完成端口移除一个完成包，如果有，移除成功，应用程序处理该完成包，否则应用程序监视完成端口的线程被阻塞。

select模型是从UNIX上的Berkeley Software Distribution(BSD)版本的套接字就实现了的，其它四种io模型windows发明的，在windows中完成端口和异步选择模型是使用比较广泛的，一般分别用于服务端和客户端开发。
这五种io模型设计还是比较巧妙的：三种选择模型很好解决了“同步非阻塞”模式编程的不足；重叠模型和完成端口是windows异步io的经典实现，不局限于网络io，对文件io同样适用。

说点题外话，socket的send完成仅仅是将数据（可能是部分）提交给系统，而不是已经发送到了网卡上，更不是已经发送到了接收端。所以要知道你的数据已经发送到了对方的应用层的唯一方法是，让对方给你发送一个应对包。
发送数据要注意，对应tcp，要防止发送和接收的乱序，对于发送，一般应该为每一个链接建立一个发送队列，采用类似nagle的算法启动数据发送。
一次发送可能是你提交数据的一部分，一定要当心，否则出问题没处找去。

㈣ 《程序员的算法趣题》pdf下载在线阅读，求百度网盘云资源

《程序员的算法趣题》（［ 日］ 增井敏克）电子书网盘下载免费在线阅读

资源链接：

链接：

书名：程序员的算法趣题

作者：［ 日］ 增井敏克

译者：绝云

豆瓣评分：7.6

出版社：人民邮电出版社

出版年份：2017-7

页数：312

内容简介：本书是一本解谜式的趣味算法书，从实际应用出发，通过趣味谜题的解谜过程，引导读者在愉悦中提升思维能力、掌握算法精髓。此外，本书作者在谜题解答上，通过算法的关键原理讲解，从思维细节入手，发掘启发性算法新解，并辅以Ruby、JavaScript等不同语言编写的源代码示例，使读者在算法思维与编程实践的分合之间，切实提高编程能力。 本书适合已经学习过排序、搜索等知名算法，并想要学习更多有趣算法以提升编程技巧、拓展程序设计思路的程序员，以及对挑战算法问题感兴趣、爱好解谜的程序员阅读。

作者简介：作者简介：

增井敏克

1979年生于奈良，毕业于大阪府立大学研究生院。增井IT工程师事务所代表、注册工程师（信息工程学方向）。从事旨在“将商务、数学和IT结合以正确、高效使用计算机”的技能提升指导、软件开发以及信息安全咨询等工作。掌握C/C++、C#、Java、PHP和Ruby等20多种编程语言。着作有《在家就能学会的安全基础》等。目前在面向IT工程师提供业务技能评估服务的平台CodeIQ上负责人气栏目“每周算法”的出题和评审工作。

译者简介：

绝云

毕业于清华软院。曾在日本创意公司KAYAC从事即时通信软件和手游的开发工作，现供职于蚂蚁金服，专攻数据可视化方向。译作有《图解简单算法》《自制编译器》等，曾参与《像外行一样思考，像专家一样实践（修订版）》的审校。

㈤ 《程序员的算法趣题》pdf下载在线阅读全文，求百度网盘云资源

《程序员的算法趣题》（［ 日］ 增井敏克）电子书网盘下载免费在线阅读

链接:

书名：程序员的算法趣题

作者：［ 日］ 增井敏克

译者：绝云

豆瓣评分：7.6

出版社：人民邮电出版社

出版年份：2017-7

页数：312

内容简介：

本书是一本解谜式的趣味算法书，从实际应用出发，通过趣味谜题的解谜过程，引导读者在愉悦中提升思维能力、掌握算法精髓。此外，本书作者在谜题解答上，通过算法的关键原理讲解，从思维细节入手，发掘启发性算法新解，并辅以Ruby、JavaScript等不同语言编写的源代码示例，使读者在算法思维与编程实践的分合之间，切实提高编程能力。 本书适合已经学习过排序、搜索等知名算法，并想要学习更多有趣算法以提升编程技巧、拓展程序设计思路的程序员，以及对挑战算法问题感兴趣、爱好解谜的程序员阅读。

作者简介：

增井敏克

1979年生于奈良，毕业于大阪府立大学研究生院。增井IT工程师事务所代表、注册工程师（信息工程学方向）。从事旨在“将商务、数学和IT结合以正确、高效使用计算机”的技能提升指导、软件开发以及信息安全咨询等工作。掌握C/C++、C#、Java、PHP和Ruby等20多种编程语言。着作有《在家就能学会的安全基础》等。目前在面向IT工程师提供业务技能评估服务的平台CodeIQ上负责人气栏目“每周算法”的出题和评审工作。

绝云

毕业于清华软院。曾在日本创意公司KAYAC从事即时通信软件和手游的开发工作，现供职于蚂蚁金服，专攻数据可视化方向。译作有《图解简单算法》《自制编译器》等，曾参与《像外行一样思考，像专家一样实践（修订版）》的审校。

㈥ 高一数学必修3 第一章 算法初步里包含的程序软件

高一就学了啊。
如果要看的话，可以看下谭浩强的C语言程序设计。
我先帖一些出来给你看啊。

C语言版本

目前最流行的C语言有以下几种：
·Microsoft C 或称 MS C
·Borland Turbo C 或称 Turbo C
·AT&T C
这些C语言版本不仅实现了ANSI C标准，而且在此基础上各自作了一些扩充，使之更加方便、完美。
面向对象的程序设计语言
在C的基础上，一九八三年又由贝尔实验室的Bjarne Strou-strup推出了C++。 C++进一步扩充和完善了C语言，成为一种面向 对象的程序设计语言。C++目前流行的最新版本是Borland C++4.5,Symantec C++6.1,和Microsoft VisualC++ 2.0。C++提出了一些更为深入的概念，它所支持的这些面向对象的概念容易将问题空间直接地映射到程序空间，为程序员提供了一种与传统结构程序设计不同的思维方式和编程方法。因而也增加了整个语言的复杂性，掌握起来有一定难度。

C和C＋＋

但是，C是C++的基础，C++语言和C语言在很多方面是兼容的。因此，掌握了C语言，再进一步学习C++就能以一种熟悉的语法来学习面向对象的语言，从而达到事半功倍的目的。

C源程序的结构特点

为了说明C语言源程序结构的特点，先看以下几个程序。这几个程 序由简到难，表现了C语言源程序在组成结构上的特点。虽然有关内容还未介绍，但可从这些例子中了解到组成一个C源程序的基本部分和书写格式。main()
{printf("c语言世界www.vcok.com，您好！\n");
}
main是主函数的函数名，表示这是一个主函数。每一个C源程序都必须有，且只能有一个主函数(main函数)。函数调用语句，printf函数的功能是把要输出的内容送到显示器去显示。printf函数是一个由系统定义的标准函数，可在程序中直接调用。
#include
#include
main()
{
double x,s;
printf("input number:\n");
scanf("%lf",&x);
s=sin(x);
printf("sine of %lf is %lf\n",x,s);
}

每行注释

include称为文件包含命令扩展名为.h的文件也称为头文件或首部文件
定义两个实数变量，以被后面程序使用
显示提示信息
从键盘获得一个实数x
求x的正弦，并把它赋给变量s
显示程序运算结果
main函数结束

程序的功能是从键盘输入一个数x，求x的正弦值，然后输出结果。在main()之前的两行称为预处理命令(详见后面)。预处理命令还有其它几种，这里的include 称为文件包含命令，其意义是把尖括号""或引号<>内指定的文件包含到本程序来，成为本程序的一部分。被包含的文件通常是由系统提供的，其扩展名为.h。因此也称为头文件或首部文件。C语言的头文件中包括了各个标准库函数的函数原型。因此，凡是在程序中调用一个库函数时，都必须包含该函数原型所在的头文件。在本例中，使用了三个库函数：输入函数scanf，正弦函数sin,输出函数printf。sin函数是数学函数，其头文件为math.h文件，因此在程序的主函数前用include命令包含了math.h。scanf和printf是标准输入输出函数，其头文件为stdio.h，在主函数前也用include命令包含了stdio.h文件。

需要说明的是，C语言规定对scanf和printf这两个函数可以省去对其头文件的包含命令。所以在本例中也可以删去第二行的包含命令#include。同样，在例1.1中使用了printf函数，也省略了包含命令。

在例题中的主函数体中又分为两部分，一部分为说明部分，另一部分执行部分。说明是指变量的类型说明。例题中未使用任何变量，因此无说明部分。C语言规定，源程序中所有用到的变量都必须先说明，后使用，否则将会出错。这一点是编译型高级程序设计语言的一个特点，与解释型的BASIC语言是不同的。说明部分是C源程序结构中很重要的组成部分。本例中使用了两个变量x，s，用来表示输入的自变量和sin函数值。由于sin函数要求这两个量必须是双精度浮点型，故用类型说明符double来说明这两个变量。说明部分后的四行为执行部分或称为执行语句部分，用以完成程序的功能。执行部分的第一行是输出语句，调用printf函数在显示器上输出提示字符串，请操作人员输入自变量x的值。第二行为输入语句，调用scanf函数，接受键盘上输入的数并存入变量x中。第三行是调用sin函数并把函数值送到变量s中。第四行是用printf 函数输出变量s的值，即x的正弦值。程序结束。

printf("input number:\n");
scanf("%lf",'C10F10&x);
s=sin(x);
printf("sine of %lf is %lf\n",'C10F10x,s);
运行本程序时，首先在显示器屏幕上给出提示串input number，这是由执行部分的第一行完成的。用户在提示下从键盘上键入某一数，如5，按下回车键，接着在屏幕上给出计算结果。

输入和输出函数

在前两个例子中用到了输入和输出函数scanf和 printf，在第三章中我们要详细介绍。这里我们先简单介绍一下它们的格式，以便下面使用。scanf和 printf这两个函数分别称为格式输入函数和格式输出函数。其意义是按指定的格式输入输出值。因此，这两个函数在括号中的参数表都由以下两部分组成： “格式控制串”，参数表 格式控制串是一个字符串，必须用双引号括起来，它表示了输入输出量的数据类型。各种类型的格式表示法可参阅第三章。在printf函数中还可以在格式控制串内出现非格式控制字符，这时在显示屏幕上将原文照印。参数表中给出了输入或输出的量。当有多个量时，用逗号间隔。例如：
printf("sine of %lf is %lf\n",x,s);
其中%lf为格式字符，表示按双精度浮点数处理。它在格式串中两次现，对应了x和s两个变量。其余字符为非格式字符则照原样输出在屏幕上
int max(int a,int b);
main(){
int x,y,z;
printf("input two numbers:\n");scanf("%d%d",&x,&y);
z=max(x,y);
printf("maxmum=%d",z);
}
int max(int a,int b){
if(a>b)return a;else return b;
}
此函数的功能是输入两个整数，输出其中的大数。
/*函数说明*/
/*主函数*/
/*变量说明*/
/*输入x,y值*/
/*调用max函数*/
/*输出*/
/*定义max函数*/
/*把结果返回主调函数*/
上面例中程序的功能是由用户输入两个整数，程序执行后输出其中较大的数。本程序由两个函数组成，主函数和max 函数。函数之间是并列关系。可从主函数中调用其它函数。max 函数的功能是比较两个数，然后把较大的数返回给主函数。max 函数是一个用户自定义函数。因此在主函数中要给出说明(程序第三行)。可见，在程序的说明部分中，不仅可以有变量说明，还可以有函数说明。关于函数的详细内容将在第五章介绍。在程序的每行后用/*和*/括起来的内容为注释部分，程序不执行注释部分。

上例中程序的执行过程是，首先在屏幕上显示提示串，请用户输入两个数，回车后由scanf函数语句接收这两个数送入变量x,y中，然后调用max函数，并把x,y 的值传送给max函数的参数a,b。在max函数中比较a,b的大小，把大者返回给主函数的变量z，最后在屏幕上输出z的值。

C源程序的结构特点

1.一个C语言源程序可以由一个或多个源文件组成。

2.每个源文件可由一个或多个函数组成。

3.一个源程序不论由多少个文件组成，都有一个且只能有一个main函数，即主函数。

4.源程序中可以有预处理命令(include 命令仅为其中的一种)，预处理命令通常应放在源文件或源程序的最前面。

5.每一个说明，每一个语句都必须以分号结尾。但预处理命令，函数头和花括号“}”之后不能加分号。

6.标识符，关键字之间必须至少加一个空格以示间隔。若已有明显的间隔符，也可不再加空格来间隔。

书写程序时应遵循的规则

从书写清晰，便于阅读，理解，维护的

㈦ 快速排序算法原理与实现

快速排序的基本思想就是从一个数组中任意挑选一个元素（通常来说会选择最左边的元素）作为中轴元素，将剩下的元素以中轴元素作为比较的标准，将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边。

然后以当前中轴元素的位置为界，将左半部分子数组和右半部分子数组看成两个新的数组，重复上述操作，直到子数组的元素个数小于等于1（因为一个元素的数组必定是有序的）。

以下的代码中会常常使用交换数组中两个元素值的Swap方法，其代码如下

publicstaticvoidSwap(int[] A, inti, intj){

inttmp;

tmp = A[i];

A[i] = A[j];

A[j] = tmp;

(7)程序员算法每日一练第三题扩展阅读：

快速排序算法 的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一 部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直 到所有要进行排序的数据变为有序为止。

定义两个变量low和high，将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1，接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。

定义一个变量key，接下来以key的取值为基准将数组A划分为左右两个部分，通 常，key值为要进行排序序列的第一个元素值。第一次的取值为A[0]，以后毎次取值由要划 分序列的起始元素决定。

从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。

如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。

重复步骤(3) (4)，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high]，其中，pos下标所对应的数组元素的值就是进行划分的基准值key，所以在划分结束时还要将下标为pos的数组元素赋值 为 key。

㈧ 程序员如何学好算法

一.基本算法:

枚举. (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)

三.数据结构.

线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)

静态二叉检索树. (poj2482,poj2352)

树状树组(poj1195,poj3321)

RMQ. (poj3264,poj3368)

并查集的高级应用. (poj1703,2492)

KMP算法. (poj1961,poj2406)

四.搜索

最优化剪枝和可行性剪枝

搜索的技巧和优化 (poj3411,poj1724)

记忆化搜索(poj3373,poj1691)

五.动态规划

较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
记录状态的动态规划. (POJ3254,poj2411,poj1185)

树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
随机化算法(poj3318,poj2454)
杂题(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.

坐标离散化.

扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多边形的内核(半平面交)(poj3130,poj3335)

几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级（regional中等难度）:
一.基本算法要求:

代码快速写成,精简但不失风格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保证正确性和高效性. poj3434

二.图算法:

度限制最小生成树和第K最短路. (poj1639)

最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最优比率生成树. (poj2728)

最小树形图(poj3164)

次小生成树.

无向图、有向图的最小环

三.数据结构.

trie图的建立和应用. (poj2778)

LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法(RMQ+dfs)).(poj1330)
双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)
左偏树(可合并堆).

后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)
四.搜索

较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)
四边形不等式理论.

较难的状态DP(poj3133)

六.数学

组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.

半平面求交(poj3384,poj2540)

可视图的建立(poj2966)

点集最小圆覆盖.

对踵点(poj2079)

㈨ C语言算法

呵呵，先说说我吧，我买的书给你一个版本的！而且买书时间差不多不超过一个月，现在是高二学生（马上要高三了），学起C语言并没感觉到吃力！而我的一个同学就不同了，我们一起看的我都成了他老师了！当我看他看的时候才发现原因，他的速度是我看的3倍。这可能就是问题的所在了！建议楼主从书的目录开始看，一字一句一个都不少，你会发现结果截然不同！就你所说的所运用的数学知识大多都是逻辑，如果有条件的话希望楼主恶补一下高中数学！但还是那句话，逻辑是程序的灵魂，成绩并不能说明着什么！

如果可以的话希望楼主能买“数据结构”之类的书，对提高逻辑以及C语言有很大的帮助！

这本书的编辑是“谭浩强”教授，是中国响当当的人物，开始我也认为排序不好，但最后发现前面的每一个字都具有非凡的意义！~

你说的那个程序数太大了，我给改为1*2*3*....*10结果：如图

楼主还是要认真的读读那本书，我也不知道更好的办法了！

㈩ 小白，想入门程序员，应该从什么开始学，顺序是什么

小白想要成为程序员，首选是选择一门合适的语言，比如说：Python、Java、C、C++、GO语言等；其次，选择合适的学习方式，比如培训，周末班、脱产班还是网络班。
如果完全没有编程基础，建议大家学习Python，Python入门简单、语法清晰、通俗易懂，非常适合零基础人员。