內容選單標籤

2023年10月25日 星期三

Python Programming Bible 自學聖經 碁峰 by 文淵閣 AND w3schools/python (重點整理)

高雄市高中職學生 - "飆程式網"

http://khcode.m-school.tw/

 

Code Judger
https://www.codejudger.com/

 

 

建置開發環境


到官網 https://www.python.org/  下載 python ,並進行安裝(Cpython)。
及如何執行寫好的 python 程式。


Anaconda 附帶 Jupyter Notebook 從程式碼編寫到執行都可完成。


0. 到 python 官方網站,測試指令

1.下載並安裝 python

2. IDLE 測指令

3. IDLE完整程式並執行

4. 文字模式執行程式

 

IDLE
I
ntegrated Development and Learning Environment

 

>>> import this
The Zen of Python, by Tim Peters


python 程式執行方法

1.互動模式 interactive mode
kk@ubun:~$ python3
Python 3.10.12 (main, Nov 20 2023, 15:14:05) [GCC 11.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.

>>>        表示完成啟動

 
>>> x=3+6
>>> x
9
不使用print(),也能顯示輸入訊息
ctrl+z    離開互動模式

 

2.腳本模式 script mode
kk@ubun:~$ mkdir MyPython
kk@ubun:~$ cd MyPython
kk@ubun:~/MyPython$ vi 01.py
x=3+6
print(x)

kk@ubun:~/MyPython$ python3 01.py
9







資料型別 DataType

  • 數值 Number

>>> type(3)
<class 'int'>


>>> x=6
>>> type(x)
<class 'int'>


type(3.14)
<class 'float'>


數學中的複數,用「i」來表示虛數的部份,而在Python當中則是用「j」或是「J」來表示
複數Complex  = 實部 real + 虛部 imaginary

c=3+5j
type(c)
<class 'complex'>
c.real    #實數
3.0
c.imag    #虛數
5.0



  •  字串String

type("Hello")
<class 'str'>


  • Sequence Types:

Lst=[3,5,7]
type(Lst)
<class 'list'>

 

# 串列 list 元素可為任意不同型別,C/C++ 陣列 Array 元素型別需相同 

串列 List 使用-------------------------------------------------------- 

Lst=["A","B"]
Lst*2
['A', 'B', 'A', 'B']

 

Lst=['A','B','C','D','E','F','G']

#串列元素數目
len(Lst)
7

 

#切片Slicing :由 list 中切出一個 list 片段

#取出第1個索引值到第5個索引值
Lst[1:5]
['B', 'C', 'D', 'E']
 

#取出第1個索引值到第5個索引值,間隔2
Lst[1:5:2]
['B', 'D']


#字串轉入List

Lst=list("ABCDEF")
Lst
['A', 'B', 'C', 'D', 'E', 'F'] 

 

Lst=[]
for i in "ABCDEF":
    Lst.append(i)   

Lst
['A', 'B', 'C', 'D', 'E', 'F']


Lst=[]
Lst[0:]="ABCDEF"
Lst
['A', 'B', 'C', 'D', 'E', 'F']



Lst=list("A B C D E F")
Lst
['A', ' ', 'B', ' ', 'C', ' ', 'D', ' ', 'E', ' ', 'F']    #多空白鍵

Lst=[i for i in "A B C D E F".split()]
Lst
['A', 'B', 'C', 'D', 'E', 'F']



#List轉成字串

Lst=['A','B','C','D','E','F']
Str=','.join(i for i in Lst)
Str
'A,B,C,D,E,F' 

Str=''.join(i for i in Lst)
Str
'ABCDEF'

Lst=[1,2,3,4,5]
Str='-'.join(str(i) for i in Lst)
Str
'1-2-3-4-5'





#排序與反轉

Lst=[2,1,5,3,4]

sorted(Lst)
[1, 2, 3, 4, 5]

Lst
[2, 1, 5, 3, 4]

Lst.sort()
Lst
[1, 2, 3, 4, 5]

Lst.reverse()
Lst
[5, 4, 3, 2, 1]


Lst[::-1]
[1, 2, 3, 4, 5]




字串操作

Str="ABCDE"

Str[0]
'A'

Str[4]
'E'

Str[0:1]
'A'

Str[4:5]
'E'


for i in Str:
    print(i,end=" ")
    
A B C D E


len(Str)
5

for i in range(len(Str)):
    print(Str[i],end=" ")
    
A B C D E 


for i in range(len(Str)):
    print(Str[i:i+1],end=" ") 
 
A B C D E

 

#字串反轉
for i in range(len(Str),-1,-1):
    print(Str[i:i+1],end=" ")
    
 E D C B A


for i in range(len(Str)-1,-1,-1):
    print(Str[i],end=" ")

   
E D C B A



Str
'ABCDE'

#index:0,1,2,3,4

Str[0]
'A'


Str[4]
'E'

#反轉 index:-1,-2,-3,-4,-5
Str[-1]
'E'


Str[-5]
'A'


range(start, stop[, step])
start: 計數從start 開始。預設是從0 開始。例如range(5)等價於range(0, 5);
stop: 計數到stop 結束,但不包括stop。例如:range(0, 5) 是[0, 1, 2, 3, 4]沒有5
step:步長,預設為1。例如:range(0, 5) 等價於range(0, 5, 1)

for i in range(0,5,1):
    print(i,end=" ")

   
0 1 2 3 4 


for i in range(4,-1,-1):
    print(i,end=" ")
    
4 3 2 1 0

 

-------------------------------------------------------- 


#元組 tuple 可視為其中元素不可更改的 list


Tpl=(3,5,7)
type(Tpl)
<class 'tuple'>


Rng=range(0,5+1)
type(Rng)
<class 'range'>


  • Mapping Type:

Dic={0:"Sun",1:"Mon"}
type(Dic)
<class 'dict'>


  • Set Types:

mySet={"Sun","Mon"}
type(mySet)
<class 'set'>



  • 布林值 Boolean

type(True)
<class 'bool'>
type(False)
<class 'bool'>



  • Binary Types:

x=b"Hello"
type(x)
<class 'bytes'>


  • None Type:

x=None
type(x)
<class 'NoneType'>

 

 

 


變數 Variable 與常數 Constant


變數
---------------------------------
程式執行過程中,可以被改變的資料
x=3
x=x+2
print(x)
5



常數
---------------------------------
程式執行過程中,不能被改變的資料
import math
type(math)
<class 'module'>


dir()
['__annotations__', '__builtins__', '__doc__', '__loader__', '__name__', '__package__', '__spec__', 'math']


dir(math)
['__doc__', '__loader__', '__name__', '__package__', '__spec__', 'acos', 'acosh', 'asin', 'asinh', 'atan', 'atan2', 'atanh', 'cbrt', 'ceil', 'comb', 'copysign', 'cos', 'cosh', 'degrees', 'dist', 'e', 'erf', 'erfc', 'exp', 'exp2', 'expm1', 'fabs', 'factorial', 'floor', 'fmod', 'frexp', 'fsum', 'gamma', 'gcd', 'hypot', 'inf', 'isclose', 'isfinite', 'isinf', 'isnan', 'isqrt', 'lcm', 'ldexp', 'lgamma', 'log', 'log10', 'log1p', 'log2', 'modf', 'nan', 'nextafter', 'perm', 'pi', 'pow', 'prod', 'radians', 'remainder', 'sin', 'sinh', 'sqrt', 'tan', 'tanh', 'tau', 'trunc', 'ulp']

math.pi
3.141592653589793



 變數命名規則
---------------------------------
變數名稱第一個字元,必須是英文字母、底線或中文(不建議),後即可搭配數字
變數名稱區分大小寫
不能使用python內建的保留字:關鍵字 keyword、指令


import keyword
dir()
['__annotations__', '__builtins__', '__doc__', '__loader__', '__name__', '__package__', '__spec__', 'keyword']

type(keyword)
<class 'module'>

dir(keyword)
['__all__', '__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'iskeyword', 'issoftkeyword', 'kwlist', 'softkwlist']


#列出  keyword
keyword.kwlist
['False', 'None', 'True', 'and', 'as', 'assert', 'async', 'await', 'break', 'class', 'continue', 'def', 'del', 'elif', 'else', 'except', 'finally', 'for', 'from', 'global', 'if', 'import', 'in', 'is', 'lambda', 'nonlocal', 'not', 'or', 'pass', 'raise', 'return', 'try', 'while', 'with', 'yield']


keyword.iskeyword("else")
True

keyword.iskeyword("name")
False
 

 

+++++++++++++++++++++++++++++++++++++++++++++++++++++ 

 內建函式 builtin_function_or_method

###  dir()的用途是用於用來查詢物件的全部屬性。
如果 dir() 的括弧內不帶任何參數物件,執行結果則會最大限度地顯示出當前範圍內的變數、方法和屬性列表。

dir()
['__annotations__', '__builtins__', '__doc__', '__loader__', '__name__', '__package__', '__spec__']


dir(__builtins__)
...  'abs', 'aiter', 'all', 'anext', 'any', 'ascii', 'bin', 'bool', 'breakpoint', 'bytearray', 'bytes', 'callable', 'chr', 'classmethod', 'compile', 'complex', 'copyright', 'credits', 'delattr', 'dict', 'dir', 'divmod', 'enumerate', 'eval', 'exec', 'exit', 'filter', 'float', 'format', 'frozenset', 'getattr', 'globals', 'hasattr', 'hash', 'help', 'hex', 'id', 'input', 'int', 'isinstance', 'issubclass', 'iter', 'len', 'license', 'list', 'locals', 'map', 'max', 'memoryview', 'min', 'next', 'object', 'oct', 'open', 'ord', 'pow', 'print', 'property', 'quit', 'range', 'repr', 'reversed', 'round', 'set', 'setattr', 'slice', 'sorted', 'staticmethod', 'str', 'sum', 'super', 'tuple', 'type', 'vars', 'zip'

 type(str)
<class 'type'>

dir(str)
...  'capitalize', 'casefold', 'center', 'count', 'encode', 'endswith', 'expandtabs', 'find', 'format', 'format_map', 'index', 'isalnum', 'isalpha', 'isascii', 'isdecimal', 'isdigit', 'isidentifier', 'islower', 'isnumeric', 'isprintable', 'isspace', 'istitle', 'isupper', 'join', 'ljust', 'lower', 'lstrip', 'maketrans', 'partition', 'removeprefix', 'removesuffix', 'replace', 'rfind', 'rindex', 'rjust', 'rpartition', 'rsplit', 'rstrip', 'split', 'splitlines', 'startswith', 'strip', 'swapcase', 'title', 'translate', 'upper', 'zfill']

 type(str.upper)
<class 'method_descriptor'>

 str.upper("abc")
'ABC'

 

#Unicode 轉字元
chr(65)
'A'

#字元轉 Unicode
ord("A")
65

 

 

###  help(): 用於查看函式或模組用途的詳細說明。

help("str")
Help on class str in module builtins:

class str(object)
 |  str(object='') -> str
 |  str(bytes_or_buffer[, encoding[, errors]]) -> str
 |  
 |  Create a new string object from the given object. If encoding or
 |  errors is specified, then the object must expose a data buffer
 |  that will be decoded using the given encoding and error handler.
 |  Otherwise, returns the result of object.__str__() (if defined)
 |  or repr(object).
 |  encoding defaults to sys.getdefaultencoding().
 |  errors defaults to 'strict'.
 |  
 |  Methods defined here:
...略
|  upper(self, /)
|      Return a copy of the string converted to uppercase.

 

 

type(print)
<class 'builtin_function_or_method'>

dir(print)
['__call__', '__class__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getstate__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__module__', '__name__', '__ne__', '__new__', '__qualname__', '__reduce__', '__reduce_ex__', '__repr__', '__self__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__text_signature__']
 

help("print")
Help on built-in function print in module builtins:

print(*args, sep=' ', end='\n', file=None, flush=False)
    Prints the values to a stream, or to sys.stdout by default.
    
    sep
      string inserted between values, default a space.
    end
      string appended after the last value, default a newline.
    file
      a file-like object (stream); defaults to the current sys.stdout.
    flush
      whether to forcibly flush the stream.






 模組 modules

dir()
['__annotations__', '__builtins__', '__doc__', '__loader__', '__name__', '__package__', '__spec__']


import math
dir()
['__annotations__', '__builtins__', '__doc__', '__loader__', '__name__', '__package__', '__spec__', 'math']


dir(math)
['__doc__', '__loader__', '__name__', '__package__', '__spec__', 'acos', 'acosh', 'asin', 'asinh', 'atan', 'atan2', 'atanh', 'cbrt', 'ceil', 'comb', 'copysign', 'cos', 'cosh', 'degrees', 'dist', 'e', 'erf', 'erfc', 'exp', 'exp2', 'expm1', 'fabs', 'factorial', 'floor', 'fmod', 'frexp', 'fsum', 'gamma', 'gcd', 'hypot', 'inf', 'isclose', 'isfinite', 'isinf', 'isnan', 'isqrt', 'lcm', 'ldexp', 'lgamma', 'log', 'log10', 'log1p', 'log2', 'modf', 'nan', 'nextafter', 'perm', 'pi', 'pow', 'prod', 'radians', 'remainder', 'sin', 'sinh', 'sqrt', 'tan', 'tanh', 'tau', 'trunc', 'ulp']


math.pi
3.141592653589793 


help("modules")
Please wait a moment while I gather a list of all available modules...
... math    numpy    os    pip    ...略


    




 

 軟體包 packages

PIP is a package manager for Python packages, or modules if you like.
pip 是 Python 包管理工具,該工具提供了對Python 包的查找、下載、安装、卸載的功能。
可以透過以下命令来判斷是否已安装:

C:\Users\User>pip list
Package            Version
------------------ ----------
certifi            2023.5.7
charset-normalizer 3.1.0
colorama           0.4.6
decorator          4.4.2
ffmpeg             1.4
idna               3.4
imageio            2.30.0
imageio-ffmpeg     0.4.8
moviepy            1.0.3
numpy              1.24.3
Pillow             9.5.0
pip                23.3.1
proglog            0.1.10
pygame             2.4.0
pytube             15.0.0
requests           2.31.0
setuptools         65.5.0
tk                 0.1.0
tqdm               4.65.0
urllib3            2.0.2
youtube-dl         2021.12.17


C:\Users\User>pip install django
Collecting django
  Downloading Django-4.2.7-py3-none-any.whl.metadata (4.1 kB)
Collecting asgiref<4,>=3.6.0 (from django)
  Downloading asgiref-3.7.2-py3-none-any.whl.metadata (9.2 kB)
Collecting sqlparse>=0.3.1 (from django)
  Downloading sqlparse-0.4.4-py3-none-any.whl (41 kB)
     ---------------------------------------- 41.2/41.2 kB 499.1 kB/s eta 0:00:00
Collecting tzdata (from django)
  Downloading tzdata-2023.3-py2.py3-none-any.whl (341 kB)
     ---------------------------------------- 341.8/341.8 kB 732.0 kB/s eta 0:00:00
Downloading Django-4.2.7-py3-none-any.whl (8.0 MB)
   ---------------------------------------- 8.0/8.0 MB 2.3 MB/s eta 0:00:00
Downloading asgiref-3.7.2-py3-none-any.whl (24 kB)
Installing collected packages: tzdata, sqlparse, asgiref, django
Successfully installed asgiref-3.7.2 django-4.2.7 sqlparse-0.4.4 tzdata-2023.3

 

C:\Users\User>pip list
Package            Version
------------------ ----------
asgiref            3.7.2
certifi            2023.5.7
charset-normalizer 3.1.0
colorama           0.4.6
decorator          4.4.2
Django             4.2.7
ffmpeg             1.4
idna               3.4
imageio            2.30.0
imageio-ffmpeg     0.4.8
moviepy            1.0.3
numpy              1.24.3
Pillow             9.5.0
pip                23.3.1
proglog            0.1.10
pygame             2.4.0
pytube             15.0.0
requests           2.31.0
setuptools         65.5.0
sqlparse           0.4.4
tk                 0.1.0
tqdm               4.65.0
tzdata             2023.3
urllib3            2.0.2
youtube-dl         2021.12.17


dir()
['__annotations__', '__builtins__', '__doc__', '__loader__', '__name__', '__package__', '__spec__']


import django
dir()
['__annotations__', '__builtins__', '__doc__', '__loader__', '__name__', '__package__', '__spec__', 'django']

dir(django)
['VERSION', '__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__path__', '__spec__', '__version__', 'get_version', 'setup', 'utils']
 

type(django)
<class 'module'>

  

+++++++++++++++++++++++++++++++++++++++++++++++++++++






運算子 OPerators
 

 Arithmetic Operators:
 

#加
15+7
22

#減
15-7
8

#乘
15*7
105

#除
15/7
2.142857142857143

#兩數相除取餘數
15%7
1

#取得整除的商
15//7
2

#次方
15**7
170859375 

 

 

Assignment Operators:
x=5
x+=3
x
8

x=5
x-=3
x
2

x=5
x*=3
x
15

x=5
x/=3
x
1.6666666666666667

x=5
x%=3
x
2

x=5
x//=3
x
1

x=5
x**=3
x
125

 



Comparison Operators

#等於
5==3
False

#不等於
5!=3
True

5>3
True

5<3
False

5>=3
True

5<=3
False


Logical Operators

x=5
x>3 and x<10
True

x>3 or x<10
True

not(x>3 or x<10)
False


Identity Operators
x=3;y=5
x is y
False

x is not y
True


Membership Operators
Lst=["A","B"]
"A" in Lst
True

"A" not in Lst
False


Bitwise Operators

bin(3)
'0b11'

bin(2)
'0b10'

3&2    //二進制 10
2

3|2    //二進制 11
3

3^2    //二進制 01
1

~3    // 3的二進制 0011,反向1100,第一碼1所以是負數,後三碼100即十進制4
-4

12>>3    //右移 除 2**3
3

12<<3    //左移 乘 2**3
96








優先順序:
()

**

+x  -x  ~x

*  /  //  %

+  -

<<  >>

&

^

|

==  !=  >  >=  <  <=  is   is not   in   not in

not

and

or




程式流程控制

If ... Else

help("if")
The "if" statement
******************

The "if" statement is used for conditional execution:

   if_stmt ::= "if" assignment_expression ":" suite
               ("elif" assignment_expression ":" suite)*
               ["else" ":" suite]

 

if 3<6:
    True
--------------- 
True

Short Hand If
if 3<6:True
---------------
True

 

if 3<6:
    True
else:
    False
---------------   
True

 

Short Hand If ... Else
True if 3<6 else False
--------------
True


while Loop

 help("while")
The "while" statement
*********************

The "while" statement is used for repeated execution as long as an
expression is true:

   while_stmt ::= "while" assignment_expression ":" suite
                  ["else" ":" suite]

 

x=0
while x<=5:
    print(x)
    x+=1
---------------   
0
1
2
3
4
5


x=0
while x<=5:
    print(x)
    if x==3:break
    x+=1
---------------
0
1
2
3


x=0
while x<=5:
    print(x)
    x+=1
else:
    print("x>=5條件式不成立!")
---------------   
0
1
2
3
4
5
x>=5條件式不成立!




For Loops

help("for")
The "for" statement
*******************

The "for" statement is used to iterate over the elements of a sequence
(such as a string, tuple or list) or other iterable object:

   for_stmt ::= "for" target_list "in" starred_list ":" suite
                ["else" ":" suite]



Lst=["A","B"]
for i in Lst:
    print(i)
---------------   
A
B

for i in "AB":
    print(i)
---------------       
A
B

for i in "ABC":
    print(i)
    if i=="B":break
---------------   
A
B


for n in range(0,6):
    print(n)
---------------
0
1
2
3
4
5


for n in range(6):
    print(n)
---------------   
0
1
2
3
4
5


for n in range(0,6,1):
    print(n)
---------------   
0
1
2
3
4
5


for n in range(0,6,2):
    print(n)
---------------   
0
2
4


for n in range(0,6,3):
    print(n)
---------------   
0
3
 

 

 

 
 



輸入input()

 >>> help(input)
Help on built-in function input in module builtins:

input(prompt='', /)
    Read a string from standard input.  The trailing newline is stripped.

    The prompt string, if given, is printed to standard output without a
    trailing newline before reading input.

    If the user hits EOF (*nix: Ctrl-D, Windows: Ctrl-Z+Return), raise EOFError.
    On *nix systems, readline is used if available.

 

>>> name=input("Please input your name:")
Please input your name:小明
>>> name
'小明'
>>> type(name)
<class 'str'>


>>> score=int(input("Please your score:"))
Please your score:90
>>> score
90
>>> type(score)
<class 'int'>

 


輸出print()

>>> help(print)
Help on built-in function print in module builtins:

print(*args, sep=' ', end='\n', file=None, flush=False)
    Prints the values to a stream, or to sys.stdout by default.

    sep
      string inserted between values, default a space.
    end
      string appended after the last value, default a newline.
    file
      a file-like object (stream); defaults to the current sys.stdout.
    flush
      whether to forcibly flush the stream.


print('A','B','C');print('D','E')
A B C
D E

print('A','B','C',end='--->');print('D','E')
A B C--->D E


print('A','B','C',sep='+')
A+B+C


print('A','B','C',sep='+',end='=')
A+B+C=





參數格式化:%

name="小明"
score=90
print("%3s 的成績 %2d 分" %(name,score))
王小明 的成績 90 分


參數格式化:format()

name="王小明"
score=90
print("{0:3s} 的成績 {1:2d} 分".format(name,score))
王小明 的成績 90 分


 escape character

print("HelloWorld")
HelloWorld

print("Hello\'World")    #單引號
Hello'World

print("Hello\"World")    #雙引號
Hello"World

print("Hello\\World")    #反斜線
Hello\World

print("Hello\nWorld")    #換行
Hello
World

print("Hello\tWorld")    #Tab鍵
Hello    World





**********************************************************
python 撰寫風格
*********************************************************** 


#單行註解

''' 以下式多行註解
 「;」
    敘述很短時,可用半形分號,把多形敘述併成一行。

    python 會在指令後,如:while 或 if  ,以縮排表示程式區塊 CodeBlock (python 稱 Suite)。

   「:」    
    半形冒號,提醒使用者下一行程式碼必須縮排,預設值則以一個「Tab」鍵,
    即4個空白字元來完成縮排。
'''
    


   
x=6;y=9
if x<y:
    print("正確")
else:
    print("不正確")
----------------------------
正確




求二個正整數GCD




x=int(input("輸入第一個較大正整數:"))
y=int(input("輸入第二個較小正整數:"))
while x%y!=0:
    x,y=y,x%y    #2變數交換
else:
    print("GCD={}".format(y))

===================== RESTART: C:/Users/User/Desktop/00.py
輸入第一個較大正整數:52
輸入第二個較小正整數:39
GCD=13

 

 

自訂函式來完成

def myGCD(x,y):
    while x%y!=0:
        x,y=y,x%y    #2變數交換
    else:
        return y
    
    
x=int(input("輸入第一個較大正整數:"))
y=int(input("輸入第二個較小正整數:"))

print("GCD={}".format(myGCD(x,y)))

===================== RESTART: C:/Users/User/Desktop/00.py
輸入第一個較大正整數:52
輸入第二個較小正整數:39
GCD=13

2023年10月17日 星期二

圖說演算法 使用Python BY 吳燦銘、胡昭民 博碩

 CH1 進入演算法的世界
1-1 運算思維
電腦(computer)具備資料處理與計算的電子設備
程式設計是電腦硬體與軟體息息相關的學科
處於物聯網(Internet Of Things IOT)與雲端運算(Cloud Computing)的時代,寫程式是全民的基本能力,唯有將創意經由設計過程與電腦結合,才能因應快速變遷的雲端世代。
雲端運算(Cloud Computing):使用者透過網路登入遠端伺服器進行操作,就能使用運算資源。
物聯網(Internet Of Things IOT):將各種具有裝置感測設備的物品,例如:RFID、環境感測器、全球定位系統等與網際網路結合,並透過網路技術讓各種實體物件、自動化裝置都能彼此溝通和交換資訊。


運算思維(Computational Thinking CT):程式設計課程的目的,是分析與拆解問題能力的培養,培育AI時代必備的數位素養。
運算思維是一種利用電腦的邏輯來解決問題的思維, 就是一種能夠將問題「抽象化」與「具體化」的能力, 讓學生們能更有創意的展現出自己的想法與嘗試自行解決問題。
程式設計過程就是一種運算思維的表現,要學好運算思維,透過程式設計絕對是最佳的途徑。
Google運算思維課程提到,培養運算思維的四個面向:拆解(Decomposition)、模式識別(Pattern Recognition)、歸納與抽象化(Generalization and Abstraction)、演算法(Algorithm),雖然這並不是建立運算思維唯一的方法 ,不過透過這四個面向我們能更有效率的發想, 利用運算方法與工具解決問題的思維能力 ,進而從中建立運算思維。
1. 拆解(Decomposition)
原本複雜的問題拆解成許多小問題,先將這些小問題各個擊破,小問題全部解決之後,原本的大問題也就迎刃而解了。
2. 模式識別(Pattern Recognition)
複雜的問題分解之後,常常能發現小問題中有共有的屬性以及相似之處,這些屬性就稱為模式pattern,模式識別是指在一堆資料中找出特徵和問題中的相似之處,用來將資料進行辨識與分類,並找出規律性,才能作為快速決策判斷。
3. 歸納與抽象化(Generalization and Abstraction)
過濾不必要特徵,讓我可以集中在重要特徵上,幫助將問題具體化,進而建立模型。
4. 演算法(Algorithm)
生活當中想辦法解決問題 ,這種計劃與考量過程就是運算思維 ,按照計劃逐步執行就是一種演算法(Algorithm)。
演算法是程式設計的第一步。

大數據(big data)在一定時效(Velocity)內進行大量(Volume)且多元性(Variety)資料的取得、分析、處理、保存等動作。
人工智慧(Artificial Intelligence AI):使電腦具有類似人類學習解決複雜問題與展現思考等能力,舉凡模擬人類的聽、說、讀、寫、看、動作等電腦技術,都被歸類為人工智慧的可能範圍。

 

1-3 生活中演算法
1-3-1演算法的條件
五大特性:
輸入(Input):可以沒有多個輸入
輸出(Output):至少會有一個輸出
明確性(Definiteness)
有限性(Finiteness)
有效性(Effectiveness):能讓使用者使用紙筆推演出結果
表達方式
文字敘述、流程圖(FlowDiagram)、虛擬語言(PseudoLanguage)


1-3-2時間複雜度(Time Complexity)
要分析一個演算法的效率,是將該演算法在每個不同的輸入大小 之下,所執行的基本運算次數 設定成一個函數 (Function) T(n) ; 或稱Time function,Complexity function 。
定義一個T(n)來表示程式執行所要花費的時間,其中n代表資料輸入量, 程式的執行時間或者最大執行時間(Worse Case Executing Time)作為時間複雜度的衡量標準,一般以Big-oh表示。
O(f(n)) Big-oh of f(n) 可視為演算法在電腦中所需執行時間不會超過某一常數倍的f(n),也就是某演算法的執行時間 T(n) 的時間複雜度(Time Complexity)為O(f(n))。
即存在兩個常數 c 與 n0,若 n>=n0 ,則 T(n) <= cf(n) , f(n) 又稱之為執行時間的成長率 (rate of growth),由於寧可高估不要低估的原則,所以估計出來的函數, 是真正所需執行時間的上限。
事實上,時間複雜度只是執行次數的一個概略的量度層級,並非真實的執行次數。Big-oh用來表示最壞執行時間的表現方式,它也是最常使用在描述時間複雜度的漸進式表示法。
對於 n>=16 時,時間複雜度的優劣比較關係如下:
O(1) < O(log2^n) < O(n) < O(nlog2^n) < O(n^2) < O(n^3) < O(2^n)    

O(1):陣列讀取
O(n):簡易搜尋
O(log n):二分搜尋
O(nlogn):合併排序
O(n²):選擇排序、泡沫排序、插入排序
O(2^n):費波那契數列


1-3-3 程式設計邏輯簡介
傳統程式設計方法
由下而上法:程式設計師將整個程式需求最容易的部分先編寫,再逐步擴大來完成這個程式。由上而下法:則是將整個程式需求從上而下、由大到小逐步分解成較小的單元,或稱為模組 Module ,這樣使得程式設計師可針對各模組分別開發,不但減輕設計者的負擔、可讀性較高,對於日後為維護也容易許多。

結構化程式設計:核心精神就是「由上而下設計」與「模組化設計」。Pascal 語言中,這些模組稱為程序 Procedure,C語言中稱為函數 Function
結構化程式設計具備三種控制流程
循序結構:逐步的撰寫敘述
選擇結構:依某些條件做邏輯判斷
重複結構:依某些條件決定是否重複執行某些敘述

 

1-3-4 物件導向程式設計
物件導向程式 Objct Oriented Programming OOP:程式設計師以一種更生活化、可讀性更高設計觀念來進行,並且所開發出來的程式也較容易擴充、修改及維護。
透過物件的外部行為 Behavior 運作及內部狀態 State 模式,來進行詳細的描述。
行為 Behavior 代表此物件對外所顯示出來的運作方法,狀態 State 代表物件內部各種特徵的目前狀況。

每一個物件都是獨立的個體,對我們而言,無需去理解這些特定功能如何達成這個目標過程,僅須將需求告訴這個獨立個體便能獨立完成。
物件導向程式設計的重點是強調強制的可讀性 Readability 、重複使用性 Reusability 與延伸性 Extension 。本身還具備三種特性:

封裝性 Encapsulation
利用類別 class 來實作「抽象化資料型態 ADT」。類別是一種用來具體描述物件狀態與行為的資料型態,也可以看成是一個模型或藍圖,按照這個模型或藍圖所生產出來的實體 Instance ,就被稱為物件。
所謂抽象化就是將代表事物特徵的資料隱藏起來,並定義「方法 Method」作為操作這些資料的界面,讓使用者只能接觸到這些方法,而無法直接使用資料,符合資訊隱藏 Information Hiding 的意義。這種自訂的資料型態就稱為抽象化資料型態。

繼承性 Inheritance
物物件導向語言中最強大的功能,因為它允許程式碼的重複使用 Code Reusability ,及表達了樹狀結構中父代與子代的遺傳現象。
繼承,允許我們去定義一個新的類別來繼承既存的類別,進而使用或修改繼承而來的方法,並可在子列別中加入新的資料成員與函數成員。
 
多型 Polymorphism
按照英文字面解釋,就是一樣東西同時具有多種不同的型態。
利用類別的繼承架構,先建立一個基礎類別物件。使用者可透過物件的轉型宣告,將此物件向下轉型為衍生類別物件,進而控制所有衍生類別的「同名異式」成員方法。
就是具有繼承關係的不同類別物件,可以呼叫相同名稱的成員函數,並產生不同的反應結果。


物件 Object :可以是抽象的概念或是一個具體的東西包括了資料 Data 以及所相應的運算 Methods ,它具有狀態 State 、行為 Behavior 與識別 Identity 。每一個物件均有其相應的屬性 Attributes 及屬性值 Attributes values 。

類別 Class :是具有相同結構及行為的物件集合,是許多物件共同特徵的描述或物件的抽象化。類別中的一個物件有時就稱為該類別的一個實例 Instance

屬性 Attribute :則是用來描述物件的基本特徵與其所屬的性質。

方法 Method :則是物件導向資料庫系統裡物件的動作與行為。





 

 

 

 

 

CH2 地表上最常見經典演算法
2-1 分治演算法(Divide and conquer)
將一個難以直接解答的大問題依照不同概念,分割成兩個或更多的子問題,以便各個擊破,分而治之。

---------------------------------------------

def find_max(arr):
    # Base case: if the list has only one element, return it
    if len(arr) == 1:
        return arr[0]
    
    # Divide the list into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    # Recursively find the maximum of each half
    max_left = find_max(left_half)
    max_right = find_max(right_half)
    
    # Return the maximum of the two maximums
    return max(max_left, max_right)

# Test the function
arr = [3, 8, 1, 5, 9, 4, 2, 7, 6]
print("Maximum number in the list:", find_max(arr))

---------------------------------------------

 

2-1-1 遞迴法Recursion
分治法和遞迴法很像都是將一個複雜的演算法問題的規模變得越來越小,最終使子問題容易求解。
遞迴在早期人工智慧所用的語言,如 Lisp、Prolog 幾乎都是整個語言運作的核心,現在許多程式語言,包括C、C++、Java、Python等,都具備遞迴功能。
對程式設計師而言,函數不單只是能夠被其他函數呼叫的程式單元,在某些程式語言還提供了自身引用的功能,這種功用就是所謂的遞迴。
 

階層Factorial

---------------------------------------------
intN=int(input("輸入一個正整數:"))
fac=1

for i in range(intN,0,-1):    
    fac=fac*i

print("{0}!= {1}".format(intN,fac))   

---------------------------------------------


def fac(n):
    if n==0:
        #遞迴條件終止
        return 1
    else:
        #遞迴呼叫
        return n*fac(n-1)

intN=int(input("輸入一個正整數:"))

print("{0}!= {1}".format(intN,fac(intN)))   

---------------------------------------------
 

 

費波那契數列Fibonacci Polynomial

---------------------------------------------
def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1)+fib(n-2)

intN=int(input("輸入一個正整數:"))

print("Fibonacci({0})= {1}".format(intN,fib(intN)))    
    
#0,1,1,2,3,5,8...
#第0項:0、第1項:1、第2項:1、第3項:2、第4項:3、第5項:5、第6項:8...

---------------------------------------------

 

2-2 貪心法Greed Method-給我最好其餘免談
在每個解決問題步驟都採取當前狀態下最優化的選擇,不斷的改進該解答,逐步逼近給定的目標。
求圖形的最小生成樹(MST)、最短路徑與霍夫曼編碼Huffman Coding

2-3 動態規劃法 Dynamic Programming Algrithm PDA
將大問題拆解成各個小問題,其中與分治法最大不同的地方是可以讓每一個子問題的答案被儲存起來,以供下一次求解時直接取用,這樣的做法不但能減少再次需要計算的時間,並將這些解組合成大問題的解答,故使用動態規劃可以解決重複計算的缺點。
 

Fibonacci

---------------------------------------------

def fib(n):          
    if n in dic:return dic[n]
    if n<=1:
        return n
    else:
        dic[n]=fib(n-1)+fib(n-2)        
        return dic[n]
    
#預設即為public  
dic={}
intN=int(input("輸入一個正整數:"))
print("Fibonacci({0})= {1}".format(intN,fib(intN)))
 

print(dic)
---------------------------------------------



 

2-4 疊代法(iterative method)
無法使用公式一次求解,而須反覆運算。for 迴圈、while 迴圈

2-4-1 巴斯卡(Pascal)三角形演算法
C(r row,n column)
C(r,0)=1
C(r,n)=C(r,n-1)*(r-n+1)/n

2-5 窮舉法
根據問題要求,一一枚舉問題的解答,最終達到解決這個問題的目的。這種方法得到的結果總是正確的,唯一的缺點就是速度太慢。
如:列出1到500間的所有5的倍數的整數。枚舉法的作法就是從 1 開始到 500 逐一列出所有的整數,一邊枚舉一邊檢查該枚舉的數字是否為5的倍數,如果不是,不加以理會,如果是,則輸出。


2-6 回溯法(BackTracking)-不對就回頭
算是枚舉法中的一種,一旦發現不正確的數值,就回溯到上一層,節省時間。即是走不通就退回再走的方式。如:老鼠走迷宮。

CH3 超人氣資料結構簡介
3-1 認識資料結構
3-2 資料結構的種類
3-2-1 陣列 Array
3-2-2 鏈結串列 Linked List
3-2-3 堆疊 Stack 後進先出 Last in , First out
3-2-4 佇列 Queue 先進先出 First in , First out

3-3 樹狀結構
3-3-1 樹的基本概念
3-3-2 二元樹

3-4 圖形
3-5 雜湊表 Hash
雜湊表是一種儲存紀錄的連續記憶體,能透過雜湊涵數的應用,快速存取與搜尋資料。所謂雜湊函數 Hashing Function 就是將本身的鍵值,經由特定的數學函數運算或使用其他的方法,轉換成相對應的資料儲存位址。


CH4 最夯排序演算法
4-1 認識排序
4-2 氣泡排序法 Bubble Sort
4-3 選擇排序法 Selection Sort
4-4 插入排序法 Insert Sort
4-5 謝耳排序法 Shell Sort
4-6 合併排序法 Merge Sort
4-2 快速排序法 Quick Sort
4-2 基數排序法 Radix sort

CH5 必須學會的搜尋演算法
5-1 循序搜尋法 Sequential Search
5-2 二分搜尋法 Binary Search
5-3 內插搜尋法 Interpolation Search
5-4 費式搜尋法 Fibonacci Search

CH6 陣列與串列演算法
矩陣演算法與深度學習
矩陣相加演算法
矩陣相乘
轉置矩陣
稀疏矩陣
陣列與多項式
單向串列演算法
單向鏈結串列的連結
單向串列插入新節點
單向鏈結串列刪除節點
單向鏈結串列的反轉

CH7 安全性演算法
資訊安全 Information Security的基本功能必須具備以下四種特性:
秘密性 confidentiality
完整性 integrity
認證性 authentication
不可否認性 non-repudiation
7-1 資料加密
明文 Plain text --> 加密金鑰 Encrypt Key--> 密文 Cipher text --> 解密金鑰 Decrypt Key--> 明文
7-1-1 對稱鍵值加密系統
又稱單一鍵值加密系統 Single Key Encryption 或秘密金鑰 Secret Key
7-1-2 非對稱鍵值加密系統與RSA (Ron Rivest、Adi Shamir 和 Leonard Adleman 三人一起提出) 演算法
是目前較為普遍,也是金融界應用上最安全的加密系統,或稱為雙鍵加密系統 Double Key Encryption,這種加密系統主要運作方式,是以兩把不同的金鑰來對文件進行加解密。

7-1-3 認證
7-1-4 數位簽章 Digital Signature
屬於個人的一種數位身分證,可以用來作為對資料發送的身份進行辨別。
運作方式是以私有金鑰及雜湊函數互相搭配使用。
發文者先將明文與雜湊函數計算出雜湊值,接著再用自己的私有金鑰對雜湊值加密,加密後的內容即為數位簽章。
發送者將明文資料和數位簽章傳送給接收者,接受者再以發送者的公開金鑰解密,來驗證簽章。
7-2 雜湊演算法
雜湊法是利用雜湊函數來計算一個鍵值所對應的位址,進而建立雜湊表格,依賴雜湊函數來搜尋找到各鍵值存放在表格中的位址,搜尋速度與資料多少無關,在沒有碰撞溢位下,一次讀取即可,更包括保密性高,因為不事先知道雜湊函數就無法搜尋的優點。
7-2-1 除法
7-2-2 中間平方法
7-2-3 折疊法
7-2-4 數位分析法
7-3 解決碰撞與溢位處理
7-3-1 線性探測法
7-3-2 平方探測法
7-3-3 再雜湊法
7-3-4 鏈結串列

CH8 堆疊與佇列演算法
陣列實作堆疊
鏈結串列實作堆疊
河內塔演算法
八皇后演算法
陣列實作佇列
鏈結串列實作佇列
雙向佇列
優先佇列

CH9 樹狀演算法
完滿二元樹 Fully Binary Tree
完整二元樹 Complete Binary Tree
歪斜樹 Skewed Binary Tree
嚴格二元樹 Strictly Binary Tree

9-1 陣列實作二元樹
9-2 鏈結串列實作二元樹
9-3 二元樹走訪
中序走訪 Inorder Traversal
前序走訪 Preorder Traversal
後序走訪 Postorder Traversal
9-4 二元樹節點搜尋
9-5 二元樹節點插入
9-6 二元樹節點刪除
9-7 堆積數排序法
堆積樹 Heap Tree可分為最大堆積樹以及最小堆積樹。
堆積樹排序法是選擇排序法的改進版,它可以減少在選擇排序法中的比較次數,進而減少排序時間。

9-8 延伸二元樹入門
9-9 霍夫曼樹
經常用於處理資料壓縮的問題,根據資料出現的頻率來建構的二元樹。
9-10 平衡術 Balanced Binary Tree
又稱AVL樹(是由 Adelson-Velskii 和 Landis兩人所發明)
9-11 決策樹 Decision Tree

CH10 圖形演算法
10-1 圖形簡介
10-1-1 尤拉環與尤拉鍊
尤拉環 Eulerian cycle 理論:所有頂點的分支度皆為偶數時,才能從某一頂點出發,經過每一邊一次,再回到起點。

10-1-2 圖形的定義
10-1-3 無向圖形
10-1-4 有向圖形
10-2 圖形的資料表示法
10-2-1 相鄰矩陣法
10-2-2 相鄰串列法
10-2-3 相鄰複合串列法
10-2-4 索引表格法
10-3 圖形的走訪
10-3-1 先深後廣走訪法
10-3-2 先廣後深 Breadth First Search 搜尋法
10-4 最小花費擴張樹-MST
10-4-1 Prim演算法
10-4-2 Kruskal演算法
10-5 圖形最短路徑法
10-5-1 Dijkstra演算法與A*演算法
10-5-2 Floyd演算法

CH11 AI高手的神級演算法
人工智慧 Artificial Intelligence 就是讓電腦能夠表現出類似人類智慧行為的科技,讓機器能夠具備人類的思考邏輯與行為模式,其原理是認定智慧源自於人類理性反應的過程而非結果,即是來自於以經驗為基礎的推理步驟與演算法。
圖靈測試 Turing Test :如果一台機器能夠與人類展開對話,而不被看出是機器的分身,就能宣稱該機器擁有智慧。
近十年來人工智慧的應用領域越來越廣泛,關鍵因素就是圖形處理器 Graphics Processing Unit 等關鍵技術與先進演算法的高速發展。GPU 因為含有數千個小型且更高效率的 CPU,能有效平行處理 Parallel Processing,加上GPU是以向量和矩陣運算為基礎,大量的矩轉矩陣運算可以分配給眾多的核心同步進行處理 ,使得人工智慧領域正式進入實用階段,藉以加速科學、分析、遊戲、消費和人工智慧應用 。
平行處理技術是同時使用多個處理器來執行單一程式,藉以縮短運算時間。其過程為將資料以各種方式交給每一顆處理器,為了實現在多核心處理器上程式性能的提升,還必須將應用程式分成多個執行緒 Thread 來執行。

11-1 機器學習 Machine Learning 簡介
是AIi發展相當重要的一環,顧名思義就是讓電腦具備自己學習、分析並最終進行輸出的能力,主要的做法就是針對所要分析的資料進行分類 Classification ,有了這些分類才可以進一步分析與判斷這些資料的特性,最終的目的就是希望讓電腦像人類一樣具有學習能力。

11-1-1 監督式學習 Supervised learning 演算法
將輸入資料標籤化,從訓練資料截取特徵,以幫助判讀目標物,並分辨種類 。
11-1-2 半監督式學習 Semi-supervised learning演算法
11-1-3 非監督式學習 Un-supervised learning與K-平均演算法
11-1-4 增強式學習 Reinforcement learning 演算法

11-2認識深度學習 Deep Learning
讓電腦開始學會自行思考。隨著越來越強大的電腦運算功能,科學家開始採用模擬人類複雜神經架構,來實現讓電腦具備與人類相同的聽覺、視覺、理解與思考的能力。
例如:Google Deepmind 開發的AI圍棋程式 AlphaGo 接連大敗歐洲和南韓圍棋棋王。

 

------------------------------------------------ 

機器學習跟深度學習的差別是什麼?

人工智慧 Artificial Intelligence AI:讓電腦模擬人類做的事情

機器學習 (Machine Learning) 是 AI 的一個子集合,是實現 AI 的其中一種方法;讓電腦看過並「學習」大量數據,然後對問題進行推理與判斷的流程。
資料輸入 → 特徵擷取 → 訓練模型 → 輸出(判斷)
輸入資料後,機器學習需要進行「特徵擷取 (feature extraction)」,特徵是「人想出來的」;進行特徵擷取之後,將資料再輸入訓練模型中 ,最後便可以得到我們想要的答案。

深度學習 (Deep Learning) 則是機器學習的一個子集合,所以是機器學習的其中一種方法;讓電腦程式模擬人類的決策/判斷。
資料輸入 → 特徵擷取 + 訓練模型 → 輸出(判斷)
深度學習不需要再人為進行特徵擷取。只要把資料倒入訓練模型 (常常會聽到的「神經網路」) 中,訓練模型會自己進行特徵擷取,接著進行判斷,得到答案 。
當資料量越大,深度學習可以擷取的特徵可能性就越多,最後判斷的結果也會更加精準。


------------------------------------------------

 

 

11-2-1 類神經網路 Neural Network 演算法
輸入層 Input layer
隠藏層 Hidden layer
輸出層 Output layer

11-2-2 卷積神經網路 Convolutional Neural Networks CNN 演算法
11-2-3 遞迴神經網路 Recurrent Neural Network RNN 演算法