結對程式設計-四則運算（挑戰出題）

過去兩周，大家都對四則運算有了一定概念，完成了出題、判題。

接下來我們在現有的工作基礎上繼續做一些挑戰：隻出題，不判題

描述

小明（又是小明:D）目前在一家企業從事軟體開發。過年回到老家，順便看望自己的國小恩師林老師，時光飛逝，當年走路帶風的林老師已經是頭發花白，就快要退休了，目前還在教數學課。小明同林老師聊天交流這些年的見聞，林老師的日常則沒有大風大浪，孜孜不倦地教導學生一年又一年，但是有個煩惱：幾乎每一年都會遇上幾個計算能力特别好的學生，他們喜歡計算題目，而且記憶力好，還能經常發現自己做過某些題目。是以林老師在出題上可謂是傷透了腦筋，重複的工作費時費力，讓小明幫想想有沒有什麼更好的方法。小明眼睛一亮，一拍大腿，嘿~這不正是我擅長的麼！

小明說道：“我幫您寫個軟體，在電腦上運作就可以随機生成題目，省去您的煩惱。”

林老師皺皺眉頭：“前幾年上面組織過教育訓練如何使用電腦，這主意聽起來好像也不錯，不過……我這裡沒電腦可以用啊！”

小明擡頭想了幾秒：“對，手機！我給您做個手機app也可以。”

林老師從口袋裡掏出手機：“你看我這諾基亞3310可以嗎？”

小明撓頭：“這不好辦呀……有了，我回家寫個程式，直接在自己電腦上幫您生成1萬道題目，保證不重複，應該可以用到我下次回家，那時候再幫您重新生成。”

林老師：“這主意不錯。那小明同學，拜托了，你可算幫了我大忙！”

小明說幹就幹，開始分析需求，跟林老師溝通後，得出以下幾點：

• 每次生成的題目不能有重複
  • 題目去重-引用自：http://www.cnblogs.com/jiel/p/4810756.html

    程式一次運作生成的題目不能重複，即任何兩道題目不能通過有限次交換+和×左右的算術表達式變換為同一道題目。

    例如:

    • 23 + 45

      和

      45 + 23

      是重複的題目

    • 6 * 8

      8 * 6

      也是重複的題目

    • 3 + (2 + 1)

      1 + 2 + 3

      這兩個題目是重複的
      • 由于

        +

        是左結合的，

        1 + 2 + 3

        等價于

        (1 + 2) + 3

        ，也就是

        3 + (1 + 2)

        3 + (2 + 1)

    • 但是

      1 + 2 + 3

      3 + 2 + 1

      是不重複的兩道題
      • 因為

        1 + 2 + 3

        (1 + 2) + 3

        ，而

        3 + 2 + 1

        (3 + 2) + 1

        ，它們之間不能通過有限次交換變成同一個題目

• 要能指定生成題目的數量
• 要能指定題目包含的運算符數量

輸入

通過指令行參數形式指定題目要求

輸出

輸出題目到檔案，一行一個題目

輸入示例

$ java ExpressionGenerator 10000 5 expressions.txt
           

• ExpressionGenerator

  為最終執行的類（包含main函數）
• 第一個參數

  10000

  代表需要生成的題目數量
• 第二個參數

  5

  代表每個題目需包含的運算符數量（除括号以外的運算符數量）
• 第三個參數

  expressions.txt

  代表存放生成題目的檔案名

輸出示例

檢視 expressions.txt，部分内容如下：

...
7 - 8 * 9 / 1 + 2 - 3
4 * 5 / 6 + 7 - 8 * 9
1 / 2 + 3 - 4 * 5 / 6
7 / 8 + 9 - 1 * 2 / 3
...
           

特别說明

• 可執行的入口類必須為

  ExpressionGenerator

  ，友善後續驗證
• 參數順序必須遵守以上 輸入示例 說明，友善後續驗證
• 輸出格式必須遵守以上 輸出示例 說明，友善後續驗證
• 為了減小随機空間，展現出去重功能：
  • 操作數為個位整數，即選擇範圍隻能是：

    1

    ,

    2

    3

    4

    5

    6

    7

    8

    9

    這9個數字
  • 操作符選擇範圍隻能是：

    +

    -

    *

    /

    , 還有括号

要求

• 此次作業請在http://git.oschina.net/上建立一個倉庫送出代碼，并且在部落格中給出倉庫連接配接（代碼托管）
• 請将所有需要的參與編譯的

  .java

  檔案都放在該倉庫的根目錄，如:

ProjectDir
├── ExpressionGenerator.java
├── ...
└── Other.java
           

• 結對程式設計的兩位同學須各自發表部落格
• 部落格需描述各環節的輸出，如：
  • 需求分析（描述自己對需求的了解，以及後續擴充的可能性）
  • 設計思路（同時輸出UML類圖）
  • 實作過程中的關鍵代碼解釋
  • 測試方法
  • 運作過程截圖
  • 代碼托管位址
  • 遇到的困難及解決方法
• 對結對的小夥伴做出評價（重點指出需要改進的地方）
• 部落格内容中如需展示兩人的共同成果，請進行說明
• 如有參考或引用的設計、實作，請進行說明
• PSP
  • 實作之前先在PSP中預估時間
  • 實施後各個環節實際花費多少時間也請做記錄
  • 表中有一項： Estimate 指的“預估”這個活動，“預估時間”也是一項任務。
    • 例如：我估計自己需要花30分鐘來估算出整個項目需要多少時間完成，結果我花了20分鐘估算出整個項目需要6個小時完成。Estimate這一項應該在“預估耗時”填寫30分鐘，實際耗時填寫“20”分鐘。
  • 一級和二級活動的包含關系：
    • Planning 這個一級活動包含了1個二級活動（Estimate）
    • Development 這個一級活動包含了8個二級活動
    • Reporting 這個一級活動包含了3個二級活動
  • 大家在記錄時間的時候， 隻用記錄二級活動， 然後把總數加了， 就是相應的一級活動的時間
  • 這個時間的長短并不會對分數有直接影響，這是為了大家自己總結。

PSP2.1	Personal Software Process Stages	預估耗時（分鐘）	實際耗時（分鐘）
Planning	計劃
· Estimate	· 估計這個任務需要多少時間
Development	開發
· Analysis	· 需求分析 (包括學習新技術)
· Design Spec	· 生成設計文檔
· Design Review	· 設計複審 (和同僚稽核設計文檔)
· Coding Standard	· 代碼規範 (為目前的開發制定合适的規範)
· Design	· 具體設計
· Coding	· 具體編碼
· Code Review	· 代碼複審
· Test	· 測試（自我測試，修改代碼，送出修改）
Reporting	報告
· Test Report	· 測試報告
· Size Measurement	· 計算工作量
· Postmortem & Process Improvement Plan	· 事後總結, 并提出過程改進計劃
合計

打分細則

最終送出的代碼将會被拉取執行，通過傳入不同參數進行測試，測試包括：

• 記錄程式運作耗時
• 驗證最終結果的正确性（即是否有重複的題目）
• 程式得分數将根據耗時，重複率計算得出（共65分）
  • 程式不符合以上定義的輸入輸出，即不能使用工具進行正常測試，0分
  • 生成題目重複率，根據題目重複率映射至10~45分
  • 生成題目耗時，根據平均耗時映射至5~20分
  • 測試以下情況（詳見下文 測試工具）：
    • 僅能完成至生成10題的，以上得分打1折
    • 僅能完成至生成30題的，以上得分打2折
    • 僅能完成至生成100題的，以上得分打4折
    • 僅能完成至生成1000題的，以上得分打6折
    • 僅能完成至生成10000題的，以上得分打8折
    • 完成至20000題的，以上得分不打折
• 部落格（共35分）
  • 基礎分（按時送出）5分
  • PSP表格 5分
  • 需求分析 5分
  • 設計思路 5分
  • 實作過程中的關鍵代碼解釋 5分
  • 遇到的困難及解決方法 5分
  • 對結對小夥伴做出評價 5分
• 為自己的隊友打分 （在部落格中說明）
  • 這裡有獨立的100分供配置設定
    • 例如：一人如果得70分，另一人隻能得30分
  • 要求不能均分（即不能每人50分）
  • 打分要給出依據，依據可以有：
    • 代碼送出記錄
    • 設計文檔
    • 測試

約定

• 部落格中說明代碼結構，并指明如何編譯（提供編譯指令）
• 如果部落格不說明，評分老師根據自己經驗猜測執行（編譯不通過的後果由自己承擔）
• 以作業截止日期的線上代碼版本為準
• 編譯不通過 0分
• 不嚴格遵守題目輸入輸出 0分
• 運作過程有崩潰，能得分的項目得分減半
• 如遇特殊環境問題，可在成績公布至次日淩晨截止時間内提出複查
• 複查一般僅接受處理環境差異帶來的問題
• 複查原則上不對新送出的功能代碼進行評分
• 結對程式設計、團隊項目中Git代碼送出不能是一個人（要看到所有人的貢獻），貢獻可以是代碼、設計、文檔和測試

參考示例

以下是一份簡單的題目生成示例（生成題目沒進行去重，不夠随機，也無括号，需要同學們自行動手設計實作滿足以上要求的程式）：

import java.util.Random;
import java.io.IOException;
import java.io.FileWriter;

public class ExpressionGenerator {
    public static void main(String[] args) throws IOException {
        if (args.length != 3) {
            System.err.println("java ExpressionGenerator <number-of-expressions> <number-of-operator> <output-file-path>");
            System.exit(1);
        }

        int expr_num = Integer.parseInt(args[0]);
        int optr_num = Integer.parseInt(args[1]);
        String file_path = args[2];

        String digits = "123456789";
        String operators = "+-*/";

        Random rnd = new Random();
        StringBuffer expr = new StringBuffer();
        FileWriter fw = new FileWriter(file_path);

        int r1 = rnd.nextInt(100);
        for (int i = 0; i < expr_num; ++i) {
            expr.append(digits.charAt(++r1 % 9));
            int r2 = rnd.nextInt(100);
            for (int j = 0; j < optr_num; ++j) {
                expr.append(' ');
                expr.append(operators.charAt(++r2 % 4));
                expr.append(' ');
                expr.append(digits.charAt(++r1 % 9));
            }
            expr.append('\n');
            fw.write(expr.toString());
            expr.delete(0, expr.length());
        }
        fw.close();
    }
}
           

執行：

> java ExpressionGenerator 10 5 1.txt
           

在檔案

1.txt

中輸出：

4 - 5 * 6 / 7 + 8 - 9
1 * 2 / 3 + 4 - 5 * 6
7 + 8 - 9 * 1 / 2 + 3
4 * 5 / 6 + 7 - 8 * 9
1 - 2 * 3 / 4 + 5 - 6
7 - 8 * 9 / 1 + 2 - 3
4 * 5 / 6 + 7 - 8 * 9
1 / 2 + 3 - 4 * 5 / 6
7 / 8 + 9 - 1 * 2 / 3
4 - 5 * 6 / 7 + 8 - 9
           

測試工具

exprchecker.zip

功能：

• 測試：
  • 生成10道1個運算符題目
  • 生成30道1個運算符題目
  • 生成100道1個運算符題目
  • 生成1000道3個運算符題目
  • 生成10000道5個運算符題目
  • 生成20000道7個運算符題目
• 發現重複的題目（按上述題目要求）
• 計算程式生成題目耗時

注意：

• 輸出題目中出現不在1~9範圍内的數值，工具會abort退出（目前設計）
• 該工具并不完善，使用過程中可能出現報錯，崩潰，行為不正确的情況，請不要嘗試使用各類輸入來測試該工具。如果發現問題，請及時與我聯系

使用條件：

• Windows環境（在Windows10使用VS2017編譯Win32，未進行版本相容性測試）
• 須安裝JDK并配置相關環境變量
• 你編寫的Java程式須嚴格遵守以上約定

使用方法：

• 下載下傳後，請将

  exprchecker.exe

  與将要執行的類

  ExpressionGenerator.class

  放置在統一目錄，如：

ProjectDir
├── ExpressionGenerator.class
├── exprchecker.exe
├── ...
└── Other.class
           

• 輕按兩下

  exprchecker.exe

  将自動執行你的類

  ExpressionGenerator.class

  ，按照以上約定的參數，執行6組測試，輸出資訊如下：

Executing command: "java ExpressionGenerator 10 1 10.txt" ... DONE with status: 0
Checking your result in 10.txt ... DONE
Generating report into report_10.txt ... DONE

Executing command: "java ExpressionGenerator 30 1 30.txt" ... DONE with status: 0
Checking your result in 30.txt ... DONE
Generating report into report_30.txt ... DONE

Executing command: "java ExpressionGenerator 100 1 100.txt" ... DONE with status: 0
Checking your result in 100.txt ... DONE
Generating report into report_100.txt ... DONE

Executing command: "java ExpressionGenerator 1000 3 1000.txt" ... DONE with status: 0
Checking your result in 1000.txt ... DONE
Generating report into report_1000.txt ... DONE

Executing command: "java ExpressionGenerator 10000 5 10000.txt" ... DONE with status: 0
Checking your result in 10000.txt ... DONE
Generating report into report_10000.txt ... DONE

Executing command: "java ExpressionGenerator 20000 7 20000.txt" ... DONE with status: 0
Checking your result in 20000.txt ... DONE
Generating report into report_20000.txt ... DONE

Press [Enter] to exit ...
           

檢視

report_10.txt

:

===============================
total expressions: 10
duplicated expressions: 0
===============================
Generation cost 125 ms.
           

• 生成10道題目
• 沒有發現重複的題目
• 生成題目耗時125毫秒

report_30.txt

[2 + 3] @ line 12 is repeated with:
   -> [2 + 3] @ line 21

[7 / 8] @ line 10 is repeated with:
   -> [7 / 8] @ line 19

[9 * 1] @ line 2 is repeated with:
   -> [9 * 1] @ line 29

[4 * 5] @ line 4 is repeated with:
   -> [4 * 5] @ line 13

[1 + 2] @ line 7 is repeated with:
   -> [1 + 2] @ line 25

[5 + 6] @ line 9 is repeated with:
   -> [5 + 6] @ line 18

===============================
total expressions: 30
duplicated expressions: 6
===============================
Generation cost 133 ms.
           

• 生成30道題目
• 發現6道題目重複（未成功去重哦！）
• 生成題目耗時133毫秒
• 重複題目的詳細資訊在檔案前面部分說明