国产成人精品久久免费动漫-国产成人精品天堂-国产成人精品区在线观看-国产成人精品日本-a级毛片无码免费真人-a级毛片毛片免费观看久潮喷

您的位置:首頁技術(shù)文章
文章詳情頁

java - 多叉樹求值,程序高手,算法高手看過來

瀏覽:150日期:2023-10-12 14:04:03

問題描述

遇到一道筆試題,完全沒思路,求助。。。。

已知類定義如下

class Node { public Double value; public List<Node> children;}

輸入node滿足以下條件:1 node的value是大于0的浮點數(shù)2 node的下級節(jié)點(以及更下級節(jié)點)的value可能是null或者大于0的浮點數(shù)程序的作用如下:1 將樹形結(jié)構(gòu)里面所有value是null的均設(shè)為大于0的浮點數(shù)2 非葉子節(jié)點(即children數(shù)量大于0的節(jié)點)的value均等于它的children的value之和

public void doit(Node node){ ......}

示例java - 多叉樹求值,程序高手,算法高手看過來解答java - 多叉樹求值,程序高手,算法高手看過來

這個問題要如何解答?

已經(jīng)有高手答出來了,綜合一下下面兩人的答案就是完美答案。其實就是我采納那個答案里面把均分改為隨機就很完美了

問題解答

回答1:

沒有寫具體代碼,說一下思路吧首先,把問題分為2步Step1、確定非葉子節(jié)點的值Step2、確定葉子節(jié)點的值先處理Step1,處理完Step1之后,Step2就不用多說了,根據(jù)父節(jié)點的值均分即可。對于Step1,step1-1: 由下向上遍歷各個非葉子節(jié)點,通過對其子節(jié)點求和,確定其最小值。如最右側(cè)的子樹,最小值為5.5。step1-2: 由上向下,逐層確定非葉子節(jié)點,為方面描述,命名[100]為第一層,[10,20,?,?]為第二層,以此類推。根據(jù)step1-1的結(jié)果,第二層的最小值為[10,20,>60,>5.5],將100減去最小值之和,然后均分,結(jié)果為[10,20,62.25,7.75]step1-3: 同上,確定第三層,結(jié)果為[5.5, 4.5] [9.5, 5.25, 5.25] [60, 1.125, 1.125] [6.625,1.125]這里最后一組較特別,需要考慮到7.75分配的時候,其左下已經(jīng)有5.5了,所以7.75里面可自由支配的數(shù)為7.75-5.5=2.25,將2.25均分到兩邊,結(jié)果[6.625,1.125]step1-4: 最后一層相信不用再羅嗦了,其實就是step2,均分下來就好。

回答2:

剛剛看了一下這道題目,覺得很有意思。然后思考了一下,提出以下問題。我的思路的話就是遞歸。

分層次遍歷,在每層的時候把確定的值加起來,為空的節(jié)點們?nèi)シ指腹?jié)點的值減去這部分確定的值的和(題目的要求)。然后如果不是葉節(jié)點的節(jié)點按照上述方法遞歸。

但是確定每個節(jié)點的值得時候,如某些葉子節(jié)點的時候,我們需要隨機給他們賦值,他們的值有些受到父節(jié)點約束,有些不收父節(jié)點約束比如第二層的第三個節(jié)點的兩個葉子節(jié)點,如果我們賦給他們的值使得他們的父節(jié)點不滿足要求了,這就不符合題意了。所以我想的是在每次確定值得時候傳入這些節(jié)點的取值范圍。這些范圍的確定又會導致一些問題,問題又會變得復雜。

范圍確定,每個空節(jié)點的最大值肯定是父節(jié)點的值減去同行子節(jié)點的值的和,最小取值肯定是大于其子節(jié)點的有值元素的和。因為只有確定了某個范圍,其葉子節(jié)點的一些隨機值的取法不會導致其余節(jié)點不符合題意。總的意思來說每個同父節(jié)點的空節(jié)點的取值互相有約束,其中一個節(jié)點的取值雖然滿足自身,但是會使得其余節(jié)點不滿足要求。舉個例子:java - 多叉樹求值,程序高手,算法高手看過來

如果這樣取值,則局部滿足,會導致其他節(jié)點的取值不滿足要求。所以在沒約束的情況下可能會導致意想不到的結(jié)果。我們需要去確定這些范圍。

綜上,這只是我的一些思考后的一些想法,也許有錯誤的地方歡迎指正。

標簽: java
主站蜘蛛池模板: 国内精品七七久久影院 | 欧美xxxx性xxxxx高清视频 | 国产欧美亚洲三区久在线观看 | 国产主播福利片在线观看 | 国产禁女女网站免费看 | 香港日本韩国三级网站 | 中文字幕成人免费高清在线视频 | 精品欧美激情在线看 | 亚洲日本一区二区三区 | 深夜福利视频在线观看免费播放 | 成人精品 | 国产精品黄网站 | a级毛片在线观看 | 国产精品亚洲一区二区三区在线观看 | 中文字幕在线网址 | 美美女高清毛片视频黄的一免费 | 欧美一区二区三区不卡免费观看 | 亚洲精品一区二区三区中文字幕 | 免费在线黄色网址 | 亚洲欧美大片 | 免费v片视频在线观看视频 免费v片在线观看 | 三级亚洲| 国产一级做a爰片... | 视频一区二区在线 | 九九热爱视频精品视频高清 | 黄色wwwwww| 亚洲在线高清 | 日韩精品国产一区 | 亚洲欧美日韩在线观看二区 | 日本特级黄毛片毛片视频 | 久久综合网址 | 国产或人精品日本亚洲77美色 | 久热久草| 国产精品久久久久久麻豆一区 | 久操视频免费在线观看 | 亚洲国产精品乱码在线观看97 | 欧美午夜激情影院 | 99热久久国产这里是精品 | 国产精品久久久免费视频 | 午夜爽爽性刺激一区二区视频 | 亚洲精品久久九九精品 |