课 17, 主题|小节 3

进行中

← 上一页

17.2 实验与应用

2025年9月22日

课进展

0% 完成

17.2.1 实验一：小球下落问题

题目描述：一个小球从n米的高度自由下落，着地后又弹回高度的一半再下落，经过多少次落地后，小球弹起的高度才会低于0.5米？

样例输入：

样例输出：

样例解释：

初始高度为10米
第1次落地后反弹高度为5米（大于0.5米）
第2次落地后反弹高度为2.5米（大于0.5米）
第3次落地后反弹高度为1.25米（大于0.5米）
第4次落地后反弹高度为0.625米（大于0.5米）
第5次落地后反弹高度为0.3125米（小于0.5米）所以答案是5次。

代码实现：

#include <iostream>
using namespace std;

int main() {
    double n;           // 定义初始高度变量
    cin >> n;           // 输入初始高度
    int cnt = 0;        // 定义计数器变量，记录落地次数
    
    // 当小球弹起高度不小于0.5米时循环继续
    while(n >= 0.5) {
        cnt++;          // 落地次数加1
        n /= 2;         // 小球弹回高度的一半
    }
    
    cout << cnt;        // 输出结果
    return 0;           // 程序正常结束
}

思考：

这个循环的三要素是什么？

初始化：n从输入的高度开始，cnt计数器从0开始
循环条件：n >= 0.5，即当小球弹起高度不小于0.5米时继续循环
更新语句：n /= 2（小球弹回高度的一半），cnt++（落地次数加1）

17.2.2 实验二：角谷猜想

题目描述：日本一位中学生发现一个奇妙的定理，请角谷教授证明，而教授无能为力，于是产生了角谷猜想。猜想的内容：任给一个自然数，若为偶数则除以2，若为奇数则乘3加1，得到一个新的自然数后按上面的法则继续演算。若干次后得到的结果必为1。请编写代码验证该猜想：求经过多少次运算可得到自然数1。

样例输入：

样例输出：

样例解释：从22开始进行角谷猜想的运算过程： 22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1 共经过15次运算得到1。

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的自然数
    cin >> n;           // 输入初始值
    int cnt = 0;        // 定义计数器，记录运算次数
    
    while(n != 1) {     // 当n不等于1时继续循环
        cnt++;          // 运算次数加1
        if(n % 2 == 0) {    // 如果n是偶数
            n /= 2;         // 除以2
        } else {            // 如果n是奇数
            n = n * 3 + 1;  // 乘3加1
        }
        // 可以添加下面的语句查看每一步的结果
        // cout << "第" << cnt << "步：" << n << endl;
    }
    
    cout << cnt;        // 输出运算次数
    return 0;           // 程序正常结束
}

思考：

这个循环的三要素是什么？

初始化：n从输入的自然数开始，cnt计数器从0开始
循环条件：n != 1，即当n不等于1时继续循环
更新语句：根据n的奇偶性更新n的值，cnt++（操作次数加1）

注意：角谷猜想目前仍未被证明，但对于目前已经测试过的数，猜想都成立。

17.2.3 实验三：数字位数计算

题目描述：输入一个正整数，输出这个数是一个几位数？

样例输入：

样例输出：

样例解释： 12345是一个5位数。

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    int cnt = 0;        // 定义计数器，记录位数
    
    while(n != 0) {     // 当n不等于0时继续循环
        cnt++;          // 位数加1
        n /= 10;        // 去掉最低位
    }
    
    cout << cnt;        // 输出位数
    return 0;           // 程序正常结束
}

思考：

这个循环的三要素是什么？

初始化：n从输入的正整数开始，cnt计数器从0开始
循环条件：n != 0，即当n不等于0时继续循环
更新语句：n /= 10（去掉最低位），cnt++（位数加1）

原理：每次将n除以10，相当于从右往左去掉一位数字，直到n变为0，统计需要除以10的次数即为原数的位数。

17.2.4 实验四：输出数字的每一位

题目描述：输入一个正整数，从右到左输出数字的每一位。

样例输入：

样例输出：

5 4 3 2 1

样例解释：从右到左，12345的各位分别是5、4、3、2、1。

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    
    while(n) {          // 当n不为0时继续循环
        printf("%d ", n % 10);  // 输出最低位数字
        n /= 10;                // 去掉最低位
    }
    
    return 0;           // 程序正常结束
}

思考：

循环的三要素：

初始化：n从输入的正整数开始
循环条件：n != 0，即当n不等于0时继续循环
更新语句：n /= 10（去掉已输出的最低位）

原理：n % 10得到最低位数字，n / 10去掉最低位。这样从右到左依次获取每一位数字。

17.2.5 实验五：数字倒序

题目描述：输入一个正整数，输出这个数的倒序。倒序是指将原数的各位数字从右到左重新组合。

样例输入：

样例输出：

样例解释： 12345的倒序是54321。

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    int m = 0;          // 用于存储倒序数
    
    while(n) {          // 当n不为0时继续循环
        int g = n % 10;         // 取出最低位数字
        m = m * 10 + g;         // 构建倒序数
        n /= 10;                // 去掉最低位
    }
    
    cout << m;          // 输出倒序数
    return 0;           // 程序正常结束
}

思考：

这个算法巧妙地将数字倒序。每次取原数最低位，然后将结果乘以10再加上这个最低位，就构建了倒序数。

算法解析：

m初始为0
假设n = 12345
第一次循环：m = 0 * 10 + 5 = 5，n = 1234
第二次循环：m = 5 * 10 + 4 = 54，n = 123
第三次循环：m = 54 * 10 + 3 = 543，n = 12
第四次循环：m = 543 * 10 + 2 = 5432，n = 1
第五次循环：m = 5432 * 10 + 1 = 54321，n = 0
循环结束，输出m = 54321

17.2.6 实验六：回文数判断

题目描述：判断一个数是不是回文数。回文数是指正序和倒序读都相同的整数，如121、1221等。

样例输入：

样例输出：

样例解释： 12321的倒序也是12321，所以它是回文数，输出”T”表示True。

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    int t = n;          // 保存原始值
    int m = 0;          // 用于存储倒序数
    
    while(t) {          // 当t不为0时继续循环
        m = m * 10 + t % 10;    // 构建倒序数
        t /= 10;                // 去掉最低位
    }
    
    cout << (m == n ? 'T' : 'F');  // 比较倒序数与原数，相等则为回文数
    return 0;                       // 程序正常结束
}

思考：

这个算法先将原数倒序，然后比较倒序数与原数是否相等。如果相等，则是回文数。

注意：回文数的性质使它正着读和倒着读都一样，如121、12321等。

17.2.7 实验七：质数判断

题目描述：判断一个数是不是质数。质数是只能被1和自身整除的大于1的自然数。

样例输入：

样例输出：

样例解释： 17只能被1和17整除，所以它是质数，输出”T”表示True。

方法一：计数法

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    int cnt = 0;        // 用于统计因数的个数
    
    // 遍历1到n，统计能整除n的数的个数
    for(int i = 1; i <= n; i++) {
        if(n % i == 0) {    // 如果i能整除n
            cnt++;          // 因数个数加1
        }
    }
    
    // 如果因数个数为2（只有1和自身），则是质数
    cout << (cnt == 2 ? 'T' : 'F');
    return 0;           // 程序正常结束
}

方法二：直接判断法

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    
    // 特殊情况：小于2的数不是质数
    if(n < 2) {
        cout << 'F';
        return 0;
    }
    
    int cnt = 0;        // 用于统计除了1和自身外的因数个数
    
    // 只检查2到n-1之间的数
    for(int i = 2; i < n; i++) {
        if(n % i == 0) cnt++;  // 如果找到其他因数，计数加1
    }
    
    // 如果没有其他因数，则是质数
    cout << (cnt == 0 ? 'T' : 'F');
    return 0;           // 程序正常结束
}

方法三：提前终止法

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    bool f = true;      // 假设n是质数
    
    if(n < 2) f = false;    // 小于2的数不是质数
    
    // 检查2到n-1之间的数
    for(int i = 2; i < n; i++) {
        if(n % i == 0) {    // 如果找到因数
            f = false;      // 则n不是质数
            break;          // 提前终止循环
        }
    }
    
    cout << (f ? 'T' : 'F');
    return 0;           // 程序正常结束
}

方法四：优化检查范围

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    bool f = true;      // 假设n是质数
    
    if(n < 2) f = false;    // 小于2的数不是质数
    
    // 只需检查到sqrt(n)
    for(int i = 2; i <= sqrt(n); i++) {
        if(n % i == 0) {    // 如果找到因数
            f = false;      // 则n不是质数
            break;          // 提前终止循环
        }
    }
    
    cout << (f ? 'T' : 'F');
    return 0;           // 程序正常结束
}

方法五：不使用sqrt函数

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    bool f = true;      // 假设n是质数
    
    if(n < 2) f = false;    // 小于2的数不是质数
    
    // 使用i*i<=n代替i<=sqrt(n)
    for(int i = 2; i <= n/i; i++) {
        if(n % i == 0) {    // 如果找到因数
            f = false;      // 则n不是质数
            break;          // 提前终止循环
        }
    }
    
    cout << (f ? 'T' : 'F');
    return 0;           // 程序正常结束
}

方法六：进一步优化

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    bool f = true;      // 假设n是质数
    
    if(n < 2) f = false;    // 小于2的数不是质数
    else if(n % 2 == 0 || n % 3 == 0) f = false;    // 先检查是否能被2或3整除
    else {
        // 从5开始，每次增加6，检查形如6k±1的数
        for(int i = 5; i <= n/i; i += 6) {
            if(n % i == 0 || n % (i+2) == 0) {  // 检查i和i+2
                f = false;      // 如果找到因数，则n不是质数
                break;          // 提前终止循环
            }
        }
    }
    
    cout << (f ? 'T' : 'F');
    return 0;           // 程序正常结束
}

思考：

质数判断有多种优化方法，从最简单的枚举所有因数（方法一），到只需判断是否有除1和自身外的因数（方法二），再到发现有因数就提前结束（方法三），以及只需检查到平方根（方法四和方法五），最后是利用更多数学性质减少判断次数（方法六）。

算法优化解析：

方法一：时间复杂度O(n)
方法二：时间复杂度O(n)，但常数因子较小
方法三：最坏情况时间复杂度O(n)，但对于非质数可能提前终止
方法四和方法五：时间复杂度O(√n)
方法六：时间复杂度O(√n)，但常数因子更小

17.2.8 实验八：不是3的倍数的数

题目描述：输出1~n之间所有不是3的倍数的数。使用continue语句实现跳过3的倍数。

样例输入：

样例输出：

1 2 4 5 7 8 10

样例解释： 1到10中不是3的倍数的数有：1, 2, 4, 5, 7, 8, 10

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义范围上限
    cin >> n;           // 输入范围上限
    int i = 0;          // 初始化循环变量
    
    while(i < n) {      // 循环条件：i小于n
        i++;            // 先将i加1
        if(i % 3 == 0) continue;  // 如果i是3的倍数，跳过后面的输出语句
        cout << i << " ";  // 输出不是3倍数的数
    }
    
    return 0;           // 程序正常结束
}

思考：

这个循环使用了continue语句跳过3的倍数，只输出不是3倍数的数。

注意：continue语句使循环立即进入下一次迭代，跳过循环体中剩余的部分。在这个例子中，如果i是3的倍数，就不会执行输出语句。

17.2.9 实验九：和7无关的数

题目描述：求1~n（<=999）中所有和7无关的数的总和。和7无关的数是指不含有数字7且不是7的倍数的数。使用continue语句跳过和7有关的数。

样例输入：

样例输出：

样例解释： 1到20中和7无关的数有：1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 18, 19, 20 它们的总和是157。

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义范围上限
    cin >> n;           // 输入范围上限
    int sum = 0;        // 初始化总和
    int i = 0;          // 初始化循环变量
    
    while(i < n) {      // 循环条件：i小于n
        i++;            // 先将i加1
        
        // 提取i的各个位的数字
        int g = i % 10;         // 个位
        int s = i / 10 % 10;    // 十位
        int b = i / 100 % 10;   // 百位
        
        // 如果i是7的倍数或包含数字7，则跳过
        if(i % 7 == 0 || g == 7 || s == 7 || b == 7) continue;
        
        sum += i;       // 将和7无关的数加到总和中
    }
    
    cout << sum;        // 输出总和
    return 0;           // 程序正常结束
}

思考：

这个循环筛选出不含7且不是7倍数的数，计算它们的总和。使用取余和整除操作提取各个位的数字进行检查。

注意：continue语句用于跳过那些和7有关的数，只累加和7无关的数。

17.2.10 实验十：平方数判断

题目描述：判断一个数是否为平方数。平方数是指一个整数的平方，如1, 4, 9, 16等。

样例输入：

样例输出：

yes

样例解释： 16 = 4²，所以16是平方数。

方法一：枚举法

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    int i = 1;          // 从1开始枚举
    
    while(i <= n) {     // 循环条件：i不超过n
        if(i * i == n) {    // 如果i的平方等于n
            cout << "yes";  // 输出结果
            return 0;       // 程序正常结束
        }
        i++;            // 更新循环变量
    }
    
    cout << "no";       // 如果循环结束仍未找到，则不是平方数
    return 0;           // 程序正常结束
}

方法二：优化枚举范围

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    bool f = false;     // 标记是否为平方数
    int i = 1;          // 从1开始枚举
    
    while(i <= n/i) {   // 循环条件：i不超过sqrt(n)
        if(i * i == n) {    // 如果i的平方等于n
            f = true;       // 标记为平方数
            break;          // 提前结束循环
        }
        i++;            // 更新循环变量
    }
    
    cout << (f ? "yes" : "no");
    return 0;           // 程序正常结束
}

方法三：使用数学函数

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    int a = sqrt(n);    // 计算n的平方根
    
    cout << (a * a == n ? "yes" : "no");  // 判断a的平方是否等于n
    return 0;           // 程序正常结束
}

思考：

平方数判断的方法从暴力枚举（方法一），到优化搜索范围（方法二），再到使用数学函数直接计算（方法三），体现了算法优化的思路。

算法优化解析：

方法一：时间复杂度O(n)，对于大的n效率较低
方法二：时间复杂度O(√n)，通过减少枚举范围提高效率
方法三：时间复杂度O(1)，直接使用数学函数计算，最高效

17.2.11 实验十一：立方数判断

题目描述：判断一个数是否为立方数。立方数是指一个整数的立方，如1, 8, 27, 64等。

样例输入：

样例输出：

yes

样例解释： 27 = 3³，所以27是立方数。

方法一：优化枚举范围

#include <iostream>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    int i = 1;          // 从1开始枚举
    
    while(i <= n/i/i) { // 循环条件：i不超过cbrt(n)
        if(i * i * i == n) {  // 如果i的立方等于n
            cout << "yes";    // 输出结果
            return 0;         // 程序正常结束
        }
        i++;            // 更新循环变量
    }
    
    cout << "no";       // 如果循环结束仍未找到，则不是立方数
    return 0;           // 程序正常结束
}

方法二：使用数学函数

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;              // 定义输入的正整数
    cin >> n;           // 输入正整数
    int a = cbrt(n);    // 计算n的立方根
    
    cout << (a * a * a == n ? "yes" : "no");  // 判断a的立方是否等于n
    return 0;           // 程序正常结束
}

思考：

立方数判断类似于平方数判断，优化思路类似。方法一通过枚举检查，方法二使用了数学函数cbrt直接计算立方根。

注意：对于方法二，由于浮点数精度问题，可能需要使用近似比较或转整型比较。

信奥AC之路-1级

与会者 278

17.2 实验与应用

2025年9月22日

17.2.1 实验一：小球下落问题

17.2.2 实验二：角谷猜想

17.2.3 实验三：数字位数计算

17.2.4 实验四：输出数字的每一位

17.2.5 实验五：数字倒序

17.2.6 实验六：回文数判断

17.2.7 实验七：质数判断

17.2.8 实验八：不是3的倍数的数

17.2.9 实验九：和7无关的数

17.2.10 实验十：平方数判断

17.2.11 实验十一：立方数判断