2017年9月21日

[演算法] Caesar Cipher: 往後或往前推移英文字母

      , , ,  
此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

問題描述

Caesar Cipher 要做的事，是把輸入的字串根據所給定的數值往前／後推幾位，例如輸入字串 a 和數字 2，則會把 a 往後推兩位，於是要回傳 c。
function caesarCipher (str, num) {...}

caesarCipher ('zoo keeper', 2)     // bqq mggrgt

前置知識

在實做這個演算法前，我們先來瞭解一下 ASCII Code。由於電腦實際上指認得數字，並不認得我們所輸入的字母，而 ASCII Code 簡單來說，就是英文字母和數字的轉換表。
舉例來說，英文字母 a 對應到的十進位代碼就是 97； A 對應到的十進位代碼則是 65；o 對應到的十進位代碼就是 111。
從下面的 ASCII Table 中我們可以看到大寫的英文字母分別對應到 65-90；小寫的英文字母分別對應到 97-122。
透過 JavaScript 函式，我們可以很容易地將字母與數值做轉換：
String.prototype.charCodeAt(index)
透過 String.prototype.charCodeAt(index) 這個函式，我們可以將英文字母轉為 ASCII Code：
'Aao'.charCodeAt(0)          // A 是 65
'Aao'.charCodeAt(1)          // a 是 97
'Aao'.charCodeAt(2)          // o 是 111
String.fromCharCode(num1[, …[, numN]])
透過 String.fromCharCode(num1[, ...[, numN]]) 我們則可以將數值轉換成回字串：
String.fromCharCode(65, 97, 111)      // Aao
ASCII @ 維基百科
String.prototype.charCodeAt(index) @ MDN
String.fromCharCode(num1[, …[, numN]]) @ MDN

演算法實做

這個演算法中比較麻煩的部分是函式後第二個數值沒有限制正負和數值大小，因此如果原本的字串是 a ，數值是 1 ，則回傳 b ；數值如果是 -1，則回傳 z。
因此我們必須先把輸入的數值限制在某一個範圍內，由於英文字母有 26 個，我們可以透過餘數的使用讓 num 的值限制在 -25 ~ 25 之間：
function caesarCipher (str, num) {
  num = num % 26        // num: -25 ~ 25
}
再來我們要分別去跑 str 裡面的每一個字母做轉換：
function caesarCipher (str, num) {
  /* ... */
  
  for (let i = 0; i < str.length; i++) {
    let currentCharCode = str.charCodeAt(i)
  }
}
大寫英文字母的 ASCII Code 65 ~ 90；小寫英文字母的 ASCII Code 97 ~ 122。
針對大寫英文字母，因為 num 會介於 -25 到 25 之間，而大寫英文字母會介於 65 到 90 之間，所以 newCharCode 將會介於 40 ~ 115 之間。
如果 newCharCode 小於 65 的話，那麼要加 26 讓它重新介於 65 以上；如果 newCharCode 大於 90 的話，那麼要減 26 讓它重新介於 90 以下：
if (currentCharCode >= 65 && currentCharCode <= 90) {
  // 大寫英文字母轉換
  newCharCode = currentCharCode + num  // newCharCode: 40 ~ 115
  if (newCharCode < 65) {
    newCharCode = newCharCode + 26
  } else if (newCharCode > 90) {
    newCharCode = newCharCode - 26
  }
}
同樣的道理，針對小寫英文字母的轉換：
else if (currentCharCode >= 97 && currentCharCode <= 122) {
  // 小寫英文字母轉換
  newCharCode = currentCharCode + num
  if (newCharCode < 97) {
    newCharCode = newCharCode + 26
  } else if (newCharCode > 122) {
    newCharCode = newCharCode - 26
  }
}

完整程式碼

function caesarCipher (str, num) {
  let newString = []
  num = num % 26      // num: 0 ~ 25
  
  for (let i = 0; i < str.length; i++) {
    let currentCharCode = str.charCodeAt(i)
    let newCharCode
    
    /**
     * 大寫英文字母的 ASCII Code 65 ~ 90
     * 小寫英文字母的 ASCII Code 97 ~ 122
    **/
    
    if (currentCharCode >= 65 && currentCharCode <= 90) {
      // 大寫英文字母轉換
      newCharCode = currentCharCode + num
      if (newCharCode < 65) {
        newCharCode = newCharCode + 26
      } else if (newCharCode > 90) {
        newCharCode = newCharCode - 26
      }
    } else if (currentCharCode >= 97 && currentCharCode <= 122) {
      // 小寫英文字母轉換
      newCharCode = currentCharCode + num
      if (newCharCode < 97) {
        newCharCode = newCharCode + 26
      } else if (newCharCode > 122) {
        newCharCode = newCharCode - 26
      }
    } else {
      // 其餘保留原樣
       newCharCode = currentCharCode
    }
    
    newString.push(String.fromCharCode(newCharCode))
  }
  return newString.join('')
  
}

console.log(caesarCipher('Zoo Keeper', 2))    //  Bqq Mggrgt
console.log(caesarCipher('Big Car', -16))    //  Lsq Mkb
console.log(caesarCipher('JavaScript', -900))    //  TkfkCmbszd

資料來源

延伸閱讀

0 意見:

張貼留言