程式導師實驗計畫 week 2 題目與解答

hw1 印出星星

  printStars(n) {
    let star = '*'
    for (let i=1; i<n; i++) {
      console.log(i)      
    }
  }

  printStars(5)

hw2 首字母大寫

Method 1 (盡量不用內建函式)：

// a:97...z:122，A:65 ... Z:90
function CapitalizeStr(str) { 
    let FirstLetter = ''
    let remainingStr = ''
    if (str.charCodeAt(0) >= 97 &&
            str.charCodeAt(0) <= 122
    ) {
            FirstLetter = String.fromCharCode(str.charCodeAt(0) - 32 )
            for (let i=1; i < str.length; i++) {
                remainingStr += str[i]
        }
        return FirstLetter + remainingStr
    }
    return str
}
console.log(CapitalizeStr('abcde'))

Method 2 (使用內建函式)：

function capitalize(str) {
    return str[0].toUpperCase() + str.slice(1);
}

console.log(capitalize('abcde'))

hw3 反轉字串

function reverseStr(str) {
    let result = ''
    for (let i=str.length-1; i >= 0 ; i--) {
        result += str[i]
    }
    console.log(result)
}

hw4 印出因數

function printFactor(n) {
    for (let i=1; i<= n; i++) {
        if (n % i === 0) {
            console.log(i)
        }
    }
}

printFactor(30)

hw5 自己的函式自己寫

• join

Method 1：

function join(arr, separator) {
  let temp = ''
  if (arr.length === 1) {
    temp = arr[0] + separator
  } else {
    for (let i = 0; i < arr.length; i++) {
      if (i === arr.length - 1) {
        temp += arr[i]
      } else {
        temp += arr[i] + separator
      }
    }
  }
  return temp
}

console.log(join(['a', 'b', 'c'], '!'))

Method 2：

// 方法二
function join2(arr, separator) {
    let temp = arr[0]
    for (let i=1; i<arr.length; i++) {
        temp += separator + arr[i]
    }
    return temp
}
console.log(join2(['a', 'b', 'c', 'd'], '!'))

• repeat

function repeat(str, times) {
    let result = ''
    for (let i=1; i<=times; i++) {
        result += str
    }
    return result
}

console.log(repeat('yo', 3))

hw6 假裝自己是 JS 引擎

function isValid(arr) {
  for(var i=0; i<arr.length; i++) {
    if (arr[i] <= 0) return 'invalid'
  }
  for(var i=2; i<arr.length; i++) {
    if (arr[i] !== arr[i-1] + arr[i-2]) return 'invalid'
  }
  return 'valid'
}

isValid([3, 5, 8, 13, 22, 35])

判斷陣列中前 2 個數相加，是否皆等於第 3 個數

1. 執行第 11 行，呼叫 isValid 函式，傳入陣列 [3, 5, 8, 13, 22, 35]。
2. 執行第 2 行，設定變數 i 為 0。
3. 執行第 2 行，判斷 i 是否小於 arr 的陣列長度 (6)，是，繼續執行，進入迴圈。
4. 執行第 3 行，如果陣列的 (i+1) 位數的數字 (arr[i])，小於等於 0，回傳 'invalid'；如果大於 0 則繼續執行。
5. 執行第 2 行，i 加 1。
6. 重複 3 ~ 5 步驟，直到 6 次迴圈結束。
7. 執行第 5 行，設定變數 i 為 2。
8. 執行第 5 行，判斷 i 是否小於 arr 的陣列長度 (6)，是，繼續執行，進入迴圈。
9. 執行第 6 行，如果陣列的 (i+1) 位數的數字 (arr[i])，不等於「陣列的 (i) 位數的數字 (arr[i-1])」 以及「陣列的 (i-1) 位數的數字 (arr[i-2])」的總和，回傳 'invalid'；如果是，則繼續執行。
10. 執行第 5 行，i 加 1。
11. 重複 8 ~ 10 步驟，直到 3 次迴圈的第 9 步驟不符合條件，回傳 'invalid'。
12. 結束程式。
    
    

挑戰題

二分搜尋法

var readline = require('readline');

var lines = []
var rl = readline.createInterface({
  input: process.stdin
});

rl.on('line', function (line) {
  lines.push(line)
});

rl.on('close', function() {
  solve(lines)
})

function solve(lines) {
    let line1 = lines[0].split(' ')
    let arrLength = Number(line1[0])
    let targetBeginIndex = arrLength + 1
    let targetAmount = Number(line1[1])
    let arr = []
    for (let i=1; i <=arrLength; i++) {
      arr.push(lines[i])
    }

    for (let j = targetBeginIndex; j < targetBeginIndex + targetAmount; j++) {
      console.log(binarySearch(arr, Number(lines[j])))
    }
}

function binarySearch(arr, target) {
    let L = 0
    let R = arr.length - 1
    while (L <= R) {
        let M = Math.floor((L+R)/2)
        if (arr[M] == target) {
            return M
        } else if (arr[M] > target) {
            R = M -1
        } else {
            L = M + 1
        }
    }
    return -1
}

超級挑戰題 (走迷宮)

廣度優先搜尋法

廣度優先搜尋法（Breadth-First Search, BFS）是一種樹（Tree）或圖（Graph）資料結構的搜索演算法，從圖的某一節點(vertex, node) 開始走訪，接著走訪此一節點所有相鄰且未拜訪過的節點，才進一步走訪下一層級的節點。可應用於有向圖與無向圖的搜尋。

• Find Maze Shortest Exit Path
• 廣度優先搜尋法