[理工] 資結 求執行次數

看板Grad-ProbAsk作者 (bmpss92196)時間5年前 (2018/07/27 18:16), 5年前編輯推噓3(3推 0噓 11→)
留言14則, 1人參與, 5年前最新討論串1/1
想請問此題 for i=1 to n do { x=n; while(x>=0) do { x=x-i; a++; } } 問a++執行次數 Ans x=n x=n-i x=n-2i ... x=n-ki=0會執行 => k=n/i 想請問為什麼最後可以直接寫x=n-ki=0？ 若n=5則第二輪(i=2)時不會有x=0的情況 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.226.230.98 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1532686588.A.96F.html ※ 編輯: bmpss92196 (36.226.230.98), 07/27/2018 18:16:57
推
07/27 20:43, 5年前 , 1F
nlogn
07/27 20:43, 1F
→
07/27 20:43, 5年前 , 2F
x=n-ki n-ki=0 k=n/i
07/27 20:43, 2F
→
07/27 20:43, 5年前 , 3F
裡面while就n/i 外面for搭配Σ(n/i) 再把n提出來 然
07/27 20:43, 3F
→
07/27 20:43, 5年前 , 4F
後Σ (1/i)=logn 所以就nlogn了
07/27 20:43, 4F
我想知道的是x減到最後為什麼是0？ n不同，未必會有0吧 ※ 編輯: bmpss92196 (36.226.230.98), 07/27/2018 21:11:19
推
07/27 21:33, 5年前 , 5F
你假設n=5，i=1 x=n 執行5次 變到i=2 x又會等於5,又
07/27 21:33, 5F
→
07/27 21:33, 5年前 , 6F
會執行5次
07/27 21:33, 6F
→
07/27 21:33, 5年前 , 7F
但現在是n
07/27 21:33, 7F
→
07/27 21:33, 5年前 , 8F
要知道x=n 在看while（x>0) 代表x=0 while才跳出來
07/27 21:33, 8F
→
07/27 21:33, 5年前 , 9F
所以裡面的x=x-i 會減到x-ki（減了k次）等於0為止才
07/27 21:33, 9F
→
07/27 21:33, 5年前 , 10F
跳出 先知道裡面的迴圈跑幾次後在往外面展開 比較
07/27 21:33, 10F
→
07/27 21:33, 5年前 , 11F
好算
07/27 21:33, 11F
推
07/27 21:40, 5年前 , 12F
有打錯 假設n=5 i=2時 會減到-1為止才跳出 我覺得不
07/27 21:40, 12F
→
07/27 21:40, 5年前 , 13F
用想太多 題目要求是x=0跳出 現在假設是n 就會n-ki=
07/27 21:40, 13F
→
07/27 21:40, 5年前 , 14F
0
07/27 21:40, 14F
‣ 更多 bmpss92196 的文章
文章代碼(AID): #1RMl3ybl (Grad-ProbAsk)