題目：網路斷線
當太許多人同時使用Internet時, 網路變成非常慢。為了解決這個問題, 德國Ulm大學發展出在最高負載時間的應急規劃，以系統化公平的方式切斷國內一些城市的上網路徑。以 1 到N 隨機代表德國的城市。 Freiburg 是 1 , Ulm 是 2 , Karlsruhe 是 3 , 並且依此類推出一純粹隨機的次序。
然後, 隨意地選擇一數字M , 並且首先在城市 1 切斷上網路徑，接著依次切斷其後第M個城市, 超過N則回頭到1，並且不計入已經斷線的城市。例如, 如果 N=17 和 M=5 , 城市斷線的次序為 [1, 6, 11, 16, 5, 12, 2, 9, 17, 10, 4, 15, 14, 3, 8, 13, 7]。
寫一個程式讀入N後(3 ≦ N < 150)，決定最小的整數M，使得 Ulm 能夠確保成為最後一個被斷線的城市。
[範例輸入]
3
[範例輸出]
2
[範例輸入]
7
[範例輸出]
3
1. 請依題目說明畫出解答此題之流程圖
2. 承上題，請將程式碼剪貼上
想法
我的解法滿暴力的 .
我先做一個 array 城市最大數是 150 , 也就是我這個 array的大小
依照題目的說法 , 編號 2 要最後拜訪 , 所以 M 不可能是 1
如果N = 15 , 超過 15 又要從頭來 , 所以可以知道這是一個循環的狀況
於是 M 的上限是 N
因為我們想知道最小的M是多少 , 所以我的想法很簡單
我們就從 2 開始 try try到 N
只要Try到某一個 M 可以滿足題設 , 那就把這個 M output出來
所以這個程式要先準備一些東西
一個是那個循環的機制
我設一個變數叫 check 另他初始值為 1
我們去一一檢查 array內的值
如果 array 沒有被拜訪過
也就是array內的值是 0
那check才可以加1
如果check = 目前的 M 的話
我們就要看 array 的值是不是 0
如果不是 0 代表之前有斷過電
那就不管他 , 再到下一個
如果是 0 就改成 1
然後把 count + 1 ,
count 是一個計算現在斷了幾家店的計數用的變數
再中間可能會遇到一些狀況
比如在 i + 1 的時候 超過了 N
這時候就把 i 設成 2 來做到循環的樣子
最後還要判斷目前設的這個M是不是我們要的
那個條件就是
當count = N 的時候 i 是 2
就表示了 2 是最後一個被斷電的 也就是題目想要的情況
那如果不是的話 , 就要把 M 設成另一個數
把一切變數都弄回初始的樣子
然後再進行那些動作 直到找到為止
以下是程式碼 及圖片
很簡陋的流程圖
Dim a(150) As Integer
Dim i, n, check, count, j, ans As Integer
' i , j 計數用 , 其中 j 其實就是題目的 M , 只是習慣用j記數
' n是題目中的N
' check = j 時要檢查要不要斷電
' count = n時要看最後一個斷的是不是 2 , 用來當程式結束的判斷
' 你在左邊的 textbox的輸入就是input
n = TextBox1.Text
For j = 2 To n
'深藍色這一段代表你每次試一個新的 j 時要作的初始化的動作
ans = 0
check = 1
count = 1
For i = 1 To n
a(i) = 0
Next
a(1) = 1
i = 1
Do While count <> n
If check = j Then
If a(i) = 0 Then
a(i) = 1
count = count + 1
check = 1
End If
Else
If a(i) = 0 Then
check = check + 1
End If
End If
'檢察結束條件
If count = n And i = 2 Then
ans = j
End If
i = i + 1
'檢查循環
If i > n Then
i = 2
End If
Loop
'檢察結束條件
If ans <> 0 Then
Exit For
End If
Next
'把結果印在右邊的 textbox裡
TextBox2.Text = ans
最後附上整個程式的檔案
留言列表
