助教好 有兩個小問題想請教~
問題一：1-2節，第28,29頁，例題25
證明的過程都看的懂，但就是有一個關鍵地方不大清楚，
就是當圖片為(2的k+1次方)x(2的k+1次方)時，
分割為四塊2的K次方，右上角有缺一塊，根據假設這右上角會成立。
我知道補上一個L型塊會使剩下三個成立，但是為何可以平白無故又另外多加一塊L磚塊再這四塊中間~
(而且右上角的方形缺快也還在)
問題二：
2-7節，第99頁
所證出來的f(i,j) = 1 + 2 + ...+ (i+j-2)+j
想請問這公式是如何推導來的~
以前上課時老師提到特點是同一排相加值相同，j是表示在同一排上的第幾個
可是我還是找不到可以直接聯想到這公式的地方...
1 則留言:
1. 不是平白無故多加的, 應該是說加那一塊就是我們所設計出來的演算法
首先先判斷缺角在哪一象限, 在根據缺角的位置是在左上左下右上還是右下, 放一塊新的L型在中間, 如此一來會使得那4塊都各缺一角, 這樣遞迴做下去直到剩下2x2, 整個棋盤就都可以被L型給填滿了
2. 對角線上的每一排加值都相同是因為 i 和 j 有一加一減的關係, 假設現在要算f(i,j), 我們只要知道(i,j)在對角線上的哪一排, 我們就可以算出答案, 因為假設(i,j)在對角線上的第 x 排, 則f(i,j)=[1+2+...+(x-1)]+j
再觀察一下書上的圖你就會發現 (i,j) 所在的排數就相當於是從 i 開始往下數 j-1 排, 所以 x=i+j-1, 所以f(i,j)=[1+2+...+(i+j-2)]+j
張貼留言