趣味算法------开灯问题

题目描述

有 n 盏灯，编号为 1~n，第 1 个人把所有灯打开，第 2 个人按下所有编号为 2 的倍数的开关（这些灯将被关掉），第 3 个人按下所有编号为 3 的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），依此类推。一共有 k 个人，问最后有哪些灯开着？输入：n 和 k，输出开着的灯编号。k ≤ n ≤ 1000。

输入格式
输入一组数据：n 和 k，中间空格隔开。

输出格式
输出开灯的编号。

输入样例1
输入
4 3
输出
1
输入样例2
输入
7 3
输出
1
5
6
7
输入样例3
输入
10 6
输出
1
4
7
8
10
输入样例4
输入
15 1
输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入样例5
输入
21 5
输出
1
4
6
7
8
10
11
13
15
16
17
18
19

思路解析：

        在开始之前我要介绍一个运算符符号“^”，这个运算符号在C语言中表达的含义是异或，两个数字都为1或者0，异或值为0，一个为1另一个为0，异或值则为1。

        为了方便大家理解，可以将开灯关灯的过程也包含在代码中（虽然运行会比较慢），我们可以定义一个一维数组表示一排灯，下标则为对应灯的编号。数组值1，0表示灯的状态分别是开灯和关灯，编写一个函数，模拟开灯关灯。

具体代码：

#include<stdio.h>

int arr[100] = {0};

int n;

void fun(int k)

{

    for(int i = k;i<=n;i+=k)

        arr[i] = 1^arr[i];//1变0，0变1

}//模拟第k个人开灯关灯操作。

int main(void)

{

    int k;

    scanf("%d%d",&n,&k);

    for(int i = 1;i<=k;i++)

        fun(i);//让k个人轮流执行开灯关灯操作。

    for(int i = 1;i<=n;i++)

        if(arr[i])//如果还有灯为开的状态，打印该编号。

            printf("%d\n",i);

}

留言：

        基础题也讲过不少了，之后我打算开启图论的内容，会比较难，不过当然还是从最简单的开始，修行在当下，诸君切莫急。