ITPUB论坛-中国专业的IT技术社区

 找回密码
 注册
查看: 6741|回复: 10

用PL/SQL解欧拉计划270题:切割正方形

[复制链接]
论坛徽章:
399
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
发表于 2017-5-1 07:47 | 显示全部楼层 |阅读模式

将一张边长为整数、大小为N×N的正方形纸的顶点置于原点,两条相邻边分别贴着x轴和y轴。然后,我们根据下面的规则对它进行切割:   
◦我们只进行这样的切割:从正方形不同的两条边上选择两个坐标为整数的点,并沿着两点的连线切割。   
◦两次切割不能相交,但多次切割可以经过边上的同一个点。   
◦一直切割下去,直到不存在合法的切割为止。  
如果翻转或旋转后相同的切割方法视为不同,我们记切割一个N×N方块的方法数记为C(N)。举例而言,C(1) = 2,而C(2) = 30(如下图所示)。
p270_CutSquare.gif


C(30) mod 10^8 是多少?
论坛徽章:
399
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-5-2 10:01 | 显示全部楼层
用过程语言很慢
julia> @time m2(4)
  0.017698 seconds (138.50 k allocations: 9.308 MiB, 24.06% gc time)
604

julia> @time m2(5)
  2.048811 seconds (23.05 M allocations: 1.509 GiB, 8.31% gc time)
12168

julia> @time m2(6)
376.864624 seconds (3.77 G allocations: 246.898 GiB, 16.91% gc time)
238848

使用道具 举报

回复
论坛徽章:
399
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-5-2 13:50 | 显示全部楼层
〇〇 发表于 2017-5-2 10:01
用过程语言很慢
julia> @time m2(4)
  0.017698 seconds (138.50 k allocations: 9.308 MiB, 24.06% gc t ...

改善了一些


julia> @time m2(5)
  0.666805 seconds (4.21 M allocations: 261.067 MiB, 8.30% gc time)
12168

julia> @time m2(6)
45.692035 seconds (326.38 M allocations: 19.527 GiB, 12.06% gc time)
238848

julia> @time m3(5)
  0.624851 seconds (4.16 M allocations: 158.830 MiB, 7.55% gc time)
12168

julia> @time m3(6)
41.148124 seconds (302.12 M allocations: 12.756 GiB, 10.30% gc time)
238848

使用道具 举报

回复
论坛徽章:
399
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-5-2 15:49 | 显示全部楼层

把不可能画满的起始直线排除
julia> @time m4(5)
  0.418616 seconds (3.04 M allocations: 116.161 MiB, 6.54% gc time)
12168

julia> @time m4(6)
26.927065 seconds (211.89 M allocations: 8.946 GiB, 5.10% gc time)
238848

使用道具 举报

回复
论坛徽章:
399
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-5-2 20:57 | 显示全部楼层
怎么用消除对称来优化呢? arXiv:1604.02870v1

使用道具 举报

回复
论坛徽章:
399
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
 楼主| 发表于 2017-5-2 21:00 | 显示全部楼层
p270.jpg 旋转后就有很多对称

使用道具 举报

回复
论坛徽章:
496
紫蜘蛛
日期:2007-09-26 17:05:56奥运会纪念徽章:垒球
日期:2008-09-15 01:28:12生肖徽章2007版:鸡
日期:2008-11-17 23:40:58生肖徽章2007版:马
日期:2008-11-18 05:09:48数据库板块每日发贴之星
日期:2008-11-29 01:01:02数据库板块每日发贴之星
日期:2008-12-05 01:01:03生肖徽章2007版:虎
日期:2008-12-10 07:47:462009新春纪念徽章
日期:2009-01-04 14:52:28数据库板块每日发贴之星
日期:2009-02-08 01:01:03生肖徽章2007版:蛇
日期:2009-03-09 22:18:53
发表于 2017-5-3 02:15 | 显示全部楼层
你发这些的目的是什么?如果是想要和人交流,拜托写点有用的东西,感兴趣的人自然和会看。像这类梦呓般的自言自语就发自己博客去,留作这里也是垃圾。

使用道具 举报

回复
招聘 : 系统分析师
论坛徽章:
483
马上有房
日期:2014-02-19 11:55:14itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-09-29 01:14:14itpub13周年纪念徽章
日期:2014-10-08 15:15:25itpub13周年纪念徽章
日期:2014-10-08 15:15:25马上有对象
日期:2014-10-12 11:58:40马上有车
日期:2014-11-16 17:11:29慢羊羊
日期:2015-02-09 17:04:38沸羊羊
日期:2015-03-04 14:43:432015年新春福章
日期:2015-03-06 11:57:31
发表于 2017-5-3 15:20 | 显示全部楼层
newkid 发表于 2017-5-3 02:15
你发这些的目的是什么?如果是想要和人交流,拜托写点有用的东西,感兴趣的人自然和会看。像这类梦呓般的自 ...

〇〇的草稿纸

使用道具 举报

回复
论坛徽章:
289
生肖徽章2007版:猴
日期:2008-05-16 11:28:59生肖徽章2007版:马
日期:2008-10-08 17:01:01SQL大赛参与纪念
日期:2011-04-13 12:08:17授权会员
日期:2011-06-17 16:14:53ITPUB元老
日期:2011-06-21 11:47:01ITPUB官方微博粉丝徽章
日期:2011-07-01 09:45:27ITPUB十周年纪念徽章
日期:2011-09-27 16:30:472012新春纪念徽章
日期:2012-01-04 11:51:22海蓝宝石
日期:2012-02-20 19:24:27铁扇公主
日期:2012-02-21 15:03:13
发表于 2017-5-3 15:25 | 显示全部楼层
newkid 发表于 2017-5-3 02:15
你发这些的目的是什么?如果是想要和人交流,拜托写点有用的东西,感兴趣的人自然和会看。像这类梦呓般的自 ...

   OO一直是这样的习惯的啊。。。。

使用道具 举报

回复
论坛徽章:
0
发表于 2017-5-5 09:30 | 显示全部楼层
看不明白 能写的详细点不

使用道具 举报

回复

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

本版积分规则

TOP技术积分榜 社区积分榜 徽章 电子杂志 团队 统计 虎吧 老博客 知识索引树 读书频道 积分竞拍 文本模式 帮助
  ITPUB首页 | ITPUB论坛 | 数据库技术 | 企业信息化 | 开发技术 | 微软技术 | 软件工程与项目管理 | IBM技术园地 | 行业纵向讨论 | IT招聘 | IT文档 | IT博客
  ChinaUnix | ChinaUnix博客 | ChinaUnix论坛 | SAP ERP系统
CopyRight 1999-2011 itpub.net All Right Reserved. 北京盛拓优讯信息技术有限公司版权所有 联系我们 网站律师 隐私政策 知识产权声明
京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802021510 广播电视节目制作经营许可证:编号(京)字第1149号
  
快速回复 返回顶部 返回列表