owned this note   changed 4 years ago  
Published Linked with GitHub

TCIRC C++教學講義

張皓凱、沈奕呈Nov 12,2021

tags:tcirc 社課 C++ 台中一中電研社

第四節社課

電研

講義都會公告在社網上
社網：tcirc.tw
IG：tcirc_39th
ig QRcode
online judge：judge.tcirc.tw

解題方法

以下的解題方法僅供參考，並不是唯一的方法。

解題主要可以分為五個部分，分別為：

  1. 讀題
  2. 輸入
  3. 儲存
  4. 運算
  5. 輸出

以下將分步驟講解

1.讀題

將題目全部讀過一次，把題目希望你做的東西抓出來，有些題目會有題目故事來混淆，通常故事內容不重要，把關鍵字句抓出來就好。這時就可以開始想需不需要用資料結構或演算法。

原本的題目

標完重點的題目

2.輸入

一般題目的輸入種類可以分為兩種

  1. 有說接下來有幾行，每行有幾幾筆資料
  2. 輸入直到EOF(常見於多筆測資)

分別對應的解決方法為

1. 有指定

  • 先輸入接下來的行數、字數，存在變數裡
  • 利用for loop來輸入每一個資料
  • 如果需要輸入一整行包含空格的字串記得使用cin.get或getline(cin,)

2.EOF

  • 直接使用while(cin)

題目通常會給每個資料的範圍，是用來決定資料型態和算複雜度會不會TLE(time limit exceeded)，常見的範圍有以下：

  • \(-2^{31}<x<2^{31}-1\)：代表可以用int存不會溢位
  • 會超過32位元整數、但不超過64位元整數：需要使用long long才不會溢位

3.儲存

輸入進來的資料可以存在數字、字元、字串、陣列。又或者是在儲存時需要用到不同的資料型態。

  • 數字：輸入的單筆資料是數字
  • 字元：輸入的單筆資料是字元
  • 字串：輸入的資料是字串
  • 陣列：輸入多筆相同型態、有關係或連續的的資料
  • 資料結構：樹、圖、陣列

4.運算

程式最主要的部分都發生在這裡，通常簡單的題目會直接說要做什麼，困難一點的的題目在文字中可以大概找出方向，再更進階的就需要用到演算法。剩下的就要靠不斷的刷題來判斷了。

5.輸出

輸出一般都不會太刁鑽只需要特別注意是以空格還是換行分隔。能用複製的字串就用複製的，不然大小寫、空格、拼字…很容易錯。

除錯

程式碼錯誤分成兩種：編譯錯誤(compile error,CE)和執行錯誤(runtime error,RE)。編譯錯誤是指程式碼有語法上的錯誤，編譯器會跳出錯誤而無法執行，執行錯誤是執行時出的錯誤，編譯器無法偵測，程式可以正常執行，只是結果會不同。而除錯在寫程式中是非常重要的一部分。

編譯錯誤

常見的編譯錯誤有以下(不同的編譯器有不同的寫法，但都大同小異，以下以code blocks為例)：

  • 沒加分號：error: expected ';' before ''
    ⇒ 加上分號
  • 忘記include：error: '某個函式名稱' was not declared in this scope
    ⇒ 加上#include
  • 忘記宣告：error: '某個變數名稱' was not declared in this scope
    ⇒ 在前面加上變數宣告

其他的錯誤如果看不懂可以直接複製貼上到google查，stack overflow幾乎甚麼都有。

執行錯誤

這類的錯誤最麻煩，如果程式跑出來跟預期的不一樣可以看看是不是有執行錯誤的發生。

  • 讀取超出陣列大小的index
  • 除以0
  • 無限while,for loop，遞迴無終止條件
  • 溢位

要找出這種錯誤可以透過印出變數值來看是否發生了以上的狀況。(vscode左邊就有附帶除錯功能)

b072: 加法






















#include <iostream>
#include <string>

using namespace std;

int main()
{
    string a,b;
    getline(cin, a);
    getline(cin, b);
    long long num1=0,num2=0;
    for(int i=8;i<=a.size()-2;i++){
        num1*=10;
        num1+=a[i]-'0';
    }
    for(int i=8;i<=b.size()-2;i++){
        num2*=10;
        num2+=b[i]-'0';
    }
    cout << "sum = " << num1+num2;
}

b073: 節約簡訊

































#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    string after="";
    char last=s[0];
    int cnt=1;
    for(int i=1;i<n;i++){
        if(s[i]==last){
            cnt++;
        }else{
            after+=to_string(cnt);
            after+=last;
            last=s[i];
            cnt=1;
        }
    }
    after+=to_string(cnt);
    after+=last;
    if(s.size()<=after.size()){
        cout << s;
    }else{
        cout << after;
    }
}

b027: 找出學霸
























#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int hiid,hi=0,loid,lo=100;
    for(int i=1;i<=n;i++){
        int score;
        cin >> score;
        if(score>hi){
            hiid=i;
            hi=score;
        }
        if(score<lo){
            loid=i;
            lo=score;
        }
    }
    cout << hiid << " " << hi << " " << loid << " " << lo;
}

題目練習

b068: 蛇蛇矩陣
b030: 健康檢查（Ⅰ）
b069: 字串串串串串接
b053: 正確的數字

b020: 慎思湖的倒影

分析時間:

要點:將輸出內容分成兩部分來看–上半部、下半部

  • 上半部:
    第一層重複cout一次 *
    第二層重複兩次…重複l層，每層重複l次
    ->雙重迴圈
  • 下半部
    第一層重複cout l次 *
    第二層重複l-1次…
    ->和上半部方法一樣，但將第二層迴圈的變數改為有l遞減到1




















#include <iostream>
using namespace std;

int main()
{
    int l;
    cin >> l;
    for(int i=1;i<=l;i++){
        for(int j=1;j<=i;j++){
            cout << "*";
        }
        cout << "\n";
    }
    for(int i=1;i<=l;i++){
        for(int j=l-i;j>=0;j--){
            cout << "*";
        }
        cout << "\n";
    }
}

b067: 位數和

妥善利用/和%這兩個運算子解題


















#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n>=10){
        int sum=0;
        while(n>0){
            sum+=n%10;
            n/=10;
        }
        n=sum;
    }
    cout << n;
}

a002: 電話客服中心























#include <bits/stdc++.h>//懶人包
using namespace std;
string ss;
int main() {
    while(cin>>ss){
        int sum=0;
        int letter[26]{10,11,12,13,14,15,16,17,34,18,19,20,21,
                       22,35,23,24,25,26,27,28,29,32,30,31,33};
        //規則一:紀錄每個英文字母對應的前兩位數字
        for(int a=0;a<8;a++)//規則二(還沒加英文字)
            sum =sum+(ss[a]-'0')*(8-a);
        int c=(ss[8]-'0');//c=檢查碼
        for(int a=0;a<26;a++){//找那些英文字符合
            int letter_=((letter[a]%10)*9)+(letter[a]/10);//規則二
            int m=(sum+letter_)%10;//規則三、四
            if(((10-m)%10)==c)
                cout<<char(65+a);//可寫成'Ａ'+a
        }
        cout<<endl;
    }
    return 0;
}

b074: 史萊姆















#include<iostream>
using namespace std;
int main(){
  int N,T;
  while(cin>>N>>T){
    int NCount=N,TCount=0,day=0;
    while(TCount!=T){
      TCount*=2;
      TCount+=N;
      day++;
    }
    cout<<day<<'\n';
  }
}

題目練習

b071: 電梯 (Elevator)
b070: 回文數
b075: 一元一次方程式

https://hackmd.io/@tcirc39th/HJifM35wY

Select a repo