第四章作業(yè)答案

第四章作業(yè)答案6.確定{1,2,…,8}的下列排列的逆序列。

ⅰ)35168274

ⅱ)83476215解ⅰ)35168274的逆序列是2,4,0,4,0,0,1,0。 ⅱ)83476215的逆序列是6,5,1,1,3,2,1,0。7.構(gòu)造{1,2,…,8}的排列，其逆序列是ⅰ)2,5,5,0,2,1,1,0ⅱ)6,6,1,4,2,1,0,0解ⅰ) □□1□□□□□ □□1□□□2□ □□1□□□23 4□1□□□23 4□1□5□23 4□165□23 4□165723 48165723 逆序列是2,5,5,0,2,1,1,0的排列是48165723。 ⅱ) □□□□□□1□ □□□□□□12 □3□□□□12 □3□□□412 □3□5□412 □365□412 7365□412 73658412 逆序列是6,6,1,4,2,1,0,0的排列是73658412。15.對于{x7,x6,…,x1,x0}的下列每一個(gè)組合，通過使用基為2的生成算法確定其直接后繼組合：ⅰ){x4,x1,x0}ⅱ){x7,x5,x3}ⅲ){x7,x5,x4,x3,x2,x1,x0}ⅳ){x0}解ⅰ){x4,x1,x0}對應(yīng)0和1的8-元組00010011，使用基為2的生成算法求得j=2，確定00010011的下一個(gè)8-元組是00010100，其對應(yīng)的組合是{x4,x2}。因此，{x4,x1,x0}的直接后繼組合是

{x4,x2}。ⅱ){x7,x5,x3}對應(yīng)0和1的8-元組10101000，使用基為2的生成算法求得j=0，確定10101000的下一個(gè)8-元組是10101001，其對應(yīng)的組合是{x7,x5,x3,x0}。因此，{x7,x5,x3}的直接后繼組合是

{x7,x5,x3,x0}。ⅲ){x7,x5,x4,x3,x2,x1,x0}對應(yīng)0和1的8-元組10111111，使用基為2的生成算法求得j=6，確定10111111的下一個(gè)8-元組是11000000，其對應(yīng)的組合是{x7,x6}。因此，{x7,x5,x4,x3,x2,x1,x0}的直接后繼組合是{x7,x6}。ⅳ){x0}對應(yīng)0和1的8-元組00000001，使用基為2的生成算法求得j=1，確定00000001的下一個(gè)8-元組是00000010，其對應(yīng)的組合是{x1}。因此，{x0}的直接后繼組合是{x1}。17.當(dāng)使用基為2的生成算法時(shí)，{x7,x6,…,x1,x0}的哪個(gè)組合是S的組合列表中的第150個(gè)組合？第200個(gè)組合？第250個(gè)組合？（如節(jié)4.3所示，表中的這些位置是從0開始計(jì)數(shù)的）。解 150=1′27+1′24+1′22+1′21150的二進(jìn)制表示是10010110。因此，第150個(gè)組合是

{x7,x4,x2,x1}。 200=1′27+1′26+1′23200的二進(jìn)制表示是11001000。因此，第200個(gè)組合是{x7,x6,x3}。 250=1′27+1′26+1′25+1′24+1′23+1′21250的二進(jìn)制表示是11111010。因此，第250個(gè)組合是

{x7,x6,x5,x4,x3,x1}。00000000000000100011000100010100110001110010000解000,001,011,010,110,100,101,111是3階非循環(huán)Gray碼。23.確定下列9階反射Gray碼中9-元組的直接后繼。ⅰ)010100110ⅱ)110001100ⅲ)111111111解ⅰ)(010100110)=4是偶數(shù)，所以010100110的直接后繼是010100111。ⅱ)(110001100)=4是偶數(shù)，所以110001100的直接后繼是110001101。ⅲ)(111111111)=9是奇數(shù)，j=0，所以111111111的直接后繼是111111101。43.令X={a,b,c,d,e,f}，并將X上的關(guān)系R以aRb,bRc,cRd,aRe,eRf,fRd定義，證明，R是一個(gè)偏序集的覆蓋關(guān)系，并確定這個(gè)偏序集的所有的線性擴(kuò)張。證明設(shè)R是有限非空集X上的關(guān)系。R是一個(gè)偏序集的覆蓋關(guān)系的充分必要條件是：R是反自反的。R是反對稱的。若x1Rx2,x2Rx3,…,xk1Rxk，則x1xk且xkx1，其中k3。也就是說，R的關(guān)系圖滿足以下條件：每個(gè)頂點(diǎn)上都沒有自環(huán)。不存在這樣的半回路，改變其中至多一條邊的方向就能使其成為有向回路。R的傳遞閉包是嚴(yán)格偏序<，<的自反閉包，即R的自反傳遞閉包是偏序≤。畫R的關(guān)系圖如下：edbf畫偏序集的哈斯圖edbf畫出入度為0的頂點(diǎn)a。去掉a及與其關(guān)聯(lián)的邊，入度為0的頂點(diǎn)是b和e，將b和e畫在a的上方。再去掉b和e及與其關(guān)聯(lián)的邊，入度為0的頂點(diǎn)是c和f，將c和f畫在b和e的上方。再去掉c和f及與其關(guān)聯(lián)的邊，入度為0的頂點(diǎn)是d，將d畫在c和f的上方。abefabefcd

該偏序集有6個(gè)線性擴(kuò)張，它們的哈斯圖如下。adbcefadbecfadebcfadefadbcefadbecfadebcfadefbcadbefcadebfc證明任取非負(fù)整數(shù)a，a和a除以m有相同的余數(shù)，所以aRa，R是自反的。

若aRb，則a和b除以m有相同的余數(shù)，b和a除以m有相同的余數(shù)，所以bRa，