数组：一秒钟，定义 1000 个变量

任务

程序中读入一个整数 n，假设 n 不会大于 1000，请输出 1 到 n 的每一个数字二进制表示中的 1 的个数。

当 n 等于 7 的时候，我们把 1 到 7 的每个数字的二进制表示罗列出来，会得到下表所示内容：

根据表中的内容，如果你的程序编写成功的话，程序应该分别输出 1、1、2、1、2、2、3，这些输出内容分别代表每个数字二进制表示中 1 的数量。

编码

思路

如果我们用一个数组 f 记录相应数字二进制表示中 1 的数量，那么 f[i] 就代表 i 这个数字二进制表示中 1 的数量，从而我们可以推导得到 f[i] = f[i & (i - 1)] + 1，也就是说 i 比 i & (i - 1) 这个数字的二进制表示中的 1 的数量要多一个，这样我们通过一步计算就得到 f[i] 的结果。

实现

#include <stdio.h>
int f[1001];
int main() {
    int n;
    scanf("%d", &n);  //读入一个整数n，代表要求解的范围
    f[0] = 0;
    for (int i = 1; i <= n; i++) {  //循环n次
        f[i] = f[i & (i - 1)] + 1;  //每一次通过递推公式f[i] = f[i & (i - 1)] + 1 计算得到 f[i] 的值
    }
    //最后输出 1 到 n 中每个数字二进制表示中 1 的个数。
    for (int i = 1; i <= n; i++) {
        if (i != 1) printf(" ");
        printf("%d", f[i]);
    }
    printf("\n");
    return 0;
}

/*
100
1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 2 3 3 4 3
*/

思考题

1，去掉倍数

设计一个去掉倍数的程序，要求如下：
首先读入两个数字 n 和 m，n 的大小不会超过 10，m 的大小都不会超过 10000；
接下来读入 n 个各不相同的正整数，输出 1 到 m 中，有哪些数字无法被这 n 个正整数中任意的一个整除。

例子

输入
3 12
4 5 6

输出
1 2 3 7 9 11

实现

#include <stdio.h>
int check[1005] = {0};  //使用一个 check 数组作为标记，check[i] 等于 0，代表 i 这个数字不是 n 个数字中的任何一个数字的倍数。check[i] 等于 1，代表 i 这个数字能够被 n 个数字中的某个数字整除
int main() {
    int n, m, num;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);  //首先读入 n 个数字中的某一个，存储在 num 变量中
        for (int j = num; j <= m; j += num) {
            check[j] = 1;  //循环 m 以内所有 num 的倍数，把每个数字的 check 值标记为 1
        }
    }
    for (int i = 1; i <= m; i++) {
        if (check[i] == 1) continue;
        printf("%d ", i);  //最后我们循环把 1 到 m 中没有被标记的数字输出，就是符合题目要求的所有数字。
    }
    return 0;
}

小结

使用数组，可以很方便的定义出一组变量存储空间，数组下标从 0 开始。
数据的最基本存储单位是字节，每一个字节都有一个独一无二的地址。
一个变量占用若干个字节，第一个字节的地址，是这个变量的首地址，称为：变量地址。
字节是存储数据的最基本单位，比特是表示信息的最基本单位。