查看完整版本: 抛砖，关于http://projecteuler.net/

抛砖，关于http://projecteuler.net/

[url]http://projecteuler.net/[/url]是一个解题网站，这里有过帖子介绍。
应drive2me老兄的要求，开个帖子来分析讨论下上面的题目。
目前我由简单的做起，才解开1/3不到的题目，慢慢来。

集思广益，希望大家能踊跃一些，能引出些玉来是最好不过的了。

第一题
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.
题目要求的是3和5的倍数，求解方法无非就是2类，一种是穷举，一种是计算。
因为是1000以下，所以穷举还是很方便的，
[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]
可以说说的是短路或||
短路的意思是如果仅凭目前的表达式就可以决定整个表达式的最终值，就不再计算后续表达式。
比如i % 3 == 0 || i % 5 == 0，就是在i被3整除的情况下，不再考虑是否能被5整除。
使用短路应该可以提升程序效率，但是也要注意，某些在判断式中的计算，会被短路吞掉。
另外，如果采用计算法，要注意的是，3和5的公倍数，要被扣去。

再说个题外话，Ruby里负步长的循环是不是只能用Downto或者step来写？没有办法用for？

第二题
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
求Fibonacci数列中偶数的和。
前一段程序是我开始时做的，当时的想法很奇妙，结论也是对的。但是现在实在想不起为什么这么写了。当时的目的就是要把偶数的判断去掉。
这段程序必须在x比较大的时候才是正确的。
后一段就是中规中矩的写法了。
解决Fibonacci数列的办法很多，用数组，arr<<arr[arr.length-2] + arr。last也可以，像我这样用f1,f2也可以。
[code]
def Euler2(x)
sum = 2
f1 = 1
f2 = 1
while sum < x * 2  
  sum += f2 = f1 + f2
  f1 = f2 - f1
end
puts sum/2, "\n"

sum = 2
f1 = 1
f2 = 2
while f2 < x
  f2 = f1 + f2
  f1 = f2 - f1
  sum += f2 if f2 % 2 == 0  
end
puts sum
end
#test
Euler2(4000000)
[/code]

第六题
The sum of the squares of the first ten natural numbers is,
1² + 2² + ... + 10² = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)² = 55² = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
一个很简单的运算，没什么花样，知道等差数列的，可以直接把后一个式子写出来。
就算不知道等差数列公式，直接穷举之后也没多大困难。那个循环是暂时去不掉的，所以差别不大。
[code]
def Euler6(x)
  a = ((1 + x) * x / 2) ** 2
  for i in (1..x)
    a -= i**2
  end
  puts a
  sum = 0
  tmp = 0
  
  for i in (1..x)
    sum += i**2
    tmp += i
  end
  puts tmp*tmp-sum
end
#test
Euler6(100)
[/code]

第五题
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
老外讲话很别扭，这个题目的意思就是让你找1.。20的最小公倍数。
求多个数的最小公倍数，一般总是一个个加上去，不断地得到公倍数。
求2个数的最小公倍数，方法有很多，比较简单的2种，一种是我现在用的，把大数不断成倍增加，直到可以整数小数。还有种就是用辗转相除法先求得最大公约数，然后2数积除以最大公约数就是。
由于题目要求的解在整型可表达范围内，所以不需要考虑溢出问题。否则，就要写个对象来处理整型数，这就麻烦大了。
[code]
def Euler5(x)
  out = x
  while x != 1
    out = mult(out,x=x-1)
  end
puts out,"\n"
end
def mult(a,b)
  tmp = a
  while tmp % b != 0
    tmp += a
  end
  return tmp
end
#test
Euler5(20)
[/code]

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

第二题当初的想法回来了。
考虑数列：1，1，2，3，5，8，13，21，34。。。
1+1=2
3+5=8
13+21=34
。。。
所以，我把第一个1给补上，偶数的和就是总和的一半了。

jmouse很久没来了？

196有人感兴趣么？