---
# System prepended metadata

title: 程式觀念

---

# 程式觀念

如果是使用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.選擇排序

![image](https://hackmd.io/_uploads/HyMwPo1lke.png)

以下是選擇排序的範例程式碼

:::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.氣泡排序

![image](https://hackmd.io/_uploads/Bk973jylye.png)

以下是氣泡排序的範例程式碼

:::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(堆疊) 用法

![image](https://hackmd.io/_uploads/B11WbnXg1e.png)
==先進後出==

以下是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(佇列) 用法

![image](https://hackmd.io/_uploads/r1zBp3QxJx.png)
==先進先出==

以下是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.讓電腦計算你輸入的運算式(後序運算式)

我們平常生活中用的計算方式都是中序運算式，可是電腦不懂得如何處理中序運算式，所以電腦會先把中序運算式轉成後序運算式。

![image](https://hackmd.io/_uploads/BygMspExJe.png)

題目：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"; 
	}
}
```
:::