問題的來源是幫一個朋友改數據庫,要求是這樣的,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 閱讀(3683)
評論(5) 編輯 收藏