學生關燈問題

今天看到别人分享的一道華為機試題目，感覺還比較有趣，問題是這樣子的

描述：一條長廊裡依次裝有n(1 ≤ n ≤ 65535)盞電燈，從頭到尾編号1、2、3、…n-1、n。每盞電燈由一個拉線開關控制。開始，電燈全部關着。 

/有n個學生從長廊穿過。第一個學生把号碼凡是1的倍數的電燈的開關拉一下；接着第二個學生把号碼凡是2的倍數的電燈的開關拉一下；接着第三個學生把号碼凡是3的倍數的電燈的開關拉一下；

如此繼續下去，最後第n個學生把号碼凡是n的倍數的電燈的開關拉一下。n個學生按此規定走完後，長廊裡電燈有幾盞亮着。注：電燈數和學生數一緻。 

乍一看，這個問題不知道如何入手，其實分析一下，他就是個因式分解的問題的變形。如假設有4盞燈，編号為1 2 3 4，那麼會有四個同學依次通過。1号同學過去時會點亮所有的等，2号同學過去會關掉2 4 等，3号同學過去會關掉3号等，4号同學會重新點亮4号等。如果用-1表示燈泡為滅，1表示燈泡亮，則每個同學過次走廊就相當于反轉一次開關，最後仍為1的就表示亮着的燈。

于是問題具化為每個同學過去要動哪些開關。題目中交代的很清楚了就是他的倍數。是以代碼就很簡單了。如下所示

# include<iostream>
# include<string>

using namespace std;

int main()
{
	int bubble[65535]={};
	int n;
	int stilllight=0; //統計最終亮着的燈

	

	cout<<"please input the number of student,should be between 0 and 65535"<<endl;
    cin>>n;
	if(n<1||n>65535)
	{
		cout<<"wrong number"<<endl;
		exit(1);
	}
	for(int i=1;i<=n;i++)
		bubble[i]=-1; //-1表示燈滅，反轉1表示燈亮

	for(int i=1;i<=n;i++)
		for(int j=1;j<n/i+1;j++)
			bubble[i*j]=-bubble[i*j]; //反轉其動過的燈
	for(int i=1;i<=n;i++)
	{
		if(bubble[i]==1)
			stilllight++;
	}

		
	cout<<stilllight<<endl;

	return 0;


}