ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2019函数公式学习大典 不用妈妈陪默写神器 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2016实战技巧学习锦囊 WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 10241|回复: 14

[Excel 程序开发] [第30期]填充数字(已结)

[复制链接]

TA的精华主题

TA的得分主题

发表于 2007-12-2 15:34 | 显示全部楼层 |阅读模式

答题要求:
  在N*N的区域上(1≤N≤10),填入1,2,…,N*N共N*N个数,使得任意两个相邻的数之和为素数。
例如:当N=2时,有:
1 2
4 3
为了简便,左上角的格子里必须填数字1。
在O3单元格输入:N,结果填充到A1开始的区域内
如有多种解,则输出第一行、第一列之和为最小的排列方案;若无解,则输出“无解!”。

评分标准:
结果正确,且代码运行流畅,得2分,优秀答案另加分。

答案发送至:agstick@126.com,并跟贴占位,请勿在跟贴中直接发答案。

 


[此贴子已经被作者于2007-12-31 16:36:03编辑过]
单选投票, 共有 22 人参与投票

距结束还有: 4046 天21 小时48 分钟

您所在的用户组没有投票权限

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-12-5 12:16 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册

答案发送至agstick@126.com,跟贴占位.

 


结果正确。

[此贴子已经被agstick于2007-12-30 20:35:45编辑过]

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-12-8 22:59 | 显示全部楼层

答案发送至agstick@126.com,跟贴占位.

想不到更好的方案来解决此问题只能用穷举的土办法,速率慢啊.



 先填第一行在填第一列,思路正确,但是第一行与第一列之和不是最小。

[此贴子已经被agstick于2007-12-30 19:43:00编辑过]

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-12-12 17:16 | 显示全部楼层

已经发到版主的邮箱,速度非常慢[em04]

 

结果正确,速度还可以。

[此贴子已经被agstick于2007-12-30 19:45:01编辑过]

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-12-17 17:46 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助

不好意思,理解错误,重做时可能因为解题思路有问题,太慢,弃权!

期待正解!向各路高手致敬!

 


出现相邻两数不为素数,不符题意,不得分。

[此贴子已经被agstick于2007-12-30 19:47:13编辑过]

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-12-31 02:09 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册

oh my god, 感觉已经挺优化的了,但速度还是太慢了,只能跑到4, 4 以后的速度掺不忍睹。

答题时间已过。

[此贴子已经被agstick于2007-12-31 16:33:35编辑过]

TA的精华主题

TA的得分主题

 楼主| 发表于 2007-12-31 16:29 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助

此题要想出解法不难,关键是速度如何优化,当n>5以后,解空间是非常庞大的。

此题适用的算法为回溯法,所谓回溯法,就是先填一个数,如果ok,扩展(下一格),如果不满足条件,换下一个数。如果所以数都不满足条件,退回到上一格(回溯)。用回溯法求其中一个解,很快,若要求所有满足条件的解,速度可能会很慢。此题要求求出第一行与第一列之和最小的解,因此要搜索所有解。此时需要优化,否则太慢。

优化方案:

1、建立素数表,通过查表判断之和是否为素数。

2、优先填充第一行、第一列。

3、注意到此素数矩阵是奇偶相间,因此可以以2为步长循环。

4、对已经用过的数,进行标记。

5、求出其中一个解后,直接从第一行或第一列开始回溯,跳过非第一行和第一列的回溯。

6、当第一行第一列之和达到极限最小,(n为奇数时,n×(2n-1);n为偶数时,n×(2n-1)+1),结束,直接输出解。

有关回溯法,可参看附件,也可到网络上搜索相关资料。

参考答案:


抱歉,原附件上传错误,特此更正!

[此贴子已经被作者于2008-1-1 20:19:07编辑过]

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-12-31 17:19 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助

我不知道是不是我电脑问题,斑竹的程序当等于6的时候好象不对,出现两个1,而且我用5的时候,似乎第一列+第一行并不是最小的,我是用willin2000 斑竹的程序对比的

当=5时, 斑竹程序第一列+第一行=85

willin2000 斑竹,第一列+第一行=55

[em09]

抱歉,附件传错,以更正。

[此贴子已经被agstick于2008-1-1 20:22:21编辑过]

TA的精华主题

TA的得分主题

发表于 2008-1-2 14:34 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2008-1-2 19:49 | 显示全部楼层

在我的程序中加上agstric的第6条优化方法:“6、当第一行第一列之和达到极限最小,(n为奇数时,n×(2n-1);n为偶数时,n×(2n-1)+1),结束,直接输出解。”后,我的速度n=8,10还是较慢,后来发现原来中间搜索中使用先列后行比先行后列的数度要快. 虽然这个是偶然性的,但概率较大, 相比较而言符合"极限最小"的概率反而小.

我的原程序使用了的agstic优化方法1/2/4/5, 第3条我直接了使用查素数表和优化起始指针的方法,感觉比步进2的方法还要快些.(在N=10,耗时只有1/4)

附件加上了第6条方法,在8和10时速度确实快了很多. 还使用先列后行,在6/7/9时速度得到明显改善.

 

本帖子中包含更多资源

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

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

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-3-19 17:46 , Processed in 0.070214 second(s), 16 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

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