算法竞赛001之开灯问题

问题简介: 有n盏灯编号为1-n,第一个人把所有灯打开,

 第二个人按下是所有编号为2的倍数的开关.

  (这些开关被关掉),

  第三个人按下所有编号为3的倍数的开关(其中关掉的灯将被打开,开着的灯将被关闭)

  依此类推,一共有k个人问最后有哪些开关开着 ?

 输入:n和k,输出开着的灯的编号.k<=n<=1000

 样例输入:7 3

 样例输出: 1 5 6 7

 

package practice;

/**
 * @author jins
 * @date on 2019/1/11.
 */
import java.util.Scanner;

public class OpenLamp {
    public static void main(String[] args)
    {
        // n表示共有n盏灯,k表示人数
        int n,k,i,j;
        //定义数组大小,并给所有的灯的默认值是0
        //因为n和k都是从1开始,所以定的空间大了10个
        //开着灯为1,关着灯为0
        int [] number = new int[1010];
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=k;j++)
            {
                //判断灯编号为人数的倍数
                if (i%j==0)
                {
                    //如果灯是关着的,那么打开
                    if (number[i]==0)
                    {
                        number[i] = 1;
                    }else {
                        //如果灯是开着的,那么关闭
                        number[i] = 0;
                    }
                }
            }
        }
        for ( i = 1; i <= n ;i++ )
        {
            //判断如果灯开着,那么输出所在的灯的编号
            if (number[i]==1)
            {
                System.out.print(" "+i);
            }
        }
    }
}

 

    算法题后续会持续更新,由浅入深,慢慢理解!

 

如果大家喜欢我的文章,可以关注我的微信公众号,后面会陆续更新!