ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
让更多数据处理,一键完成 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
楼主: agstick

[Excel 程序开发] [第29期]捡金币(已结)

[复制链接]

TA的精华主题

TA的得分主题

发表于 2007-11-19 12:33 | 显示全部楼层

发贴占位

我自己做的,速度有问题哦。感觉很慢

最近太忙,没空改了

 

算法有误,一次最大的不一定两次之和最大。


[此贴子已经被agstick于2007-11-26 21:48:26编辑过]

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-11-20 16:37 | 显示全部楼层

下午临时做了一个,包含单程走法和双程走法各一。不知道算法对不对,参与一下。

占楼完毕

 

算法有误,一次最大的不一定两次之和最大。

 晕倒,不知怎么变成4分了,抱歉。


[此贴子已经被agstick于2007-11-26 22:23:37编辑过]

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-11-22 16:45 | 显示全部楼层

占一个位!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

算法有误,一次最大,两次之和不一定最大。


[此贴子已经被agstick于2007-11-26 21:57:34编辑过]

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2007-11-26 09:15 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
QUOTE:
以下是引用willin2000在2007-11-9 0:08:39的发言:

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

运行速度似乎还可以(不到1秒).

双线程动态规划法,正解。

 



好精妙!!! 学习ing

 [em17][em17][em17]

TA的精华主题

TA的得分主题

发表于 2007-11-26 22:03 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2007-11-26 22:28 | 显示全部楼层

最近比较忙,先把原题和答案放上来,稍后总结。


此题的目的是想考察一下动态规划的算法,从参赛答案来看除了willin2000 兄外,其他的都是递归算法。
动态规划是一种比较常用的算法,对此类的问题,其效率要比递归高。

若只考虑走一次的情况,则是一个标准的动态规划的过程。
根据走的步数来分阶段
阶段:阶段1,在位置(1,1),阶段2,位置可能有两个(1,2),(2,1),等。其中的规律是阶段k,可能的位置是(x,k+1-x),(k>=x>=1)
状态:每个阶段有若干个状态,如上所述阶段k的状态有: (x,k+1-x),(k>=x>=1)。
决策:在每个位置有可能有两个或一个决策可选择,即向下或向右走(当然不能出界)。
状态转移方程:
位置(x,y)的状态:S(x,y)=min{ s(x-1,y), s(x,y-1) }+格子(x,y)中的数。

现考虑走两次。
题目中是两次分开走的,但我们可以看成两个人同时走。这时依然按照行走的步数来分类。
这样的情况下有一个不同的情况是:可能两个人同时走入同一个格子取数,这时肯定不能取两次数。
两条路线同时进行的动态规划中,状态和决策以及状态转方程移要复杂一些。

两条路线同时进行的动态规划
阶段:按所走的步数来分阶段,从左上角走到右下角,共2n-1个步骤,故共2n-1个阶段。但,有两条线路,故每一阶段的状态都会复杂一些。
状态:有两线路同时走,在某阶段的某状态,要用两个坐标来分别表示两线路的两个点。如:第一阶段,共一个状态:(1,1),(1,1);第二阶段,(1,2),(1,2);(1,2),(2,1);(2,1),(1,2);(2,1),(2,1)共四个状态。
  由于在第k阶段的任何两个点的x,y坐标是有关系的:k+1=x+y。故可只用x坐标来表示一点的坐标,故状态可表示为(x1,x2),对应的y坐标为:y1=k+1-x1,y2=k+1-x2。
决策:若用0,1分别表示向下或向右走,则每个状态的可能决策有四种:(1,1),(0,0),(1,0),(0,1)。两个数值分别表示两个点的下一步走向。
状态转移方程:
  设map(x,y)为方格图,f(k,x1,x2)表示第k个阶段走到(x1,x2)状态的最大和
  f(0,1,1)=map(x1,1+1-x1) 即map(1,1)
  f(k,x1,x2)=max{f(k-1,x1',x2')+map(x1,y1)|x1=x2,f(k-1,x1',x2')+map(x1,y1)+map(x2,y2)|x1<>x2} (x1',x2')表示可通过某决策到达(x1,x2)的所有点。

动态规划有点类似递归,通过一个数组来存放每一步的结果,数组后面的值是由前面的值得来的,一般最后一个值就是所要的结果。

[此贴子已经被作者于2007-12-2 15:24:56编辑过]

本帖子中包含更多资源

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

x

评分

1

查看全部评分

TA的精华主题

TA的得分主题

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

单个动态规划法还好理解

双线程动态规划法看得我一头雾水.

TA的精华主题

TA的得分主题

发表于 2007-11-28 11:34 | 显示全部楼层
QUOTE:
以下是引用agstick在2007-11-26 22:28:14的发言:

最近比较忙,先把原题和答案放上来,稍后总结。


真是叹为观止了。期待版主总结。

TA的精华主题

TA的得分主题

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

这道题目跟马踏棋盘的怎么样?能不能用贪心算法!在马踏棋盘中用一般的递归算法基本得不到第一解!

TA的精华主题

TA的得分主题

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

悄悄占个位

再悄悄占个位

递归搜索,结果正确,速度优化的还行,qee用兄功力深厚啊。

 


[此贴子已经被agstick于2007-11-25 0:48:44编辑过]

本帖子中包含更多资源

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

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

本版积分规则

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

GMT+8, 2024-7-23 04:35 , Processed in 0.036747 second(s), 13 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

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

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

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