|
小学名探偵 |
|
色分け
開いた配列の場合の数L(n)= 4*3^(n-1) 閉じた配列の場合の数O(n) 両者の関係は、 n = 1,2のとき、L(n)= O(n) n >2 のとき、L(n)= O(n)+O(n-1) したがって、k>=1 のとき、 O(2k)= Σ{i= 1 to k}L(2i)- Σ{i= 1 to k-1}L(2i+1) L(x)に値を代入して、O(2k)= 3^2k+3 O(2k+1)= Σ{i= 1 to k}L(2i+1)-Σ{i= 1 to k}L(2i) （たとえば、O(5)=L(5)-L(4)+L(3)-L(2)です） L(x)に値を代入して、O(2k+1)= 3^(2k+1)-3 また、O(n)の漸化式は、 L(n)= O(n)+O(n-1)と L(n)=3L(n-1)から、 n>=4のとき、 O(n)+O(n-1)=3O(n-1)+3O(n-2) よって、 O(n)=2O(n-1)+3O(n-2) |
|
5月20日（金） 8:20:24
25116 |