作者bmpss92196 (bmpss92196)
看板Grad-ProbAsk
標題[理工] 資結 求執行次數
時間Fri Jul 27 18:16:26 2018
想請問此題
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1532686588.A.96F.html
※ 編輯: bmpss92196 (36.226.230.98), 07/27/2018 18:16:57
1F：推 godskull1535: nlogn 07/27 20:43
2F：→ godskull1535: x=n-ki n-ki=0 k=n/i 07/27 20:43
3F：→ godskull1535: 裡面while就n/i 外面for搭配Σ(n/i) 再把n提出來 然 07/27 20:43
4F：→ godskull1535: 後Σ (1/i)=logn 所以就nlogn了 07/27 20:43
我想知道的是x減到最後為什麼是0？
n不同，未必會有0吧
※ 編輯: bmpss92196 (36.226.230.98), 07/27/2018 21:11:19
5F：推 godskull1535: 你假設n=5，i=1 x=n 執行5次 變到i=2 x又會等於5,又 07/27 21:33
6F：→ godskull1535: 會執行5次 07/27 21:33
7F：→ godskull1535: 但現在是n 07/27 21:33
8F：→ godskull1535: 要知道x=n 在看while（x>0) 代表x=0 while才跳出來 07/27 21:33
9F：→ godskull1535: 所以裡面的x=x-i 會減到x-ki（減了k次）等於0為止才 07/27 21:33
10F：→ godskull1535: 跳出 先知道裡面的迴圈跑幾次後在往外面展開 比較 07/27 21:33
11F：→ godskull1535: 好算 07/27 21:33
12F：推 godskull1535: 有打錯 假設n=5 i=2時 會減到-1為止才跳出 我覺得不 07/27 21:40
13F：→ godskull1535: 用想太多 題目要求是x=0跳出 現在假設是n 就會n-ki= 07/27 21:40
14F：→ godskull1535: 0 07/27 21:40