信息學(xué)初賽問題求解解題

信息學(xué)初賽問題求解部份（14-18）（第十四屆）書架上有4本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的把這4本書擺在書架上，知足所有黑皮的書都排在一路的擺法種。知足A必需比C靠左，所有紅皮的書要擺在一路，所有黑皮的書要擺放在一路，共有 種擺法。解:一、分析（1）CDAB (2)CDBA (3)ACDB (4)BCDA (5)ABCD (6)BACD(7)DCAB (8)DCBA (9)ADCB (10)BDCA (11)ABDC二、分析(1)ABCD （2）BACD (3)ABDC (4)BADC有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距如下表所示，那么城市1到城市6的最短距離為 7 。城市1城市2城市3城市4城市56城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920解：(1->2->5->6)12，5，62+3+2=7.是距離最短的。（第十五屆）小陳現(xiàn)有2個(gè)任務(wù)A，B要完成，每一個(gè)任務(wù)別離有假設(shè)干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時(shí)候，小陳只能專心做某個(gè)任務(wù)的一個(gè)步驟?？墒侨羰乔樵?，他能夠在做完手中任務(wù)的當(dāng)前步驟后，切換至另一例如……a2->b2->a3->b3……a2->b3->a3->b2……是不合法的。Bb1A，其他的都忘了。使計(jì)算小陳飯前已做的可能的任務(wù)步驟序列共有 種解法一：ABa3014102035a201361015a101234501b11b21b31b41b5a3解法二：排列組合+加法原理B任務(wù)中的b1必然做，而且確信是第一個(gè)做的。除b1外第一類：完成A任務(wù) 只有1種。第二類：完成A任務(wù)和b2 有C(4,1)=4種。第三類：完成A任務(wù)和b二、b3 有C(5,2)=10種第四類：完成A任務(wù)和b二、b3、b4 有C(6,3)=20種Abb3、b4、b5C(7,4)=351+4+10+20+35=70。1.a:=1;2.b:=a;3.d:=-a;4.e:=a+d;5.c:=2*d;6.f:=b+e-d;7.g:=a*f+c;此刻要把這段程序分派到假設(shè)干臺（數(shù)量充沛）用電纜連接的PC上做并行執(zhí)行。每臺PC執(zhí)行其中的某幾個(gè)語句，并可隨時(shí)通過電纜與其他PC通信，互換一些中間結(jié)果。假設(shè)每臺PC每單位時(shí)刻能夠執(zhí)行一個(gè)語句，且通信花費(fèi)的時(shí)刻不計(jì)。那么這段程序最快能夠在 單位時(shí)刻內(nèi)執(zhí)行完畢。注意：任意中間結(jié)果只有某臺PC上已經(jīng)取得，才能夠被其他PC引用。例如假設(shè)語句4和6被別離分派到兩臺PC上執(zhí)行，那么因?yàn)檎Z句6需要引用語句4的計(jì)算結(jié)果，語句6必需在語句4以后執(zhí)行。1，2345，6，7。（第十六屆）1、LZW編碼是一種自適應(yīng)詞典編碼。在編碼的進(jìn)程中，開始時(shí)只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，若是在編碼的進(jìn)程中碰到一個(gè)新的詞條，那么該詞條及一個(gè)新的編碼會被追加到詞典中，并用于后繼信息的編碼。舉例說明，考慮一個(gè)待編碼的信息串：“xyxyyyyxyx”。初始詞典只有3個(gè)條款，第一個(gè)為x,編碼為1；第二個(gè)為y，編碼為2；第三個(gè)為空格，編碼為3；于是串“xyx”的編碼為1-2-1（其中-為編碼分隔符），加上后面的一個(gè)空格確實(shí)是1-2-1-3。但由于有了一個(gè)空格，咱們就明白前面的“xyx”是一個(gè)單詞，而由于該單詞沒有在詞典中，咱們就能夠夠自適應(yīng)的把那個(gè)詞條添加到詞典里，編碼為4，然后依照新的詞典對后繼信息進(jìn)行編碼，以此類推。于是，最后取得編碼：。此刻已知初始詞典的3個(gè)條款如上述，那么信息串“yyxyxxyyxyxyxxx的編碼是解：2-2-1-2-3--1-3-5-3-6（或2236）2、隊(duì)列快照是指在某一時(shí)刻隊(duì)列中的元素組成的有序序列?，F(xiàn)有3個(gè)正整數(shù)元依次入隊(duì)、出隊(duì)。已知它們的和為8，那么共有 種可能的不同的隊(duì)列照（不同隊(duì)列的相同快照只計(jì)一次）。例如，"51"、"422"、""都是可能的隊(duì)列快照；而"7"不是可能的隊(duì)列快照，因?yàn)槭Ｏ碌?個(gè)正整數(shù)的和不可能是1。解：49（第十七屆）1每份考卷都有一個(gè)8位二進(jìn)制序列號當(dāng)且僅當(dāng)一個(gè)序列號含有偶數(shù)個(gè)1時(shí)，它才是有效的。例如01010011都是有效的序列號，而不是。那么有效的序列號共有 個(gè)解：這是個(gè)排列組合問題中的組合問題。8個(gè)二進(jìn)制各不干與，且只有2當(dāng)選擇即0或1，知足題意的序列號序列號中有0個(gè)1的有1個(gè)，序列號中有2個(gè)1的有28個(gè)，4個(gè)1的有70個(gè)，6個(gè)1的有28個(gè)，8個(gè)1的有1個(gè)。取得：1+28+70+28+1=1282、概念字符串的大體操作為：刪除一個(gè)字符、插入一個(gè)字符和將一個(gè)字符修改成另一個(gè)字符這三種操作。將字符串A變成字符串B的最少操作步數(shù)，稱為字符串A到字符串B的編輯距離。字符串"ABCDEFG"到字符串"BADECG"的編輯距離為 。解：編輯距離為3ABCDEFG刪除A 得出BCDEFG(A→)BCDEFG將C替換成A 得出BADEFGBADEFG將F替換成C 得出BADECG(F→C)（第十八屆）1、若是平面上任取n個(gè)整點(diǎn)（橫縱坐標(biāo)都是整數(shù)），其中必然存在兩個(gè)點(diǎn)，它連線的中點(diǎn)也是整點(diǎn)，那么n至少是 。解：5想象橫縱交織的網(wǎng)格紙，就像棋盤那樣的，每一個(gè)橫縱線交點(diǎn)確實(shí)是一個(gè)整點(diǎn)。如以下圖：任意三個(gè)點(diǎn)若是共線，即處在水平，豎直，或?qū)蔷€上，那么其中定存在兩個(gè)點(diǎn)知足連線中點(diǎn)是整點(diǎn)。若是n=2，取兩個(gè)持續(xù)的整點(diǎn)，那么連線中點(diǎn)不是整點(diǎn)。若是n=3，取水平兩個(gè)持續(xù)的點(diǎn)，垂直也兩個(gè)持續(xù)的點(diǎn)，組成三角形。那么連線中點(diǎn)不是整點(diǎn)。若是n=4，取四個(gè)整點(diǎn)組成一個(gè)正方形，那么連線中點(diǎn)不是整點(diǎn)。而取5個(gè)點(diǎn)的話，必然有兩個(gè)點(diǎn)的連線中點(diǎn)是整點(diǎn)。2、在NOI期間，主辦單位為了歡迎來自各國的選手，舉行了盛大的晚宴。在第十八桌，有5名大陸選手和5名港澳選手一起進(jìn)膳。為了增進(jìn)交流，他們決定相隔就坐，即每一個(gè)大陸選手左右旁都是港澳選手，每一個(gè)港澳選手左右旁都是大陸選手。那么，這一桌一共種不同的就坐方案。注：若是在兩個(gè)方案中，一個(gè)選手左右相鄰的選手相同，那么視為同一種方案。解1：288011054410*5*4*4*3*3*2*2*1*1。這其中有重復(fù)的，同一種坐法，能夠繞著桌子走一圈，確實(shí)是上一個(gè)人坐到下一個(gè)人的位置，串一下，如此所有坐法就算重復(fù)了10105*4*4*3*3*2*2*1*1。解2：28805然后再安排五個(gè)港澳選手，是一起進(jìn)膳應(yīng)該只有55P（5，5）種坐法，然后相乘。可到那個(gè)地址并非是就終止了，因?yàn)槟莻€(gè)地址面包括了重復(fù)的，可是重復(fù)的情形超級極端，“每一個(gè)選手左側(cè)相鄰的選手均相同”，每一種方案，每一個(gè)人都往左或往右移動一個(gè)位子，兩個(gè)位子，三個(gè)位子……跟原先的仍是一樣的方案，也確實(shí)是說每十種方案里一共有5種是重復(fù)的。因此要去除重復(fù)，除以5。因此應(yīng)該是P（5，5）*P（5，5）/5。附：排列組合原理一、加法原理與乘法原理一、加法原理：nm1種不同的方式，m2nmn那么完成這件事共有N=m1+m2+...+mn種不同的方式。二、乘法原理：做一件情形，完成它需要分成nm1m2nmn有N=m1*m2*...*mn種不同的方式。完成”，乘法原理是“分步完成”。二、排列與組合的概念與計(jì)算公式一、排列及計(jì)算公式nm(1≤m≤n)nmnm(m≤n)素的所有