随笔-55  评论-208  文章-0  trackbacks-0

问题的来源是帮一个朋友改数据库,要求是这样的,60个题目,总分是100分,正确答案的分值有2分的 1.5分,其中分值的排列关系是随机的,请问如何设置答对题目,使得答题总分刚好为一个数值,如82分
我的解决办法是:
用一个集合记录判断是正确的2分题,当发现期望总分和当前累加总分差值小于1.5时,因为最小单位是1.5,在2分集合中退出一个正确的2分,然后继续遍历下去
虽然后来用上面办法解决了这个问题,但是我觉得这个问题的解法不够通用,有很多问题,对这个问题扩展了一下,大家一起讨论一下
一维的:和上面的题目一样。用变量来描述一下这个问题
有m个元素,其中每个元素有1个value值,o<value>,value的取值有x,y,z...,按照value值m个元素排列是随机的,问如何用一次遍历m,而得到n个元素,这n个元素的value总和是W
二维的:其实就是俄罗斯方块了,大家想象我们玩的俄罗斯方块是不是这个道理
有m个元素,其中每个元素有1个value值对,o<v1,v2>,value的取值有x,y,z...,按照value值m个元素排列是随机的,问如何用一次遍历m,而得到n个元素,这n个元素的value中,v1
的总和乘以v2的总和是W
n维的:不知道用什么现实中的情况来描述了
有m个元素,其中每个元素有1个value值对,o<v1,v2,v3,...vn>,value的取值有x,y,z...,按照value值m个元素排列是随机的,问如何用一次遍历m,而得到n个元素,这n个元素的value中,v1
的总和乘以v2的总和乘以v3的总和...一直乘到vn的总和是W

呵呵,也许是我孤陋寡闻,上面这个题可能早有算法了,希望知道的朋友能告诉我一声:)

发现我好像犯了一个逻辑死角的错误,其实一次遍历后拿到value的分布图就很简单了。。。。
汗自己一个,不删除文章了,看看有没有更好的算法,最好是不遍历完就可以得到一个正确的结果

posted on 2007-10-02 13:13 rocket 阅读(3661) 评论(5)  编辑  收藏

评论:
# re: 一个堆积木的算法题,比较有意思,欢迎大家讨论 2007-10-02 18:08 | t
不知你的“一次遍历后拿到value的分布图就很简单了”是什么意思?难道是把所有的情况都记录下来?那样的话似乎情况太多了吧!  回复  更多评论
  
# re: 一个堆积木的算法题,比较有意思,欢迎大家讨论 2007-10-03 17:38 | 海边沫沫
程序员有时候也要用数学的头脑思考问题撒。
60个题目,总分100分,先列个方程组撒。得到的结果很显然是有20个两分题,40个1.5分题。

对于最后得分这个数值,我认为首先应该判断得分是奇数分还是偶数分,如果是偶数分,如82分,说明做对的1.5分题肯定是4的整数倍个。依此类推。

然后再考虑数据结构撒。  回复  更多评论
  
# re: 一个堆积木的算法题,比较有意思,欢迎大家讨论[未登录] 2007-10-04 10:51 | Ryan
发到水木的算法版问问,
其实只要遍历一遍,得出阈值范围,求解方程即可。
好像没有好的直接算法,因为是随机的,很多因素不固定!  回复  更多评论
  
# re: 一个堆积木的算法题,比较有意思,欢迎大家讨论 2007-10-09 21:47 | glamour
表达不清楚,在说一边!  回复  更多评论
  
# re: 一个堆积木的算法题,比较有意思,欢迎大家讨论 2007-12-20 12:24 | sai
多少年没更新啦,现在很忙?  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: