首先我先說一下什么是開燈問題:有從1到n一次編號的n個同學(有的題目中可能是猴子),1號同學將所有的燈都關掉;2號同學將編號為2的倍數的燈打開;3號同學則將編號為3的倍數的燈都做相反方向處理(該燈是打開的,關掉;是關掉的,打開.)讓所有的同學都處理一遍后,問那些燈還是打開的.
這個題目本身不難,主要是怎么樣才能使編碼簡單,大家都可能想到用array[i]=0來表示燈滅,array[i]=1表示燈亮.那怎么樣做相反方向的操作呢?(呵呵,想一下);一般的可能想到用if條件語句判斷,如果array[i]=0,則賦值為1,即:array[i]=1;如果array[i]=1;則array[i]=0.那是不是有更好的模擬燈的開關呢?我們說是有的,通過這條語句可以做到:array[1]=1-array[i];(思考一下!).
我的代碼如下,僅供參考,有更好的可以貼出來討論:



















































array[1] = !(array[i]);
嗯,好的想法!
其實這個還有更好的做法,可以把這個O(n*logn)降到O(n)的算法!這個關鍵是對實質的分析(提示:因子的個數).