[最小值搜尋] 給定一個絕對值函數如下: 其中,x 為整數 (可正可負), n 為正整數且 3 < n < 350,請計算在輸入正整數 n 的 情況下, f (x) 函數的最小值和此時的 x 數值;舉例來說,當輸入 n = 19 時,f (x) 函數會在 x = 14 時出現最小值 f (x) = 720 。 輸入/輸出說明:請在表單上建立 3 個 LABEL、3 個 TEXTBOX 及一個按鈕。第 1 個 LABEL 標示「輸入正整數 n」,相對應的第 1 個 TEXTBOX 可以輸入一個正整數 n,第 2 個 LABEL 標示「f(x)函數最小值發生於 x」,第 2 個 TEXTBOX 輸出 f (x) 最小值 發生時 𝑥 的數值。第 3 個 LABEL 標示「f(x)函數最小值」,第三個 TEXTBOX 輸出 f (x) 最小值。程式執行順序:輸入正整數 n,按下按鈕,輸出 f(x) 函數最小值和 此時的 x 數值。 本題有兩種解法,暴力法與公式法:說明如下: Youtube 視頻教學 1)暴力法:直接使用 for 迴圈,令 x= 1 to n 搜尋即可。 有視頻可供參考 程式碼如下 Dim n As Integer = TextBox1.Text Dim x As Integer, k As Integer, s As Integer, min As Integer, minX As Integer min = Integer.MaxValue "最大整數 min = &H7FFFF For x = 1 To n s = 0 For k = 1 To n s = s + k * Math.Abs(x - k) Next If (s < min) Then min = s minX = x End If Next MsgBox(min) TextBox2.Text = minX | |||||
2)公式法 先複習一下級數和公式 請思考 f(x) 的座標圖形,當 n=4 時,f(x)座標圖如下: : 當 n=5 時,f(x)座標圖如下: 請思考,對任一個 n 時,f(x) 座標圖,x=t會有極小值,t 在哪裡? 家豪版 此版為公式解 Dim n As Integer = TextBox1.Text Dim t As Integer, fx As Integer t = Math.Floor((-1 + Math.Sqrt(1 + 2 * (n * n + n))) / 2) "floor 為無條件去小數 fx = t * t * (t - 1) - ((n + 1) * n *t / 2) - (((2 * t * t - 3 * t + 1) * t / 3) - ((2 * n * n + 3 * n + 1) * n / 6)) TextBox2.Text = t TextBox3.Text = fx 此版為暴力解 有個基本功,要找出最小值,該值初值必為最大。 Dim n As Integer = TextBox1.Text Dim x As Integer, k As Integer, s As Integer, min As Integer, minX As Integer min = Integer.MaxValue "最大整數 min = &H7FFFF For x = 1 To n s = 0 For k = 1 To n s +=k * Math.Abs(x - k) "計算絕對值總和 Next If (s < min) Then min = s minX = x End If Next TextBox2.Text = minX TextBox3.Text = min 昊朋版 此版是利用圖形最低點,則 f(x)>f(x-1) 且 f(x-2)>f(x-1) 此版可以改善的地方,可知 x 最小發生點必定是 1≤x≤n,且靠近 n。 因此 x 可由 n-1 開始搜尋,每次遞減 1。在大數據下,效果差很多。 Dim n As Integer = Val(TextBox10.Text) Dim x As Integer = 0 Dim f(n * n) As Integer Do While True x += 1 For i = 1 To n f(x) += i * Math.Abs(x - i) "先求出所有 f(x) 值 Next If x > 2 Then If f(x - 2) > f(x - 1) And f(x - 1) < f(x) Then TextBox11.Text = x - 1 TextBox12.Text = f(x - 1) Exit Do End If End If Loop 黃翰版 此版想法不錯,明知 n>3,且極小值發生點除了 n = 4 以外,均發生在 x≥4, 因此在計算 總和時,就直接跳過 x < 4 的部分,可以說是提升效率。 正因如此,可以將紅色程式碼省略,直接寫成如下,也不失一個好方法。 If n=3 Then min_x = 3 min_y =8 Else 藍色程式碼 EndIf Dim n As Integer = Val(TextBox1.Text), x As Integer Dim i, j As Integer, min_x As Integer = 3 Dim y, min_y As Integer If n <= 3 Or n >= 350 Then MsgBox("n範圍為4~349,您已超出範圍") Exit Sub End If For i = 1 To n min_y += i * Math.Abs(min_x - i) Next For i = 4 To n x = i y = 0 For j = 1 To n y += j * Math.Abs(x - j) Next If y < min_y Then min_x = x min_y = y End If Next TextBox2.Text = min_x TextBox3.Text = min_y |