查看完整版本: 介绍一个做题网站

介绍一个做题网站

[url]http://projecteuler.net/index.php?section=problems[/url]
-----------------------------------------------------------------------------------------
目前共有178个题, 第1个也是最简单的问题是这样的,

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.
-------------------------------------------------------------------------------------

我的答案是这样的,

max = 1000
sum = 0
m3 = 0
m5 = 0
m15 = 0
sum += m3 while (m3 += 3) < max
sum += m5 while (m5 += 5) < max
sum -= m15 while (m15 += 15) < max
puts sum

-------------------------------------------------------------------
解出来以后你可以去论坛看别人的源码

比如用PYTHON的
using list comprehension in python:
>>> sum([x for x in range(1000) if x % 3== 0 or x % 5== 0])
233168

---------------------------------------------------------------------------------------
排名前1000里翻了前面几页, 中国人极少, 越南的倒有好多.

这是论坛上比较有RUBY味的解法

def sum_multiples(ary, range)
range.inject(0) do |sum, n|
ary.any? { |i| n % i == 0 } ? sum + n : sum
end
end

puts sum_multiples([3,5], 0..999)

这个也非常好

puts (3..999).to_a.reject{|n| n%3!=0 and n%5!=0}.inject{|sum,n|sum+n}

还有这个

puts (1...1000).inject(0) { |s, n| (s + n if (n%3).zero? or (n%5).zero?) or s }

喜欢，不错的地方

第4题
-----------------------------------------------------
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.
-----------------------------------------------------
我的解法
class Fixnum
        def palindromic?
                self.to_s.reverse == self.to_s
        end
end
from = 999
to = 100
max = 0
while from > to do
        from.downto(to) do |i|
                if (from * i).palindromic?
                        max = from * i if max < from * i
                        to = i
                        break
                end
        end
        from -= 1
end
puts max

这儿如果数字太大了, 超过了Fixnum的范围, 这个就有些麻烦了, 还是直接判比较好
-------------------------------------------------------
另一中国人的解法

class Fixnum
  def palindromic?
    s = self.to_s
    s.reverse == s
  end
end

t = Time.now
num = 0
999.downto(100) do |i|
  999.downto(i) do |j|
    if (i*j).palindromic? and i*j>num
      puts i, j, num = i*j
      break
    end
  end
end

puts "Time: #{Time.now - t}s"
puts "Answer: #{ num }."
-------------------------------------------------
没我的快, :)

第4题最后一个不就是我的答案吗？

[code]

def c(x)
    return true if x.to_s.reverse == x.to_s
    return false
  end

  def f()
    (999 * 999).downto(100 * 100) {|i|
     if c(i)
       999.downto(100){|x|
       return i if (i.divmod(x)[1] == 0) && (i.divmod(x)[0] <= 999)}
     end
     }
  end

  p f()

[/code]

嘿嘿, 我做的时候你的答案还没在上面呢.

第10题, 求1_000_000以内的所有素数和. 一个美国人的程序飞快, 在我的机上跑只要4秒的, 而我最快的也要44秒.
他用一个一百万的布尔数组, 初始化为真, 然后从2开始写假...

程序在这儿[code]imit = 1000000
limitRt = Math.sqrt(limit)
sieveList = Array.new(limit,true)


prime = 2
while prime <= limitRt
  i = prime**2
  while i <= limit
    sieveList[i-1] = false
    i +=  prime
  end
  prime += 1
  until sieveList[prime - 1] == true
   prime += 1
  end
end


# print list
primeTotal = 0
for i in (1...limit)
if sieveList[i] == true
   primeTotal += (i+1)
end
end

print primeTotal[/code]

--------------------------------------------------------
11题看着头比较大, 硬着头皮做下去...
[url=http://projecteuler.net/index.php?section=problems&id=11]http://projecteuler.net/index.php?section=problems&id=11[/url]
In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 [color=Red]26[/color] 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 [color=Red]63[/color] 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 [color=Red]78[/color] 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 [color=Red]14[/color] 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

[[i] 本帖最后由 5swords 于 2008-1-19 09:39 编辑 [/i]]

[code]
class MyMatrix
        def initialize(file)
                f = File.open file
                @m = f.readlines.join.gsub("\n"," ").split(" ").map {|x| x.to_i}
                @len = (@m.size**0.5).floor
        end
        def max_loc(p)
                i = p / @len
                j = p % @len
                east = esouth = south = wsouth = 0
                east = @m[p]*@m[p+1]*@m[p+2]*@m[p+3] if j < @len - 3
                esouth = @m[p]*@m[p+@len+1]*@m[p+2*@len+2]*@m[p+3*@len+3] if j < @len - 3 && i < @len - 3
                south = @m[p]*@m[p+@len]*@m[p+2*@len]*@m[p+3*@len] if i < @len - 3
                wsouth = @m[p]*@m[p+@len-1]*@m[p+2*@len-2]*@m[p+3*@len-3] if j > 2 && i < @len - 3
                [east, esouth, south, wsouth].max
        end
        def max_all
                (0...@len*@len).inject(0) {|max,n| [max, max_loc(n)].max}
        end
end

matrix = MyMatrix.new "matrix_20_20.txt"
puts matrix.max_all
[/code]

原来楼上就是chaofan啊

是啊，你到哪题了，我卡在12题，13题倒是简单。

有难度啊，不过不要告诉我什么。

12题摸到思路了，但具体算法有点头大，所以用笨办法花2分多钟死算出来结果。
现在开始做13题。

目前进度是18题做了一大半，18题解决了，67题也解决了，休息，明天继续。

楼上个位真棒，加油，忙过这段我也加入~
:)

刚才终于把18和67解决了。
一开始以为自己的算法应该是最优的，结果证明不对，百思不得其解后准备采用穷举先看看结果再说，结果在考虑穷举的解法时找到了真正的解法，汗自己一个.......

没时间, 要出差了, 可能会落下BBSCHAT好多. 12题还没出来.

今天白天也挺忙的，没空做题，晚上抽点时间完成了19，20（可能比较简单吧），以后能保持1天1道的进度我就满足了。因为难度会越来越高，估计50题以后就要3天一道，100题以后一个星期一道就很不错了。

汇报一下战果。
23题昨天卡了一下，今天解决完23后一股作气又解决了4题，目前进度到第28题。
其中有些题对Ruby来说还是比较简单的。

插一脚，第一题：
[code]
def Euler1(x)
sum = 0
(1...x).each{|i| sum += i if (i % 3 == 0 || i % 5 == 0)}
puts sum
end
#test
Euler1(1000)
[/code]

终于结束了第12题, 我用了和大多数人不同的算法, 不幸的是, 其中一个式子有误, 以致于机器开了几天都没算出来, 好象是到了(4266000*4266001 )/2.
具体的程序请看EULER第11页

交流一下，第12题
[code]
def Euler12(x)
factor = 0
num = 1
while factor <= x
  num = num + 1
  tr = (1+num)*num/2
  arr=[]
  n = 2
  tt = tr
  while tt != 1
    if tt % n == 0 then
      arr << n
      tt = tt / n      
    else
      n += 1
    end
  end
  factor = 1
  tmp = arr[0]
  kk = 1
  for i in 1..arr.length-1
    if arr[i] == tmp then
      kk += 1
    else
      factor *= (kk+1)
      kk = 1
      tmp = arr[i]
    end
  end
  factor *= (kk+1)
end
puts tr, "\n"
end
#test
Euler12(500)

[/code]
在我机器上跑，30秒不到。

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

第10题美国人用的方法其实是中国人发明的。这样找素数的方法叫“筛法”，便于用递归做。
方法就是取第一个数（必定为素数），然后把它的倍数去掉。
继续上一步。

目前进度42/185，我是由简至难做的
跳过了19，24，35，97，31
现在回头去看19

[[i] 本帖最后由 jmouse 于 2008-3-13 14:44 编辑 [/i]]

完成50题了
下周开始补前面跳过的题。

[quote]原帖由 [i]jmouse[/i] 于 2008-3-15 01:30 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=12478&ptid=2960][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
完成50题了
下周开始补前面跳过的题。 [/quote]

能不能把你们的方法帖出来，给大家参考？

谢谢！ :)

那个网站的设置就是让你在做出题目之后再进行交流。我想，冒然把方法就贴出来并不是太好。况且这里的每日一题栏目可能还会引用一些题目。
但是我不反对针对某一道特定题目进行讨论。
另外，该网站用的名字是欧拉，很多解题方法其实都有数学的思路在里面。计算机语言只是一种工具。

[quote]原帖由 [i]jmouse[/i] 于 2008-3-16 02:22 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=12538&ptid=2960][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
那个网站的设置就是让你在做出题目之后再进行交流。我想，冒然把方法就贴出来并不是太好。况且这里的每日一题栏目可能还会引用一些题目。
但是我不反对针对某一道特定题目进行讨论。
另外，该网站用的名字是欧 ... [/quote]

如果有一种方法出来了，大家就会加入进来讨论。起到抛砖引玉的效果。我们的目的还是要吸引更多的会员加入进来讨论和学习。对吧？这是我们论坛的目的之一，帮助广大Ruby爱好者学习和掌握Ruby。 :)

having solved 61 out of 186 problems.

柿子挑软的捏