幾個問題的算法實現(xiàn)

幾個問題的算法實現(xiàn)一、打印法雷序列【問題描述】對任意給定的一個自然數(shù)n,將分母Wn的不可約的真分?jǐn)?shù)按照升序排列，并且在第一個分?jǐn)?shù)前面加上數(shù)0/1，在最后一個分?jǐn)?shù)后面加上數(shù)1/1，這個序列被稱之為n級法雷序列，以Fn表示。例如：F8為：0/1、1/8、1/7、1/6、1/5、1/4、2/7、1/3、3/8、2/5、3/7、1/2、4/7、3/5、5/8、2/3、5/7、3/4、4/5、5/6、6/7、7/8、1/1【分析與實現(xiàn)】可以證明，b/a<(b+d)/(a+c)<d/c(略)，故采用二分法并遞歸，只要分母大于給定數(shù)值就退出查找。【代碼(C++)】#include<iostream>usingnamespacestd;intn;intgcd(intm,intn){if(n==0)return1;if(m%n==0)returnn;elsegcd(n,m%n);}intfaray(inta,intb,intc,intd){intx=a+c,y=b+d,r;r=gcd(x,y);x/=r,y/=r;if(y>n)return0;faray(a,b,x,y);cout<<x<<"/"<<y<<",";faray(x,y,c,d);}intmain()cin>>n;cout<<"0/1,";faray(0,1,1,1);cout<<"1/1";return0;}二、約瑟夫問題【問題描述】每N個乘客同乘一艘船，因為嚴(yán)重超載，加上風(fēng)高浪大，危險萬分，因此船長告訴乘客，只有將全船一半乘客投入海中，其余人才能幸免于難。無奈，大家只得同意這種辦法，并議定N個人圍成一圈，由第1個人數(shù)起，依次報數(shù)，數(shù)到第m人，便把他投入大海中，然后再從他的下一個人數(shù)起，數(shù)到第m人，再將他扔到大海中，如此循環(huán)地進(jìn)行，直到剩下n個乘客為止。問哪些位置是將被扔下大海的位置?！痉治雠c實現(xiàn)】由于需要頭尾銜接，并且沒有對數(shù)據(jù)的處理，故采用結(jié)構(gòu)(struet)單向循環(huán)鏈表；采用指針p進(jìn)行移動計數(shù)，指針f指向指針p前一節(jié)點(diǎn)以便于刪除節(jié)點(diǎn)，eount記錄p走過的節(jié)點(diǎn)數(shù)，達(dá)到間隔值就進(jìn)行刪除；在輸出前應(yīng)尋找最小節(jié)點(diǎn)位置，逐一移動p,直到p所指向節(jié)點(diǎn)的值大于下一節(jié)點(diǎn)的值?！敬a(C++)】#inelude<iostream>usingnamespaeestd;struetperson{intnum;person*next;};intmain(){inttotal,leavings,interval;ein>>total>>leavings>>interval;person*pe=newperson[total+1];inti;pe[total].next=&pe[1];for(i=0;i<=total;i++)pe[i].num=i;for(i=0;i<total;i++)pe[i].next=&pe[i+1];person*p,*f;intn=total,eount;p=&pe[1],f=&pe[total];for(eount=1;n!=leavings;eount++)if(eount==interval){f->next=p->next,count=0,n--;}f=p;p=p->next;}cout<<"leavings:";for(;;){if(p->num>p->next->num){p=p->next;for(i=0;i<leavings;i++){cout<<p->num;p=p->next;if(i<leavings-1){cout<<",";}}break;}p=p->next;}return0;}三、漢諾塔問題【問題描述】在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，求把圓盤從下面開始按大小順序重新擺放在另一根柱子上需要移動多少次。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。【分析與實現(xiàn)】這是個典型的遞歸問題，將n個盤子從A柱移到C柱具體分為以下三步：1?將A柱上的n-1個盤子借助C柱先移至B柱；2?將A柱上第n個盤子移至C柱；3.將B柱上n-1個盤子借助A柱移至C柱?！敬a(C++)】#include<iostream>usingnamespacestd;intmain()voidhanoi(intn,charone,chartwo,charthree);intm;cout<<"輸入盤子數(shù):"；cin>>m;;hanoi(m,'A','B','C');voidhanoi(intn,charone,chartwo,charthree){voidmove(charx,chary);if(n==1){move(one,three);}else{hanoi(n-1,one,three,two);move(one,three);hanoi(n-1,two,one,three);}}voidmove(charx,chary){cout<<x<<"-->"<<y<<endl;}四、八皇后問題【問題描述】在8*8的棋盤上擺放8個皇后，使其不能互相攻擊，即任意的兩個皇后不能處在同意行，同一列，或同意斜線上?？梢园寻嘶屎髥栴}拓展為n皇后問題，即在n*n的棋盤上擺放n個皇后，使其任意兩個皇后都不能處于同一行、同一列或同一斜線上?！痉治雠c實現(xiàn)】【代碼(C++)】回溯法顯然，每一行可以而且必須放一個皇后，所以n皇后問題的解可以用一個n元向量X二(xl,x2, xn)表示，其中，1WiWn且1WxiWn,即第n個皇后放在第i行第xi列上。由于兩個皇后不能放在同一列上，所以，解向量X必須滿足的約束條件為:xiHxj。若兩個皇后的擺放位置分別是(i,xi)和(j,xj),在棋盤上斜率為-1的斜線上，滿足條件i-j=xi-xj;在棋盤上斜率為1的斜線上，滿足條件i+j=xi+xj。綜合兩種情況，由于兩個皇后不能位于同一斜線上，所以，解向量X必須滿足的約束條件為：|i-xi|H|j-xj|#include<iostream>#include<math.h>usingnamespacestd;intx[100];boolplace(intk);inti;for(i=1;i<k;i++)if(x[k]==x[i]||abs(k-i)==abs(x[k]-x[i]))returnfalse;returntrue;}voidqueue(intn){inti,k;for(i=1;i<=n;i++)x[i]=0;k=1;while(k>=1){x[k]=x[k]+1;while(x[k]<=n&&!place(k))x[k]=x[k]+1;if(x[k]<=n&&k==n){for(i=1;i<=n;i++)printf("%d",x[i]);printf("\n");}elseif(x[k]<=n&&k<n)k=k+1;else{x[k]=0;k=k-1;}}}Intmain(){intn=8;queue(n);return0;}遞歸-回溯法#include<iostream>usingnamespacestd;structQueen{intx;inty;};structChessBoard{boolXY[8][8];};QueenMyQueen[8];ChessBoardMyChessBoard[8];intN;voidprint(){cout<<"case"<<++N<<":";for(inti=0;i<=7;i++){cout<<MyQueen[i].y+1<<"";}cout<<endl;}voidFunc(intx,inty,intstep){MyChessBoard[step]=MyChessBoard[step-1];for(inti=0;i<=7;i++){MyChessBoard[step].XY[x][i]=true;MyChessBoard[step].XY[i][y]=true;}inttempx=x;inttempy=y;while(x<8&&y<8){MyChessBoard[step].XY[x][y]=true;x++;y++;}while(tempx<8&&tempy>=0) //左斜向{MyChessBoard[step].XY[tempx][tempy]=true;tempx++;tempy--;}}voidStart(intstep){if(step==9)print();else{MyQueen[step-1].x=step-1;for(inti=0;i<8;i++){if(MyChessBoard[step-1].XY[step-1][i]==true)continue;MyQueen[step-1].y=i;if(step<8)Func(MyQueen[step-1].x,MyQueen[step-1].y,step);Start(step+1);}}}intmain(){Start(1);return0;}殘卷法：采用3維數(shù)組實現(xiàn)#include"stdio.h"voidmain(){staticinta[9][10][1645],x,y,i,j,z=1,k,flag,h,m,n=0;for(k=1;k<=z;k++){for(x=1;x<=8;x++){if(x==8&&m==0){flag=z+1;m=1;}if(a[x][0][k]==2)continue;for(y=1;y<=8;y++){if(a[0][y][k]==2)continue;if(x>1)if(a[x-1][y-1][k]==1||a[x-1][y+1][k]==1)continue;

continue;continue;continue;continue;continue;continue;if(x>2)if(a[x-2][y-2][k]==1||a[x-2][y+2][k]==1)if(x>3)if(a[x-3][y-3][k]==1||a[x-3][y+3][k]==1)if(x>4)if(a[x-4][y-4][k]==1||a[x-4][y+4][k]==1)if(x>5)if(a[x-5][y-5][k]==1||a[x-5][y+5][k]==1)if(x>6)if(a[x-6][y-6][k]==1||a[x-6][y+6][k]==1)if(x>7)if(a[x-7][y-7][k]==1||a[x-7][y+7][k]==1)continue;continue;continue;continue;continue;continue;for(i=0;i<9;i++)for(j=0;j<9;j++)a[i][j][z+1]=a[i][j][k];a[x][y][z+1]=1;a[0][y][z+1]=2;a[x][0][z+1]=2;z++;}break;}}for(k=flag;k<=z;k++){for(i=1;i<=8;i++){for(j=1;j<=8;j++)printf("%d",a[i][j][k]);printf("");for(j=1;j<=8;j++)printf("%d",a[9-j][i][k]);printf("");for(j=1;j<=8;j++)printf("%d",a[9-i][9-j][k]);printf("");for(j=1;j<=8;j++)printf("%d",a[j][9-i][k]);printf("");printf("\n");}printf("\n");n++;if(n%4==0)getchar();}printf(“總共％d種"，n*4);}五、電話本【問題描述】編寫一個電話薄程序，實現(xiàn)以下內(nèi)容：寫入聯(lián)系人姓名、電話、地址；查找聯(lián)系人姓名，顯示聯(lián)系人電話與地址，并給出修改或刪除選項；若不存在，則詢問是否添加該聯(lián)系人；可按人名進(jìn)行排序?！痉治雠c實現(xiàn)】菜單采用可選擇式，以判斷實現(xiàn)；添加部分：記錄聯(lián)系人個數(shù)，對下標(biāo)進(jìn)行操作；查找部分：逐一尋找，用strcmp函數(shù)進(jìn)行對比；顯示結(jié)果后繼續(xù)給出修改或刪除選項，刪除采用用無意義字符覆蓋人名的方法實現(xiàn)；排序部分：直接對人名字符串?dāng)?shù)組進(jìn)行冒泡排序(從小到大)。【代碼(C++)】#include<iostream>#include<string.h>usingnamespacestd;classphonenum{charname[20]，num[5][15]，adds[50];public:voidadd(){intj;cout<<"name:";cin>>name;cout<<"number:";for(j=0;j<5;j++)cin>>num[j];cout<<"address:";cin>>adds;}voidedit(){add();}voiddel(charnadel[]){strcpy(name,nadel);}intser(charna[]){if(strcmp(na,name)==0)return1;elsereturn0;}voidprint(){inti;cout<<"name:"<<name<<endl;for(i=0;i<5;i++)cout<<"phonenumber"<<i<<':'<<num[i]<<endl;cout<<"address:"<<adds<<endl;}voidcover(phonenumph){strcpy(name,ph.name);inti;for(i=0;i<5;i++)strcpy(num[i],ph.num[i]);strcpy(adds,ph.adds);}friendvoidswap(phonenumph1,phonenumph2);friendintcmp(phonenumph1,phonenumph2);};voidmain_menu(){cout<<"(A)dd(S)erch(C)ompose(E)xit)"<<endl;}voidswap(phonenum*ph1,phonenum*ph2){phonenumtemp;temp.cover(*ph1);ph1->cover(*ph2);ph2->cover(temp);}intcmp(phonenumph1,phonenumph2)if(strcmp(ph1.name,ph2.name)>0)return1;elsereturn0;}intmain(){phonenumph[100];intcal=0,i,j;charcho,na[20],nadel[20]={'*','/0'};for(;;){main_menu();cin>>cho;if(cho=='a'){for(i=0;i<cal;i++){if(ph[i].ser(nadel)==1){ph[i].add();break;}}if(i==cal){ph[cal].add();cal++;}}elseif(cho=='s'){cout<<"Pleaseputinthename:";cin>>na;for(i=0;i<cal;i++){if(ph[i].ser(na)==1)break;}if(i==cal){cout<<"NotFound!Wouldyoulikeaddthisperson?\n";cout<<"(Y)es(N)o";cin>>cho;if(cho=='y'){ph[cal].add();cal++;}}else{ph[i].print();cout<<"Wouldyoulikeeditordeletethismessage?"<<endl;cout<<"(E)dit(D)elete(N)either";cin>>cho;if(cho=='e')ph[i].edit();elseif(cho=='d')ph[i].del(nadel);}}elseif(cho=='c'){for(i=0;i<cal;i++){for(j=i;j<cal-i-1;j++){if(cmp(ph[j],ph[j+1])==1)swap(&ph[j],&ph[j+1]);}}for(i=0;i<cal;i++){if(ph[i].ser(nadel)==1)continue;ph[i].print();}}elseif(cho=='e')return0;}}六、大數(shù)加減法【問題描述】在計算機(jī)中，某些數(shù)據(jù)類型范圍較小，無法實現(xiàn)大數(shù)的運(yùn)算，今需要一個能進(jìn)行大數(shù)加減法的程序解決問題?！痉治雠c實現(xiàn)】用字符串讀取大數(shù)，并用類似豎式的方法實現(xiàn)大數(shù)運(yùn)算。【代碼(C)】加法：#include<stdio.h>#include<string.h>#defineLEN30intmain(){charj[LEN];charb[LEN];charsum[LEN+1];inti,longer,temp=0;voidduiqi(char*,char*);memset(sum,'0',sizeof(sum));scanf("%s",j);scanf("%s",b);if(strlen(j)>strlen(b))duiqi(j,b);elseduiqi(b,j);longer=(strlen(j)>strlen(b)?strlen(j):strlen(b));for(i=longer-1;i>=0;i--){sum[i+1]+=(j[i]-'0')+(b[i]-'0');if(sum[i+1]>=58){sum[i+1]-=10;sum[i]='1';}}for(i=0;i<longer+1;i++){if(sum[i]!='0'||i!=0)printf("%c",sum[i]);}printf("\n");return0;}voidduiqi(char*longA,char*shortA){inti;intlenOflong,lenOfshort;lenOflong=strlen(longA);lenOfshort=strlen(shortA);for(i=0;i<lenOfshort;i++){shortA[lenOflong-i-1]=shortA[lenOfshort-1-i];}shortA[lenOflong]='\0';for(i=0;i<lenOflong-lenOfshort;i++){shortA[lenOflong-lenOfshort-i-1]='0';}/*printf("%s\n",longA);printf("%s\n",shortA);*/}減法：#include<stdio.h>#include<string.h>#defineLEN50intmain(){charj[LEN],b[LEN];inti;voidduiqi(char*,char*);voidjian(char*,char*);freopen("t","r",stdin);scanf("%s",j);scanf("%s",b);if(strlen(j)>=strlen(b)){duiqi(j,b);jian(j,b);}else{duiqi(b,j);printf("-");jian(b,j);}return0;}voidduiqi(char*longa,char*shorta){inti;intlenoflong,lenofshort;lenoflong=strlen(longa);lenofshort=strlen(shorta);for(i=0;i<lenofshort;i++){//printf("%d%d\n",strlen(shorta),lenoflong);shorta[lenoflong-i-1]=shorta[lenofshort-1-i];}shorta[lenoflong]='\0';longa[lenoflong]='\0';for(i=0;i<lenoflong-lenofshort;i++){shorta[lenoflong-lenofshort-i-1]='0';}printf("%s\n",longa);printf("%s\n",shorta);//printf("%d%d%s\n",lenofshort,strlen(shorta),shorta);}voidjian(char*j,char*b){intlonger,i,temp=0;shortjiewei=0;charsub[LEN+1];memset(sub,'0',sizeof(sub)-1);sub[LEN-1]='\0';//printf("%d%dsub=%s\n",strlen(sub),sizeof(sub),sub);longer=strlen(j)>strlen(b)?strlen(j):strlen(b);for(i=longer-1;i>=0;i--){if(jiewei==1)temp=j[i]-b[i]-1;elsetemp=j[i]-b[i];if(temp<0){/*if(i>longer-3)printf("s[%d]=%c%d\n",i,sub[i],sub[i]);*/sub[i]+=(temp+10);jiewei=1;}else{sub[i]+=temp;jiewei=0;/* if(sub[i]<48||sub[i]>57)printf("temp=%dsub[%d]=%c%d\n",temp,i,sub[i],sub[i]);*//* printf("temp=%dsub[%d]=%c\n",temp,i,sub[i]);*/}for(i=0;i<longer;i++){if(sub[i]!='0'||i!=0)printf("%c",sub[i]);}printf("\n");}七、撲克牌發(fā)牌模擬【問題說明】模擬正常發(fā)牌的隨機(jī)過程?！痉治雠c說明】主要是隨機(jī)數(shù)實現(xiàn)?！敬a(C++)】#include<iostream>#include<cstdlib>#include<ctime>#include<cmath>usingnamespacestd;intrand_0toN1(intn);voiddraw_a_card();intselect_next_available(intn);char*suits[4]={"hearts","diamonds","spades","clubs"};char. 1 I-Q"I 1 q q? 1*ranks[13]={"ace","two","three","four","five","six","seven","eight",11 1 ? "night","ten","jack","queen","king"};boolcard_drawn[52];intcards_remaining=52;intmain(){intn,i;srand(time(NULL));while(true){cout<<"Enterno.ofcardstodraw";cout<<"(0toexit):";cin>>n;if(n==0)cout<<n<<endl;break;}for(i=1;i<=n;i++)draw_a_card();}return0;}voiddraw_a_card(){intr;ints;intcard,n;if(cards_remaining==0){cout<<"Reshufing."<<endl;cards_remaining=52;for(inti=0;i<52;i++)card_drawn[i]=false;}n=rand_0toN1(cards_remaining--);card=select_next_available(n);r=card%13;s=card/13;cout<<ranks[r]<<"of"<<suits[s]<<endl;}intselect_next_available(intn){inti=0;while(card_drawn[i]){i++;}while(n-->0){i++;while(card_drawn[i])i++;}card_drawn[i]=true;returni;intrand_0toN1(intn){returnrand()%n;}八、馬踏棋盤【問題說明】國際象棋的棋盤為8*8的方格棋盤。現(xiàn)將"馬"放在任意指定的方格中，按照"馬"走棋的規(guī)則將"馬"進(jìn)行移動。要求每個方格只能進(jìn)入一次，最終使得"馬"走遍棋盤的64個方格。【分析與實現(xiàn)】有兩種解決：第一種深度優(yōu)先搜索的方法是比較常用的算法，主要是采用遞歸的思想，一級一級的尋找，最后找到合適的解。第二種貪婪算法則是依據(jù)貪婪算法的思想設(shè)置一種標(biāo)準(zhǔn)，然后依據(jù)標(biāo)準(zhǔn)進(jìn)行選擇，從而得到解，但是不一定能夠得到最優(yōu)解。【代碼】1.深度優(yōu)先搜索#include<stdio.h>#include<stdlib.h>#include<time.h>#defineROWS 8#defineCOLS 8intchess[ROWS][COLS];/*eightdirectionsofxmoved*/constintx_move[]={-2,-1,1,2,2,1,-1,-2};/*eightdirectionsofymoved*/constinty_move[]={1,2,2,1,-1,-2,-2,-1};voidprint_matrix(){inti=0,j=0;for(i=0;i<ROWS;++i){for(j=0;j<COLS;++j){printf("%d\t",chess[i][j]);}printf("\n\n\n");}}/*findthenextpoint*/intnextxy(int*x,int*y,intcount)if(count>7&&count<0)return-1;switch(count){case0:/*checktheconditions*/if(*x+x_move[0]<ROWS&&*x+x_move[0]>=0&&*y+y_move[0]<COLS&&*y+y_move[0]>=0&&chess[*x+x_move[0]][*y+y_move[0]]==0){*x+=x_move[0];*y+=y_move[0];break;}else/*failed*/return0;case1:if(*x+x_move[1]<ROWS&&*x+x_move[1]>=0&&*y+y_move[1]<COLS&&*y+y_move[1]>=0&&chess[*x+x_move[1]][*y+y_move[1]]==0){*x+=x_move[1];*y+=y_move[1];break;}elsereturn0;case2:if(*x+x_move[2]<ROWS&&*x+x_move[2]>=0&&*y+y_move[2]<COLS&&*y+y_move[2]>=0&&chess[*x+x_move[2]][*y+y_move[2]]==0){*x+=x_move[2];*y+=y_move[2];break;}elsereturn0;case3:if(*x+x_move[3]<ROWS&&*x+x_move[3]>=0&&*y+y_move[3]<COLS&&*y+y_move[3]>=0&&chess[*x+x_move[3]][*y+y_move[3]]==0){*x+=x_move[3];*y+=y_move[3];break;}elsereturn0;case4:if(*x+x_move[4]<ROWS&&*x+x_move[4]>=0&&*y+y_move[4]<COLS&&*y+y_move[4]>=0&&chess[*x+x_move[4]][*y+y_move[4]]==0){*x+=x_move[4];*y+=y_move[4];break;}elsereturn0;case5:if(*x+x_move[5]<ROWS&&*x+x_move[5]>=0&&*y+y_move[5]<COLS&&*y+y_move[5]>=0&&chess[*x+x_move[5]][*y+y_move[5]]==0){*x+=x_move[5];*y+=y_move[5];break;}elsereturn0;case6:if(*x+x_move[6]<ROWS&&*x+x_move[6]>=0&&*y+y_move[6]<COLS&&*y+y_move[6]>=0&&chess[*x+x_move[6]][*y+y_move[6]]==0){*x+=x_move[6];*y+=y_move[6];break;}elsereturn0;case7:if(*x+x_move[7]<ROWS&&*x+x_move[7]>=0&&*y+y_move[7]<COLS&&*y+y_move[7]>=0&&chess[*x+x_move[7]][*y+y_move[7]]==0){*x+=x_move[7];*y+=y_move[7];break;}elsereturn0;default:return0;}return1;}intdeepsearch(intx,inty,intj){/*savethevaluex,y*/intx1=x,y1=y;inttag=0,i=0;/*savejonchess[x][y]*/chess[x][y]=j;/*recursionexitcondition*/if(j==COLS*ROWS){return1;}/*findthenextpointineightdirections*/tag=nextxy(&x1,&y1,i);/*findthenextx,nexty*/while(tag==0&&i<7){i++;tag=nextxy(&x1,&y1,i);}/*thenextxybefound*/while(tag){if(deepsearch(x1,y1,j+1))return1;/*iffailed,anewfindingprocess*/x1=x;y1=y;i++;tag=nextxy(&x1,&y1,i);while(tag==0&&i<7){i++;tag=nextxy(&x1,&y1,i);}}/*nodirectioncanfindnextpoint*/if(tag==0)chess[x][y]=0;return0;}voidmain(){clock_tstart=clock();deepsearch(2,0,1);print_matrix();intseconds=(clock()-start)/CLOCKS_PER_SEC;printf("\n%d\n",seconds);return;}2.貪婪算法2.貪婪算法#include<stdio.h>#include<stdlib.h>#include<math.h>#defineROWS 8#defineCOLS 8/*axisimovematrix*/constintiktmove[8]={-2,-1,1,2,2,1,-1,-2};/*axisjmovematrix*/constintjktmove[8]={1,2,2,1,-1,-2,-2,-1};intboard[ROWS][COLS];/*initalthematrix*/voidmatrix_init(intmatrix[][COLS],introws,intcols){inti,j;for(i=0;i<rows;++i)for(j=0;j<cols;++j){matrix[i][j]=0;}}/*printthematrix*/voidprint_matrix(intmatrix[][COLS],introws,intcols){inti,j;for(i=0;i<rows;++i){for(j=0;j<cols;++j)printf("%d\t",matrix[i][j]);printf("\n\n\n");}}/*findtheindexofminnon-zerospositive*/intminindex_in_matrix(inta[],intcols){inti=0,index=0;intmin=a[0];for(i=0;i<cols;++i){if(a[i]>0){min=a[i];index=i;break;}}for(i=index+1;i<cols;++i)if(a[i]>0&&min>a[i]){min=a[i];index=i;}}if(a[index]>0)returnindex;return-1;}intmaxindex_in_matrix(inta[],intcols){inti=0,index;intmax;for(i=0;i<cols;++i){if(a[i]>0){max=a[i];index=i;break;}}for(i=index+1;i<cols;++i){if(a[i]>0&&max<a[i]){max=a[i];index=i;}}if(a[index]>0)returnindex;return-1;}/**/rows,intcols,intvoidwarnsdorff_role(intmatrix[][COLS],start_i,intstart_j)rows,intcols,int{inti,npos,m,min,j,nnpos;intnexti[8]={0,0,0,0,0,0,0,0};int