108年延平校內程式設計競賽

108年延平校內程式設計競賽

題目:

1.由小到大輸出
2.羊吃草
3.判斷英文字母是否為迴文
4.求相加的總和及進位次數
5.兩迷宮出口的最短路徑
6.換最少的銅板數量
7.數字系統

解法:

1.由小到大輸出

解說:

很基礎的由小到大輸出

code:

1. #include<iostream>
2. using namespace std;
3. int main(){
4.  int a,b;
5.  while(cin>>a>>b){
6.   if(a>b){
7.    int t=a;
8.    a=b;
9.    b=t;
10.   }
11.   for(int i=a;i<b;i++)cout<<i<<' ';
12.   cout<<b<<'\n';
13.  }
14. }

2.羊吃草

解說:

輸入N(1<=N<=100000)

然後有N個整數

求以此整數為半徑長的3/4扇形的面積

code:

#include<iostream>


#include<iomanip>


#define PI 3.14159265358979323846


using namespace std;


int main(){


    int n;


    cin>>n;


    while(n--){


        long double a;


        cin>>a;


        cout<<fixed<<setprecision(1)<<a*a*PI*0.75<<'\n';


    }


}

3.判斷英文字母是否為迴文

解說:

判斷一字串有無可能經重新排列後形成迴文

code:

#include<iostream>


using namespace std;


int main(){


 string s;


 while(cin>>s){


  int a[26]={0};


  for(int i=0;i<s.length();i++){


   if(s[i]>='a'&&s[i]<='z')a[s[i]-'a']++;


   if(s[i]>='A'&&s[i]<='Z')a[s[i]-'A']++;


  }


  int ans=0;


  for(int i=0;i<26;i++){


   if(a[i]%2)ans++;


  }


  if(ans<=1)cout<<"Yes\n";


  else cout<<"No\n";


  for(int i=0;i<26;i++){


   if(a[i]>0)cout<<(char)(i+'A')<<":"<<a[i]<<'\n';


  }cout<<'\n';


 }


}

4.求相加的總和及進位次數

解說:

有兩個正整數n,m(n,m<=10^100)

求他們相加時的進位次數和運算結果

code:

1. #include<iostream>
2. using namespace std;
3. int main(){
4.  int n;
5.  cin>>n;
6.  while(n--){
7.   string a,b;
8.   cin>>a>>b;
9.   int c[102]={0},d[102]={0},e[102]={0},ans=0;
10.   for(int i=0;i<a.length();i++){
11.    c[a.length()-i-1]=a[i]-'0';
12.   }
13.   for(int i=0;i<b.length();i++){
14.    d[b.length()-i-1]=b[i]-'0';
15.   }
16.   for(int i=0;i<=max(a.length(),b.length());i++){
17.    e[i]=c[i]+d[i];
18.   }
19.   for(int i=0;i<=max(a.length(),b.length());i++){
20.   if(e[i]>=10){
21.     ans++;
22.     e[i+1]+=(e[i]/10);
23.     e[i]%=10;
24.    }
25.   }
26.    for(int i=max(a.length(),b.length());i>=0;i--){
27.     if(e[i]==0&&i==max(a.length(),b.length()))i=i;
28.     else cout<<e[i];
29.   }
30.   cout<<' '<<ans<<'\n';
31.  }
32. }

5.兩迷宮出口的最短路徑

解說:
輸入兩個數n,m(3<=n,m<=100),分別代表迷宮的長、寬
再來輸入大小為n*m的迷宮
迷宮由起點"s",終點"g",通道"."和牆壁"#"組成
起點必位於迷宮的左上角
其中一個終點必為於迷宮的左下角
另一個終點必位於迷宮的右下角
請求出從起點到終點所需的最小步數

*本題假定一定能從起點走到終點

使用BFS,並用queue實現

code:

1. #include<iostream>
2. #include<queue>
3. #include<utility>
4. using namespace std;
5. int n,m;
6. char maze[100][100];
7. int d[100][100];
8. #define UF 10000
9. typedef pair<int,int> pa;
10. int dn[4]={0,1,0,-1},dm[4]={1,0,-1,0};
11. int bfs(){
12.     queue<pa> que;
13.     for(int i=0;i<n;i++){
14.         for(int j=0;j<m;j++){
15.             d[i][j]=UF;
16.         }
17.     }
18.     int sn=0,sm=0;
19.     int gn1=n-1,gm1=m-1;
20.     int gn2=n-1,gm2=0;
21.     que.push(pa(sn,sm));d[sn][sm]=0;
22.     while(que.size()){
23.         pa p=que.front();que.pop();
24.         if((p.first==gn1&&p.second==gm1)||(p.first==gn2&&p.second==gm2))break;
25.         for(int i=0;i<4;i++){
26.             int tn=p.first+dn[i],tm=p.second+dm[i];
27.             if(tn>=0&&tn<n&&tm>=0&&tm<m&&maze[tn][tm]!='#'&&d[tn][tm]==UF){
28.                 que.push(pa(tn,tm));
29.                 d[tn][tm]=d[p.first][p.second]+1;
30.             }
31.         }
32.     }
33.     if(d[gn1][gm1]>d[gn2][gm2])return d[gn2][gm2];
34.     else return d[gn1][gm1];
35. }
36. int main(){
37.     cin>>n>>m;
38.     for(int i=0;i<n;i++){
39.         for(int j=0;j<m;j++){
40.             cin>>maze[i][j];
41.         }
42.     }
43.     cout<<bfs()<<'\n';
44. }

6.換最少的銅板數量

解說:

輸入不同面值的銅板,再輸入一個金額,窮舉所有能湊出此金額的銅板數及最少需要的銅板數
使用DFS(深度優先搜索法)

code:

#include<iostream>


#include<vector>


using namespace std;


vector<int>coin;


int money,sum=100;


void change(int tempmoney,vector<int>ans,int j){


 if(tempmoney==0){


  int tempmin=0;


  printf("(");


  for(int i=0;i<ans.size();i++){


   printf("%d",ans[i]);


   if(i<ans.size()-1)printf(",");


   tempmin+=ans[i];


  }


  printf(")\n");


  if(tempmin<sum)sum=tempmin;


 }


 if(j<coin.size()){


  for(int i=0;i<=money/coin[j];i++){


   if(tempmoney-coin[j]<0)return;


   if(i){tempmoney-=coin[j],ans[j]++;}


   change(tempmoney,ans,j+1);


  }


 }


}


int main(){


 int n;


 while(scanf("%d",&n)==1){


  vector<int>ans;


  for(int i=1,in;i<=n;i++){


   scanf("%d",&in);


   coin.push_back(in);


   ans.push_back(0);


  }


  scanf("%d",&money);


  change(money,ans,0);


  printf("%d\n\n",sum);


  coin.clear();


  ans.clear();


  sum=100;


 }


}

7.數字系統

解說:
有一個數字系統為七進位制
其中:
'#' 代表 0
'%' 代表 1
'$' 代表 2
'&' 代表 3
'\' 代表 4
'~' 代表 5
'!' 代表 6
'@'代表 -1
輸入一個由此數字系統表示的數字
輸出此數用十進位制表示的結果
*(注):此題測資是用pow生的,若不是用pow運算會因為浮點數誤差而WA
code:

#include<iostream>


#include<cmath>


using namespace std;


/*long long mypow(long long b){


 long long c=1;


  for(int i=1;i<=b;i++){


  c=c*7;


 }


 return c;


}*/


int main(){


 char a[8]={'#','%','$','&',92,'~','!','@'};


 long long c[8]={0,1,2,3,4,5,6,-1};


 string s;


 while(cin>>s&&s!="0"){


  long long ans=0;


  for(int i=0;i<s.length();i++){


  for(int j=0;j<8;j++){


   if(s[i]==a[j]){


    ans+=(c[j]*pow(7,s.length()-i-1));


   }


  }


 }cout<<ans<<'\n';


 }


}

本人的分享到此結束
若有更好的想法或建議,請在留言區留言喔