[算法]Fibonacci数列

dskongenius 发表于 2007/12/20 22:38:07

快速Fibonacci数算法(Fib_Quick)
在非递归的Fibonacci程序中，在算f(n)的时候最多不超过n-2个加法，请编写一个更快的程序，或许可以用乘法。如果每一个乘法用m单位时间，每一个加法用p单位时间，于是非递归的写法因为最多有n-2个加法，因此最多用(n-2)×p的时间。请问，改良程序要用多少时间？假设只考虑加法和乘法。

解答：
考虑：
f(n) = f(n-1) + f(n-2) = 1×f(n-1) + 1×f(n-2)
f(n-1) = f(n-1) = 1×f(n-1) + 0×f(n-2)
可以用矩阵乘法来表示两个式子：
|f(n)   | = | 1 1 | ×|f(n-1)|
|f(n-1)|  

 [算法]判断点是否在多边形内的算法

dskongenius 发表于 2007/12/20 1:08:09

判断点是否在多边形内的算法如下。
以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，
考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多
边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的
交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能计算一个
，有些情况下交点不应被计算（你自己画个图就明白了）；如果L和多边形的一条边重合，
这条边应该被忽略不计。为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于
多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边
上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判断P属
于多边行。由此得出算法的伪代码如下：

1. count ← 0;
2. 以P为端点，作从右向左的射线L; 
3, for 多边形的每条边s<

 [算法]关于算法学习的入门书本

dskongenius 发表于 2007/12/20 0:30:49

关于算法学习的入门书本

1. [CLRS]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliffor
d Stein. Introduction to Algorithms. The MIT Press and McGraw-Hill, second edition, 2001. 国内有高教版影印。也有中文版。这本书一出来就取代了做了20年的经典教材[AHU]。提供了初级到中级课程的材料，而且chapter notes指引了进一步阅读的方向。四个作者都极猛。

2. [KT]Jon Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley, 2005.国
内有清华影印版。
观点很新的书。两个作者都在Cornell教了好多年的算法课，而且在纯理论之外都有所侧重
。习题非常之精彩，而且大部分都是Cornell这些年的作业或者习题。

清华Yao的课就是用上面两本教材，课文是[CLRS]，[K

阅读全文(1908) | 回复(0) | 编辑 | 精华 | 删除

 [五分钟热度][领会]清华校长送给毕业生的五句话　

dskongenius 发表于 2007/12/17 22:55:08

　 “未来的世界：方向比努力重要，能力比知识重要，健康比成绩重要，生活比文凭重要，情商比智商重要！ ”
                                       ——清华大学校长留给毕业生的一段话

    方向比努力重要。

      现在是讲究绩效的时代，公司、企业、政府，需要的是有能力且能与企业方向共同发展的人，而不是一味努力但却南辕北辙的人。自己适合哪些行业，哪些职业，有很

阅读全文(2234) | 回复(2) | 编辑 | 精华 | 删除

 [五分钟热度]执着、勤奋-年轻院士走过的路　

dskongenius 发表于 2007/12/14 19:19:19

最近，张运教授以其心内科学的杰出成就，当选为中国工程院院士，实现了山东省医药卫生界院士零的突破，而且，以他49岁的年龄，成为我省最年轻的院士。当掌声响起来，当荣誉和鲜花涌向面前，张运教授一如既往，坦然、平和地面对这一切。回顾他走过的路，我们会看到沟沟坎坎之后的一个个闪光点。上帝并不格外青睐于他，而每一次，他都凭着一股永不服输的力量，死死扼住命运的咽喉，奏响自己的强者之音。 

　　小工厂里的“博士” 

　　1952年，张运出生在聊城的一个医生家庭。幼年的他就展露了不凡的才华，不仅学习始终遥遥领先，而且乒乓球打得好，参加全省普通话比赛还得了第一名。然而在那场“史无前例”的文化大革命中，父母被打成“反动学术权威”，关牛棚、挨批斗，作为“狗崽子”的他，竟也被戴高帽子游校示众，受尽冷眼与歧视。为了找工作，他曾经干过泥瓦匠、编过笼箩、拉过钢筋，他曾经有幸找到一份好工作——在糖果厂包糖纸，第二天由于别人举报他是“狗崽子”而被辞退。那时，张运最大的愿望就是能够成为一名正式工人，有时梦见自己如愿以偿，“比今天当了院士都高兴”。 

阅读全文(1551) | 回复(0) | 编辑 | 精华 | 删除

 [数据挖掘]人工智能机器学习数据挖掘著名会议（转自述绝挖掘青年）

dskongenius 发表于 2007/12/14 12:07:30

转自论坛http://www.ieee.org.cn/dispbbs.asp?BoardID=62&replyID=31567&id=29962&star=1&skin=0
作者好像是南大周志华老师　 我知道的几个人工智能会议(一流)
下面同分的按字母序排列: 

阅读全文(2095) | 回复(0) | 编辑 | 精华 | 删除

 [数据挖掘]数据挖掘经典算法（转自数据挖掘青年）

dskongenius 发表于 2007/12/14 12:05:53

Classification
==============  #1. C4.5 Quinlan, J. R. 1993. C4.5: Programs for Machine Learning.
Morgan Kaufmann Publishers Inc.
 #2. CART L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and
Regression Trees. Wadsworth, Belmont, CA, 1984.  #3. K Nearest 

阅读全文(1707) | 回复(0) | 编辑 | 精华 | 删除

 [硬件OS]微处理器

dskongenius 发表于 2007/12/13 22:27:51

　转自百度百科 微处理器 目录·简介
·初期CPU
·从386到奔腾
·多核时代

阅读全文(3472) | 回复(2) | 编辑 | 精华 | 删除

 [硬件OS]读核日记(转)　

dskongenius 发表于 2007/12/13 22:20:30

　读核日记(转)
读核日记(一) 本文出自:http://os.silversand.net 作者: sunmoon (2001-08-31 10:00:00) 今天开始我的读核罹难记.第一次读内核,整整上学时的考试前.胡里胡涂的就过去了,没甚收获.这次我发誓要彻底读一次. 面对近50 m 的源码,困惑是难免的所以我决定先从大面上把握,再在某一些具体的点上切入.这样一来linux 的启动过程便十分重要,因此我先用dmesg命令察看一下linux启动时打出的消息.(我想源文件应在/usr/src/linux/init/main.c中) 内核的启动最后是到 start_kernel ( in /init/main.c )也就是说启动的过程是从 head.S ( arch/i386/boot/ ) 一直运行到 main.c(start_kernel) .它的作用是完成开机后的设置与内核的初始化,然后,系统究竟入一个无限的循环中等待用户的输入,调用fork来

阅读全文(4170) | 回复(0) | 编辑 | 精华 | 删除

 [美文美图]《时代》杂志评出2007年十大科学发现(组图)

dskongenius 发表于 2007/12/12 15:18:16

新浪科技讯 北京时间12月11日消息，美国《时代》杂志最近评出了2007年十大科学发现，美国及日本科学家在干细胞研究方面获得的突破位居榜首，而今年6月内蒙古确认发现当今世界上最大似鸟恐龙化石，也入选这一榜单，位列第7位。 　　以下为《时代》杂志评出的2007年十大科学发现： 　　1. 干细胞研究获得突破

阅读全文(2319) | 回复(2) | 编辑 | 精华 | 删除