ITeye博客

Triforce

googya · 共 65 篇文章

八枚银币

說明 現有八枚銀幣a b c d e f g h,已知其中一枚是假幣,其重量不同於真幣,但不知是較輕或較重,如何使用天平以最少的比較次數,決定出哪枚是假幣,並得知假幣比真幣較輕或較重。 解法 單就求假幣的問題是不難,但問題限制使用最少的比較次數,所以我們不能以單純的迴圈比較來求解,我們可以使用決策樹(decision tree),使用分析與樹狀圖來協助求解。 一個簡單的狀況是這樣的,我們比較a+b+c與d+e+f ,如果相等,則假幣必是g或h,我們先比較g或h哪個較重,如果g較重,再與a比較(a是真幣),如果g等於a,則g為真幣,則h為假幣,由於h比g輕而 g是真幣,則h假幣的重量比真幣輕。…

2009-09-29 14:46 · 算法系列 · 评论(20)

8皇后

西洋棋中的皇后可以直線前進,吃掉遇到的所有棋子,如果棋盤上有八個皇后,則這八個皇后如何相安無事的放置在棋盤上,1970年與1971年, E.W.Dijkstra與N.Wirth曾經用這個問題來講解程式設計之技巧。 解法 關於棋盤的問題,都可以用遞迴求解,然而如何減少遞迴的次數?在八個皇后的問題中,不必要所有的格子都檢查過,例如若某列檢查過,該該列的其它格子就不用再檢查了,這個方法稱為分支修剪。 八個皇后 所以檢查時,先判斷是否在已放置皇后的可行進方向上,如果沒有再行放置下一個皇后,如此就可大大減少遞迴的次數,例如以下為修剪過後的遞迴檢查行進路徑: 八個皇后 八個皇后的話,會有92個解答,如果…

2009-09-28 19:11 · 算法系列 · 评论(0)

老鼠走迷宫

说明 老鼠走迷宫是递回求解的基本题型,我们在二维阵列中使用2表示迷宫墙壁,使用1来表示老鼠的行走路径,试以程式求出由入口至出口的路径。 解法 老鼠的走法有上、左、下、右四个方向,在每前进一格之后就选一个方向前进,无法前进时退回选择下一个可前进方向,如此在阵列中依序测试四个方向,直到走到出口为止,这是递回的基本题,请直接看代码应就可以理解。 class Point attr_accessor :x,:y def initialize(x,y) @x=x @y=y end end class Maze def initialize(maze,end_1) @maze=maze @end=end_…

2009-09-27 17:12 · 算法系列 · 评论(0)

Pascal三角形

Pascal三角形基本上就是在解 nCr ,因為三角形上的每一個數字各對應一個nCr,其中 n 為 row,而 r 為 column,如下: 0C0 1C0 1C1 2C0 2C1 2C2 3C0 3C1 3C2 3C3 4C0 4C1 4C2 4C3 4C4 Pascal三角形中的 nCr 可以使用以下這個公式來計算,以避免階乘運算時的數值溢位: nCr = * nCr-1 nC0 = 1 def combi(n,r) p=1 for i in 1..r p=p*(n-i+1)/i end p end def paint() nN=12 for n in 0..nN for r in 0.…

2009-09-26 16:03 · 评论(0)

斐波那契数列

說明 Fibonacci為1200年代的歐洲數學家,在他的著作中曾經提到:「若有一隻免子每個月生一隻小免子,一個月後小免子也開始生產。起初只有一隻免子,一個月後就有兩隻免子,二個月後有三隻免子,三個月後有五隻免子(小免子投入生產)......」。 如果不太理解這個例子的話,舉個圖就知道了,注意新生的小免子需一個月成長期才會投入生產,類似的道理也可以用於植物的生長,這就是Fibonacci數列,一般習慣稱之為費氏數列,例如以下: 1、1 、2、3、5、8、13、21、34、55、89...... def fibonacci(n) unless n>=0 puts "请输入一个正数!" end …

2009-09-26 15:32 · 算法系列 · 评论(0)

汉诺塔

关于汉诺塔大家应该很熟悉吧。 河內之塔(Towers of Hanoi)是法國人M.Claus(Lucas)於1883年從泰國帶至法國的,河內為越戰時北越的首都,即現在的胡志明市;1883年法國數學家 Edouard Lucas曾提及這個故事,據說創世紀時Benares有一座波羅教塔,是由三支鑽石棒(Pag)所支撐,開始時神在第一根棒上放置64個由上至下依由小至大排列的金盤(Disc),並命令僧侶將所有的金盤從第一根石棒移至第三根石棒,且搬運過程中遵守大盤子在小盤子之下的原則,若每日僅搬一個盤子,則當盤子全數搬運完畢之時,此塔將毀損,而也就是世界末日來臨之時。 写个简单的递归算法。 def …

2009-09-26 15:09 · 算法系列 · 评论(0)

ruby中的字符编码

长期以来,都被Ruby中的字符乱码所困惑,但是一直高估了解决乱码出现的难度,所以一直不敢去真正的理解,导致问题一直存在。看来逃避不是办法,要勇敢的去面对,是解决该问题的时候了! 最近在看Leonard ricbardson &sam ruby合著的《RESTful web services》,很赞同书里面的观点。同时这本书同时给了我很多的启发,如何去了解以及使用那些提供了API的网站,虽然现在只能做些很小的客户端,仍然很有成就感。毕竟从不懂,到会用,到可以编写简单的客户端进步还是有点的。 言归正传。 看到 Ruby:rest-open-uri and net/http这一节的时候,看到书中举…

2009-09-24 16:15 · JRuby&Ruby · 评论(0)

js变量

学习Ruby的时候,感觉Ruby的变量有点特别,但是理解多了之后觉得其实Ruby的变量的环境还是设计得挺好的,觉得很自然。最近在学习JavaScript,它的原型继承、闭包之类的东西不难理解,尤其是学习了Ruby之后,最使我郁闷的是JS的变量,可能JS的变量机制我还没有理解清楚,我不晓得以后我还能不能理解清楚,我感觉JS的变量真的很麻烦! /*var msg="global"; function show(){ var msg; msg="local"; alert(msg); } show(); alert(msg);*/ /*void function(){ var t; t="hell…

2009-09-16 16:51 · javascript · 评论(0)

Java的内部类与Ruby的内部类的区别

今天经过 night-stalker 的提醒,突然意识到Ruby的内部类和Java的内部类存在不少区别。其中我发现最大的区别是: 在Java中,内部类方法可以访问其自身的数据字段,也能够访问创建它的外部类的数据字段。在Java中内部类对象要有一个银隐含引用,指向创建它的对象。 而在Ruby中,恰好相反。外部类的方法可以访问内部类的字段,但是反过来却不行。 若单独的使用,只要熟悉相应的语法规则,不会出现问题。但是要在JRuby中的时候,就有可能出现问题,因为有2中截然不同的方式实现内部类,这时可能会出现乱子! module MyPackage module InnerPacage class …

2009-08-23 16:06 · JRuby&Ruby · 评论(0)

impl与内部类

# To change this template, choose Tools | Templates # and open the template in the editor. #puts "Hello World" include Java include_class javax.swing.JFrame include_class javax.swing.JPanel include_class javax.swing.JButton include_class java.awt.event.ActionListener include_class javax.swing.JOpti…

2009-08-23 11:20 · JRuby&Ruby · 评论(2)

JRuby处理按钮点击事件

# To change this template, choose Tools | Templates # and open the template in the editor. #puts "Hello World" include Java include_class javax.swing.JFrame include_class javax.swing.JPanel include_class javax.swing.JButton include_class java.awt.event.ActionListener include_class javax.swing.JOpti…

2009-08-23 08:15 · JRuby&Ruby · 评论(0)

用JRuby写个小MIDI

include Java include_class javax.sound.midi.MidiSystem include_class javax.swing.JFrame include_class java.awt.event.KeyListener # 准备合成 hecheng = MidiSystem.synthesizer hecheng.open channel = hecheng.channels[0] # 接收按键的frame midi_frame = JFrame.new("Music Frame") midi_frame.set_size 200, 200 midi_f…

2009-08-21 10:47 · JRuby&Ruby · 评论(0)

简单比较IKAnalyzer和je-analysis中文分词包

最近在突然对全文信息检索有了兴趣,本来嘛,以前是学信息管理的, 对全文信息检索有一定的了解,不过只是停留在理论上的,具体的如何操作没有什么概念,现在有一点空闲时间,来研究研究。 研究全文信息检索的,对于Lucene应该多少有一点的了解吧。当然它自己本身有分词的功能,但主要是在英文环境下面,所以对中文的支持不是好,但是它提供了一个接口,可以让其他的分词包能使用。下面简单的比较一下ikanalyzer和je-analysis这两个中文分词包,主要是它们对中文分词的效果的比较。下面是一段代码 String text = "IK Analyzer是一个结合词典分词和文法分词的中文分词开源工具包。它使…

2009-07-22 13:16 · 搜索引擎 · 评论(0)

算法之贪心

def greedySelector(n,a,b) b[0]=true j=0 for i in 1..n-1 if(a[i][0]&gt;=a[j][1]) b[i]=true j=i else a[i]=false end end c=b.select{|x|x==true}.size end a=[[1,23],[12,28],[25,35],[27,80],[36,50]] p a.sort!{ |x,y|x[1]<=>y[1} b=[] n=a.size p greedySelector(n,a,b) 活动安排问题是可以用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列…

2009-06-30 09:53 · 算法系列 · 评论(0)

有关microsoft的奇怪问题

这几天在我的机器上microsoft一直登不上去,我一直以为是微软的服务器出现问题,或者是被屏蔽了,过一阵子就好了。过了一阵子确实好了,在别人的机器上可以登录到微软网站,我也能登上live,msn,bing等,但是一直不能登上microsoft.com,不知道为什么.在火狐中,出现这样的提示: Server not found Firefox can't find the server at www.microsoft.com. * Check the address for typing errors such as ww.example.com instead of www.exampl…

2009-06-27 11:31 · 评论(3)