acm中矩陣乘法的應(yīng)用精講-免費(fèi)閱讀
【正文】 什么是奮斗？奮斗就是每天很難，可一年一年卻越來越容易。 continue。 }}int main(){ Matrix mat。i++) for(j=0。j++) for(k=0。j++) [i][j]=(i==j)。void matrixMultiplication(Matrix amp。}【HDU1005】Number Sequence（矩陣乘法）by 三江小渡Categories: 數(shù)據(jù)結(jié)構(gòu)和算法Tags: HDU, 矩陣乘法Comments: No CommentsPublished on: 2011 年 09 月 16 日A number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n – 1) + B * f(n – 2)) mod 7.Given A, B, and n, you are to calculate the value of f(n).題意：給出一個(gè)遞推公式，求第N項(xiàng)。for (int k=0。m, amp。else if (exp amp。for (int i=0。void CMatrix::setSize(int a){for (int i=0。/m)class CMatrix{public:long element[MAX_SIZE][MAX_SIZE]。這個(gè)圖的構(gòu)造過程類似于用有限狀態(tài)自動(dòng)機(jī)做串匹配。數(shù)據(jù)規(guī)模n=2 000 000 000。把這8種狀態(tài)的轉(zhuǎn)移關(guān)系畫成一個(gè)有向圖，那么問題就變成了這樣：從狀態(tài)111出發(fā)，恰好經(jīng)過n步回到這個(gè)狀態(tài)有多少種方案。同理，如果要求經(jīng)過k步的路徑數(shù)，我們只需要二分求出A^k即可。每多乘一次這個(gè)矩陣，這兩個(gè)數(shù)就會(huì)多迭代一次。首先將這m個(gè)置換“合并”起來（算出這m個(gè)置換的乘積），然后接下來我們需要執(zhí)行這個(gè)置換k/m次（取整，若有余數(shù)則剩下幾步模擬即可）。這道題兩次二分，相當(dāng)經(jīng)典。由于矩陣乘法具有結(jié)合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。經(jīng)典題目1 給定n個(gè)點(diǎn)，m個(gè)操作，構(gòu)造O(m+n)的算法輸出m個(gè)操作后各點(diǎn)的位置。不要以為數(shù)學(xué)中的矩陣也是黑色屏幕上不斷變化的綠色字符。在數(shù)學(xué)中，一個(gè)矩陣說穿了就是一個(gè)二維數(shù)組。操作有平移、縮放、翻轉(zhuǎn)和旋轉(zhuǎn)這里的操作是對(duì)所有點(diǎn)同時(shí)進(jìn)行的。我們可以得到這樣的結(jié)論：當(dāng)n為偶數(shù)時(shí)，A^n = A^(n/2) * A^(n/2)；當(dāng)n為奇數(shù)時(shí)，A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。首先我們知道，A^i可以二分求出。注意任意一個(gè)置換都可以表示成矩陣的形式。那么，我們把這個(gè)2 x 2的矩陣自乘n次，再乘以(0,1)就可以得到第n個(gè)Fibonacci數(shù)了。經(jīng)典題目9 用1 x 2的多米諾骨牌填滿M x N的矩形有多少種方案，M=5，N2^31，輸出答案mod p的結(jié)果我們以M=3為例進(jìn)行講解。比如，n=2時(shí)有3種方案，11101111111110111
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1