[最小值搜尋] 給定一個絕對值函數如下:

其中,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