1

わかりました、私はクヌースの具体的な数学に苦労しており、まだ理解していない例がいくつかあります.

J(n) = 2*J(n/2) - 1

第一章からです。具体的には、具体的な数学に精通している可能性のある人のために、ヨセフス問題を解決します。解決策はありますが、説明はまったくありません。イテレーション法で解いてみました。これがこれまでに思いついたものです

J(n) = (2^k)*J(n/(2^k)) - (2^k - 1)

そして、私はここで立ち往生しています。ヘルプやヒントをいただければ幸いです。

4

3 に答える 3

1

いくつかの簡単な例から始めて推測し、帰納法を使用してその推測を (反証) 証明します。

n = 2 の累乗と考えてください。

J(2^0) = 1 (与えられた)

J(2^1) = 2J(2^0) - 1 = 1

J(2^2) = 2J(2^1) - 1 = 1

さて、すべての n >= 1 に対して J(n) = 1 と推測しましょう。

基本ケース: J(1) = 1、これは定義上真です。

誘導ステップ: 任意の k に対して J(k) = 1 と仮定します。J(2k) = 2J(k) - 1 = 1 です。

したがって、帰納法により、すべての n に対して J(n) = 1 になります (除算が整数に切り捨てられると仮定します)。

于 2013-04-17T03:10:43.463 に答える