# ZFCSC17 社課講義
:::spoiler 目錄
[ToC]
:::
## 1. hello world
### 引言
hello word 最早出現在C語言白皮書中
作為第一個範例，同時也是許多人的第一句程式語言
我們來看看他是怎麼寫的吧
#### C語言版本
```cpp=
#include <stdio.h>
int main()
{
printf("hello world");
return 0;
}
```
### 解析
第一行`#include<stdio.h>`是引入(include)「標頭檔」。
顧名思義，是拿來丟在第一行的，裡面包含了各種不一樣的函式(function)，所以在用一些特殊函式的時候就會需要引入其他標頭檔。
第二行`int main()`是主要函式，所有專案中都會有這麼一個主要函式。
程式會從這裡開始執行。
第三行`{`對應到第六行`}` 這組大括號裡包含了隸屬於主程式下的所有行為。
第四行`printf("hello world");`是輸出指令雙引號("")裡面夾的句子(除了特殊字)將忠誠的顯示出來。
第五行`return 0;`回傳0代表程式結束，若回傳非0則代表程式出錯。回傳值通常會在執行完後出現在終端機上(也就是printf顯示的視窗)。
#### C++版本
```cpp=
#include<iostream>
using namespace std;
int main()
{
cout << "hello world" << endl;
return 0;
}
```
不難發現其實跟c版結構上非常相似，只是多了第二行的`using namespace std;`
和原本代表輸出的`ptintf("hello world");`被換成了`cout << "hello world" << endl;`
### 解析
第一行的標頭被換成了支援`cout`的`iostream`。
第二行`using namespace std;`算是一種簡化的寫法(雖然單就這個程式來看是更麻煩的)用意是讓後面從`namespace std`出來的程式都不用加前墜`
std::`
故若是沒有遞沒有第二行，第五行需改成`std::cout << "hello world" << endl;`
第五行`cout << "hello world" << endl;`是輸出指令，意思是把`endl`接在`endl`後面並導入`cout`指令以輸出，可以理解為照順序把各種常數、變數接在一起然後輸出。
### 練習
利用上述知識印出
`哇哈哈哈哈`
利用上述知識印出
**
* **
* * **
### 補充-常用標頭
#### C
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#### C++
#include<iostream>
#include<cmath>
#### 萬用標頭
#include<bits/stdc++.h>'
### 補充-void
有些網路範例會在宣告函式時在()裡加void代表不需要引入，我們可以習慣性省略。
---
## 2.變數-變數輸出
### 引言
變數是個可以儲存單元資料的地方，有各種不同的資料型態(補充-型態)
建議養成沒有馬上Input就賦予初始值的好習慣~
#### C語言版本
```cpp=
#include <stdio.h>
int main()
{
int a=0;
printf("%d\n",a);
return 0;
}
```
### 解析
第四行`int a=0;`宣告型態為int(整數)的變數a(除了保留字 補充-保留字 和不合法命名 補充-不合法命名 都可以任意幫變數命名)並設定值為0，在C/C++中所有的變數都需要經過宣告（但不一定要設定初始值）。
第五行`printf("%d",a);`%d為指令字元，意思是以整數(十進位)輸出`,`後的變數(不一定是整數)，有兩個以上的指令(如%d)，則照順序輸出(第一的%d對應第一個變數)，\n則是換行的指令。
#### C++版本
```cpp=
#include <iostream>
using namespace std;
int main()
{
int a=0;
cout << a << endl;
return 0;
}
```
### 解析
跟C語言長的差不多，比較值得注意的是`<<`後面也是可以接變數(不用告知型態)的呦!
### 練習
設定一個字元變數，設定值為'a'並使用整數型態輸出。
### 補充-常用資料型態
int - 整數(十進位)---%d
float - 浮點數(小數)---%f
double - 倍精度浮點數(小數-範圍較大)---%lf
char - 字元---%c
string - 字串---%s
### 補充-不合法命名
1.第一個字符是數字
例如:`int 1a;`
2.中文
例如: `int 變數;`
3.不合法符號(除了_以外的符號皆不合法)
例如:`int money$$;`
4.常見保留字(通常是有其他用途的字元)
APPLOADER1 BASE CODE
CONFORMING DATA DESCRIPTION
DEV386 DISCARDABLE DYNAMIC
EXECUTE-ONLY EXECUTEONLY EXECUTEREAD
EXETYPE EXPORTS FIXED1
FUNCTIONS2 HEAPSIZE IMPORTS
IMPURE1 INCLUDE2 INITINSTANCE2
IOPL LIBRARY1 LOADONCALL1
LONGNAMES2 MOVABLE1 MOVEABLE1
MULTIPLE NAME NEWFILES2
NODATA1 NOIOPL1 NONAME
NONCONFORMING1 NONDISCARDABLE NONE
NONSHARED NOTWINDOWCOMPAT1 OBJECTS
OLD1 PRELOAD PRIVATE
PROTMODE2 PURE1 READONLY
READWRITE REALMODE1 RESIDENT
RESIDENTNAME1 SECTIONS SEGMENTS
SHARED SINGLE STACKSIZE
STUB VERSION WINDOWAPI
WINDOWCOMPAT WINDOWS
### 補充-區域變數與全域變數
請自己跳到函式那邊去看，我把這個補充丟在那裏。
---
## 3.運算元
有了變數，就可以做運算啦!!
#### 範例
```cpp=
#include<stdio.h>
int main()
{
int a=5,b=8;
a=a/b;
a++;
a=a%2;
b*=a;
printf("%d %d",a-5,b-1);
}
```
### 解析
第四行是先前講過的變數宣告，值得注意的是，這邊一次宣告了兩個同型態的變數。
第五行計算`a/b`並把結果設定給`a`。
第六行是一種簡化寫法，代表把`a`加1(也就是`a=a+1`)。
第七行把`a`除以2的餘數設定給`a`。
第八行把`a`乘以`b`的值設定給`b`，*=是簡化語法，代表`b=b*a`也就是把等號後方的值(`a`)乘上自己(`b`)並把值設定給自己(`b`)。
第九行輸出`a-5`的值後再輸出`b-1`的值。
### 練習
設定一個變數，設值為5並輸出a*5/19+6%2+8(先乘除後加減)
### 補充- a++ 與 ++a
看似相同的兩個寫法其實有些微的不同。
`a++`代表先取值再+1。
`++a`代表先+1再取值。
體現在code上就是:
`x=0; printf("%d",x++);`輸出0。
`x=0; printf("%d",++x);`輸出1。
---
## 4.Debug、Bug
### 引言
看到這裡，相信你已經算是個寫過程式的人了。
如果前面的習題都有做的話，不知道你有沒有遇到過Bug呢?
### Bug
bug也就是程式錯誤分為兩種:
語法錯誤以及語意錯誤
#### 語法錯誤
會導致無法編譯的錯誤，在少打`;`、變數打錯等等的錯誤時，編譯器報錯的地方將會告訴你錯在哪以及錯誤原因，由於機器能辨識相對好解決，把報錯的訊息貼到GOOGLE上照網路上的說法解即可。
#### 錯誤示範
```cpp=
include <stdio.h> //沒加#
int main()
[//要用{}
x=1//沒宣告型態,沒加;
]
```
#### ↑Dev-C++中的報錯畫面
#### 語意錯誤
不會導致編譯錯誤但更加可怕的錯誤，由於程式可以執行不難發現，執行結果出乎意料時還要自己寫log(也就是printf)來確認出錯點著實令人頭疼。如`==`打成`=`;
### 補充-小知識
句尾沒加;的提示通常會出現在下一行，所以如果報錯那行沒錯的話不妨看看前一行是不是忘記加;了呢?
## 5.註解
### 引言
在之前的錯誤示範中，可以看到`//`的出現
他就是註解-增加可讀性的好幫手
### 範例
```cpp=
#include<stdlib.h>
int main()
{
printf("hello world");//對我又寫了一個hello world
}
/*這個程式信奉著至高無上的海星*/
```
### 解析
第四行`//`是註解的意思(只有副檔名是.cpp能用)，他會註解掉該行在`//`後的任何東西，使其不被編譯器讀取。
第六行`/*這個程式信奉著至高無上的海星*/`也是註解，會註解掉包在`/*`和`*/`中間的任何東西，使其不備編譯器讀取。
---
## 6.輸入
### 引言
好啦大家感覺都迫不及待想學input了，講一下，雖然我輸出狂愛用C的printf不過輸入更愛用C++的cin，真的太方便了。
### 範例
#### C/C++混寫
```cpp=
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int main()
{
cout << input age << endl;
int age;
cin >> age;
cout << input name << endl;
string name;
getline(cin,name);
char school[2000];
scanf("school: %s",&school);
printf("age: %d",age);
cout << "name: " << name << endl;
printf("school: %s",school);
}
```
第九行輸入一個數值進變數`age`
第十二行輸入一個字串進變數`name`
第十四行輸出`school: `並輸入一個字串進school的位址這會牽扯到指標而且scanf很難用這邊就不細講。
第十五到第十七行使用C&C++輸出
### 補充-getline and cin >> string
getline的結束是\n(換行)
cin字串結束則是' '(空格)
---
## 7.陣列與字串
一個資料存在記憶體叫變數，很多個同類型資料存在一組有序的記憶體內叫陣列，而字串則是字元(char,%c)的陣列。
### 範例
#### C語言
```cpp=
#include<stdio.h>
int main()
{
char str[5]={95,96,97,98,99};
int arry[3]={0};
printf("%c",str[2]);
printf("%d %d %d %d %d",arry[0],arry[1],arry[2]);
}
```
### 解析
第四行陣列宣告基本和變數宣告大同小異，不過後面加了個由`[]`包起來的正整數 代表該陣列的長度，而賦予初值則是由`{}`包起來`,`分隔的資料一一賦予。
第五行與前一行不同，初值設定只有一個值，表示將陣列中所有值設為0。--注意！這種寫法只有全部設為0時可行。
第六行輸出str陣列的第2個值，注意這裡的第二是從零開始數，也就是說最開頭的值是第零個值。
#### C++
```cpp=
#include <iostream>
using namespace std;
int main()
{
char str[5]={95,96,97,98,99};
int arry[3]={0};
printf("%c",str[2]);
printf("%d %d %d %d %d",arry[0],arry[1],arry[2]);
}
```
---
## 8.if判斷子
if判斷是程式神聖而不可分割的一部份，可以用來判斷某段程式的執行與否。
### 範例
#### C++
```cpp=
#include<iostream>
using namespace std;
int main()
{
int a=0,b=0,c=1,d=5;
cin >> a;
if(a==0)
{
cout << b;
}
else if(a==d)
cout << d;
else
cout << c;
return 0;
}
```
### 解析
第五行宣告三個變數`a,b,c,d`
第六行輸入變數`a`
第七行判斷`a`是否為0，若結果為[是]則執行由`{}`框起的程式
第十一行表示若第七行的判斷結果為[否]則判斷`a`是否為`d`若結果為是則執行`cout << d;`(`｛}`內的程式只有一行時`{}`可省略)
第十三行表示~~十三行文化~~若第七行的判斷結果為[否]且第十一行判斷結果為[否]則執行內含程式
### 補充-判斷子
`==`相等時回傳`true`反之回傳`false`
`>`大於時回傳`true`反之回傳`false`
`<`小於時回傳`true`反之回傳`false`
`<=`小於等於時回傳`true`反之回傳`false`
`>=`大於等於時回傳`true`反之回傳`false`
`!=`不相等時回傳`true`反之回傳`false`
### 補充-三元運算符
神秘的簡化寫法
[參考文獻](https://shengyu7697.github.io/cpp-ternary-operator/)
#### 範例
```cpp=
#include<iostream>
using namespace std;
int main()
{
int a=3,b=4;
int c = a=b?a:b;
}
```
```cpp=
#include<iostream>
using namespace std;
int main()
{
int a=3,b=4;
if(a=b)
c=a;
else
c=b;
}
```
上述兩組程式代表的意義是一樣的
另外，除了設質，三元運算子也可以直接執行指令。
如下
```cpp=
#include<iostream>
using namespace std;
int main()
{
int a=3,b=4;
a = b ? cout << a << endl : cout << b << endl ;
}
```
---
## 9.while迴圈
while迴圈是程式神聖而不可分割的一部份，可以用來重複某段程式的執行。
### 範例
```cpp=
#include<iostream>
using namespace std;
int main(){
while(1){
cout << "-";
}
return 0;
}
```
### 解析
第四行while迴圈判斷`()`中的運算結果是否不為0(false)，是則執行故此程式會一直印`-`直到電腦當機。
### 補充-指定次數
#### 範例
```cpp=
#include<iostream>
using namespace std;
int main()
{
int i=10;
while(i--)
{
printf("%d",i);
}
return 0;
}
```
#### 解析
在此程式中i--如單元「運算元」中的補充所述，先偵測再減一(但第一次進迴圈會先減一再偵測再減一)，當偵測到i == 0時會跳出迴圈。
所以這個程式會印出9 - 0。
---
## 10.for迴圈
### 範例
```cpp=
#include<iostream>
using namespace std;
int main(){
for(int i=0;i<10;i=i+1)
{
cout << i;
}
return 0;
}
```
### 解析
第四行設定整數變數i=0在i<10時執行並在最後最後執行i=i+1
此程式會印出0-9
### 補充-迭代
c++11後提供了一種寫法for(int i:arry)
用變數i把陣列arry裡所有的值跑過一次(也就是迭代一次)
#### 範例
```cpp=
#include<iostream>
using namespace std;
int main()
{
int some_arry[4] = {2,5,8,55};
for(int i:some_arry)
{
cout << i;
}
}
```
### 補充-我都學while了為甚麼要會for
確定次數時用for能用for就用for不然程式會很醜，小心寫code寫到沒朋友。
---
## 巣狀迴圈
就是把一堆迴圈跟code嵌在一起，簡單來說就是迴圈應用。
如果有不會的，社團可以幫忙請公假讓你中午來社辦問。
### 範例
:::spoiler 我忘記甚麼時候的解題紀錄
```cpp=
#include<bits/stdc++.h>
using namespace std;
string data;
int main()
{
int k,i=0;
cin >> k;
cin >> data;
int output=0;
int nota=0;
int tmplen=0,det=0;
nota=(data[i]>=97);
while(i<data.length()-k+1)
{
for(int j=0;j<k;j++)
{
if((data[j+i]>=97)!=nota)
{
det+=1;
break;
}
else if(j==k-1)
{
nota = !nota;
tmplen+=k;
i+=k;
}
}
if(det)
{
output = max(tmplen,output);
if(tmplen>0)
i -=k ;
tmplen=0;
det=0;
i++;
nota=(data[i]>=97);
}
}
output = max(tmplen,output);
cout << output << endl;
}
```
:::
---
## 11.變數的域
變數分為全域和區域。
### 全域變數
可以在不被覆蓋掉的前提下，在程式的所有地方隨時被調用、更改。
### 區域變數
則可以覆蓋掉全域變數，並在執行跳出某個區域的時候被回收，釋放記憶體空間。
#### 當變數重名時，作用涵蓋範圍較小者優先。
#### 沒必要別用全域變數，除非你的專案很小(競程code之類的)，不然後期開發維護很累。
---
## 12.函式
在學hello world的時候我們提過一次函式了，這邊重新提一下函式的功能。
### 功能
函式的用途是把一整段的程式打包，需要的時候可以抓出來重複利用。
### 範例
```cpp=
#include <iostream>
using namespace std;
int b=51;//全域變數宣告
bool detect(/*僅作用於detect的變數宣告*/int a,int b,int c=10)
{
if(a>b)
return 0;
else
return 1;
}
int main()
{
int a=5;//僅作用於main的變數宣告
if(detect(b,a))
cout << "a is bigger?" << endl;
return 0;
}
```
### 解析
對我知道這串程式又冗又亂，但裡面有帶到挺多觀念的。
第三行宣告全域變數(參見補充)b並設值。
第四行宣告函式回傳(return)值為bool(true/false)的detect，並設計都是int(整數)型態的引入值a,b,c。而c的預設值(若沒有特殊宣告則c為預設值)為10。可以理解為設定一個bool型態的detect變數，並設值為裡面程式碼的執行結果。
第七、九行為變數回傳，將`return`後的常數丟到函式的回傳中
第十四行判斷detect(b,a)的回傳值是true還是false，注意!引入變數進到其他函式時可以改名!
---
## 遞迴
就是函式透過不停地呼叫自己達成某些處理。
### 特色
1. 其實大部分可以用while,for loop解掉，但奈何用遞迴帥啊(還有code比較簡潔)。
2. 持續呼叫自己
3. 有停止條件
### 範例-階乘
```cpp=
#include<iostream>
using namespace std;
int O_O(int a)
{
if(a!=1)//停止條件
return a*O_O(a-1);//呼叫自己
else
return 1;
}
int main(void)
{
cout << O_O(5) << endl;
return 0;
}
```
---
---
# Git/Github
對，我懶得備第三堂課所以來不務正業了~
## Git與Github的差別
git是一個可以灌在電腦裡面的玩意，功能是整理專案的更新紀錄。
而github則是雲端服務(有網頁也有手機板跟桌面板)主要功能是延伸git的功能，讓儲存在自己電腦裡的專案可以丟到雲端供其他機器(比如另一台電腦)存取或修改，可以想像成Programmer(程式設計師)的雲端硬碟。
順帶一提，git是開源軟體而github是免費服務，也就是說--完全免費!!!超級佛心!!!
## 連結
[Github網頁連結](https://github.com/)
[Git下載連結](https://git-scm.com/)
這兩個的註冊跟下載介面都挺人性化的。
相信各位被我放生到能靠自己的能力把IDE下載好的天才一定會用的。
## Github使用
## Git使用方法
### 設定目標資料夾
首先，在你的電腦裡面找一個看起來很順眼的資料夾，不然就創一個新的也行。
對著它(那個資料夾)按右鍵->選擇`Git brash here`(如果你是win11的話它在`更多操作`裡)，或直接選擇從終端機開啟。
會進入一個終端機(Terminal)畫面，接著輸入以下指令(或直接複製github上的)。
>git init
>git branch -M main
>git add *
>git commit -m "first commit"
#### 介紹一下指令
`git init` 初始化，定位資料夾，通常不加不會怎麼樣，但當真的怎麼樣的時候，我可能救不了你。
`git branch -M main` 在本地端(你的主機)創建一個名為main的分支。
`git add *` 把資料夾裡的符合`*`的檔案全部丟進git裡，`*`是萬用字元所以凡在資料夾裡的檔案都會被丟進去。
`git commit -m "first commit"` 更新git把剛剛add後的東東變成一個叫first commit的版本
#### 檔案在記憶體裡的狀況:
### Git-push
git push origin main
git pull origin main
git log
Bar:我怠惰了，找時間再回來更新剩下的
New Bar:I'm back.
### clone別人的專案
>git clone https://github.com/githubid/projectname
>clone似乎會把下面那整套都做完的樣子，不用特別init
### 在新電腦上pull新資料夾
>git init
>git remote origin https://github.com/你github的名字/名稱
>git branch -M main
>git pull origin main
>第一次拉還是推薦用clone第二次後再用pull
### push新檔案上去
>git add *
>git commit -m "commit name(可以自己取名)"
>git push
這個時候會報錯叫你交出mail跟name，照著指示登入github然後打他叫你打的指令即可。在自己的電腦上試一次吧!
---
---
# 複雜度分析
## 前言
如何分辨一個演算法是不是好的演算法呢?
判斷這個問題，我們一般從兩個角度下手:時間和空間(是一切規則的起點 by莫拉)
而比較常用來盼端時、空間是多或少的方法，就是家喻戶曉(有嗎)的BIG-O啦!!!
## 複雜度
程式都會有複雜度，我們一般認為複雜度大的程式比較爛，相對的，複雜度小的程式就超棒。
當然，如果你的目的是幹爛別人的電腦的話，你可以直接寫一個while(true)。
## Big-O
數學定義
f(n) ∈ O(g(n)) ⇐⇒ ∃k > 0, ∃N, ∀n > N, f(n) ≤ k · g(n)
### 實用層面理解的話
#### 科技進步
k常數代表在複雜度計算時，常數可以忽略。
因為電腦的進步程度是倍數成長的，今天不能使用演算法或許幾年後會是最棒的演算法。
#### 成長程度
常數N代表在n>N時，f(n)的執行時間(或空間)會穩定小於g(n)的。
我們一般假設N趨近於無限。
我們用張圖來解釋為甚麼要這樣做。
可以發現O(log n)在input size小於某個數字的時候是比O(n)大的。但O(log n)明顯是個更好的複雜度，所以條件才會多一個n要大於N。
### 常見的複雜度
Sign in with Wallet
Connect another wallet