作者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/cn.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