查看完整版本: 2008-03-17 测试题(00002)

2008-03-17 测试题(00002)

我认为我们的第一期非常成功，谢谢大家热情的参与。有大家的支持，我们的RC一定能红火起来。目前还有后续工作要做，就是，我希望我们有能力的会员能对第一期各位的答案做评论，给（可能）需要帮助的同学，提供指点。我们的目的不仅仅让大家来答题，还希望通过这种方式让别人来帮助(指点)你，这也是我认为最快的学习方式。自愿者，有吗？报名，直接给我站内短信。或者 加我的GTalk martin.xus#spam#gmail.com 或者给我email.


版规：
1:周一至周五 每日一题，周末休息
2:请用ruby/rails解答，你可以任选一题，或者全选
3:每人在回帖时，请尽量在一贴内答完，将余下的版面留给其他的用户。
4:大家在做题之前，尽量不要去看别人的答案，[b][color=Red]为了防止你的答案影响别人的思维定势，或者被别人直接抄袭，请将你的全部内容包含在discuz代码 hide中，不会使用bbcode的用户，请点击回复按钮，进入富文本编辑器，点隐藏代码，然后在其中输入内容。[/color][/b]

5:根据你的答案我们会做出评选，并给予小小的积分奖励

说明：
1:欢迎你踊跃提供你认为有趣的题目，请发在，题目征集栏目中
2:我们需要评委，如果你认为你可以，并且时间充足，请站内短信联系我。期待你能为大家贡献。

本期Ruby题目由xavier 出，非常感谢他的支持:)

[color=DarkRed][b][size=3]Ruby 类：[/size][/b][/color]

二项式定理(杨辉三角)，既二项式系数表，参见[url]http://baike.baidu.com/view/7804.htm[/url]
                               1                                               n=0

                          1        1                                          n=1

                        1     2      1                                       n=2

                    1     3      3      1                                   n=3

                1     4      6      4      1                               n=4

           1     5     10     10      5     1                            n=5

        1     6     15     20     15     6    1                        n=6



可是发现如果不用组合数来做的话是挺麻烦的
所以题目如下：
做程序输出杨辉三角，尽量不用组合数而用该表的行间结构来做，
即每行的两头都是1，其余的数是它肩上的两个数之和

[color=DarkRed][b][size=3]Rails 类：[/size][/b][/color]

我相信大家都用过rails中的
[code]
h "&nbsp;<p>aaa</p>"
[/code]
的关键字[b][color=Red]h[/color][/b]，用来转义html字符，防止非法的输入。同时大家也可能在用
white_list :[url]http://svn.techno-weenie.net/projects/plugins/white_list/README[/url]。

但是，现在的编辑器基本都是富文本编辑器，将html的关键字转义过来，内容压根不可读。现在我们需要设计一个新的方法，去除所有的噪音的东西，只返回text部分。举个简单的例子：

[code]
html =<<__HTML__
<div style="position: absolute; z-index: 50; clip: rect(auto, auto, auto, auto); left: 755px; top: 161px; display: none;" id="memcp_menu" class="headermenu_popup">
    <table cellspacing="0" cellpadding="4" border="0">
        <tbody>
            <tr><td class="popupmenu_option" style="opacity: 0.85;"><a href="memcp.php">控制面板首页</a></td></tr>
        </tbody>
    </table>
</div>
__HTML__

[/code]

现在假设有这样一个方法text
[code]
puts html.text
# 控制面板首页
[/code]

Cool！太完美了。

开动脑筋，再一次发挥你的创意，我们期待你的精彩表现。

[[i] 本帖最后由 martin 于 2008-3-17 10:56 编辑 [/i]]

**** Hidden Message *****

[[i] 本帖最后由 martin 于 2008-3-17 12:41 编辑 [/i]]

能否稍微解释一下什么是"组合数"

**** Hidden Message *****

o(9)

             1            
            1 1            
           1 2 1           
          1 3 3 1         
         1 4 6 4 1         
       1 5 10 10 5 1      
     1 6 15 20 15 6 1      
    1 7 21 35 35 21 7 1   
  1 8 28 56 70 56 28 8 1   
1 9 36 84 126 126 84 36 9 1

[[i] 本帖最后由 bbschat 于 2008-3-17 19:40 编辑 [/i]]

杨辉三角形里暗藏了二项式定理。
说暗藏其实过分了点，由于基本原理一致，想不暗藏都不可能。
组合数就是排列组合，高中学的东西，楼上的解法就是。

写杨辉三角形是学BASIC那会儿的基本题。

**** Hidden Message *****

[[i] 本帖最后由 martin 于 2008-3-17 12:41 编辑 [/i]]

rails类的问题正是我昨天碰到的一个问题, 开动脑筋。。。。。。。。。。。。。。。。。。

用Hpricot来试下。

我来尝试一下,这两道题都非常有趣,我都没有想到最好的答案,反而在解答过程中想到了新的问题
**** Hidden Message *****

[[i] 本帖最后由 lgn21st 于 2008-3-17 15:47 编辑 [/i]]

1gn21st思路比较好。当成xml去解析。我暂时没有想到好的解决方法。

Rails没玩过，是不是这个意思？

[code]
def html2text(str)
  str.gsub(/\<.*?\>/,"")
end
  
puts html2text(html)
[/code]

<hide>
[code]def pascal_triangle(m)
a = Array.new
p a[0]  = a[1] = 1
2.upto(m){|i|
j = (i*i-i)/2
print a[j] = 1
print ' '
(j+1).upto(j+i-2){|k|  print a[k] = a[k-i]+a[k-i+1]
  print ' '                                 
}
p a[j+i-1] = 1
}
end
pascal_triangle(20)
[/code]</hide>

[[i] 本帖最后由 Ragnarok 于 2008-3-17 21:25 编辑 [/i]]

Hpricot有个text方法可以直接去掉那些标签。
爬下来的网页直接就可以用那个方法了。
另些方法的话，我想正则表达式能不能解决这个问题呢。研究下Hpricot的源码看看哈。

有点跑题哦,那就继续跑吧
用REXML::Document是因为他是ruby的标准库,完全ruby实现,答题的时候不想代码运行还多一个外部依赖,且我不知道XP下面怎么装这个,预编译的么?
REXML::Document效率是最差的,但是基本完整实现了XPath,不过其实REXML::Document目前的版本是有Bug的,间接影响了ruby在处理xml这件事情上名声,哪天我放bug代码上来大家看看
实际项目中我也是用Hpricot的,Hpricot的parse部分是用C语言实现的,效率高,我也没有碰见什么bug,推荐使用!
看见regex就头大的人飘过~~~

[[i] 本帖最后由 lgn21st 于 2008-3-17 23:34 编辑 [/i]]

我来看答案,我做不出!

``你们辛苦了,!!

[quote]原帖由 [i]lgn21st[/i] 于 2008-3-17 15:42 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=12621&ptid=3768][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
我来尝试一下,这两道题都非常有趣,我都没有想到最好的答案,反而在解答过程中想到了新的问题
**** 本内容被作者隐藏 ***** [/quote]

lgn21st,看到你的帖子快笑死我了。真有趣！
我也没有忘记我的中学数学老师，我也没有忘记在中学，我们没有学过什么杨辉三角，什么Pascal三角的。那些都是上大学后学的了...呵呵。

basic=[[1],[1,1]]
printf "please give a number:"
max=gets.chomp.to_i
for row in 2..max-1            
t=[1]
for j in 1..row-1
t<<basic[row-1][j-1]+basic[row-1][j]
end
t<<1
basic<<t
end
p basic

[quote]原帖由 [i]drive2me[/i] 于 2008-3-18 10:13 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=12684&ptid=3768][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]


lgn21st,看到你的帖子快笑死我了。真有趣！
我也没有忘记我的中学数学老师，我也没有忘记在中学，我们没有学过什么杨辉三角，什么Pascal三角的。那些都是上大学后学的了...呵呵。 [/quote]

我记得大学开始就是定积分,不定积分,然后是其他高数什么的,差不多也都还给老师了~~~偶可怜的大学数学老师~~~我还记得您~~~~

**** Hidden Message *****

[[i] 本帖最后由 jmouse 于 2008-3-24 01:05 编辑 [/i]]

大家加油~~‘
学习

回复 18# 的帖子

没有想到好方法哦，郁闷呢

那个，关于三角的bbchart的代码可以解释一下么？我是新手，看不懂。可以解释一下算法么？这里先谢谢

[[i] 本帖最后由 snakeqx 于 2008-4-3 10:04 编辑 [/i]]

这个还没有结吧？调试了一早上终于写出来一个：[code]**** Hidden Message *****[/code]

有没有求组合数算法的函数？

我还一位这样会速度很慢呢，我试了下还行……
**** Hidden Message *****

惭愧！看答案的！