Browsed by
Month: September 2014

“复杂” 读书笔记 (美 梅拉尼 米歇尔)

“复杂” 读书笔记 (美 梅拉尼 米歇尔)

序章: 还原论,即整体=部分之和这一观点是无法解释存在的复杂系统的,如,人的思维,天气。    复杂的系统是由简单的系统产生的,需要用控制论,协同学,系统科学,复杂系统科学 来解释 第一章:复杂性是什么 行为最简单的个体,行军蚁,在当其个体数目达到很大的一个数量的时候(这个数量能用定量的形式来给出么?),会产生复杂的智能行为,这种现象产生的智能成为 集体智能 什么是复杂系统 定义: 是由大量组分组成的网络,不存在中央控制,通过简单的运作规则产生出复杂的集体行为和复杂的信息处理,并通过学习和进化产生适应性 希尔伯特问题 : 哥德尔猜想  不完备理论

POJ 1860 Currency Exchange

POJ 1860 Currency Exchange

Currency Exchange Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 20346 Accepted: 7298 Description Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point…

Read More Read More

单源最短路分析及算法实现

单源最短路分析及算法实现

最短路径的理解性解释:Va 到 Vb 的最短路的意义是 在一个带权图中,从节点Va到节点Vb的权值总和最小的路径 就是Va 到 Vb的最短路,这个权值可以是距离 时间 等各种量 理解最短路径首先要理解什么是最优子结构  最优子结构是在各种动态规划,贪心以及最短路算法中都很关键的一个结构。  最优子结构的意思就是,问题局部的最优解包含在全局的最优解之中,这样才能把问题分成较小的问题先进行处理。 可以通过反证法证明,最短路问题是最优子结构,方法详见 算法导论第三版 P375 在计算最短路之前,还要考虑一个特殊情况,如果在图中存在负权值的边,就可能有一种比较特殊的情况了: 如果 图中存在负权值的边的话但不存在和的权值为负的环,那么 每一个路径的最短距离都可以精确求出,没有问题,不过,如果图中存在和为负权值的环,最短路就没有意义了  因为 总可以通过经过完整的一次环,来得到更小的一个权值 ,理论上 这个最短路径的大小为  -∞ 求最短路的某些算法假设输入的边权值全为非负 如 Dijkstra算法,而还有一些算法只要没有负权值的环就可以 如 Bellman Ford算法 ,如果存在负权值的环的环也可以通过算法报告出来 先试试如何应用这个算法,再继续研究算法的正确性;                             //参考POJ 1860  

POJ 题目分类整理 [转]

POJ 题目分类整理 [转]

OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串 (poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书 page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: 1.加法原理和乘法原理. 2.排列组合. 3.递推关系. (POJ3252,poj1850,poj1019,poj1942) (2)数论. 1.素数与整除问题 2.进制位. 3.同余模运算. (poj2635, poj3292,poj1845,poj2115) (3)计算方法. 1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122) 七.计算几何学. (1)几何公式. (2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039) (3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交) (poj1408,poj1584) (4)凸包. (poj2187,poj1113) 中级: 一.基本算法: (1)C++的标准模版库的应用. (poj3096,poj3007) (2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706) 二.图算法:…

Read More Read More

POJ 1018 DP入门

POJ 1018 DP入门

http://blog.csdn.net/xiaoxiaoluo/article/details/7787168      代码完全参考这个blog  刚开始学习DP真是很艰难阿,  题目如下:   We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices. By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all…

Read More Read More

WordPress 源码学习 #03

WordPress 源码学习 #03

继续学习WP源码 每天都保证2h来学习它  这里先来说一下 注释里面 的那个 @**** 使用 @号是一种标准的注释格式,是对这个程序的功能的一个很清晰的说明和解释 ,在自己写PHP代码的时候也要会用这种注释。 下面继续  version.php中,也没有什么东西,只是一些对版本变量的定义和一些必要的配置 ,语言 以及manifest ver之类的  为了格式一致,这里也放上它的代码 <?php /** * The WordPress version string * * @global string $wp_version */ $wp_version = ‘3.4.1’; /** * Holds the WordPress DB revision, increments when changes are made to the WordPress DB schema. * * @global int $wp_db_version */ $wp_db_version = 21115; /** * Holds the TinyMCE version * * @global string $tinymce_version */ $tinymce_version = ‘349-20805’; /** * Holds the cache manifest version *…

Read More Read More

WordPress 源码学习 #02

WordPress 源码学习 #02

继续研究WP的源码 ,在继续之前解释一下昨天的wp-config里面的前面几个常量的定义  由于我用的是SAE 所以 数据库名 ,用户名 神码的都是SAE预设的 常量 就不用我自己去起名了 ,好了我们继续  这一期开始就要看wp-settings.php这个文件了 先上代码: <?php /** * Used to set up and fix common variables and include * the WordPress procedural and class library. * * Allows for some configuration in wp-config.php (see default-constants.php) * * @internal This file must be parsable by PHP4. * * @modified Elmer Zhang <[email protected]> * @package WordPress */ /** * Stores the location of the WordPress directory of functions, classes, and core content. * * @since…

Read More Read More