# 演算法課程題解 - 巢狀迴圈
# TOJ 104
## 題目
https://toj.tfcis.org/oj/pro/104/
輸入一個正整數 $n$ ，輸出高度為 $n$ 的星星樹
## 解法 By Koios1143
### 想法
第一次接觸星星樹這類的題目可以藉由觀察來寫下迴圈
我們可以先把星星樹的每一層給一個數字
以下考慮 $n=4$ 的情況
```
0 | *
1 | ***
2 | *****
3 |*******
```
接下來觀察每一行內空格和數字的關係
```
第 0 行 有 3 個空格
第 1 行 有 2 個空格
第 2 行 有 1 個空格
第 3 行 有 0 個空格
```
因為空個的數量與 $n$ 息息相關，我們換成與 $n$ 相關的話來看看
```
第 0 行 有 n-1 個空格
第 1 行 有 n-2 個空格
第 2 行 有 n-3 個空格
第 3 行 有 n-4 個空格
```
再加上與行數的關係
```
第 0 行 有 (n-1)-0 個空格
第 1 行 有 (n-1)-1 個空格
第 2 行 有 (n-1)-2 個空格
第 3 行 有 (n-1)-3 個空格
```
發現到關係了嗎? 那麼我們也考慮星星的情況
```
第 0 行 有 1 個星星
第 1 行 有 3 個星星
第 2 行 有 5 個星星
第 3 行 有 7 個星星
```
星星的數量無論 $n$ 是多少，順序仍然相同，都是從 $1$ 開始，並且每次加上 $2$ ，所以接下來直接考慮與行數的關係
```
第 0 行 有 (0+1)*2-1 個星星
第 1 行 有 (1+1)*2-1 個星星
第 2 行 有 (2+1)*2-1 個星星
第 3 行 有 (3+1)*2-1 個星星
```
有了這些關係式，我們就可以輕易地寫出巢狀迴圈了
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main() {
int n;
cin>>n;
// i 表示行數
for(int i=0 ; i<n ; i++){
// 先輸出空格
for(int j=0 ; j<n-1-i ; j++){
cout<<' ';
}
// 再輸出星星
for(int j=0 ; j<2*(i+1)-1 ; j++){
cout<<'*';
}
cout<<'\n';
}
return 0;
}
```
### 複雜度分析
總時間複雜度約為 $O(n^2)$
# TOJ 110
## 題目
https://toj.tfcis.org/oj/pro/110/
第一行有一個正整數數 $n$，接下來有 $n$ 行，每行有一個數，表示三角形的高度
請依照題目的樣子輸出六芒星
例如 $n = 4$ 時輸出
```
*
*******
*****
*******
*
```
$n = 5$ 時輸出
```
*
***
*********
*******
*********
***
*
```
## 解法 By Koios1143
### 想法
把六芒星拆成上面的三角形、中間三個橫線、下面的三角形來輸出
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n;
while(n--){
cin>>m;
// 上面星星樹樹
// i 表示行數
for(int i=0 ; i<m-3 ; i++){
// 先輸出空白
for(int j=0 ; j<m-1-i ; j++){
cout<<' ';
}
// 再輸出星星
for(int j=0 ; j<(i+1)*2-1 ; j++){
cout<<'*';
}
cout<<'\n';
}
// 中間三條線
for(int i=0 ; i<2*m-1 ; i++){
cout<<'*';
}
cout<<"\n ";
for(int i=0 ; i<2*m-3 ; i++){
cout<<'*';
}
cout<<"\n";
for(int i=0 ; i<2*m-1 ; i++){
cout<<'*';
}
cout<<'\n';
// 下面星星樹
// i 表示行數
for(int i=0 ; i<m-3 ; i++){
// 先輸出空白
for(int j=0 ; j<3+i ; j++){
cout<<' ';
}
// 再輸出星星
for(int j=0 ; j<(m-3)*2-1-2*i ; j++){
cout<<'*';
}
cout<<'\n';
}
}
return 0;
}
```
### 複雜度分析
總時間複雜度約為 $O(n(2m^2 + 3m))$ 約為 $O(nm^2)$
# UVa 382
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?382
給很多個數字 $n$ ，對於每個 $n$ ，求該數字的所有因數，不包含自己本身的總和
如果等於輸出 `PERFECT` ，若小於輸出 `DEFICIENT` ，若大於輸出 `ABUNDANT`
## 解法 By Koios1143
### 想法
對於每個 $n$ 暴力掃過一遍看看有那些因數，加總起來判斷
至於輸出要對齊的部分，這邊採用 log 的方式得知求出的數字是幾位數，進而判斷出應該要填充多少的空格
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<cmath>
using namespace std;
int n, cnt=0;
int main(){
cout<<"PERFECTION OUTPUT\n";
while(cin>>n && n){
cnt=0;
for(int i=1 ; i<n ; i++){
if(n%i==0){
cnt+=i;
}
}
for(int i=0, p=5-((int)log10(n)+1) ; i<p ; i++){
cout<<' ';
}
cout<<n<<" ";
if(cnt==n){
cout<<"PERFECT\n";
}
else if(cnt<n){
cout<<"DEFICIENT\n";
}
else{
cout<<"ABUNDANT\n";
}
}
cout<<"END OF OUTPUT\n";
return 0;
}
```
### 複雜度分析
每筆測試資料時間複雜度為 $O(n)$
# UVa 488
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?488
輸入兩個整數 $a, f$ 表示三角形波的振幅以及頻率，請輸出該三角波
## 解法 By Koios1143
輸出格式要多加留意
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int t,f,a;
bool out=false;
int main(){
cin>>t;
while(t--){
if(out)
cout<<"\n";
else
out=true;
cin>>a>>f;
for(int i=0 ; i<f ; i++){
if(i!=0)
cout<<"\n";
// 上大三角
for(int j=1 ; j<=a ; j++){
for(int k=1 ; k<=j ; k++){
cout<<j;
}
cout<<'\n';
}
// 下小三角
for(int j=a-1,l=0 ; j>=1 ; j--, l++){
for(int k=a-1-l ; k>0 ; k--){
cout<<j;
}
cout<<"\n";
}
}
}
return 0;
}
```
### 複雜度分析
每筆測試資料時間複雜度約為 $O(2f(a^2))$
總時間複雜度約為 $O(2tf(a^2))$
# UVa 11074
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11074
依照題目需求輸出圖形
## 解法 By Koios1143
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main(){
int s,t,n,l,Case=1;
while(cin>>s>>t>>n && (s!=0 && t!=0 && n!=0)){
cout<<"Case "<<Case++<<":\n";
l=s*n+t*(n+1);
for(int k=0 ; k<n ; k++){
for(int i=0 ; i<t ; i++){
for(int j=0 ; j<l ; j++){
cout<<'*';
}
cout<<"\n";
}
for(int i=0 ; i<s ; i++){
for(int j=0 ; j<n ; j++){
for(int p=0 ; p<t ; p++){
cout<<'*';
}
for(int p=0 ; p<s ; p++){
cout<<'.';
}
}
for(int j=0 ; j<t ; j++){
cout<<'*';
}
cout<<"\n";
}
}
for(int i=0 ; i<t ; i++){
for(int j=0 ; j<l ; j++){
cout<<'*';
}
cout<<"\n";
}
cout<<"\n";
}
return 0;
}
```
### 複雜度分析
每筆測試資料時間複雜度為 $O((s*n+t*(n+1))^2)$
###### tags: `SCIST 演算法 題解`
Sign in with Wallet
Connect another wallet