[問題] 遞迴函數

[pentiumevo]

n是正整數,函數L定義為
0 if n = 1
L =
L([n/2])+1 if n > 1

Describe what this function does?(此處[x]表高斯函數)

解答首先計算L(25)

L(25)=L(12)+1
=(L(6)+1)+1 =L(6)+2
=(L(3)+1)+2 =L(3)+3
=(L(1)+1)+3 =L(1)+4
=0+4
=4

Each time n divided by 2,the value of L is increased by 1.Hence L is the

greatest integer such that

2^L 小於等於 n

Accordingly,L(n)=[(log n)/(log 2)]

計算的部分相當簡單,但是後來的推論我看不懂,完全不知如何推出

L(n)是"以2為底的log n再取高斯函數"

題目出自Schaum's Set Theory and Related Topics, pp.112 Problem 4.30

有書的人可以幫看嗎?謝謝.

--
亦正亦邪!喜怒無常!兇暴鬥狠!多情無義!

洪 興 大 飛 哥

搏感情! 拼氣魄! 絕對不輸人!


--

--
※ Origin: 交大次世代(bs2.to)
◆ From: 125-233-6-44.dynamic.hinet.net

[(short)(-15074)]

※ 引述《pentiumevo (pentiumevo)》之銘言：

Post by pentiumevo
n是正整數,函數L定義為
0 if n = 1
L =
L([n/2])+1 if n > 1
Describe what this function does?(此處[x]表高斯函數)
解答首先計算L(25)
L(25)=L(12)+1
=(L(6)+1)+1 =L(6)+2
=(L(3)+1)+2 =L(3)+3
=(L(1)+1)+3 =L(1)+4
=0+4
=4
Each time n divided by 2,the value of L is increased by 1.Hence L is the
greatest integer such that
2^L 小於等於 n
Accordingly,L(n)=[(log n)/(log 2)]
計算的部分相當簡單,但是後來的推論我看不懂,完全不知如何推出
L(n)是"以2為底的log n再取高斯函數"
題目出自Schaum's Set Theory and Related Topics, pp.112 Problem 4.30
有書的人可以幫看嗎?謝謝.

在 n 變成 1 之前除以 2 的次數由後面加的 1 的個數來計數

每除以一次 2 這個計數就會加 1

例如以這個計算

3 要除以一次 2 才會變成 1 => L(3) = 1
6 要除以二次 2 才會變成 1 => L(6) = 2
12 要除以三次 2 才會變成 1 => L(12) = 3
25 要除以四次 2 才會變成 1 => L(25) = 4

因此 若 L(n) = k 表示 n 要除以 k 次 2 才會變成 1

那麼我們就有 2^k ≦ n ＜ 2^(k+1)

即 k ≦ log n ＜ k+1 這正是結論
2
--
"Shan't say nothing if you don't say please," said Peeves in his annoying
sing-song voice. "All right -- please."
"NOTHING! Ha haaa! Told you I wouldn't say nothing if you didn't say please!
Ha ha! Haaaaaa!" And they heard the sound of Peeves whooshing away and
Filch cursing in rage.
---'Harry Potter and the Philisopher's Stone', P119

--
※ Origin: 交大次世代(bs2.to)
◆ From: wlan.csie.ntu.edu.tw