RUC_JudgeOnline 1001 开关灯问题_C/C++_编程开发_程序员俱乐部

开关灯问题

Description

n盏灯排成一排，从1到n按顺序依次编号。有n个人也从1到n依次编号。第一个人（1号）将灯全部关闭。第二个人（2号）将凡是2和2的倍数的灯打开。第三个人（3号）将凡是3和3的倍数的灯作相反处理（该灯如为打开的将其关闭；如为关闭的，将其打开）。以后的人都和三号一样，将凡是与自己相同的灯和是自己编号倍数的灯作相反处理。请问，当第n个人操作之后，哪几盏灯是点亮的。

Input

共1行。
第1行只有一个整数，即灯的数目n(1≤n≤10000)。

Output

共1行，按从小到大的顺序输出第n个人操作之后还点亮的灯的编号，每两个编号之间用空格隔开。

Sample Input

6

Sample Output

2 3 5 6

Source

习题5-1

?

问题分析：

???????这个题目思路简单，有两种思维方式。一种是基于人的，另外一种是基于灯的。

?????? a.从人入手，将序号每个能整除人的序号的灯的状态改变，如果是关的就打开，否则就关闭；

?????? b.从灯入手，计算每个灯的序号的因子数。如果是奇数，则最后状态为关闭，如果是偶数个因子，则最后的状态为打开。

解决方案：

??????设定一个数组light[10001]来表示灯的状态，可以用1表示打开状态，用0表示关闭状态。

???? ?对于a思路，可以用一个双重循环。外层循环控制人的序号从1~n，内层循环控制灯的序号，也是从1~n。每次都判断一下是否整除，如果整除则改变light的状态，即1变0，0变1。当然，我们还有更好的方法，即直接用人的序号当做步长?，去改变灯的序号的状态。这样可以减少循环的次数。在经过n的循环之后。最后用一个1~n的循环扫描一下light数组，将状态为1的灯的序号打印出来。

?????对于b思路。直接看这个数是不是平方数。只要是平方数，则因子个数为奇数；不是平方数的话，则最终状态肯定是打开的，即为我们的输出。在这种方法的情况下，是不需要对输出进行一个单独的扫描的，边判断边输出即可。

参考程序a：

?

//*****************************
//Author：GWL
//Date：2010-12-09
//version：1.0
//*****************************
#include<stdio.h>

int main()
{
    //----------input&&init---------------
    int i,n;
    scanf("%d",&n);
    int Light[10001]={0};                  //0:open 1:close because it's easy to init to 0
                                           //but we had better to init to 1 , it's more meaningful
    //--------------End-------------------

    //------------operate-----------------
    for(i=1;i<=n;i++)
    {
        int step = i;                      //use step to reduce the loop time
        int now = i;
        while(now<=n)
        {
            if(Light[now]==1){
                Light[now]=0;
            } 
            else{
                Light[now]=1;
            }
        now = now + step;
      }
    //--------------End-------------------

    //--------------output----------------
    for(i=1;i<=n;i++)
    {
        if(Light[i]==0)
        printf("%d ",i);  
    }
    //--------------End-------------------
    return 0;
}

??

Memory:20K??Time:150MS
Language:GCC??Result:Accepted

?

参考程序b：

//*****************************
//Author：GWL
//Date：2010-12-09
//version：1.0
//*****************************
#include<stdio.h>
#include<math.h>

int main()
{
    //----------input&&init---------------
    int i,n;
    scanf("%d",&n);
    int Light[10001]={0};                  //0:open 1:close because it's easy to init to 0
                                           //but we had better to init to 1 , it's more meaningful
    //--------------End-------------------

    //---------operate&&output------------
    for(i=1;i<=n;i++)
    {
        int tmp=(int)sqrt(i);
        if(tmp*tmp!=i)                        //not k^2
        printf("%d ",i);
    }
    //--------------End-------------------

    return 0;
}

?
Memory:20K??Time:150MS
Language:GCC??Result:Accepted

常见问题：

??? 1.数组大小申明为10000，导致越界。