编程中的时间估算、递归方法与Hi-Lo游戏开发

### 编程中的时间估算、递归方法与 Hi - Lo 游戏开发 #### 1. 程序运行时间估算 在编程中，我们常常需要估算程序的运行时间。不过，我们得到的运行时间值只是一个粗略的估计。这是因为运行时间会受到多种因素的影响，比如运行程序的 CPU 不同，以及同时是否有其他进程在运行。例如，当一个方法运行时，如果垃圾回收程序启动，那么运行时间的估算可能会有很大偏差。另外，使用像 Java 这样的高级语言进行计时时，粒度非常粗，比如无法区分运行时间为 5 毫秒和 6 毫秒的程序。 要估算循环语句的运行时间，可以按照以下步骤进行： 1. 在循环语句之前创建一个 `Date` 对象，例如 `startTime`，记录开始时间。 2. 在循环语句之后创建另一个 `Date` 对象，例如 `endTime`，记录结束时间。 3. 计算经过的时间（以毫秒为单位），公式为：`elapsedTime = endTime.getTime() - startTime.getTime();` #### 2. 递归方法 除了常见的三种重复控制语句（`while`、`do - while` 和 `for`），还有一种控制程序重复流程的方法，即使用递归方法。递归方法是指包含调用自身语句的方法。 ##### 2.1 递归方法的示例 以计算 N 的阶乘为例，数学上 N 的阶乘定义为 `N! = N * (N - 1) * (N - 2) * ... * 2 * 1`。我们可以用递归方法来计算阶乘，代码如下： ```java //Assume N is greater than 0 public int factorial(int N) { if (N == 1) return 1; else return N * factorial(N - 1); } ``` 递归方法包含三个必要组件： 1. 一个用于停止或继续递归的测试。 2. 一个终止递归的结束情况。 3. 一个或多个继续递归的递归调用。 为了确保递归最终会停止，我们传递的参数必须与传入的参数不同。在阶乘方法中，传入的参数是 `N`，而递归调用中传递的参数是 `N - 1`，这种差异最终会使递归调用中的参数变为 1，从而停止递归。 ##### 2.2 更多递归方法示例 - **计算前 N 个正整数的和**： ```java public int sum ( int N ) { //assume N >= 1 if (N == 1) return 1; else return N + sum( N - 1 ); } ``` - **计算指数 `A^N`**： ```java public double exponent ( double A, int N ) { if (N == 1) return A; else return A * exponent( A, N - 1 ); } ``` - **计算字符串的长度**： ```java public int length(String str) { if (str.equals("")) { //str has no characters return 0; } else { return 1 + length(str.substring(1)); } } ``` ##### 2.3 使用递归的条件 在实际编程中，使用递归需要满足以下条件： 1. 递归解决方案自然且易于理解。 2. 递归解决方案不会导致过多的重复计算。 3. 等效的迭代解决方案过于复杂。 ##### 2.4 欧几里得最大公约数的递归实现 ```java public int gcd_recursive(int m, int n) { int result; if (m == 0) { //test result = n; //end case } else { result = gcd_recursive(n % m, m); //recursive case } return result; } ``` #### 3. Hi - Lo 游戏开发 Hi - Lo 游戏的目标是让用户猜出计算机生成的 1 到 100 之间的秘密数字，用户最多可以猜 6 次。当用户猜测时，程序会根据猜测结果回复 HI（猜测数字大于秘密数字）或 LO（猜测数字小于秘密数字）。 ##### 3.1 总体计划 开发这个游戏的总体计划如下： 1. 每次游戏开始时生成一个秘密数字。 2. 进行游戏。 3. 当用户想继续玩时，重复上述两个任务。 可以用伪代码表示为： ```plaintext do { Task 1: generate a secret number; Task 2: play one game; } while ( the user wants to play ); ``` 涉及的类及其用途如下表所示： | 类 | 用途 | | ---- | ---- | | Ch6HiLo | 顶级控制对象，处理游戏逻辑并管理其他对象，是可实例化的主类 | | Scanner | 用于输入用户的猜测 | | PrintStream (System.out) | 用于显示提示和其他消息 | ##### 3.2 开发步骤 开发这个游戏可以分为以下四个主要步骤： 1. 从 `Ch6HiLo` 类的骨架开始。 2. 向 `Ch6HiLo` 类添加代码，使用一个虚拟的秘密数字来玩游戏。 3. 向 `Ch6HiLo` 类添加代码，生成随机数字。 4. 通过移除临时语句并处理遗留问题来完成代码。 以下是各步骤的详细内容： ##### 3.2.1 步骤 1：程序骨架 在这个步骤中，我们要实现程序的基本结构。使用 `while` 循环，让用户有不玩游戏的选择。伪代码如下： ```plaintext describe the game rules; prompt the user to play a game or not; while ( answer is yes ) { generate the secret number; play one game; prompt the user to play another game or not; } ``` `Ch6HiLo` 类的工作设计文档如下： | 方法 | 可见性 | 目的 | | ---- | ---- | ---- | | `<constructor>` | public | 创建并初始化 `HiLo` 对象使用的对象 | | `start` | public | 开始 Hi - Lo 游戏，用户可以选择是否玩游戏 | | `describeRules` | private | 在 `System.out` 中显示游戏规则 | | `generateSecretNumber` | private | 为下一轮 Hi - Lo 游戏生成一个秘密数字 | | `playGame` | private | 玩一轮 Hi - Lo 游戏 | | `prompt` | private | 提示用户输入是或否的回复 | 以下是 `Ch6HiLo` 类的骨架代码： ```java import java.util.*; /* Chapter 6 Sample Development: Hi-Lo Game (Step 1) The instantiable main class of the program. */ class Ch6HiLo { private static enum Response {YES, NO} private Scanner scanner; //Main Method public static void main (String[] args) { Ch6HiLo hiLo = new Ch6HiLo( ); hiLo.start(); } public Ch6HiLo( ) { scanner = new Scanner(System.in); } public void start( ) { Response answer; describeRules(); answer = prompt("Do you want to play a Hi-Lo game?"); while (answer == Response.YES) { generateSecretNumber( ); playGame(); answer = prompt("Do you want to play another Hi-Lo game?"); } System.out.println("Thank you for playing Hi-Lo."); } private void describeRules( ) { System.out.println("Inside describeRules"); //TEMP } private void generateSecretNumber( ) { System.out.println("Inside generateSecretNumber"); //TEMP } private void playGame( ) { System.out.println("Inside playGame"); //TEMP } private Response prompt(String question) { String input; Response response = Response.NO; System.out.print(question + " (Yes - y; No - n): "); input = scanner.next(); if (input.equals("Y") || input.equals("y")) { response = Response.YES; } return response; } } ``` 为了验证步骤 1 的正确执行，我们需要进行以下测试： 1. 选择不玩游戏，确保程序不进行游戏就停止。 2. 选择玩一次游戏，验证 `generateSecretNumber` 和 `playGame` 方法被正确调用。 3. 选择玩多次游戏，确保程序可以正常处理。 ##### 3.2.2 步骤 2：使用虚拟秘密数字玩游戏 在这一步，我们要添加玩 Hi - Lo 游戏的逻辑。`playGame` 方法的控制流程如下： 1. 设置猜测次数计数器 `guessCount` 为 0。 2. 进入循环，获取下一个猜测，增加猜测次数。 3. 根据猜测与秘密数字的大小关系，输出提示信息（HI 或 LO）。 4. 当猜测次数达到最大允许次数或猜对时，结束循环。 5. 根据猜测结果输出相应的消息（获胜或失败）。 伪代码如下： ```plaintext //Method: playGame set guessCount to 0; do { get next guess; increment guessCount; if (guess < secretNumber) { print the hint LO; } else if (guess > secretNumber) { print the hint HI; } } while (guessCount < number of guesses allowed && guess != secretNumber ); if (guess == secretNumber) { print the winning message; } else { print the losing message; } ``` 为了支持更好的用户界面，我们添加了输入错误处理，将其放在一个新的私有方法 `getNextGuess` 中。`getNextGuess` 方法的伪代码如下： ```plaintext //Method: getNextGuess while ( true ) { get input value; if (valid input) return input value; print error message; } ``` `Ch6HiLo` 类的工作设计文档更新如下： | 方法 | 可见性 | 目的 | | ---- | ---- | ---- | | ... | ... | ... | | `getNextGuess` | private | 返回用户的下一个猜测，只接受 1 到 100 之间的猜测，输入无效猜测时打印适当的错误消息 | 以下是相关代码： ```java private final int MAX_GUESS_ALLOWED = 6; private final int LOWER_BOUND = 1; private final int UPPER_BOUND = 100; private int secretNumber; private void generateSecretNumber( ) { secretNumber = 45; //TEMP } private void playGame( ) { int guessCount = 0; int guess; do { //get the next guess guess = getNextGuess(); guessCount++; //check the guess if (guess < secretNumber) { System.out.println("Your guess is LO"); } else if (guess > secretNumber) { System.out.println("Your guess is HI"); } } while ( guessCount < MAX_GUESS_ALLOWED && guess != secretNumber ); //output appropriate message if ( guess == secretNumber ) { System.out.println("You guessed it in " + guessCount + " tries."); } else { System.out.println("You lost. Secret No. was " + secretNumber); } } private int getNextGuess( ) { int input; while (true) { System.out.print("Next Guess: "); input = scanner.nextInt(); if (LOWER_BOUND <= input && input <= UPPER_BOUND) { return input; } //invalid input; print error message System.out.println("Invalid Input: " + "Must be between " + LOWER_BOUND + " and " + UPPER_BOUND); } } ``` 在这一步，我们需要测试两个方法： - **`getNextGuess` 方法**：输入无效和有效猜测，验证方法的正确性。测试用例包括输入小于 1 的数、大于 100 的数、2 到 99 之间的数、1 和 100。 - **`playGame` 方法**：已知虚拟秘密数字为 45，进行以下测试： - 输入小于 45 的数，检查是否显示正确的提示 LO。 - 输入大于 45 的数，检查是否显示正确的提示 HI。 - 输入正确的猜测，检查游戏是否在显示适当的消息后终止。 - 输入六个错误的猜测，检查游戏是否在显示适当的消息后终止。 ##### 3.2.3 步骤 3：生成随机数字 在这一步，我们要添加生成 1 到 100 之间随机数字的逻辑。可以使用 `Math` 类的 `random` 方法，公式为 `secretNumber = (int) Math.floor( X * 100 ) + 1`，其中 `0.0 ≤ X < 1.0`。 `generateSecretNumber` 方法的代码如下： ```java private void generateSecretNumber( ) { double X = Math.random(); secretNumber = (int) Math.floor( X * 100 ) + 1; System.out.println("Secret Number: " + secretNumber); // TEMP } ``` 为了验证该方法是否生成正确的随机数字，我们编写了一个单独的测试程序： ```java class TestRandom { public static void main (String[] args) { int N = 1000, count = 0, number; double X; do { count++; X = Math.random(); number = (int) Math.floor( X * 100 ) + 1; } while ( count < N && 1 <= number && number <= 100 ); if ( number < 1 || number > 100 ) { System.out.println("Error: " + number); } else { System.out.println("Okay"); } } } ``` 需要注意的是，成功生成 1000 个有效随机数字并不能保证第 1001 个数字也有效，但我们假设用户在一次会话中不会玩超过 1000 次 Hi - Lo 游戏。执行 `TestRandom` 类后，对 `Ch6HiLo` 类进行必要的更改并运行，验证程序是否按预期运行。 ##### 3.2.4 步骤 4：完成程序 在最后一步，我们要对程序进行全面审查，查找未完成的方法、不一致性或错误，检查不清楚或缺失的注释等。同时，完成 `describeRules` 方法，添加描述游戏规则的代码。对于用于验证目的的临时输出语句，可以选择删除或注释掉，这里我们选择注释掉，以便后续修改、调试或更新程序时不需要重新输入。 通过以上步骤，我们完成了 Hi - Lo 游戏的开发，同时学习了程序运行时间估算和递归方法的相关知识。这些知识在编程中非常重要，可以帮助我们更好地优化程序性能和设计更复杂的算法。 ### 编程中的时间估算、递归方法与 Hi - Lo 游戏开发（续） #### 4. 总结与关键概念回顾 在编程中，重复控制语句是非常重要的工具，它们可以帮助我们多次执行相同的代码块，直到满足特定条件为止。下面对一些关键概念进行总结回顾： - **重复控制语句**：主要有 `while`、`do - while` 和 `for` 三种。 - `while` 语句是一种预测试循环，在每次循环开始前检查条件是否满足。 - `do - while` 语句是一种后测试循环，先执行一次循环体，然后再检查条件。 - `for` 语句也是预测试循环，通常用于执行固定次数的循环。 - **循环类型**： - **计数控制循环**：使用固定次数执行循环体，通常使用 `for` 语句实现最为自然。 - **哨兵控制循环**：执行循环体直到遇到指定的哨兵值，通常使用 `while` 或 `do - while` 语句实现。 - **常见错误**： - **差一错误**：在循环控制中，由于边界条件设置不当导致的错误。 - **无限循环**：循环条件始终为真，导致循环无法终止。 - **其他要点**： - **循环与半循环控制**：是编写循环的最通用方式，使用 `break` 语句在满足特定条件时退出循环。 - **嵌套 `for` 语句**：常用于处理表格数据。 - **输出格式化**：可以使用 `Formatter` 类对输出值进行格式化。 - **执行时间估算**：可以使用 `Date` 类估算程序的执行时间。 下面是这些概念的关系流程图： ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A(重复控制语句):::process --> B(while):::process A --> C(do - while):::process A --> D(for):::process E(循环类型):::process --> F(计数控制循环):::process E --> G(哨兵控制循环):::process H(常见错误):::process --> I(差一错误):::process H --> J(无限循环):::process K(其他要点):::process --> L(循环与半循环控制):::process K --> M(嵌套for语句):::process K --> N(输出格式化):::process K --> O(执行时间估算):::process ``` #### 5. 练习题解析 以下是对一些练习题的详细解析，通过这些练习可以加深对上述概念的理解和应用。 ##### 5.1 识别重复语句中的错误 ```plaintext a. for (int i = 10; i > 0; i++) { x = y; a = b; } ``` 此代码存在逻辑错误，`i` 初始值为 10，条件是 `i > 0`，每次循环 `i` 增加 1，这会导致 `i` 永远不会小于等于 0，从而形成无限循环。应将 `i++` 改为 `i--`。 ```plaintext b. int sum = 0; Scanner scanner = new Scanner(System.in); do { num = scanner.nextInt(); sum += num; } until (sum > 10000); ``` Java 中没有 `until` 关键字，应使用 `while` 关键字。正确的代码如下： ```java int sum = 0; Scanner scanner = new Scanner(System.in); int num; do { num = scanner.nextInt(); sum += num; } while (sum > 10000); ``` ```plaintext c. while (x < 1 && x > 10) { a = b; } ``` 条件 `x < 1 && x > 10` 永远不可能为真，因为一个数不可能既小于 1 又大于 10，这会导致循环体永远不会执行。 ```plaintext d. while (a == b) ; { a = b; x = y; } ``` `while` 语句后面的分号导致 `while` 循环体为空，而 `{ a = b; x = y; }` 这部分代码会在 `while` 循环结束后执行，与预期不符。应去掉分号。 ```plaintext e. for (int i = 1.0; i <= 2.0; i += 0.1) { x = y; a = b; } ``` `for` 循环的控制变量 `i` 被声明为 `double` 类型，但在 Java 中，`for` 循环通常使用整数类型的控制变量，因为浮点数的比较可能会由于精度问题导致意外结果。 ##### 5.2 编写循环语句计算和与积 以下是使用 `for`、`do - while` 和 `while` 语句计算不同和与积的代码示例： ```java // a. 1 + 2 + 3 + ... + 100 // for 语句 int sumAFor = 0; for (int i = 1; i <= 100; i++) { sumAFor += i; } // do - while 语句 in ```