# [CS101] 初心者的計概與 coding 火球術

###### tags:`Algorithm`
[TOC]

## 程式碼不是重點，解決問題才是
透過逐步拆解，把大問題分成小問題來解決 => 條列式列出步驟來達成。例如用函式來把重複性高的地方獨立出來，外加作為整體的解決結構。

#### 小作業
給你一個亂數的數列，例如說：1, 8, 9, 2, 5 ,4，你能想出什麼步驟把這些數字由小到大排好嗎？
請用本堂課程教的寫法把解法寫出來。或者用自己的話講也可以

假設有min, tmp, i = 0 三個變數
設 min = arr[i]
if min > arr[i+1]，則把 arr[i]和 arr[i+1]的值互換，也就是 arr[i] = arr[i+1], arr[i+1] = min
else min < arr[i+1]，則不做動作
i++
檢查 i 是否 < 5，是則結束迴圈，印出 arr，否則跳回第2行

第一次的內迴圈如上↑，剩下２３４５次迴圈原理同上

## command line
GUI, 圖形化的使用者介面
CLI, 文字的使用者介面
* Terminal.app (MAC)
* cmd.exe (Windows)

### 常用 command line 指令

筆記整合在[[CMD101] Command Line 超新手入門](https://hackmd.io/@ouR5x-oVSMy4d8R5uFsKNg/BJ2Bdjl8_)

## 電腦中的資料儲存與表示方法

> 這世界上只有 10 種人，一種是懂二進位的人，另一種是不懂二進位的人

### 電腦中的容量儲存單位
* 8 bit = 1 byte
* K, kilobyte, kilo = 1000, 1KB = 1024 byte (規定的用法)
* M, megabyte, 1 MB = 1024 KB
* G, gigabyte, 1GB = 1024 MB
* T

### 數字的儲存

* 電腦的記憶體空間有限，根據使用的程式語言不同，不同 data type 有不同的大小限制。
* 假如用 32 bit 來存放整數，那麼正整數會有 2^31-1 個，負整數會有 2^31個，也可以進一步推論得到 「最後一個 bit (第32bit） 是'0'/'1'」可以用來判斷正數或負數，因為正整數最多只會存在於第 1-31 bit，第 32 bit 必為 '0'，負整數再根據下面的儲存規則，可以知道第 32 bit 必為'1'.
* 負數的儲存方式：把正數的所有位元顛倒之後加1，這麼做的好處是運算方便，這樣一來，相同的值(正負數)相加之後會是 0，最後一個 bit 會 overflow (1 => 0)
* 如果負數的儲存方式只是把正數的位元顛倒的話，正負數相加之後會全部都是 111111...，做 +1 bit 的目的是為了讓全部的儲存空間都變成 (1)0000...，只在最後一位 bit overflow.

* 

### 小數的儲存方式


根據 IEEE 754 規則，小數 0.001234 = 0.1234*10(-2)，藍色框放 +-，綠色框放 -2，紅色框放 1234

小數的儲存方式有 float, double 兩種 type

#### 補充資料
[浮點數精準度 (Floating-Point Precision)的問題](https://cg2010studio.com/2012/03/30/cc-%E6%B5%AE%E9%BB%9E%E6%95%B8%E7%B2%BE%E6%BA%96%E5%BA%A6-floating-point-precision/)
[使用浮點數最最基本的觀念](http://blog.dcview.com/article.php?a=VmhQNVY%2BCzo%3D)

## 網路基礎概論
VPN:先連到某個地方在連到另一個地方

內網:只在特定範圍內有效的IP，這裡的範圍指的是使用私有IP的電腦

## 演算法

演算法就是「解決問題的方法」

### 如何衡量演算法的好壞

* 時間複雜度
一個演算法**平均**要花多少**時間**才能完成
* 空間複雜度
一個演算法**平均**要花多少**空間**才能完成

### 選擇排序法 Selection sort

從**還沒排序好**的數列裡找出最小的值，把最小的值移到最左邊

function selection(arr){
  for(let i = 0; i < arr.length-1; i++){
    let min = arr[i];
    let index;
    for(let j = i+1; j < arr.length; j++){ //找出最小值
      if(arr[j] < min){
        min = arr[j]
        index = j
      }
    }
    arr[index] = arr[i] //switch
    arr[i] = min
console.log(arr)
  }
  return arr
}
let arr = [29,10,14,37,14]
console.log(selection(arr))

### bubble sort

左右相比，比較大的數字 switch 到右邊

function bubble(arr){
  for(let j = 0; j < arr.length-1-j; j++){
    for(let i = 0; i < arr.length-1; i++){
      let max = arr[i];
      let tmp = arr[i+1];
      if(arr[i+1] < max){
        arr[i+1] = arr[i]
        arr[i] = tmp
      }
console.log(arr)
    }
  }
  return arr
}
let arr = [29,10,14,37,14]
console.log(bubble(arr))

### insertion sort

依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置

// 這邊的 pattern 可以對照紙本筆記的規律圖來看會比較好理解
function insertSort(arr){
    for(let i = 0; i < arr.length; i++){
        for(let j = 0; j < i+1; j++){
            if(arr[i+1-j] < arr[i-j]){insert(arr, i+1-j, i-j)} //這一步可以再精簡，等找到該插入的位置再做 insert() 就好
            else{break}
        }
    }
    return arr
}
let arr = [29,10,14,37,14,0,13,24,39,11]
console.log(insertSort(arr))

function insert(arr, from, to){ //把 index 第 from 的值，插入第 to 的值
    let tmp = arr[to]
    arr[to] = arr[from]
    for(let i = 0; i < from - to -1; i++){
      arr[from - i] = arr[from - i - 1]
    }
    arr[to + 1] = tmp
    return arr
  }

### merge sort
把一個數列切割成左右兩半，分別排列之後再合併
遞迴
> 還是不會

### quick sort
從最左邊挑一個基準點，讓左邊的數字都小於它，右邊的數字都大於它
> 還是不會