###### tags: `多元選修`
# 基礎程式設計
<br />
## 一、CH1 變數與運算子
1. ### a001 哈囉
- 輸入 一個字串
- 輸出 hello, 你所輸入字串
```cpp=
#include <iostream>
#include <string>
using namespace std;
int main(int argc, const char * argv[])
{
string str;
while (cin>>str)
{
cout<<"hello, "<<str<<endl;
}
return 0;
}
```
2. ### a002 簡易加法
```cpp=
#include <iostream>
#include <string>
using namespace std;
int main(int argc, const char * argv[])
{
int a,b;
while(cin>>a>>b)
{
cout<<a+b<<endl;
}
return 0;
}
```
3. ### d489 伏林的三角地
- 海龍公式計算三角形面積
- 須使用整數型別否則會有誤差
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
unsigned long long int a,b,c;
while(cin>>a>>b>>c)
{
int s;
s = (a+b+c)/2;
s = s*(s-a)*(s-b)*(s-c);
cout<< s << endl;
}
return 0;
}
```
4. ### d827 買鉛筆
```cpp=
#include <iostream>
#include <string>
using namespace std;
int main()
{
int num;
while (cin>>num)
{
if(num<12)
{
cout<<5*num<<endl;
}
else
{
if(num==12)
{
cout<<50<<endl;
}
int sum;
sum=num/12;
cout<<((num%12)*5)+(50*sum)<<endl;
}
}
return 0;
}
```
5. ### d060 還要等多久啊？
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
unsigned int a;
while(cin>>a)
{
a >25 ? cout<<60-a+25 : cout<<25-a;
}
return 0;
}
```
6. ### d485 我愛偶數
```cpp=
#include <iostream>
#include <cmath>
int main()
{
int x,y,count;
while(std::cin>>x>>y)
{
while(x<=y)
{
if((x%2)==0)
{
count++;
}
x++;
}
std::cout<<count;
}
return 0;
}
```
7. ### d051 糟糕，我發燒了！
```cpp=
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
double f;
while(std::cin>>f)
{
f=(f-32)*5/9;
cout<<fixed<<setprecision(3)<<f;
}
return 0;
}
```
8. ### b004 繩子上吃草的牛
```cpp=
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main()
{
double a,b,c,d,p;
p = 4*atan(1);
while(cin>> a >> b)
{
if(a<b)
{
int t;
t=a;
a=b;
b=t;
}
c = a/2;
d = sqrt((a/2*a/2)-(b/2*b/2));
cout<<fixed<<setprecision(3)<< p*c*d << "\n";
}
return 0;
}
```
9. ### d039 11044 - Searching for Nessy
```cpp=
#include <iostream>
using namespace std;
int main()
{
int n,m,t;
cin >> t;
while (cin>> n>> m)
cout << (n/3) * (m/3) << endl;
return 0;
}
```
<br />
## 二、CH2 條件判斷
1. ### a012 10055 - Hashmat the Brave Warrior
```cpp=
#include <iostream>
using namespace std;
int main()
{
long long int m,n,ans;
while(cin >> m >>n)
{
if( m>n )
{
cout << m-n << endl;
}
else
{
cout << n-m << endl;
}
}
return 0;
}
```
2. ### d065三人行必有我師
- &&運算子
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int a,b,c;
while(cin>> a >> b >> c)
{
if(a>b&&a>c)
cout<< a << endl;
else
if(b>c)
cout<< b <<endl;
else
cout<< c << endl;
}
}
```
3. ### d984 棄保效應
```cpp=
#include <iostream>
using namespace std;
int main()
{
unsigned long long int a,b,c;
while(cin>> a >> b >> c)
{
if( (a>b+c) || ((c>a&&a>b) && a+b>c) || ((b>a&&a>c) && a+c>b) )
cout<< "A" << endl;
else if ( (b>a+c) || ((c>b&&b>a) && a+b>c) || ((a>b&&b>c) && b+c>a) )
cout<< "B" << endl;
else
cout<< "C" << endl;
}
return 0;
}
```
4. ### a004 文文的求婚
```cpp=
#include <iostream>
using namespace std;
int main()
{
int year;
while(cin>>year)
{
if((year%4)==0&&(year%100)!=0)
{
cout<<"閏年"<<endl;
}
else
{
if((year%4)==0&&(year%100)==0)
{
if((year)%400==0)
{
cout<<"閏年"<<endl;
}
else
{
cout<<"平年"<<endl;
}
}
else
{
cout<<"平年"<<endl;
}
}
}
}
```
<br />
## 三、CH3 重複結構
1. ### d490 我也愛偶數
- for
- i=i+1(i++)
- 變數初值，區塊變數 v.s. 區域變數
- 先練習1+2+3+…+n，int sum 除錯練習1
```cpp=
#include <iostream>
using namespace std;
int main()
{
int a, b;
while (cin>> a >> b)
{
int sum=0;
for (int i=a; i<=b; i++)
{
if(i%2==0)
sum+=i;
}
cout << sum << endl;
}
return 0;
}
```
2. ### d074 電腦教室
```cpp=
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n)
{
int maxx=-1,p;
for (int i=0;i<n;i++)
{
cin >> p;
if (p>maxx)
{
maxx=p;
}
}
cout << maxx << endl;
}
return 0;
}
```
3. ### a215 明明愛數數
- do_while迴圈
```cpp=
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin>> n >> m)
{
int count=0,sum=0;
do
{
sum+=n;
count++;
n++;
}
while(sum<=m);
cout<< count << endl;
}
return 0;
}
```
4. ### a024 最大公因數(GCD)
- 利用展轉相除法 (a=bq+r，則gcd(a, b) = gcd(b, r))
- 使時間複雜度降至O(log(n))
- do_while迴圈
```cpp=
#include <iostream>
using namespace std;
int main ()
{
int a,b;
while(cin>> a >> b)
{
int r = 0;
do
{
r = a%b;
a = b;
b = r;
}
while(r>0);
cout<< a << endl;
}
}
```
5. ### c418 Bert的三角形(1) c419 Bert的三角形(2)
- 巢狀迴圈(內外圈變數不能重複)
```cpp=
#include <iostream>
using namespace std;
int main ()
{
int n;
while(cin>> n)
{
for(int i=0; i < n; i++)
{
for(int j=0; j <=i ; j++)
{
cout<< "*";
}
cout<<endl;
}
}
return 0;
}
```
```cpp=
#include <iostream>
using namespace std;
int main ()
{
int n;
while(cin>> n)
{
for(int i=0; i < n; i++)
{
for(int k=0; k<n-i-1; k++)
{
cout<<"_";
}
for(int j=0; j <= i; j++)
{
cout<< "*";
}
cout<<endl;
}
}
return 0;
}
```
<br />
## 四、CH4 陣列
1. ### d212 東東爬階梯
- 一維陣列
- 費式數列
```cpp=
#include <iostream>
using namespace std;
int main()
{
int n;
unsigned long long int f[100]={1,1}; //unsigned lon long int只能到f[92]
for(int i=2;i<100;i++)
f[i]=f[i-1]+f[i-2];
while(cin >> n)
cout << f[n] << endl;
return 0;
}
```
2. ### c067 Box of Bricks
- 一維陣列
```cpp=
#include <iostream>
using namespace std;
int main()
{
int n,Set=1;
while(cin >> n && n>0)
{
int h[n],sum=0,ave,mov=0;
for (int i=0;i<n;i++)
{
cin >> h[i];
sum+=h[i];
}
ave=sum/n;
for (int i=0;i<n;i++)
{
if(h[i]>ave)
{
mov+=(h[i]-ave);
}
}
cout << "Set #" << Set++ << endl << "The minimum number of moves is " << mov << "." << endl << endl;
}
return 0;
}
```
3. ### a104 排序
- 利用insertion sort
```cpp=
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int M[n];
for(int i=0; i<n; i++)
cin>>M[i];
for(int i=1; i<n; i++)
{
int key=M[i],j=i-1;
while(M[j]>key && j>=0)
{
M[j+1]=M[j];
j--;
}
M[j+1]=key;
}
for(int i=0; i<n; i++)
cout<<M[i]<<" ";
cout<<endl;
}
return 0;
}
```
4. ### d452 二、直線最小距離和
- 利用selection sort
```cpp=
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main()
{
int n,T;
cin>>T;
while(T--)
{
cin>>n;
int M[n],sum=0;
for(int i=0; i<n; i++)
cin>>M[i];
for(int i=0; i<n-1; i++)
{
int index;
for(int j=i+1; j<n; j++)
{
if(M[index]>M[j])
index=j;
}
swap(M[index],M[i]);
}
for(int i=0; i<n; i++)
sum+=abs(M[n/2]-M[i]);
cout<<sum<<" ";
cout<<endl;
}
return 0;
}
```
5. ### d153 六、智力测验
- 時間複雜度O(n^2^)的排序法會TLE
- (n-1)+(n-2)+….+1=n(n-1)/2=n2/2-n/2，當n很大時，如1百萬時，500,000,000,000-500,000=499,999,500,000(n/2可以忽略)
- 其它排序演算法觀念
* [merge sort](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)
* [quick sort1](http://notepad.yehyeh.net/Content/Algorithm/Sort/Quick/Quick.php)
* [quick sort2](https://ithelp.ithome.com.tw/articles/10202330?sc=iThelpR)
- 排序演算法比較
* [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms)
* [Comparison Sorting Algorithms](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char** argv)
{
int T,n;
cin>>T;
while(T--)
{
cin>>n;
int s[n];
for(int i=0; i<n; i++)
{
cin>>s[i];
}
sort(s,s+n);
cout<<(n%2==1 ? (s[n/2]) : (s[n/2-1])) <<endl;
}
return 0;
}
```
6. ### a694: 吞食天地二
- 二維陣列
- C++ IO加速
``` javascript
ios::sync_with_stdio(false);
cin.tie(0);
```
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
while(cin>>n>>m)
{
int mat[n+1][n+1];
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin>>mat[i][j];
while(m--)
{
int r1,r2,c1,c2,sum=0;
cin>>r1>>c1>>r2>>c2;
for(int i=r1; i<=r2; i++)
for(int j=c1; j<=c2; j++)
sum+=mat[i][j];
cout<<sum<<endl;
}
}
return 0;
}
```
<br />
## 五、CH5 字元陣列、字串
1. ### a149: 乘乘樂
- 改寫為以字元陣列方式讀入
- 字串結束符號 '\0'
```cpp=
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int sum=1;
char n[11];
cin >> n;
for (int i=0;i<strlen(n);i++)
sum*=(int)n[i]-48;
cout << sum << endl;
}
return 0;
}
```
2. ### d124: 3的倍数
- 3的倍數判別法：各個數字和為3的倍數
```cpp=
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char n[10001];
while(cin>>n)
{
int sum=0;
for (int i=0;i<strlen(n);i++)
sum+=(int)n[i]-48;
cout << (sum%3==0?"yes":"no") << endl;
}
return 0;
}
```
3. ### a782: 4. Redundant Acronym Syndrome Syndrome
- getline(cin,字串名稱)
- toupper()將字元變大寫
```cpp=
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(int argc, char** argv)
{
string line;
while(getline(cin,line) && line != "END")
{
int index;
cout<<(char)(toupper(line[0]));
for(int i=1; i<line.size(); i++)
{
if(line[i]==' ')
{
cout<<(char)(toupper(line[i+1]));
index=i+1;
}
}
cout<<" ";
for(int i=index; i<line.size(); i++)
cout<<line[i];
cout<<endl;
}
return 0;
}
```
4. ### a011: 00494 - Kindergarten Counting Game
- 不能只算空的數量，字母的前一個是非字母即一個字
- 不能使用cin >> s
- cin.getline(s,1000)
- isalpha()
```cpp=
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(int argc, char** argv)
{
string line;
while(getline(cin,line))
{
int sum=0;
for(int i=0; i<line.size(); i++)
if(isalpha(line[i]) && !isalpha(line[i-1]))
sum++;
cout<<sum<<endl;
}
return 0;
}
```
5. ### a022: 迴文
- string類別
- getline(cin,str)
- str.length()
- i\-\-
- str.clear()
- 將字串反轉後比較是否相等
- reverse(str.begin(),str.end()) 需含入 algorithm 標頭檔
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char** argv)
{
string s;
while(cin>>s)
{
string rev=s;
reverse( s.begin(), s.end() );
cout<<(s == rev ? "yes" : "no") <<endl;
}
return 0;
}
```
6. ### a130: 12015 - Google is Feeling Lucky
- 找最大值
- struct(結構)
- printf()，需含入 cstdio 標頭檔
```cpp=
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main(int argc, char** argv)
{
int T,cnt=1;
struct rec
{
string name;
int v;
}web[10];
cin>>T;
while(T--)
{
int mx=0;
for(int i=0; i<10; i++)
{
cin>>web[i].name>>web[i].v;
if(web[i].v>mx)
mx=web[i].v;
}
printf("Case #%d:\n",cnt++);
for(int i=0; i<10; i++)
{
if(web[i].v==mx)
cout<<web[i].name<<endl;
}
}
return 0;
}
```
<br />
## 六、CH6 函式
1. ### d171: 飛蛾撲火(二)
- 內建函式：log10、floor
- logN^M^ = M*logN
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n,m;
while (cin >> n >> m) {
cout <<floor(m*log10(n)+ 1)<< endl;
}
return 0;
}
```
2. ### c039: 00100 - The 3n + 1 problem
- 自訂函式(先練習寫pow(n,m))
- 內建函式：swap、max、min
```cpp=
#include <iostream>
#include <cstdio>
using namespace std;
int func(int n)
{
int i=1;
while (n!=1)
{
if (n%2==1)
n=3*n+1;
else
n=n/2;
i++;
}
return i;
}
int main()
{
int a,b;
while(cin >> a >> b)
{
int ans=0;
for(int i=min(a,b);i<=max(a,b);i++)
ans=max(ans,func(i));
//cout <<a<<" "<<b<<" "<<ans<<endl;
printf("%d %d %d\n",a,b,ans);
}
return 0;
}
```
3. ### a215: 明明愛數數
- do_while迴圈
```cpp=
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin>> n >> m)
{
int count=0,sum=0;
do
{
sum+=n;
count++;
n++;
}
while(sum<=m);
cout<< count << endl;
}
return 0;
}
```
4. ### b112: 5.高中運動會
- 多個數的最大公因數
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int gcd(int a,int b)
{
while(a!=0 && b!=0)
{
if(a>b)
a=a%b;
else
b=b%a;
}
if(a==0)
return b;
else
return a;
}
int main()
{
int n;
while(cin>>n)
{
int num[n];
for(int i=0;i<n;i++)
cin >> num[i];
for(int i=1;i<n;i++)
num[i]=gcd(num[i],num[i-1]);
cout << num[n-1] << endl;
}
return 0;
}
```
5. ### a216: 數數愛明明
- 遞迴(先印出費式數列)
- long long int
- TLE(遞迴求一般項)
```cpp=
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
long long int num[30001],num2[30001];
num[1]=1; num2[1]=1;
for(int i=2;i<30001;i++)
{
num[i]=i+num[i-1];
num2[i]=num[i]+num2[i-1];
}
int n;
while(cin>>n&& n!='EOF')
{
cout<<num[n]<<" "<<num2[n]<<endl;
}
return 0;
}
```
6. ### a227: 三龍杯 -> 河內之塔
- [河內塔|樂和遊戲](http://www.novelgames.com/zh-HK/tower/)
- [河內塔程式參考](http://notepad.yehyeh.net/Content/DS/CH02/4.php)
```cpp=
#include <iostream>
#include <cstdio>
using namespace std;
void tower(int N,char a,char b,char c)
{
if(N>0)
{
tower(N-1,a,c,b);
printf("Move ring %d from %c to %c\n",N,a,c);
tower(N-1,b,a,c);
}
}
int main()
{
int N;
ios::sync_with_stdio(false);
cin.tie(0);
while (cin>>N)
{
tower(N,'A','B','C');
}
}
```
Sign in with Wallet
Connect another wallet