三：棧和隊(duì)列

1、第三章 棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS3.1 棧（stack）棧的定義和特點(diǎn)v定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾棧頂，表頭棧底，不含元素的空表稱空棧v特點(diǎn)：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）ana1a2.棧底棧頂.出棧進(jìn)棧棧s=(a1,a2,an)棧的存儲結(jié)構(gòu)v順序棧l實(shí)現(xiàn)：一維數(shù)組sMtop=0123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值為0top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=0,?？?，此時出棧，則下溢（underflow)top=M,棧滿，此時入棧，則上溢（overflow)to

2、ptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？誰入棧算法0M-1棧1底棧1頂棧2底棧2頂l出棧算法l在一個程序中同時使用兩個棧v鏈棧棧頂 .topdata link棧底l結(jié)點(diǎn)定義l入棧算法l出棧算法typedef struct node int data; struct node *link;JD; .棧底toptopxptop .棧底topq棧的應(yīng)用v過程的嵌套調(diào)用r主程序主程序srrrs子過程子過程1rst子過程子過程2rst子過程子過程3例例 遞歸的執(zhí)行情況分析遞歸的執(zhí)行情況分析 v遞歸過程及其實(shí)現(xiàn)l遞歸：函數(shù)直接或間接的調(diào)用自身叫l(wèi)實(shí)現(xiàn)：建立

3、遞歸工作棧void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i1時，先把上面n-1個圓盤從A移到B,然后將n號盤從A移到C,再將n-1個盤從B移到C。即把求解n個圓盤的Hanoi問題轉(zhuǎn)化為求解n-1個圓盤的Hanoi問題，依次類推，直至轉(zhuǎn)化成只有一個圓盤的Hanoi問題l算法：l執(zhí)行情況：u遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址u返回地址用行編號表示n x y z 返回地址 main() int m; printf(Input number of disks”); scanf(%d,&m); printf(”Ste

4、ps : %3d disks”,m); hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 6 main() int m; printf(Input the numbe

5、r of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 6

6、 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 83 A B C 02 B A C 81

7、B C A 6ABC3 A B C 02 B A C 83 A B C 0 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3

8、 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0?？? A B C 02 B A C 8Hanoi.c D:fengyibkcpowerpower.cv回文游戲：順讀與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.去掉空格（原串）3.壓入棧4.原串字符與出棧字符依次比較 若不等，非回文 若直到?？斩枷嗟?，回文v多進(jìn)制輸出：字符串：“madam im adam”例 把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732v表達(dá)式求值 中

9、綴表達(dá)式 后綴表達(dá)式（RPN) a*b+c ab*c+ a+b*c abc*+ a+(b*c+d)/e abc*d+e/+中綴表達(dá)式：操作數(shù)棧和運(yùn)算符棧例 計(jì)算 2+4-3*6操作數(shù)運(yùn)算符24+操作數(shù)運(yùn)算符6-操作數(shù)運(yùn)算符6-36*操作數(shù)運(yùn)算符6-18操作數(shù)運(yùn)算符12后綴表達(dá)式求值步驟：1、讀入表達(dá)式一個字符2、若是操作數(shù)，壓入棧，轉(zhuǎn)43、若是運(yùn)算符，從棧中彈出2個數(shù)，將運(yùn)算結(jié)果再壓入棧4、若表達(dá)式輸入完畢，棧頂即表達(dá)式值； 若表達(dá)式未輸入完，轉(zhuǎn)1top4top43top735top例 計(jì)算 4+3*5后綴表達(dá)式：435*+top415top19(1)(2)(4)(5)(6)(7)(3)v地圖

10、四染色問題R 7 7 1 2 3 4 5 6 71 2 3 4 5 6 7 1 0 0 0 0 1 00 1 1 1 1 1 01 0 1 0 1 1 01 0 1 1 0 1 01 1 0 1 1 0 01 0 0 1 1 0 00 0 0 0 0 0 01 2 3 4 5 6 7 122 3414334231# 紫色紫色 2# 黃色黃色3# 紅色紅色4# 綠色綠色3.2 隊(duì)列隊(duì)列的定義及特點(diǎn)v定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表l隊(duì)尾(rear)允許插入的一端l隊(duì)頭(front)允許刪除的一端v隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)a1 a2 a3.an 入隊(duì)出隊(duì)f

11、rontrear隊(duì)列Q=(a1,a2,an)v雙端隊(duì)列a1 a2 a3.an 端1端2入隊(duì)出隊(duì)入隊(duì)出隊(duì)鏈隊(duì)列v結(jié)點(diǎn)定義typedef struct node int data; struct node *link;JD;頭結(jié)點(diǎn) .front隊(duì)頭隊(duì)尾rear設(shè)隊(duì)首、隊(duì)尾指針front和rear,front指向頭結(jié)點(diǎn)，rear指向隊(duì)尾frontrearx入隊(duì)xfrontreary入隊(duì)xyfrontrearx出隊(duì)xyfront rear空隊(duì)front reary出隊(duì)v入隊(duì)算法v出隊(duì)算法隊(duì)列的順序存儲結(jié)構(gòu)v實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)sqMfront=-1rear=-1123450隊(duì)空123450frontJ

12、1,J1,J3入隊(duì)J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6front設(shè)兩個指針front,rear,約定：rear指示隊(duì)尾元素；front指示隊(duì)頭元素前一位置初值front=rear=-1空隊(duì)列條件：front=rear入隊(duì)列：sq+rear=x;出隊(duì)列：x=sq+front;rearrearfrontrear123450J1,J2,J3出隊(duì)J1J2J3frontfrontfrontv存在問題設(shè)數(shù)組維數(shù)為M，則：l當(dāng)front=-1,rear=M-1時，再有元素入隊(duì)發(fā)生溢出真溢出l當(dāng)front-1,rear=M-1時，再有元素入隊(duì)發(fā)生溢出假溢出v解決方案l隊(duì)首固

13、定，每次出隊(duì)剩余元素向下移動浪費(fèi)時間l循環(huán)隊(duì)列u基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq0接在sqM-1之后，若rear+1=M,則令rear=0;0M-11frontrear.u實(shí)現(xiàn)：利用“?！边\(yùn)算u入隊(duì)： rear=(rear+1)%M; sqrear=x;u出隊(duì)： front=(front+1)%M; x=sqfront;u隊(duì)滿、隊(duì)空判定條件012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：front=rear隊(duì)滿：front=rear解決方案：1.另外設(shè)一個標(biāo)志以

14、區(qū)別隊(duì)空、隊(duì)滿2.少用一個元素空間： 隊(duì)空：front=rear 隊(duì)滿：(rear+1)%M=frontu入隊(duì)算法：u出隊(duì)算法：隊(duì)列應(yīng)用舉例 劃分子集問題v問題描述：已知集合A=a1,a2,an，及集合上的關(guān)系R= (ai,aj) | ai,ajA, ij，其中(ai,aj)表示ai與aj間存在沖突關(guān)系。要求將A劃分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均無沖突關(guān)系，同時要求分子集個數(shù)盡可能少例 A=1,2,3,4,5,6,7,8,9 R= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7

15、,5), (7,6), (3,7), (6,3) 可行的子集劃分為： A1= 1,3,4,8 A2= 2,7 A3= 5 A4= 6,9 v算法思想：利用循環(huán)篩選。從第一個元素開始，凡與第一個元素?zé)o沖突的元素劃歸一組；再將剩下的元素重新找出互不沖突的劃歸第二組；直到所有元素進(jìn)組v所用數(shù)據(jù)結(jié)構(gòu)l沖突關(guān)系矩陣urij=1, i,j有沖突urij=0, i,j無沖突l循環(huán)隊(duì)列cqnl數(shù)組resultn存放每個元素分組號l工作數(shù)組newrnv工作過程l初始狀態(tài)：A中元素放于cq中，result和newr數(shù)組清零，組號group=1l第一個元素出隊(duì)，將r矩陣中第一行“1”拷入newr中對應(yīng)位置，這樣，凡

16、與第一個元素有沖突的元素在newr中對應(yīng)位置處均為“1”,下一個元素出隊(duì)u若其在newr中對應(yīng)位置為“1”，有沖突，重新插入cq隊(duì)尾，參加下一次分組u若其在newr中對應(yīng)位置為“0”, 無沖突，可劃歸本組；再將r矩陣中該元素對應(yīng)行中的“1”拷入newr中l(wèi)如此反復(fù)，直到9個元素依次出隊(duì)，由newr中為“0”的單元對應(yīng)的元素構(gòu)成第1組,將組號group值“1”寫入result對應(yīng)單元中l(wèi)令group=2,newr清零，對cq中元素重復(fù)上述操作，直到cq中front=rear,即隊(duì)空，運(yùn)算結(jié)束v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1

17、0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqf r0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 result初始R= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5)

18、, (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr1 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 result

19、R= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0

20、 0 0 0 00 1 2 3 4 5 6 7 8 newr1 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0

21、0 0 01 0 0 0 1 1 0 1 1R= 2 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 1 1 0 00 1 2 3 4 5 6 7 8 newr1 0 1 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0

22、 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3)

23、v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2

24、,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr

25、1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6

26、 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1

27、 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6 7 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0

28、0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6 7 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,

29、4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 5 6 7 90 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resul

30、tR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 6 7 9 50 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1

31、10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01

32、0 0 0 1 1 0 1 1R= 7 9 5 60 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1

33、 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 9 5 60 1 2 3 4 5 6 7 8 cqfr1 0 1 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 2 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0

34、0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 5 6 90 1 2 3 4 5 6 7 8 cqfr1 0 1 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 2 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),

35、 (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 6 90 1 2 3 4 5 6 7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2 1 1 3 0 2 1 00 1 2 3 4 5 6 7

36、8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 9 60 1 2 3 4 5 6 7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2 1 1 3 0 2 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (