出場人物介紹

小美：小學4年級學生堪侯，參加了學校的編程興趣小組舷夺，已經了解了Python語言的基本語法，能夠看懂一些簡單的程序攻旦。她做事風風火火喻旷，對所有的事情都很好奇，喜歡打破砂鍋問到底牢屋，是一個叫人又愛又恨的小丫頭。

阿福：一個酷愛編程的8年級男生槽袄。大家都說他長得像國寶大熊貓烙无，動作緩慢，憨態(tài)可掬遍尺。他做事情確實夠慢的截酷，連說話也慢條斯理，可是他一點也不擔心乾戏，他常常說：“慢就是快迂苛，只要堅持下去，蝸牛也能爬上金字塔鼓择∪茫”

古老師：雖然年近不惑，但依然對生活充滿熱情呐能∧畎幔“愛生活愛運動”是他的人生信條，和孩子們一起編程是他最大的樂趣摆出。他神出鬼沒朗徊，總是在孩子們最需要幫助的時候出現(xiàn)。當然偎漫，你也不能動不動就找古老師爷恳，因為他很忙，非常非常忙象踊。所以温亲，遇到問題還是自己先思考吧。

算法進化歷程之燈泡開關

阿福：最近古老師讓我到力扣（leetcode）網去刷題通危，我遇到了一個很有趣的題目铸豁。

小美：是嗎？趕快拿出來瞧瞧菊碟。

題目1：

燈泡開關节芥。

n個燈排成一排，依次編號為1-n，開始時都是關著的⊥纺鳎現(xiàn)進行如下操作： 第 1 輪蚣驼，所有電燈的按鈕按動一次；第2 輪相艇，所有編號為2的倍數(shù)的電燈按鈕按動一次颖杏；第3輪，所有編號為3的倍數(shù)的電燈的按鈕按動一次坛芽；……第n 輪留储，所有編號為n的倍數(shù)的電燈的按鈕按動一次。最后請統(tǒng)計?n?輪后有多少只電燈是亮的咙轩。

函數(shù)功能：統(tǒng)計?n?輪后有多少只電燈是亮的获讳。

函數(shù)名：bulbSwitch(n:int)-> int

參數(shù)表：n-- 燈的數(shù)量。

返回值：?n?輪后亮著的燈的數(shù)量活喊。

示例1：n=3丐膝，則返回1。

解釋：初始時钾菊，燈泡狀態(tài) [關閉, 關閉, 關閉]帅矗；第一輪后, 燈泡狀態(tài) [開啟, 開啟, 開啟]；

第二輪后煞烫，燈泡狀態(tài) [開啟, 關閉, 開啟]浑此；第三輪后, 燈泡狀態(tài) [開啟, 關閉, 關閉]。

故第3輪后红竭，只有編號為1的燈泡是亮的尤勋。

示例2：n=10，則返回3茵宪。

解釋：第10輪后最冰，編號為1,4,9的燈泡是亮的。

小美：我感覺這道題不難啊稀火，用模擬算法就能解決暖哨。我們可以分別用0和1表示燈泡的暗亮狀態(tài)，然后模擬整個開關燈過程凰狞，最后統(tǒng)計值為1的元素個數(shù)篇裁。

代碼1：

def bulbSwitch(n: int) -> int:

??? a = [0] * (n + 1) #初始時所有燈泡均關閉

??? for i in range(1, n + 1):

??????? for j in range(i, n + 1, i): #只處理i的倍數(shù)

??????????? a[j] = 1 - a[j] #實現(xiàn)0和1的相互轉換

??? return sum(a)#對列表a求和，即統(tǒng)計值為1的元素個數(shù)

阿福：這個思路簡單直接赡若。我一開始也是這樣想的达布，可是提交代碼以后，系統(tǒng)判定超時逾冬。

小美：超時黍聂？那說明我們的算法效率太低了躺苦。可是我已經盡可能對代碼進行優(yōu)化了啊产还。

阿福：沒錯匹厘，如果使用模擬算法的話，你的代碼已經寫得很好了脐区∮希可是模擬算法本身就不是高效的算法。這道題目要用到一些數(shù)學知識牛隅。

小美：數(shù)學知識炕柔？

阿福：沒錯，就是數(shù)學知識倔叼。請你仔細觀察一下汗唱，n輪操作下來，編號為i的開關切換的次數(shù)與i有什么關系丈攒？例如當n=10時，編號為6的開關總共切換了幾次授霸？分別是在第幾輪被切換過巡验？

小美：當n=10時，編號為6的開關在第1輪碘耳、第2輪显设、第3輪和第6輪被切換過，總共切換了4次辛辨。

?阿福：編號為9的開關呢捕捂？

小美：當n=10時，編號為9的開關在第1輪斗搞、第3輪和第9輪被切換過指攒，總共切換了3次。

阿福：看出規(guī)律來了嗎僻焚？

小美：規(guī)律允悦？哦，我看出來了虑啤。編號為i的開關切換的次數(shù)恰好為i的因數(shù)個數(shù)隙弛。

阿福：沒錯，正是這樣狞山！我們可以根據(jù)編號i的因數(shù)個數(shù)來判斷燈的暗亮狀態(tài)全闷，若i的因數(shù)個數(shù)為奇數(shù)，則最后該燈亮萍启。

小美：道理是沒錯总珠，但怎么判斷i的因數(shù)個數(shù)是奇數(shù)還是偶數(shù)呢？

阿福：你再觀察一下6和9的因數(shù)分布情況。

小美：我發(fā)現(xiàn)了姚淆，因數(shù)都是對稱分布的孕蝉。例如，6=1*6=2*3腌逢，9=1*9=3*3降淮。i的因數(shù)以平方根為軸對稱分布，成對出現(xiàn)搏讶。如果i是完全平方數(shù)佳鳖，它的因數(shù)有奇數(shù)個（因為平方根只能和自己配對），否則就是偶數(shù)個媒惕。

?阿福：沒錯系吩，n輪操作下來，只有編號為完全平方數(shù)的燈泡亮妒蔚，我們就只需統(tǒng)計有多少個完全平方數(shù)就行了穿挨。代碼如下：

代碼2：

def bulbSwitch2(n: int) -> int:

??? s = 0

??? for i in range(1, n + 1):

??????? sqr = int(i ** 0.5)

??????? if i == sqr * sqr: #統(tǒng)計完全平方數(shù)的個數(shù)

??????????? s += 1

??? return s

小美：阿福真棒！

阿福：唉肴盏，當時我也覺得自己挺棒的科盛。可代碼提交以后菜皂，系統(tǒng)仍判定超時贞绵。

小美：這都不行啊恍飘？難道還有什么更高效的方法嗎榨崩？會不會是因為開根號的操作太耗時了？

阿福：我也猜測是這個原因章母∧钢耄可不開根號還能怎么辦呢？

古老師：阿福胳施，你采用的是枚舉算法溯祸，那你還記得枚舉算法要考慮的因素是哪幾個嗎？

小美：這個我知道舞肆！枚舉算法要考慮的因素有枚舉變量焦辅，枚舉范圍和枚舉條件。

古老師：不錯椿胯，那在這個題目中筷登，它們分別是什么呢？

阿福：枚舉變量是i哩盲，枚舉范圍是[1, n]前方，枚舉條件是判斷i是否為完全平方數(shù)狈醉，通過計算i的平方根sqr來判斷枚舉條件是否成立。

古老師：是啊惠险，這個算法中最耗時的地方就是計算sqr的值苗傅。那你們有沒有想過逆向思維，枚舉sqr班巩，利用sqr來求i呢渣慕？

小美：逆向思維？枚舉sqr抱慌？哦逊桦，我想到了！可以從1開始遞增sqr的值抑进，判斷sqr *

sqr是否小于等于 n强经，最后sqr的值就是完全平方數(shù)的個數(shù)。

阿福：不對寺渗， sqr的值減一才是正解匿情，因為最后一個sqr已經不滿足條件了。

小美：沒錯信殊，是要減一码秉。還是阿福考慮周到鸡号。

代碼3：

def bulbSwitch3(n:int) -> int:

??? sqr = 1

?? ?while sqr * sqr <= n:

??????? sqr += 1

??? return sqr - 1 #最后一個sqr已經不滿足條件了

阿福：哇，通過了须鼎！還戰(zhàn)勝了62.72%的用戶呢鲸伴。

古老師：不錯不錯！看來你對完全平方數(shù)已經有一定的了解了晋控。

小美：一定的了解汞窗？難道我們研究的還不夠透徹嗎？

古老師：應該說研究得比較透徹了赡译。但請你再仔細觀察一下仲吏，[1, n]范圍內的完全平方數(shù)個數(shù)與n到底有什么關系呢？

小美：這還有關系蝌焚？

阿福：我把n和[1, n]范圍內的完全平方數(shù)個數(shù)s組成一個元組(n, s)裹唆，列舉了[1, 20]范圍內的(n, s)值如下，(1, 1),(2, 1),(3, 1),(4, 2),(5, 2),(6, 2),(7, 2),(8, 2),(9, 3),(10, 3),(11, 3),(12, 3),(13, 3),(14, 3),(15,3),(16, 4),(17, 4),(18, 4),(19, 4),(20, 4)只洒。小美许帐，你發(fā)現(xiàn)有什么規(guī)律沒有？

小美：規(guī)律毕谴？我看到了成畦，只有當n等于完全平方數(shù)的時候距芬，s的值才會增加。

阿福：沒錯循帐！而且s的值恰好等于n的平方根框仔。

小美：那就好辦了！代碼簡單得很拄养！

代碼4：

def bulbSwitch4(n:int) -> int:

return int(n ** 0.5) #[1, n]范圍內的完全平方數(shù)個數(shù)恰好為其平方根

古老師：果然是高手啊离斩，觀察力一流！看你們這么厲害衷旅，我就再給你們出一道題目吧捐腿。題目不難，就是把上一題稍微改動一下柿顶。

題目2：

哪些電燈是亮的茄袖。

n個燈排成一排，依次編號為1-n嘁锯，開始時都是關著的∠芟椋現(xiàn)進行如下操作： 第 1 輪，所有電燈的按鈕按動一次家乘；第2 輪蝗羊，所有編號為2的倍數(shù)的電燈按鈕按動一次；第3輪仁锯，所有編號為3的倍數(shù)的電燈的按鈕按動一次耀找；……第n 輪，所有編號為n的倍數(shù)的電燈的按鈕按動一次业崖。最后請輸出?n?輪后有哪些電燈是亮的野芒。

函數(shù)功能：輸出?n?輪后有哪些電燈是亮的。

函數(shù)名：bulbSwitch(n:int)-> list

參數(shù)表：n-- 燈的數(shù)量双炕。

返回值：一個存儲了所有亮燈編號的列表狞悲。

示例1：n=10，則返回[1, 4, 9]妇斤。

示例2：n=30拿穴，則返回[1, 4, 9, 16, 25]奋献。

小美：好像沒什么區(qū)別嘛历恐。

阿福：區(qū)別還是有的角寸，需要輸出具體哪些電燈是亮的。這樣一來就不能直接套用數(shù)學公式了顷编。

古老師：雖然不能直接套用數(shù)學公式戚炫，但是前面總結的數(shù)學規(guī)律還是有用的。也別想得太復雜媳纬，其實只要把前面的代碼1双肤、2施掏、3修改一下就行了。好了茅糜，我只能說這么多了七芭，剩下的自己去琢磨吧。拜拜咯蔑赘。

彩蛋：

小美：只要把代碼1狸驳、2、3修改一下就行了缩赛？

阿福：沒錯耙箍，前面我們做的是統(tǒng)計工作，現(xiàn)在只要把每個亮燈的編號都存儲起來就行了酥馍。這樣吧辩昆，你修改代碼1，我來修改代碼2和代碼3旨袒。

小美：好的汁针，沒問題。

代碼4：

分別用0和1表示燈泡的暗亮狀態(tài)砚尽，然后模擬整個開關燈過程施无，最后輸出值為1的元素

def bulbSwitch4(n:int) -> list:

??? a = [0] * (n + 1) #初始時所有燈泡均關閉

??? for i in range(1, n + 1):

??????? for j in range(i, n + 1, i):

??????????? a[j] = 1 - a[j]

return [i for i in range(n + 1) if a[i] == 1]

代碼5：

編號為完全平方數(shù)的燈泡亮，枚舉i必孤，計算sqr

def bulbSwitch5(n:int) -> list:

??? res = []

??? for i in range(1, n + 1):

??????? sqr = int(i ** 0.5)

??????? if i == sqr * sqr:

??????????? res.append(i)

return res

代碼6：

編號為完全平方數(shù)的燈泡亮猾骡，枚舉sqr，存儲sqr*sqr

def bulbSwitch6(n:int) -> list:

??? res = []

??? sqr = 1

??? while sqr * sqr <= n:

??????? res.append(sqr * sqr)

??????? sqr += 1

??? return res