信息競賽初賽-問題求解

1、問題求解12008_2(提高組)書架上有21本書，編號從1到21，從其中選4本，其中每兩本的編號都不相鄰的選法一共有_種。答案：3060 分析：方法一：首先135713521共15種 136813621共14種 以此類推 以13開頭的一共1+2+3+15=120種 類似的14開頭的1+2+3+14=105種 1 17開頭的1種 然后2 4開頭的105種 3 5開頭的91種 這樣子 一共就有120*1+105*2+91*3+78*4+1*15=3060種 2方法二：隔板排列,公式C(n-m+1,m)意思就是,把要選的4本先拿出來,不是還剩17本嗎? 如果要這4本不相鄰,那這4本的編號之間,必然就

2、還隔著那17本里不會被選到的書. 就是說把那17本插到這4本之間或者兩頭. 而反過來說,也是把這4本插到那17本之間,當(dāng)然也包括兩頭.這樣也保證這4本不會相鄰. 所以一共是18個空位.插4本,即C（18，4）=3060方法三：當(dāng)在這4個數(shù)字中有1或21中的一個時 a) C2選1*（C18選3-16） 當(dāng)在這4個數(shù)字中1.21都有的時候 b) C17選2-15 當(dāng)在這4個數(shù)字中1.21都沒有的時候 C19選4-18 所以答案應(yīng)該是a)+b)+c) 32007_1(提高組).給定n個有標(biāo)號得球，標(biāo)號依次為1，2，n。將這n個球放入r個相同得盒子里，不允許有空盒，其不同放置方法得總數(shù)記為s(n,r)

3、。例如，s(4,2)=7,這7種不同的放置方法依次為(1),(234)，(2),(134)，(3),(124)，(4),(123)，(12),(34)，(13),(24)，(14),(23)。當(dāng)n=7，r=4時，s(7,4)=_ 。分析：s(n,k)=k*s(n-1,k)+s(n-1,k-1)答案：350S(3,2)=2*s(2,2)+s(2,1)=2*1+1=3S(4,3)=3*s(3,3)+s(3,2)=3*1+3=6S(5,3）=3*s(4,3)+s(4,2)=3*6+7=25S(5,4)=4*s(4,4)+s(4,3)=4*1+6=10S(6,4)=4*s(5,4)+s(5,3)=4*10+25=65S(6,3)=3*s(5,3)+s(5,2)=3*25+15=90S(5,2)=2*s(4,2)+s(4,1)=2*7+1=15S(7,4)=4*s(6,4)+s(6,3)=4*65+90=260+90=35042007_2(提高組).N個人在操場里圍成一圈，將這N個人安順時針方向從1到N編號，然后，從第一個人起，每隔一個人讓下一個人離開操場，顯然，第一輪過后，具有偶數(shù)編號的人都離開了操場。依次做下去，直到操場只剩一個人，記這個人的編號為J(N)，例如，J(5)=3，J(10)=5，等等。則J(400)=_。答案：289略解： 把N寫成2的K次方加X的形式 則JN=2X+