算法合集之《信息學(xué)中守恒法的應(yīng)用》

1、信息學(xué)中守恒法的應(yīng)用 兩個質(zhì)量相等的小球，速度分別為5m/s, 4m/s，他們相向運動，碰撞之后速度分別變成多少？動能動量守恒10g C和10g O2在密閉容器中反應(yīng)一個小時。最后的總質(zhì)量是多少？質(zhì)量守恒變化中的不變量變化中的不變量數(shù)列操作問題(1)問題描述：有一個數(shù)列a1, a2, a3, , an。每次可以從中任意選3個相鄰的數(shù)ai-1, ai, ai+1，進(jìn)行如下操作(ai-1, ai, ai+1)(ai-1+ai, -ai, ai+ai+1)1 4 9 2 7 64+9 -9 9+21 13 -9 11 7 6數(shù)列操作問題(2)問題：給定初始和目標(biāo)序列，請判斷能不能通過以上定義的操作，

2、從初始變到目標(biāo)狀態(tài)。1 6 9 4 2 01 6 13 -4 6 01 6 13 2 -6 67 -6 19 2 -6 6Input.txt1 6 9 4 2 07 6 19 2 6 6Output.txtYES數(shù)列操作問題(3)(ai-1, ai, ai+1)(ai-1+ai, -ai, ai+ai+1)5 9 214 -9 11S1=5S2=14S3=16S1=14S2=5S3=16S1和S2交換數(shù)列操作問題(4)(ai-1, ai, ai+1)(ai-1+ai, -ai, ai+ai+1)x y zx+y -y y+zS1=xS2=x+yS3=x+y+zS1=x+yS2=xS3=x+y+

3、zS1和S2交換數(shù)列操作問題(5)1 6 9 4 2 0S1=1S2=7S3=16S4=20S5=22S6=227 -6 19 2 -6 6S1=7S2=1S3=20S4=22S5=16S6=221,7,16,20,22,221,7,16,20,22,22相等數(shù)列操作問題(6)(ai-1, ai, ai+1)(ai-1+ai, -ai, ai+ai+1)x y zx+y -y y+zS1=xS2=x+yS3=x+y+zS1=x+yS2=xS3=x+y+z對對(ai-1,ai,ai+1)的操作，的操作，相當(dāng)于交換相當(dāng)于交換Si-1, Si數(shù)列操作問題(7)對對(ai-1,ai,ai+1)的操作，

4、相當(dāng)于交換的操作，相當(dāng)于交換Si-1, SiSn不可能被交換，所以初始和目標(biāo)序列的Sn應(yīng)該相等集合S1, S2, , Sn-1始終不變經(jīng)過若干操作后，序列S1, S2, , Sn-1發(fā)生順序的改變反之，如果兩個Si和Si(1=i=n-1)完全相等，只是順序不同。他們必然可以通過一系列操作互相轉(zhuǎn)化(前提是Sn要相等)數(shù)列操作問題(8)輸入數(shù)列Ai, Bi求出SAiSBi把SAn和SBn比較；再把SAiSBi（1=i=n-1）分別排序，然后直接比較。如果都相等輸出“YES”，否則“NO”時間復(fù)雜度O(nlogn)（排序復(fù)雜度）小結(jié)：數(shù)列變換的過程中，數(shù)字雜亂無章，沒什么規(guī)律。但是他們的和是有規(guī)律的

5、。抓住變化中的不變量，一切都變得很輕松。棋子移動(1)問題描述：有一列無限長的格子里面。某些格子里面放了棋子如果某個格子里面有棋子，可以拿走這一顆，并且在這個格子的左邊兩個格子里面各放一顆。26321153棋子移動(2)問題描述：如果連續(xù)兩個格子里面都有棋子，可以分別在兩個格子里面各拿走一顆，并且在它們右邊的格子里面放一顆。26321153棋子移動(3)問題：給定初始狀態(tài)，要求用以上操作，使得：每個格子里面至多只有1個棋子（或者沒有）。沒有相鄰的兩個格子都有棋子。簡單的說：就是無法繼續(xù)操作！棋子移動(4)121111111111111棋子移動(5)棋子變小橡皮泥！Wi第i個格子中橡皮泥的大小W

6、i=Wi-1+Wi-2棋子移動(6)Wi=Wi-1+Wi-2Fibonacci數(shù)列11235813213455891111212*1+8*2+34*1=5211235813213455895*1+13*2+34*1=52相等棋子移動(7)棋子變小橡皮泥！操作的過程中操作的過程中橡皮泥的總量是保持橡皮泥的總量是保持不變不變的。的。棋子移動(8)112358132134558912111235813213455892*1+8*2+34*1=5252-34=1818-13=55-5=0111棋子移動(9)棋子移動的過程紛繁復(fù)雜，也沒什么規(guī)律可尋。我們通過發(fā)現(xiàn)“橡皮泥質(zhì)量守恒橡皮泥質(zhì)量守恒”，把復(fù)雜的移動規(guī)則，變成了簡單的數(shù)字加減?！跋鹌つ噘|(zhì)量”就是變化中的不變量還有一些細(xì)節(jié)：高精度，解的存在性的證明，解的唯一性的證明。格子有無窮多個，到底從什么地方開始標(biāo)“質(zhì)量”？這些大家可以自己研究。這里只想揭示最本質(zhì)的東西：守