# **APCS程式選修**

這些是本學期在程式選修上課時，自己練習實作題時，有完成的程式碼。

## 心得
覺得有些程式碼應該能更簡化且讓記憶體使用的更少，以達到縮時，像是費氏數列，自己在寫其他類似的題目時很容易就超時(TLE)，導致測資不通過。

## 題庫
- [秘密差](#秘密差)
- [排隊](#排隊)
- [費氏數列-遞迴](#費氏數列-遞迴)
- [最後倒數](#最後倒數)
- [找最大值](#找最大值)
- [特殊編碼](#特殊編碼)

## 秘密差
題目來源:[ZJ c290](https://zerojudge.tw/ShowProblem?problemid=c290)

程式:

#include<bits/stdc++.h>
using namespace std;
string x;
int a,b;
int main(){
    cin>>x;
    int len=x.length();
    for(int i=0;i<len;i++){
        if(i%2!=0)a=a+x[i]-48;
        else b=b+x[i]-48;
    }
    cout<<abs(a-b)<<endl;
}

想法:
分別計算奇數位和偶數位的總和，再相減取絕對值(abs)，因為ASCII碼，所以讀進來的數字要減48。

## 排隊
題目來源:[GJ c049](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=c049)

程式:

#include<bits/stdc++.h>
using namespace std;
//by icerain
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,sum;
cin>>n;
int a[n],b[n],c[n];
for(int i=0;i<n-1;i++){
	cin>>a[i]>>b[i];
}
c[0]=a[0];
for(int j=1;j<n;j++){
	if(a[j]==b[j-1]){
		c[j]=a[j];
	}
}
c[n-1]=b[n-2];
sum=c[0]%997;
for(int k=1;k<n;k++){
	sum=(sum*7+c[k])%997;
}
cout<<sum;
return 0;
}

想法:
以第一個輸入的數字為開頭，開始循序搜尋去排出完整的陣列後再做計算。

## 費氏數列-遞迴
題目來源:[GJ b022](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b022)

程式:

#include<bits/stdc++.h>
using namespace std;
int sum=0;
long long f(int n){
    sum++;
    if(n==0)return 0;
    if(n==1)return 1;
        return f(n-1)+f(n-2);
    
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    int n;
    cin>>n;
    cout<<f(n)<<" ";
    cout<<sum<<endl;
}

想法:
直接套用常用的費氏數列的遞迴函式，再加以改寫。
費氏數列:

#include<bits/stdc++.h>
using namespace std;
long long F[1000005];
long long f(int n){
	if(n==1)return 1;
	if(n==2)return 2;
	if(F[n])return F[n];
	return F[n]=f(n-1)+f(n-2);
}
int main(){
	int n;
	cin>>n;
	while(n!=0){
	cout<<f(n)<<endl;
	cin>>n;
	}
}

## 最後倒數
題目來源:[GJ b001](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b001)

程式:

#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
long long n;
cin>>n;
long long a[n];
for(long long i=0;i<n;i++){
	cin>>a[i];
}
for(long long j=n-1;j>=0;j--){
	cout<<a[j]<<" ";
}
return 0;
}

想法:
單純使用一維陣列去紀錄，再由後往前輸出。

## 找最大值
題目來源:[GJ b002](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b002)

程式:

#include<bits/stdc++.h>
using namespace std;
//by icerain
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
int a[n];
int max=0,s;
for(int i=0;i<n;i++){
	cin>>a[i];
	if(a[i]>max){
	max=a[i];
	s=i+1;
	}
}
cout<<s<<" "<<max;
return 0;
}

想法:
一個一個循序比較，只記錄最大值跟在第幾個。

## 特殊編碼
題目來源:

程式:

#include<bits/stdc++.h>
using namespace std;
//by icerain
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
int a,b,c,d;
cin>>n;
for(int i=0;i<n;i++){
	cin>>a>>b>>c>>d;
	if(a){
		if(b){
			if(d)cout<<"D";
			else cout<<"F";
		}
		else cout<<"E";
	}
	else{
		if(b){
			if(c)cout<<"B";
			else cout<<"A";
		}
		else cout<<"C";
	} 
}
return 0;
}

想法:
每個字元都由四個0或1組成，所以從是0或是1為分支，慢慢去搜尋出來。
類似題:[ZJ e283](https://zerojudge.tw/ShowProblem?problemid=e283)

## 資料來源
題目都是老師給的，但是有備註在哪裡抓到的，APCS的題目則是能在ZERO JUDGE找到。

高中生程式解題系統(ZJ):https://zerojudge.tw/
台中女中程式解題系統(GJ):http://www.tcgs.tc.edu.tw:1218/

---
###### tags: `C/C++` `APCS`