平面距離計算

12月 28 2021 Example

來自 LIOJ 上的題目，這一題最難的地方在於「讀取資料」的方式，所以想記錄下來。

大方向

  1. 總共有幾組座標資料（每組有 4 個值）
  2. 怎麼取得想要的資料

總共有幾組座標資料

可以從 lines[0] 得知迴圈要跑幾圈，所以最外層的結構會是：

1
2
3
for(let i=0; i<Number(lines[0]); i++) {
  ...
}

怎麼取得想要的資料

接著就是最麻煩的地方了，要怎麼在每一圈裡面去取得對應的 4 個座標？

關於這點你可以先做個假設，把每一圈你希望取得的資料寫出來：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
i=0 // 第一組
lines[1]
lines[2]
lines[3]
lines[4]

i=1 // 第二組
lines[5]
lines[6]
lines[7]
lines[8]

i=2 // 第三組
lines[9]
lines[10]
lines[11]
lines[12]

...

可以先注意到，每一圈都會固定是 4 筆資料，所以只要專注在第一個 lines 的值就好，其他的可以用 +1 +2 +3 的方式來取得，所以：

  • i=0 的時候，第一個 lines 值要是 1
  • i=1 的時候，第一個 lines 值要是 5
  • i=2 的時候，第一個 lines 值要是 9

接著這部分可以參考 印出星星（金字塔） 裡面提到的方法，用「數學函數」的方式來求出公式：

1
2
3
f(i) = f(0) = 1
f(i) = f(1) = 5
f(i) = f(2) = 9

從這裡可以發現規律是 「每一圈都會增加 4」，也就是說，每一圈都要 x4：

1
2
3
4
f(i) = i * 4
f(0) = 0
f(1) = 4
f(2) = 8

當寫到這裡後你應該也能發現，只要在 +1 就可以實現我們的目標：

1
2
3
4
f(i) = i * 4 + 1
f(0) = 1
f(1) = 5
f(2) = 9

如果真的沒有頭緒，那妳可以用最笨的方法，就是一個一個試：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
f(i) = i * 1
f(0) = 0
f(1) = 1
f(2) = 2

f(i) = i * 2
f(0) = 0
f(1) = 2
f(2) = 4

f(i) = i * 3
f(0) = 0
f(1) = 3
f(2) = 6

// 在這邊的時候，你就會發現只要每一項在 + 1 就能符合規律
f(i) = i * 4 + 1
f(0) = 0 + 1 => 1
f(1) = 4 + 1 => 5
f(2) = 5 + 1 => 9

// 這邊雖然看起來可以把第三項 -1，但是第一個 0 跟第二個 5 的部分會不符合，所以沒有辦法
f(i) = i * 5
f(0) = 0
f(1) = 5
f(2) = 10

// 之後就更不可能了，所以不會再往下做
f(i) = i * 6
f(0) = 0
f(1) = 6
f(2) = 12

所以最後求出的公式就是 i * 4 + 1。

解題

在求出規律後，要解出這題就不困難了，所以這裡直接附上原始碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function solve(lines) {
  // 轉成數字
  const arr = lines.map(value => value * 1)
  // 總共有幾組
  const total = arr[0]
  // from 0 to 1
  for(let i=0; i<total; i++) {
    // i=0，start=1
    // i=1，start=5
    // i=2，start=9
    const start = i*4 + 1
    const x1 = arr[start] * 1   // lines[1]
    const y1 = arr[start+1] * 1 // lines[2]
    const x2 = arr[start+2] * 1 // lines[3]
    const y2 = arr[start+3] * 1 // lines[4]
    console.log(calculateDistance(x1, y1, x2, y2)) // 1.41
  } 
}
function calculateDistance(x1, y1, x2, y2) {
  const x = (x1-x2) ** 2
  const y = (y1-y2) ** 2
  return Math.sqrt(x + y).toFixed(2)
}

Bonus 我原本的解法

我原本的想法比較單純，我希望：

  1. calculateDistance 會接收一個陣列當作參數，並計算距離
  2. 建立一個巢狀陣列，裡面儲存每一組的座標陣列，例如說 [[1, 1, 2, 2], [3, 3, 4, 4]]
  3. 遍歷巢狀陣列，把一組陣列都丟給 calculateDistance 計算出距離

簡單來說大概就是這樣的架構：

1
2
3
4
const nestedArray = [[1, 1, 2, 2], [3, 3, 4, 4]]
for(let i=0; i<nestedArray; i++) {
  console.log(calculateDistance(nestedArray[i]))
}

所以只要實作出一個可以把 [1, 1, 2, 2, 3, 3, 4, 4] 轉成巢狀陣列的 function 就可以了。

這裡就不細說怎麼實作，直接參考原始碼中的註解裡應該就能理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function createNestedArray(arr, unit=4) {
  // 拷貝原陣列
  const copyArr = [...arr]
  // 儲存最後的結果
  const result = []
  // 建立群組
  while(copyArr.length !== 0) {
    // 暫存陣列
    const tempArr = []
    // unit 是多少就會推多少個元素到 tempArr
    // ( 預設是 4 個 )
    for(let i=0; i<unit; i++) {
      tempArr.push(copyArr[i])
    }
    // 推回群組陣列
    result.push(tempArr)
    // 更新陣列內容
    copyArr.splice(0, unit)
  }
  return result
}

最後只要把整個架構組合起來就完成了，這裡一樣附上原始碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function solve(lines) {
  // 轉成數字
  const temp = lines.map(value => value * 1)
  // 移除第一個元素
  temp.splice(0,1)
  // 建立群組陣列 => [[1, 1, 2, 2], [3, 3, 4, 4]]
  const group = createNestedArray(temp)
  // 計算每一組的距離
  for(let i=0; i<group.length; i++) {
    console.log(calculateDistance(group[i]))
  }
}

function createNestedArray(arr, unit=4) {
  // 拷貝原陣列
  const copyArr = [...arr]
  // 儲存最後的結果
  const result = []
  // 建立群組
  while(copyArr.length !== 0) {
    // 暫存陣列
    const tempArr = []
    // 儲存元素
    for(let i=0; i<unit; i++) {
      tempArr.push(copyArr[i])
    }
    // 推回群組陣列
    result.push(tempArr)
    // 更新陣列內容
    copyArr.splice(0, unit)
  }
  return result
}
function calculateDistance(arr) {
  // x 軸
  const x = (arr[0]-arr[2]) ** 2
  // y 軸
  const y = (arr[1]-arr[3]) ** 2
  // 開根號，取小數第二位
  const result = Math.sqrt(x+y).toFixed(2)
  // 回傳結果
  return result
}

Bonus 更簡潔的寫法

只要找出規律，並搭配陣列的內建函式以及解構賦值，可以寫得超簡潔：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function solve(lines) {
  // 轉成數字
  const temp = lines.map(value => value * 1)
  // 全部有幾組
  const total = temp[0]
  // 計算每一組的距離
  for(let i=0; i<total; i++) {
    // i=0 => start=1
    // i=1 => start=5
    // i=2 => start=9
    // ... 
    let start = i*4+1
    // i=0 => slice(1, 5) [1, 1, 2, 2]
    // i=1 => slice(5, 9) [3, 3, 4, 4]
    // ...
    // 搭配解構賦值取出每一點
    const [x1, y1, x2, y2] = temp.slice(start, start+4)
    const distance = calculateDistance(x1, y1, x2, y2)
    console.log(distance)
  }
}
function calculateDistance(x1, y1, x2, y2) {
  const x = Math.pow(x1-x2, 2)
  const y = Math.pow(y1-y2, 2)
  return Math.sqrt(x+y).toFixed(2)
}
凱薩加密 mentor-program-day17
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×