Project Euler解题汇总(更新至309在1楼)

newkid · 发表于 2010-12-5 01:06

这个取石子游戏好像中国古代也有。题目中这样少量的数字加上平方数限制，还是可以用穷尽法求出来的。

〇〇 · 发表于 2010-12-5 19:38

http://projecteuler.net/index.php?section=problems&id=313
Problem 313
05 December 2010

In a sliding game a counter may slide horizontally or vertically into an empty space. The objective of the game is to move the red counter from the top left corner of a grid to the bottom right corner; the space always starts in the bottom right corner. For example, the following sequence of pictures show how the game can be completed in five moves on a 2 by 2 grid.

Let S(m,n) represent the minimum number of moves to complete the game on an m by n grid. For example, it can be verified that S(5,4) = 25.

There are exactly 5482 grids for which S(m,n) = p2, where p 100 is prime.

How many grids does S(m,n) = p2, where p 106 is prime?

[ 本帖最后由〇〇于 2010-12-5 19:40 编辑 ]

lastwinner · 发表于 2010-12-17 23:42

解除阅读权限限制，大家共同探讨，共同进步

lastwinner · 发表于 2010-12-20 00:36

原帖由〇〇于 10-11-8 07:51 发表
--利用1/i的极限等于999...9/(i*10^n)的原理
…………
最长i=983,长度=984, 0.(
00101729399796541200406917599186164801627670396
74465920651068158697863682604272634791454730417
09053916581892166836215666327568667344862665310
27466937945066124109867751780264496439471007121
05798575788402848423194303153611393692777212614
44557477110885045778229908443540183112919633774
16073245167853509664292980671414038657171922685
65615462868769074262461851475076297049847405900
30518819938962360122075279755849440488301119023
39776195320447609359104781281790437436419125127
16174974567650050864699898270600203458799593082
40081383519837232960325534079348931841302136317
39572736520854526958290946083418107833163784333
67243133265513733468972533062054933875890132248
21973550356052899287894201424211597151576805696
84638860630722278738555442522889114954221770091
55645981688708036622583926754832146490335707019
32858596134282807731434384537131230925737538148
52492370295015259409969481180061037639877924720
24415055951169888097660223804679552390640895218
718209562563580874872838250254323499491353
)

〇〇，长度是982，不是984

看到吹NB的回复，我才意识到你的答案是不对的

原帖由 tree_new_bee 于 10-12-19 13:35 发表
在循环小数部分，商的部分可能会有重复，但余数不可能重复（余数只要重复，必然意味着后续序列重复）

btw: 由这个可以得到一个推论：任何数的倒数的循环长度，都不可能超过这个数本身。

用这个思路，就变的容易多了。

tree_new_bee · 发表于 2010-12-20 10:01

原帖由〇〇于 2010-11-9 08:15 发表

确实是bug,我再看看
是最后打印的循环上标差1

/*
设计思路：
如果一个数是有限小数，那么余数乘以10的n次方，总有能整除的。
比如1/8，第1步1/8余数1，第2步10/8余数2，第3步20/8余数4，第4步40/8余数0
如果一个数是循环小数，记为0.(a),a的长度是b，展开式为a*(1/10^b+1/10^2b+...10^nb)
按照等比数列求和公式0.(a)=a*(1-q^n)/(1-q),当n趋向无穷，等于a/(1-q)=a/(1-1/10^b)
=a*10^b/(a^b-1),因此可以断定:长度为b的连续9组成的数一定能被a整除。
比如1/7=0.(142857),142857=999999/7,
另外，分母*2或者*5不影响循环节长度，比如1/3=0.(3),1/6=0.1(6),1/15=0.0(6),
因此可以忽略分母能被2，5整除的那些数。
实现：穷举法，对每个分母i，分别计算
余数1=10^n /i 的余数，下个余数*10
余数2=(10^n-1) /i 的余数,下个余数*10+9,例如:9/7->29/7->19/7->59/7->39/7->49/7
任何一个余数如果为0表示整除或者一轮循环节结束。
*/

这下容易懂多了。

不过，证明1/n的循环节长度的99...999能被n整除, 其实不用极限的方法。以下步骤很简单的就能得到这个结论：

设 1/n = 0.a(b)
a的长度为La, b的长度为Lb

则: 1/n *10^La = a.(b)
1/n *10^(La+Lb) = ab.(b)
两式相减得：
1/n* (10^(La+Lb) - 10^La)= ab.0
=> 1/n*(10^Lb-1) * 10^La = ab.0
右边的ab.0为整数
所以(10^Lb-1) * 10^La 能被n整除。

所以，严格说是99..99000能被n整除，其中9的个数为循环节长度。0的个数为非循环部分长度。

regonly1 · 发表于 2010-12-20 18:10

求1000以内所有连续N个数乘积最大的数：
with tmp as (select
replace('73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450',chr(10),'') a from dual),
rxp as (select replace(ssum('(.)'), ',') s,
            rtrim(replace(ssum('\'||rownum||'*'), ','),'*') d,
            max(rownum) r
      from dual connect by rownum <= &N)
select * from (
select n, v, rr, row_number()over(order by n desc) rn from (
select dbms_aw.eval_number(regexp_replace(substr(a,rownum,r), s, d)) n, rownum rr, substr(a,rownum,r) v
  from tmp, rxp
connect by rownum <= 1000-r+1))
where rn = 1

〇〇 · 发表于 2010-12-31 10:18

Project Euler前70题的Scala解法.pdf (481.62 KB, 下载次数: 13)

〇〇 · 发表于 2010-12-31 10:44

project_euler解题表格.doc.pdf (310.2 KB, 下载次数: 16)

〇〇 · 发表于 2011-1-8 07:07

从108楼挑出1个难度适中的
71 2 比3/7小且分子分母均不大于1000000的最简枚举分母，由于分子递增，可以维护一个指针， 428570
分数中，最接近3/7的分数的分子是多少？总复杂度O(N)。计算差之后更新答案即可。

又是循环小数
3/7=0.(428571)
=428571/999999
所以...

〇〇 · 发表于 2011-1-8 07:16

SQL> select case when (428571/1E6-1/7)<(428570/(1E6-1)-1/7) then 428571 else 428570 end from dual;

CASEWHEN(428571/1E6-1/7)<(428570/(1E6-1)-1/7)THEN428571ELSE428570END
--------------------------------------------------------------------
428570

[转载] Project Euler解题汇总(更新至309在1楼)

浏览过的版块