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

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

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

[复制链接]
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
发表于 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 是多少?
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 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

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 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

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 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

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 2017-5-2 20:57 | 显示全部楼层
怎么用消除对称来优化呢? arXiv:1604.02870v1

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
 楼主| 发表于 2017-5-2 21:00 | 显示全部楼层
p270.jpg 旋转后就有很多对称

使用道具 举报

回复
论坛徽章:
480
榜眼
日期:2015-09-09 10:34:21秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12状元
日期:2015-11-23 10:04:09举人
日期:2015-11-23 10:04:09
发表于 2017-5-3 02:15 | 显示全部楼层
你发这些的目的是什么?如果是想要和人交流,拜托写点有用的东西,感兴趣的人自然和会看。像这类梦呓般的自言自语就发自己博客去,留作这里也是垃圾。

使用道具 举报

回复
招聘 : 系统分析师
论坛徽章:
477
本田
日期:2014-01-05 16:51:44技术图书徽章
日期:2014-04-21 10:26:402014年世界杯参赛球队: 伊朗
日期:2014-05-23 10:41:312014年世界杯参赛球队: 比利时
日期:2014-06-17 12:09:43itpub13周年纪念徽章
日期: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
发表于 2017-5-3 15:20 | 显示全部楼层
newkid 发表于 2017-5-3 02:15
你发这些的目的是什么?如果是想要和人交流,拜托写点有用的东西,感兴趣的人自然和会看。像这类梦呓般的自 ...

〇〇的草稿纸

使用道具 举报

回复
论坛徽章:
264
布鲁克
日期:2016-10-08 10:06:50秀才
日期:2016-05-20 15:09:32射手座
日期:2016-05-26 14:02:50双子座
日期:2016-05-25 16:05:44白羊座
日期:2016-05-23 11:49:19双鱼座
日期:2016-04-29 17:13:05秀才
日期:2016-04-29 15:03:39秀才
日期:2016-04-29 15:04:10技术图书徽章
日期:2016-04-29 15:04:10秀才
日期:2016-03-28 10:21: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号
  
快速回复 返回顶部 返回列表