第一题：程序（1）——数字减半小精灵

一、先读懂程序：它在做什么？

这个程序的代码如下：

#include<iostream>using namespace std;intmain(){    int n;    cin >> n;    int x = 1, y = 1;    while (n > 0) {        if (n % 2 == 0) {            ++x;        } else {            ++x;            ++y;        }        n = n / 2;    }    cout << x << ' ' << y << endl;    return 0;}

对应试卷第16～21题。

1. 给程序编一个故事

想象有一个数字小精灵，它拿着一个正整数。

每次行动时，它都会：

• 看看手里的数字是奇数还是偶数。

• 不管奇数还是偶数，都会让 x 增加1。

• 如果是奇数，还会让 y 增加1。

• 最后，把手里的数字除以2，舍去小数部分。

如此反复，直到数字变成0。

最后，程序报告 x 和 y 的值。

2. 认识三个重要角色

这里要特别注意：

n = n / 2;

因为 n 是 int 类型，所以整数除法会舍去小数部分。

例如：

7 / 2 = 36 / 2 = 33 / 2 = 11 / 2 = 0

因此，数字会逐渐变小，最终到达0。

二、第16题：输入3，输出是不是3 3？

原题：

当输入为3时，程序输出为3 3 。（判断题）

我们来模拟。

初始状态：

n = 3x = 1y = 1

第1轮循环

此时 n = 3。

判断：

n % 2 == 0

3除以2余1，所以条件不成立，进入 else。

执行：

++x;++y;

得到：

x = 2y = 2

接着：

n = n / 2;

得到：

n = 1

第2轮循环

现在 n = 1。

1是奇数，所以再次执行：

++x;++y;

得到：

x = 3y = 3

然后：

n = 1 / 2 = 0

循环结束

因为：

while (n > 0)

此时 n = 0，条件不成立，循环结束。

输出：

3 3

答案：√，正确。

侦探笔记

不要把 n = n / 2 忘记了！

如果漏掉这一行，程序中的 n 一直不变，循环就可能永远执行下去。

三、第17题：删除第11行的 ++x，两个数一定相等吗？

原题：

将第11行的 ++x; 删除后，程序输出的两个数一定相等。（判断题）

我们先看修改后的程序逻辑。

原来的代码：

if (n % 2 == 0) {    ++x;} else {    ++x;    ++y;}

删除 else 中的 ++x 后，相当于：

if (n % 2 == 0) {    ++x;} else {    ++y;}

也就是说：

• 遇到偶数，只有 x 增加。

• 遇到奇数，只有 y 增加。

而且 x 和 y 一开始都是1。

用输入3试一试

初始：

x = 1y = 1n = 3

第一轮，3是奇数：

x = 1y = 2

n 变成1。

第二轮，1还是奇数：

x = 1y = 3

n 变成0，循环结束。

最终：

x = 1y = 3

显然不相等。

答案：×，错误。

侦探笔记

题目中出现“一定”两个字时，要特别小心。

如果要证明“一定相等”，必须保证所有符合条件的输入都相等。

只要找到一个反例，就能推翻这个结论。

四、第18题：第一个数一定不小于第二个数吗？

原题：

假设输入为非负整数，则程序输出的第一个数一定不小于第二个数。（判断题）

程序没有修改，仍然是：

if (n % 2 == 0) {    ++x;} else {    ++x;    ++y;}

我们发现：

• 每轮循环，x 都增加1。

• 遇到奇数，y 也增加1。

• 遇到偶数，y 不增加。

因此，x 增加的次数一定不少于 y 增加的次数。

又因为它们的初始值相同：

x = 1y = 1

所以最终：

x >= y

即第一个数一定不小于第二个数。

答案：√，正确。

侦探笔记

这道题不必枚举所有输入。

只要比较两个变量每轮的变化规律，就可以直接得出结论。

这种方法叫作分析变量变化规律。

五、第19题：把 while (n > 0) 改成 while (n >= 0) 会怎样？

原题：

将第7行的：

while (n > 0)

改为：

while (n >= 0)

程序可能出现的问题是：

A. 陷入死循环 B. 输出结果比原来大 C. 输出结果比原来小 D. 输出结果不受影响

1. 原来的循环有什么特点？

原来是：

while (n > 0)

当 n 变成0时，条件不成立，循环结束。

2. 修改后呢？

现在变成：

while (n >= 0)

当 n = 0 时：

0 >= 0

条件仍然成立！

进入循环后：

n = n / 2;

于是：

0 / 2 = 0

下一轮还是0，再下一轮还是0……

n = 0n = 0n = 0n = 0……

循环永远无法结束。

答案

A. 陷入死循环。

侦探笔记

循环题一定要问自己三个问题：

1. 循环什么时候开始？

2. 每轮循环变量如何变化？

3. 变量变化后，能不能让循环条件最终变成假？

尤其要警惕：

while (n >= 0)

如果 n 是非负整数，并且循环中不断进行 n = n / 2，那么它最终会停在0，而不是变成负数。

六、第20题：输入6，输出什么？

原题：

当输入为6时，输出为：

A. 3 3 B. 4 2 C. 4 3 D. 5 2

这次我们用一张表格追踪程序。

初始：

n = 6x = 1y = 1

逐轮模拟

当 n = 0 时，循环结束。

最终：

x = 4y = 3

答案

C. 4 3。

七、第21题：有多少个输入会让第二个数恰好为2？

原题：

若输入 n 依次取遍：

0, 1, 2, ..., 2^31 - 1

程序输出的第二个数恰好为2的次数为：

A. 16 B. 30 C. 31 D. 32

这道题稍微有一点数学味道，但我们把它拆开就很简单了。

1. 先看 y 是怎么变化的

程序开始时：

int x = 1, y = 1;

所以：

y = 1

只有当 n 是奇数时，才会执行：

++y;

因此，想让最终的 y = 2，就必须满足：

整个循环过程中，恰好遇到一次奇数。

2. 用二进制观察

一个整数除以2时，整数部分相当于二进制数右移一位。

而：

n % 2

恰好可以判断二进制数最右边的一位是0还是1。

例如：

十进制 n = 6二进制   = 110

依次除以2：

6 → 3 → 1 → 0

对应二进制：

110 → 11 → 1 → 0

每遇到一个奇数，就相当于发现一个二进制中的1。

所以，y 最终等于：

1 + n 的二进制表示中1的个数

3. 什么时候 y = 2？

必须满足：

二进制中恰好有一个1

这样的数就是：

110100100010000……

也就是十进制的：

1、2、4、8、16、32、……

这些数都是2的整数次幂。

4. 统计有多少个

题目给出的范围是：

0 ≤ n ≤ 2^31 - 1

符合条件的数为：

2^0, 2^1, 2^2, ..., 2^30

从指数0到指数30，一共有：

30 - 0 + 1 = 31

个。

注意，2^31 已经超过题目给出的最大值，不能计算进去。

答案

C. 31。

第一题总结

第一题通关！