推 VictorTom:推一下證明, 這是歸納法對吧?? 03/30 22:53
→ yauhh:不知道耶,我證明方面超弱的 03/31 00:20
推 LPH66:感覺不像歸納法 (雖然由小推大的感覺有像到) 03/31 01:10
推 Ross0916:全校前兩名一定是班上前兩名.. 是這個意思嗎? 03/31 19:27
推 attomahawk:小弟和樓上的見解相同。 03/31 20:27
→ yauhh:對,全校前二名一定在班上前二名 04/01 01:46
※ 引述《WWWZZZXXXMMM (WZXM)》之銘言：
: 一個array a[0],...a[n-1]
: ps：每個element的key可能有相同的
: 目的：use parallel algorithm 找出second-largest key
: 目前只有想到用parallel reduction找max的方式來做
: 找出max之後 回去砍掉此值
: 然後再跑一次parallel reduction 找max
: 應該就可以找到second-largest key
: 不知道版上高手有無其他idea可提供
: 感激不盡 謝謝
將資料分成幾個段落,每個段落各由一個節點處理. 每個節點找出最大二個數字拋回來,
由中樞節點收集並找出其中第二大的數字.
可以證明給你看: 令陣列數字構成集合 N, 有 l_1, l_2 屬於 N 且 l_1 > l_2 為
N 中最大二個數字. 由 N 取子集合 Z, 並知道 z_1, z_2 屬於 Z 且 z_1 > z_2 為
Z 中最大二個數字. 於是我們知道有下列敘述成立,
對每個屬於 N 的 x, l_1 = x 或 l_2 = x 或 l_2 > x.
對每個屬於 Z 的 x, z_1 = x 或 z_2 = x 或 z_2 > x.
目標是要證明以下二句敘述成立:
對每個屬於 Z 的 x, 若 x = z_1 或 x = z_2, 則 z_1 = l_1 或 z_i = l_2
或 z_i < l_2
對每個屬於 Z 的 x, 若 x 不等於 z_1 也不等於 z_2, 則 x 既不等於 l_1
也不等於 l_2.
如果以上二句可以證實,則你對每個節點處理的片段陣列數字可以相信一件事: 任何
不是頭二個最大數字的數字一定不會是整個陣列的頭二個最大數字.
證明:
1. 因為 z_i 屬於 Z, 且 Z 包含於 N, 所以 z_1 可能等於 l_1 或小於 l_1.
又因為 z_2 < z_1, 所以 z_2 小於 l_1. 且因 l_2 < l_1, z_2 可能等於 l_2 或
小於 l_2.
2. 對每個屬於 Z 的 x, 若 x 不等於 z_1 也不等於 z_2, 則 x < z_2.
又因前一條證明結果, x 既小於 z_2 也小於 l_1, 並且 x 必定小於 l_2,
所以 x 既不等於 l_1 也不等於 l_2.
--
/yau
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.114.217