[理工] 資結 求執行次數

[bmpss92196 (bmpss92196)]

想請問此題
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
推 godskull1535: nlogn
→ godskull1535: x=n-ki   n-ki=0  k=n/i
→ godskull1535: 裡面while就n/i 外面for搭配Σ(n/i) 再把n提出來 然
→ godskull1535: 後Σ (1/i)=logn 所以就nlogn了
我想知道的是x減到最後為什麼是0？
n不同，未必會有0吧
※ 編輯: bmpss92196 (36.226.230.98), 07/27/2018 21:11:19
推 godskull1535: 你假設n=5，i=1 x=n 執行5次 變到i=2 x又會等於5,又
→ godskull1535: 會執行5次
→ godskull1535: 但現在是n
→ godskull1535: 要知道x=n 在看while（x>0) 代表x=0 while才跳出來
→ godskull1535: 所以裡面的x=x-i 會減到x-ki（減了k次）等於0為止才
→ godskull1535: 跳出  先知道裡面的迴圈跑幾次後在往外面展開 比較
→ godskull1535: 好算
推 godskull1535: 有打錯 假設n=5 i=2時 會減到-1為止才跳出 我覺得不
→ godskull1535: 用想太多 題目要求是x=0跳出 現在假設是n 就會n-ki=
→ godskull1535: 0