Day 8 - 基礎計概 & 演算法


大學時修計概沒學好,現在慢慢補回來。基本上就是自己整理的筆記貼上來,完全零相關知識來看這篇應該有些部分難懂,不過我都有貼參考資料,有興趣可以連去看看。

程式語言基礎概念

所謂程式語言就是寫給電腦看懂的語言,把要做的事情拆解成一個個步驟,就是寫程式的概念;電腦(或其他裝置)會根據輸入的 code 一條條解讀並行動。


進位制度 Positional notation

常用進位制

  • 十進位 Decimal (簡寫 dec)
  • 二進位 Binary
  • 八進位 Octal (簡寫 oct)
  • 十六進位 Hexadecimal (簡寫 hex)

電腦裡的色碼表示

色碼是十六進位表示法,電腦裡的三原色:紅(Red)、綠(Green)、藍(Blue),每個顏色又細分成 256 個數值(0 到 255 共 256 個數字)。

範例

若 R: 255, G: 255, B: 0
那就是紅色 + 綠色,也就是黃色

經過十六進位轉換後結果
R: FF , G: FF, B: 00,所以色碼是 #FFFF00

#FFFF00
利用線上工具截的圖


二進位 Binary

二進位的 1010 = 2^3 + 2^1 轉換成十進位就是 10

十進位的 56 = 2^5 + 2^4 + 2^3 轉換成二進位 111000

56(十進位)轉換成 111000(二進位)的思路:
  1. 56 和 2 的哪個次方最接近?答 2^5 = 32
  2. 56 減去 32 剩下 24
  3. 對 24 重複 Step 1. & 2. 的處理方式...
  4. 最後可知 56 = 2^5 + 2^4 + 2^3
  5. 再寫得更仔細 56 = 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 0 * 2^0
  6. 所以換到二進位 111000
其他練習

27 = 2^4 + 2^3 + 2^1 + 2^0 -> 11011
32 = 2^5 -> 100000
100 = 2^6 + 2^5 + 2^2 -> 1100100


二位元負數

對應正數按 位元取反再加 1,這樣做的好處是正數負數相加可得到 0

舉例
0   1   1   1   1   1   1   1   =   127
0   0   0   0   0   0   1   0   =   2
0   0   0   0   0   0   0   1   =   1
0   0   0   0   0   0   0   0   =   0
1   1   1   1   1   1   1   1   =   −1
1   1   1   1   1   1   1   0   =   −2
1   0   0   0   0   0   0   1   =   −127
1   0   0   0   0   0   0   0   =   −128

浮點數

[C&C++] 浮點數精準度 (Floating-Point Precision)

使用浮點數最最基本的觀念


儲存空間單位

電腦的最小單位為 Bit (位元)

  • 1 Byte = 8 Bits,Byte 又稱位元組
  • 1 Kilobyte (KB) = 1024 Bytes
  • 1 Megabyte (MB) = 1024 KB
  • 1 Gigabyte (GB) = 1024 MB
  • 1 Terabyte (TB) = 1024 GB
  • 1 Petabyte (PB) = 1024 TB
  • 1 Exabyte (EB) = 1024 PB
  • 1 Zettabyte (ZB) = 1024 EB
  • 1 Yottabyte (YB) = 1024 ZB

參考:
文件大小


電腦語言

重要觀念:電腦只看得懂機器語言(二進位的 0101...)

組合語言(assembly language):接近電腦底層的組合語言,一個指令只做一兩件事情,只翻譯成 機器語言

編譯器(compiler):一種電腦程式,它會將某種程式語言寫成的原始碼(原始語言)轉換成另一種程式語言(目標語言)。可以想成是翻譯器,把人類容易看懂的內容轉換成電腦能讀懂的內容。

逆向工程:透過反組譯(disassemble)將機器語言轉換為組合語言,與編譯器所做的事情相反。用這個方法可以知道電腦程式的內容,甚至可以修改其中內容而變成破解版的程式。


演算法 Algorithm

演算法簡單來說就是解決問題的方法

輸入 + 演算法 = 輸出

複雜度 來衡量演算法的好壞,分兩類

  • 時間複雜度(Time Complexity):演算法需要消耗的時間資源。
  • 空間複雜度(Space Complexity):演算法需要消耗的空間資源。

參考:
圖形動畫講解演算法 VisuAlgo
基礎電腦科學:演算法概要
【演算法】時間複雜度與空間複雜度Time & Space Complexity


時間複雜度(Time Complexity)

通常使用 Big O notation 大 O 符號 來表示時間複雜度。

Big-O Complexity Chart
圖源

參考:
Complexity:Asymptotic Notation(漸進符號)


搜尋法

二分搜尋法:每次都切一半來找目。

排序演算法(Sorting algorithm)

選擇排序法(Selection sort)
  1. 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
  2. 再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。
  3. 以此類推,直到所有元素均排序完畢。
泡沫排序法(Bubble sort)
  1. 從序列第一個元素開始往後比較。
  2. 若後面的比現在挑中的還大,那就把挑中的元素換成該數繼續往後比;若後面的比現在挑中的還小,那就把兩者順序對調然後再和下一個數字比。
  3. 重複以上步驟直到排序結束。
插入排序法(Insertion sort)

和撲克牌排序方式一樣。

合併排序
  1. 將陣列分割直到只有一個元素。
  2. 開始兩兩合併,每次合併同時進行排序,合併出排序過的陣列。
  3. 重複 2 的動作直接全部合併完成。
快速排序
  1. 挑選基準值:從數列中挑出一個元素,稱為「基準」(pivot),
  2. 分割:重新排序數列,所有比基準值小的元素擺放在基準前面,所有比基準值大的元素擺在基準後面(與基準值相等的數可以到任何一邊)。在這個分割結束之後,對基準值的排序就已經完成,
  3. 遞迴排序子序列:遞迴地將小於基準值元素的子序列和大於基準值元素的子序列排序。

參考:
【演算法】排序演算法 Sorting Algorithm

#Computer #計算機概論 #演算法 #二進位 #learning






你可能感興趣的文章

CS50 Tries

CS50 Tries

python迴圈

python迴圈

Vue.js 學習旅程Mile 14 – Form Input Bindings 表單綁定篇:v-model

Vue.js 學習旅程Mile 14 – Form Input Bindings 表單綁定篇:v-model






留言討論