[转]程序员能力矩阵 Programmer Competency Matrix

 c++, linux, 程序员, 算法, 网络  [转]程序员能力矩阵 Programmer Competency Matrix已关闭评论
8月 192012
 

原文地址

http://static.icybear.net/[CN]Programmer%20competency%20matrix.htm

[译文]程序员能力矩阵 Programmer Competency Matrix

注意:每个层次的知识都是渐增的,位于层次n,也蕴涵了你需了解所有低于层次n的知识。

计算机科学 Computer Science

2n (Level 0)
n2 (Level 1)
n (Level 2)
log(n) (Level 3)
Comments

数据结构
不知道数组和链表的差异
能够解释和使用数组,链[……]

继续阅读

[转]约瑟夫问题的数学方法

 算法  [转]约瑟夫问题的数学方法已关闭评论
7月 202009
 

直觉一直告诉我约瑟夫问题当报数长度固定的时候有递推公式,可惜我太笨,一直推不出来,今天终于在网上看到了,转载一下~~~

1.问题描述:n个人(编号1~n),从1开始报数,报到m的退出,剩下的人继续从1开始报数。按顺序输出列者编号。数学解法复杂度:O(n)

下面的代码摘自雨中飞燕博客,这个公式推的太牛了,我还没看懂。。。

#include <stdio.h>
#include <conio.h>
int main( void )
{
     int n, i = 0, m, p;
   &n[……]

继续阅读

关于用Dijkstra算法算最长路

 算法  关于用Dijkstra算法算最长路已关闭评论
6月 232009
 

之前做实验的时候想用Dijkstra算法来算DAG(有向无回路图)且边权不为负的单源最长路,发现单纯地改不等号方向的话,邻接矩阵输进去以后出来的答案是错的。稍微想了一下,终于想明白了。

Dijkstra算法的大致思想是每次选择距离源点最近的结点加入,然后更新其它结点到源点的距离,直到所有点都被加入为止。当每次选择最短的路改为每次选择最长路的时候,出现了一个问题,那就是不能保证现在加入的结点以后是否会被更新而使得到源点的距离变得更长。例如这次加入结点u,最长路为10,下次有可能加入一个结点v,使得u通过v到源点的距离大于10,但由于u在之前已经被加入到集合中,无法再更新,导致结果是不正确的。

那[……]

继续阅读

骑士周游问题的感想

 算法  骑士周游问题的感想已关闭评论
6月 232009
 

最近算法课做了个骑士周游问题的实验,现在谈一下我的看法。

打分(或者叫预读2步的方法)可以看作是一种对回溯的搜索顺序进行改变的优化手段和技巧,但类优化手段只是把有可能是解的分支先走而已,并没有做到真正的剪枝,没办法保证先走的分支是有解的,算法的复杂度并没有降低;这样会造成一种现象,可能很大的上百的棋盘可以很快算出来,但有一些几十乘几十的棋盘会算不出来,刚好每次都先不走有解的分支,这个现象是这种改变搜索顺序的手段所无法避免的问题,无法保证对于每个棋盘,无论棋盘大小,先选择的分支是有解的。

更有效的办法是换一个思路,用分治法来解决,试想我们假如已经知道了8×8解,是否可以用48×8的解构[……]

继续阅读

6月 232009
 
昨晚想起叉积,竟然没印象了,在网上看了一下,转载出来,BS自己一下~

向量积 a x b = (^n) * |a| * |b| * sin<a, b>, 其中^n是同时垂直于a/b且符合右手定则的单位向量。
若已知向量a = (ax, ay, az), b = (bx, by, bz);
则 a x b = (ay * bz – by * az, az * bx – ax * bz, ax * by – ay * bx);
可以把i, j, k和a,b的坐标分别循环写成一行如下:
i   ~~~~   j   ~~~[……]

继续阅读