# 程式觀念
如果是使用Dev C++去撰寫程式
記得要去"工具>>編譯器選項>>一般"，打勾"呼叫編譯器時加入以下命令，並且輸入"
```
-std=c++11
```
參考資料：https://blog.csdn.net/qq_44631615/article/details/109263351
## 1. 二分搜
以下是二分搜的範例程式碼
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int search(const int (&a)[10],int start,int end,int target){
if(start>end || target>a[end] || target<a[start])
return -1;
int mid=(start+end)/2;
if(target==a[mid]) return mid;
else if(target>a[mid]) search(a,mid+1,end,target);
else search(a,start,mid-1,target);
}
int main(){
int a[10]={1,12,20,42,56,67,84,95,100,120};
int size=sizeof(a)/sizeof(a[0]);
int target=56;
int result=search(a,0,size-1,target);
result==-1?
cout<<"沒有在陣列中找到目標"<<target:
cout<<"在索引:"<<result<<" 找到目標"<<target;
}
```
:::
練習題目：https://zerojudge.tw/ShowProblem?problemid=d732
解答：
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int search(int a[],int start,int end,int target){
if(start>end || target>a[end] || target<a[start])
return 0;
int mid=(start+end)/2;
if(target==a[mid]) return mid+1;
else if(target>a[mid]) search(a,mid+1,end,target);
else search(a,start,mid-1,target);
}
int main(){
int n,t;
cin>>n>>t;
int a[n],target[t],result[t];
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<t;i++) cin>>target[i];
for(int i=0;i<t;i++){
int tt=target[i];
result[i]=search(a,0,n-1,tt);
}
for(int i=0;i<t;i++){
cout<<result[i]<<"\n";
}
}
```
:::
影片介紹：https://youtu.be/zmaui9rUhe0?si=U7kP7EYbkhrQp_3h
## 2.印出一顆愛心
以下是印出一顆愛心的範例程式碼
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
double a=1;
double bond=1.3*sqrt(a);
double step=0.05;
for(double y=bond;y>=-bond;y-=step){
for(double x=-bond;x<=bond;x+=0.5*step){
if(pow((pow(x,2)+pow(y,2)-a),3)-pow(x,2)*pow(y,3)<=0)
cout<<"*";
else
cout<<" ";
}
cout<<"\n";
}
}
```
:::
影片介紹：https://youtu.be/_jxmTs5HEAA?si=7uBIn-pt5PyeU8_K
## 3.選擇排序
以下是選擇排序的範例程式碼
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[]={5,9,101,21,50,28,52,41,63,74};
int size=sizeof(a)/sizeof(a[0]);
for(int i=0;i<size;i++){
int min_index=i;
for(int j=i+1;j<size;j++){
if(a[min_index]>a[j]) min_index=j;
}
swap(a[i],a[min_index]);
}
for(int i=0;i<size;i++) cout<<a[i]<<" ";
}
```
:::
==ps. 有很多人會把它跟氣泡排序法搞混==
影片介紹：https://youtu.be/Nn3SRxPnZB0?si=IhiVIWlTW77nf4zs
## 4.氣泡排序
以下是氣泡排序的範例程式碼
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[]={5,9,101,21,50,28,52,41,63,74};
int size=sizeof(a)/sizeof(a[0]);
for(int i=0;i<size;i++){
for(int j=0;j<size-1-i;j++){
if(a[j]>a[j+1]){
swap(a[j],a[j+1]);
}
}
}
for(int i=0;i<size;i++) cout<<a[i]<<" ";
}
```
:::
影片介紹：https://youtu.be/-YHUGj1yG1s?si=hiBNCTs-UagFSMji
## 5.vector 用法
==vector相較一般的陣列有更加靈活的操作，例如：長度的限制、陣列大小需要自己算...==
以下是vector的範例程式碼
:::spoiler
```cpp=
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int main(){
//默認初始化
vector<int> v1;
//列表初始化
vector<char> v2={'a','b','c'};
//也可以不用加等號
vector<char> v3{'a','b','c'};
//直接初始化(把長度訂出來)
vector<char> v4(4);
//直接初始化(把初始化的值全變100)
vector<int> v5(4,100);
//訪問元素
cout<<"更改前："<<v5[3]<<"\n";
//更改元素
v5[3]=10;
cout<<"更改後："<<v5[3]<<"\n\n";
//查看長度
int length=v5.size();
cout<<"v5的長度："<<length<<"\n";
//遍歷所有元素
for(int i=0;i<length;i++)
cout<<v5[i]<<" ";
cout<<"\n";
//更便利的方式
for(int j:v5)
cout<<j<<" ";
cout<<"\n";
//添加元素
v5.push_back(65);
for(int j:v5)
cout<<j<<" ";
cout<<"\n";
}
```
:::
影片介紹：https://youtu.be/R8GoFdza8Fw?si=lgO3F1YN8MP44a2l
## 6.stack(堆疊) 用法
==先進後出==
以下是stack的範例程式碼
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
//默認初始化
stack<int> stack;
//訪問頂端元素
stack.top()
//從頂端移出元素(注意:如果stack為空，在pop時會崩潰)
stack.pop();
//查看stack內有多少元素
stack.size();
//將元素放入stack頂端
stack.push();
//判斷stack是否為空(空:1 有元素:0)
stack.empty();
}
```
:::
練習題目：https://zerojudge.tw/ShowProblem?problemid=i213
解答：
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,c=0;
cin>>n;
long long int log[n];
stack<int> stack;
for(int i=0;i<n;i++){
int k;
cin>>k;
if(k==1){
long int x;
cin>>x;
stack.push(x);
}
else if(k==2){
if(stack.empty()) log[c]=-1;
else log[c]=stack.top();
c++;
}
else if(k==3){
if(stack.empty()==0) stack.pop();
}
}
for(int i=0;i<c;i++) cout<<log[i]<<"\n";
}
```
:::
## 7.queue(佇列) 用法
==先進先出==
以下是queue的範例程式碼
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
//默認初始化
queue<int> queue;
//訪問最前面元素
queue.front()
//訪問最後面元素
queue.back()
//把最前面的元素移出(注意:如果queue為空，在pop時會崩潰)
stack.pop();
//查看queue內有多少元素
stack.size();
//將元素放入queue最後面
stack.push();
//判斷queue是否為空(空:1 有元素:0)
stack.empty();
}
```
:::
練習題目：https://zerojudge.tw/ShowProblem?problemid=e447
解答：
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,c=0;
cin>>n;
queue<int> q;
long int log[n];
for(int i=0;i<n;i++){
int x;
cin>>x;
if(x==1){
int y;
cin>>y;
q.push(y);
}
else if(x==2){
if(q.empty()) log[c]=-1;
else log[c]=q.front();
c++;
}
else if(x==3){
if(q.empty()==0) q.pop();
}
}
for(int i=0;i<c;i++) cout<<log[i]<<"\n";
}
```
:::
## 8.讓電腦計算你輸入的運算式(後序運算式)
我們平常生活中用的計算方式都是中序運算式，可是電腦不懂得如何處理中序運算式，所以電腦會先把中序運算式轉成後序運算式。
題目：https://zerojudge.tw/ShowProblem?problemid=f377
中序運算式 -> 後序運算式：
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
string s,c;
while(getline(cin,s)){
vector<string> out;
stack<string> st;
stringstream ss;
ss<<s;
while(ss>>c){
if(c==")"){
while(st.top()!="("){
out.push_back(st.top());
st.pop();
}
st.pop();
}
else if(c=="("){
st.push(c);
}
else if(c=="*" || c=="/"){
while(!st.empty() && (st.top()=="*" || st.top()=="/")){
out.push_back(st.top());
st.pop();
}
st.push(c);
}
else if(c=="+" || c=="-"){
while(!st.empty() && (st.top()=="*" || st.top()=="/" || st.top()=="+" || st.top()=="-")){
out.push_back(st.top());
st.pop();
}
st.push(c);
}
else{
out.push_back(c);
}
}
while(!st.empty()){
out.push_back(st.top());
st.pop();
}
for(int i=0;i<out.size();i++){
if(i==0) cout<<out[i];
else cout<<" "<<out[i];
}
cout<<"\n";
}
}
```
:::
題目：https://zerojudge.tw/ShowProblem?problemid=f698
後序運算式 -> 運算結果
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
string s,c;
stack<int> st;
stringstream ss;
getline(cin,s);
ss<<s;
while(ss>>c){
if(c=="+" || c=="-" || c=="*" || c=="/"){
int b=st.top(); st.pop();
int a=st.top(); st.pop();
if(c=="+") st.push(a+b);
else if(c=="-") st.push(a-b);
else if(c=="*") st.push(a*b);
else if(c=="/") st.push(a/b);
}
else{
st.push(stoi(c));
}
}
cout<<st.top();
}
```
:::
題目：https://zerojudge.tw/ShowProblem?problemid=a017
實際應用(上面兩個功能結合)：
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
string s,c;
while(getline(cin,s)){
stack<string> st;
vector<string> cale;
stringstream ss;
ss<<s;
while(ss>>c){
if(c==")"){
while(st.top()!="("){
cale.push_back(st.top());
st.pop();
}
st.pop();
}
else if(c=="("){
st.push(c);
}
else if(c=="+" || c=="-"){
while(!st.empty() && (st.top()=="*" || st.top()=="/" || st.top()=="+" || st.top()=="-" || st.top()=="%")){
cale.push_back(st.top());
st.pop();
}
st.push(c);
}
else if(c=="*" || c=="/" || c=="%"){
while(!st.empty() && (st.top()=="*" || st.top()=="/")){
cale.push_back(st.top());
st.pop();
}
st.push(c);
}
else{
cale.push_back(c);
}
}
while(!st.empty()){
cale.push_back(st.top());
st.pop();
}
stack<int> cc;
for(int i=0;i<cale.size();i++){
string c=cale[i];
if(c=="+" || c=="-" || c=="%" || c=="*" || c=="/"){
signed int b=cc.top(); cc.pop();
signed int a=cc.top(); cc.pop();
if(c=="+") cc.push(a+b);
else if(c=="-") cc.push(a-b);
else if(c=="*") cc.push(a*b);
else if(c=="/") cc.push(a/b);
else if(c=="%") cc.push(a%b);
}
else{
cc.push(stoi(c));
}
}
cout<<cc.top()<<"\n";
}
}
```
:::
影片介紹：https://youtu.be/1pWR4Qm6fAM?si=MHupCEa9UwYiWujp
## 9.加快計算質數(埃拉托斯特尼篩法)
想要計算質數，如果使用傳統的方式，從 1 找到 n-1 ，時間複雜度會很大。
如果想要加快的話，可以套用以下的規則。
>[!Note]方法
1 . 如果遇到 1 ，就返回 "False"
2 . 如果遇到 2、3 ，就返回 "True"
3 . 如果可以被 2、3 整除，就返回 "Talse"
4 . 質數都是 6 的倍數加減 1
5 . 做到 sqrt(n) 就好了
練習題目：https://zerojudge.tw/ShowProblem?problemid=a121
解答：
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int cale(int n){
if(n==1) return 0;
else if(n<=3) return 1;
else if(n%2==0 || n%3==0) return 0;
for(int j=5;j*j<=n;j+=6){
if(n%j==0 || n%(j+2)==0) return 0;
}
return 1;
}
int main() {
int a,b;
while(cin>>a>>b){
int all=0;
for(int i=a;i<=b;i++){
if(cale(i)) all++;
}
cout<<all<<"\n";
}
}
```
:::
Sign in with Wallet
Connect another wallet