Project Euler 数学计算挑战

斷羽鳥

这些的确是很有趣的题目 。。。LZ很不错的介绍啊。
楼主，应该是指楼的主人 。。。就是开帖的那位啦。

铁蛋

一个把搜查空间减少的方法就是只检查从 2 到 sqrt(600851475143)
的 prime numbers. 而这个从 2 到 sqrt(600851475143) prime number list，则需要写另外一个程序来造出。一个很古老的方法是 Sieve of Erathothenes，不妨到 http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 去看看。

p/s: 大部份的人也是边玩边学的

[ 本帖最后由 铁蛋 于 25-2-2009 12:56 PM 编辑 ]

chingjun

原帖由 puangenlun 于 23-2-2009 05:10 PM 发表
Problem 17
17 May 2002


If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1 ...

hi puangenlun，记得我吗？？哈哈。。
其实这题算是很简单的了。。。
只要写一点简单的规则让电脑去算一算就可以了
而且只到1000啊。。
以前比赛的时候这种题目是出来要你用手算的。。

原帖由 铁蛋 于 24-2-2009 01:15 PM 发表
楼主 = 楼上的主人 = 你 .

在论坛的语言中，楼主是开帖的人，而上面那个人叫楼上的。。

原帖由 img3nius 于 25-2-2009 08:51 AM 发表
我从这个学期开始学C++
(大概学了数星期)

我看了从问题1~10
作了7题的答案,结果只有5题对了,
有些编程做了但是遇到楼主说的"搜索空间大"而导致电脑无法计算出答案

在这些问题中 还可以发现很多关于数学的知 ...

学习一个语言只是在学习一个工具的使用方法。。
除了使用方法之外还需要学使用技巧，而这才是难点所在。。
你可以想想如何优化自己的代码使得可以计算的更快，比如说一些不必要的计算可以去掉的之类的。。

比如你说的找最大质因数的那题，如果你要一个一个质数去找来除来看看是否可以整除的时候你至少要除到sqrt(60085147514) 才可以
要如何减少你的计算次数呢？？
就是如果你发现了它的因数（假设是k），那么你可以将你的搜索范围减少到sqrt(60085147514/k) 甚至更低。。。
这么说你明白了吧？






这些确实很有趣，只是时间长了很难坚持下去，哈哈。。。
大家去把国籍都set成malaysia吧。。这样我们可以互相查看别人的进度，然后可以把那边的id post到这边来我们才知道谁是谁。。
目前我还是malaysia地区里面第一名的人，不过我不是在炫耀说我很厉害，只是我前阵子太得空罢了，哈哈。。
我相信，也希望很快cari就有人可以超越我了。。呵呵

[ 本帖最后由 chingjun 于 25-2-2009 07:24 PM 编辑 ]

puangenlun

记得你，不敢忘记！

17题已经通过最原始的方法解决

我是用笔算的，反正有规律

慢慢算就算出来了

这样：1~9，10~19，20~99，1~99，100~999，1~1000

有些题目很不好玩（17题）

有些则很有意义（上面那个求解空间大的题目）

还有那种要很大的数字的每一位digit

那个以前看过怎样解

现在终于自己来了

不过，我个人认为有些题目根本就是浪费时间精神

完全是在玩大digit而已。

img3nius

再问...关于题目2

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

这里是指斐波那契数的偶数数列之和不超过4m?
或者是第偶数数列之值不超过4m?

比方说
1,2,3,5,8,13,21,34....

低于40之偶数数列之和
是     
    2+5+13=20 <=40
或者是
    2+5+13+34=54    ,   34<=40
??

铁蛋

Fibonacci Sequence: 1,2,3,5,8,13,...,T(n),

T(n) < 4 000 000

再从这个序列找出那些偶数的和。

puangenlun

Problem 26
13 September 2002


A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 =  0.5
1/3 =  0.(3)
1/4 =  0.25
1/5 =  0.2
1/6 =  0.1(6)
1/7 =  0.(142857)
1/8 =  0.125
1/9 =  0.(1)
1/10 =  0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d  1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

这题想不通！

大家有什么想法？

img3nius

这里有多少人是在做着这些问题的?

有许多问题我完全没头绪该如何开始....
也有些问题因为误解题意
让我一直找不着正确答案

img3nius

关于题目3(largest prime factor)

我找到
   600851475143=71*8462696833
但是我给与答案 8462696833 (我test了是质数)
却是错的= =?

还是我的程序有问题?
8462696833不是质数吗?

img3nius

原帖由 铁蛋 于 26-2-2009 03:29 PM 发表
Fibonacci Sequence: 1,2,3,5,8,13,...,T(n)

T(n) < 4 000 000 , 再从这个序列找出那些偶数的和。

我找到的n=偶数
sumT(n)=  2+
                  5+
                 13+
                 34+
                 89+
                233+
                610+
               1597+
               4181+
              10946+
              28657+
              75025+
             196418+
             514229+
            1346269+
            3524578=
            5702886

答案错了
我错在哪里@@?

铁蛋

不对吧，偶数是 even numbers,

2 + 8 + 34 + 144 + ... + 3524578 = ?

铁蛋

我的做法是：

１）对每个 1 < d < 1000 算６＾５小位数。
２）用一个６个数字的＂MOTIF＂(第1到第个6小数位)，从第７到第１２小数位开始对查。
３）如果这６个数字完全和吻合，停止计算，报告停止的位置。
４）如果这６个数字不完全吻合，继续对查第１３到１８的小数位 ...

要用多少个数字的 MOTIF，没有一个标准，只是不能太短。

[ 本帖最后由 铁蛋 于 3-3-2009 02:37 PM 编辑 ]

铁蛋

要找600851475143 的 prime factors，只需要检查到 sqrt(600851475143) 的 prime numbers. 在这个集合里，除了600851475143 没有余的 prime numbers 就是你要的 prime factors,
然后再找它们的最大值就解决了。

这种题目要先写一个程序列出需要用到 prime numbers.

puangenlun

你的问题二和问题三确实是错了

8462696833=10086647*839

至于问题2，需要看你的program才知道！




#27的问题26原来只是依赖于小学知识而已！

想了几天才恍然大悟！

img3nius

原帖由 puangenlun 于 4-3-2009 07:55 AM 发表
你的问题二和问题三确实是错了

8462696833=10086647*839

==这个很明显是我的编程有问题了
因为我test到8462696833是质数@@需要重做了

至于问题2，需要看你的program才知道！

==这个很明显是我的编程有问题了
因为我test到8462696833是质数@@需要重做了

我确实错了= ="
我是将所有n=偶数加起来
而不是T(n)=偶数,
哈哈


-------------------------
稍微改了改编程
两题都做对了


这里我又有点问题
普通电脑的c++能记录的数值能到多大?
比如题目10
当和数超过某一数值时
我的答案会从-xxxxxxxxxx再开始加??

[ 本帖最后由 img3nius 于 4-3-2009 02:52 PM 编辑 ]

puangenlun

后面有些题目会牵扯到很大的数

比方说1*10^200

这样的话就不可以按照老方法来做

（据说用python可以高高精度）

这里就牵涉到一些技巧了！

puangenlun

原帖由 铁蛋 于 3-3-2009 02:35 PM 发表
我的做法是：

１）对每个 1 < d < 1000 算６＾５小位数。
２）用一个６个数字的＂MOTIF＂(第1到第个6小数位)，从第７到第１２小数位开始对查。
３）如果这６个数字完全和吻合，停止计算，报告停止的位置。
４） ...

我的做法跟你的是一样的

不过看起来比你的简单一些

一句话：记录reminder！

reminder的范围在0~999之间

所以最长的cycle小于1000

根据reminder的记录

比较两个相同的reminder出现的位置

即可知道cycle的长度了！

img3nius

我想问
如果输入某数值
要如何用c++将所有位数的可能性排列列出来?
如输入
123

输出
123 132 213 231 312 321

??

puangenlun

这道题目我是用笔算出来的

用排列组合的知识可以一个个位数算出来

铁蛋

你可以去 GOOGLE 搜索 C++ Library，应该是有写好的程序来列出 Permutations。其中一个方法是用隔壁交换 (Adjacent swapping) 的方式来列出。

[ 本帖最后由 铁蛋 于 5-3-2009 05:59 PM 编辑 ]