鱼C论坛

 找回密码
 立即注册
查看: 3786|回复: 5

[技术交流] 小练习:20171002 取石子游戏

[复制链接]
发表于 2017-10-1 22:27:18 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 冬雪雪冬 于 2017-10-11 20:04 编辑

从现在开始我们要开展一批欧拉计划的习题练习。

其实在我们论坛中已有欧拉计划的板块,可能有些鱼油还没注意到。

什么是欧拉计划:http://bbs.fishc.com/thread-60405-1-1.html

我们欧拉板块现已给出了200余题,这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势,可以更简洁更方便的实现。

如果大家有兴趣也可浏览欧拉的英文网站:https://projecteuler.net/archives

这里已经有了500余题。


                               
登录/注册后可看大图


要求:

以python语言完成,如果是python2请注明。

程序以代码文字格式发帖。

注重程序效率和创意。

答题在一周内完成,即10.2 10:00之前,其后将公开大家的答案,并评比成绩。

另程序和答案可以在网上搜到,希望大家独立完成。题目不难,大家看看谁的效率高。

-- 回帖需写明解题思路,鼓励在程序中加上注释 --

-- 一些鱼油反映题目有些过难,为此略过一部分偏难的题目 --


                               
登录/注册后可看大图
301




题目:
取石子游戏
1.jpg

Nim
2.jpg

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-10-3 09:12:39 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-10-3 09:20 编辑

这题用了点投机取巧的办法,虽然应该有一大堆理论的验证来说明为啥这题符合“斐波那契数列”,但是我还是没有彻底搞清楚。

先说说,我的解题步骤吧。

一开始拿到这题目,我也是没有方向的,唯一可以确定的就是:如果某个状态假设(i,j,k)可以通过去掉某一堆中的x而得到(i-x,j,k)或(i,j-x,k)或(i,j,k-x)为0的话,那么(i,j,k)就为非0;反之,如果没有任何x满足以上条件,那么(i,j,k)就为0.

所以,这题目就可以利用动态规划的思路来求解,但是由于n<=2**30数组比较大,所以我没有直接求解,而是先列出前前几位数看看都有一些什么规律。

  1. T = {(0,0,0):0}
  2. index = [[0,0,0]]
  3. while index:
  4.         i = index.pop(0)
  5.         for j in range(3):
  6.                 idx = i.copy()
  7.                 idx[j] += 1
  8.                 if tuple(sorted(idx)) not in T:
  9.                         index.append(idx)
  10.                 else:
  11.                         continue
  12.                 for k in range(1,max(idx)+1):
  13.                         flag = 1
  14.                         for l in range(3):
  15.                                 iidx = idx.copy()
  16.                                 iidx[l] -= k
  17.                                 if iidx[l] >= 0 and T[tuple(sorted(iidx))] == 0:
  18.                                         T[tuple(sorted(idx))] = 1
  19.                                         flag = 0
  20.                                         break
  21.                         if not flag:
  22.                                 break
  23.                 if flag:
  24.                         T[tuple(sorted(idx))] = 0
  25.         if sum(i)>200:
  26.                 break
  27. for i in range(50):
  28.         if (i,2*i,3*i) in T and T[i,2*i,3*i]==0:
  29.                 print(i,2*i,3*i)
复制代码

输出:
0 0 0 #0不算
1 2 3 #小于等于2**0=1的有1个
2 4 6 #小于等于2**1=2的有2个
4 8 12 #小于等于2**2=4的有3个
5 10 15
8 16 24 #小于等于2**3=8的有5个
9 18 27
10 20 30
16 32 48 #小于等于2**4=16的有8个
17 34 51
18 36 54
20 40 60
21 42 63
32 64 96 #小于等于2**5=32的有13个
33 66 99
对于1,2,3,5,8,13这几个数是不是很眼熟?对的,他们就是“斐波那契数列”,所以小于等于2**30的个数其实就是求“斐波那契数列的第30项”,就这么简单。
  1. F=[1,2]
  2. for _ in range(1,30):
  3.         F.append(F[-1]+F[-2])
  4. print(F[30])
复制代码

2178309
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-10-3 10:53:37 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-10-3 11:00 编辑

另外去网上搜了一下,凡是符合(i,j,k)=0的情况,i^j^k=0,也就是i^j=k。
所以也可以这样写:
  1. print(sum(1 for i in range(1,2**30+1) if i^(2*i)==3*i))
复制代码


python的循环效率还是比较低,如果没有优化,基本上要4~5分钟才能出结果。

同样的逻辑,用aardio编写的话(C/C++内核),1分钟不到就可以了。
  1. import console;
  2. import time;

  3. st = time.tick();

  4. console.setTitle("euler301");

  5. var count = 0;
  6. for (i=1;2**30) begin
  7.     if (i^(2*i)^(3*i)==0) begin
  8.         count++;
  9.    
  10.     end;
  11.    

  12. end;
  13. console.print(count);

  14. console.print(time.tick()-st, 'ms');

  15. console.pause();
复制代码

评分

参与人数 1荣誉 +10 鱼币 +10 贡献 +10 收起 理由
冬雪雪冬 + 10 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-10-7 18:57:57 | 显示全部楼层
jerryxjr1220 发表于 2017-10-3 10:53
另外去网上搜了一下,凡是符合(i,j,k)=0的情况,i^j^k=0,也就是i^j=k。
所以也可以这样写:

aardio 应该是 Lua 内核
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-10-8 08:32:37 | 显示全部楼层
SixPy 发表于 2017-10-7 18:57
aardio 应该是 Lua 内核

aardio程序编写同样也是很方便的,而且运行速度又快,唯一的缺点就是没有python那么多现成的模块可以用,一些很简单的功能都需要从头写代码完成。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-10-8 09:08:36 | 显示全部楼层
jerryxjr1220 发表于 2017-10-8 08:32
aardio程序编写同样也是很方便的,而且运行速度又快,唯一的缺点就是没有python那么多现成的模块可以用, ...

aardio的定位是502快粘胶,不是大而全的语言。
核心没开源,只能靠作者一个人维护。
不过aardio可以通过调用其它语言的引擎来实现所有的功能。包括python。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:22

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表