阿摩線上測驗
題組內容
六、給定一陣列名稱為 NUM，包含 n 個不重複整數(n ＞ 2)，請撰寫虛擬程式碼找出該陣
列 中 元 素 兩 兩 乘 積 最 大 者(即 Maximum pairwise product， 變 數名 稱 為 maxprod，
maxprod = maximum (NUM[i] * NUM[j], i ＜＞ j) )，完成下列 2 項子題。
(二)請在演算法時間複雜度須為 O(n)的限制下，撰寫虛擬程式碼。(請注意，如作答內容之演算法時間複雜度經分析為 O(n2)，本子題僅給 5 分)（15 分）
詳解 (共 9 筆)
草莓族
詳解 #5186634
蔡明勳
詳解 #5640626
piano2489
詳解 #4635732
int maximum(int NUM[...
(共 397 字，隱藏中）
前往觀看
shang
詳解 #6211641
int max(int NUM[],in...
(共 1505 字，隱藏中）
前往觀看
Cuda Chen
詳解 #4405416
參考來源：https://www.gee...
(共 640 字，隱藏中）
前往觀看
Lin Jin
詳解 #6211904
只回答難題(除非別人回答太爛)
詳解 #6227161
Ethan 智傑 Chiang
詳解 #6081177
function max(arr) ...
(共 765 字，隱藏中）
前往觀看
adamhsu622
詳解 #6833858
以下為簡單的虛擬碼
int getmaxprod() {
// max1,max2,min1,min2 儲存陣列索引值
//
// 找最大值
//
max1 <- 0 // 假設 num[0] 為最大值
for i <- 1 to (n-1) do
若 num[i] > num[max1] 則 max1 <- i
end for
swap(num[max1],num[0]) // 交換 num[max1]和 num[0]
// max1,max2,min1,min2 儲存陣列索引值
//
// 找最大值
//
max1 <- 0 // 假設 num[0] 為最大值
for i <- 1 to (n-1) do
若 num[i] > num[max1] 則 max1 <- i
end for
swap(num[max1],num[0]) // 交換 num[max1]和 num[0]
ㅤㅤ
// 找次大值
//
max2 <- 1 // 假設 num[1] 為次大值
for i <- 2 to (n-1) do
若 num[i] > num[max2] 則 max2 <- i
end for
swap(num[max2],num[1]) // 交換 num[max2]和 num[1]
//
max2 <- 1 // 假設 num[1] 為次大值
for i <- 2 to (n-1) do
若 num[i] > num[max2] 則 max2 <- i
end for
swap(num[max2],num[1]) // 交換 num[max2]和 num[1]
prod1 <- num[0]*num[1] // 計算第一組最大乘積
ㅤㅤ
// 找最小值
//
min1 <- 0 // 假設 num[0] 為最小值
for i <- 1 to (n-1) do
若 num[i] < num[min1] 則 min1 <- i
end for
swap(num[min1],num[0]) // 交換 num[min1]和 num[0]
//
min1 <- 0 // 假設 num[0] 為最小值
for i <- 1 to (n-1) do
若 num[i] < num[min1] 則 min1 <- i
end for
swap(num[min1],num[0]) // 交換 num[min1]和 num[0]
ㅤㅤ
// 找次小值
//
min2 <- 1 // 假設 num[1] 為次小值
for i <- 2 to (n-1) do
若 num[i] < num[min2] 則 min2 <- i
end for
swap(num[min2],num[1]) // 交換 num[min2]和 num[1]
//
min2 <- 1 // 假設 num[1] 為次小值
for i <- 2 to (n-1) do
若 num[i] < num[min2] 則 min2 <- i
end for
swap(num[min2],num[1]) // 交換 num[min2]和 num[1]
prod2 <- num[0]*num[1] // 計算第二組最大乘積
ㅤㅤ
// 最後結果
//
if prod1 > prod2 then
maxprod <- prod1
else
maxprod <- prod2
//
if prod1 > prod2 then
maxprod <- prod1
else
maxprod <- prod2
ㅤㅤ
return maxprod;
}
}
過程用到四個迴圈,每個迴圈的時間複雜度為 O(n),
故加總起來還是為 O(n)
ㅤㅤ
私人筆記 (共 1 筆)
目標國營聯招
私人筆記 #3590333