Prooving N-1と呼ば回

Question

これは問題から擬似コードである：

Procedure Foo(A,f,L)、前提条件：

• A [f..L]の配列であります整数
• f、Lはf < = Lの2つの自然数> = 1です。

コード

procedure Foo(A,f,L 
    if (f=L) then 

     return A[f] 

    else 

     m <-- [(f+L)/2] 

     return min(Foo(A,f,m), Foo(A, m+1,L)) 

    end if 

質問：誘導を使用して

は、fooが最大n-1回の分を起動すると主張しています。

パート（iii）の証拠をどのように継続するのか少し失われています。私は主張と同様に書かれた主張を持っています。それはn> = 2であると私はそれを信じています。しかし、k + 1項のためにはどうすればいいですか？これは誘導による証拠なので。

おかげ

Answer 1

我々はn = L - f + 1に誘導によって続行されます。

ベースケース：n = 1、f=LとすぐにA[f]を返します。minを0回呼び出します。帰納仮説：k - 1を含むすべてのnについて、その主張が真であると仮定する。n-1 = 1 - 1 = 0。

誘導ステップ：kの主張が真であることを示す必要があります。 L > fから、minを1回呼び出す第2のブランチを実行し、サイズfloor(k/2)とceiling(k/2)のサブ配列に対してFooを呼び出します。

• kが偶数である場合、k/2は整数とfloor(k/2) = ceiling(k/2) = k/2あります。これらは両方ともkよりも小さいので、Fooは、minを少なくとも呼び出しごとにk/2 - 1回呼び出すことがわかっています。しかし、2(k/2 - 1) + 1 = k - 2 + 1 = k - 1なので、呼び出しの最小回数はの場合はk - 1でなければなりません。
• kが奇数の場合、k/2は整数ではなく、floor(k/2) = ceiling(k/2) - 1です。 k > 1の場合、これらの値はどちらもkより小さく、したがって、それぞれの再帰呼び出しが少なくともfloor(k/2) - 1とceiling(k/2) - 1の時刻にそれぞれminを呼び出していることがわかります。しかし、floor(k/2) - 1 + ceiling(k/2) - 1 + 1 = floor(k/2) - 1 + floor(k/2) + 1 = 2*floor(k/2) - 1 + 1 = 2*floor(k/2)。 kは奇数であるので、k/2はw+1/2と書くことができ、w = floor(k/2)と書くことができる。再調整すると、k = 2w + 1があり、少なくとも2*w回、minが呼び出されます。しかしk - 1 = 2*w + 1 - 1 = 2*w = 2*floor(k/2)、kので

を必要に応じてどちらか偶数か奇数であり、我々はminの呼び出しの最小数は、少なくともk - 1で両方のケースで、これは証拠を完了することが示されています。