算法設計與分析習題(3~5)

算法設計與分析(第二版)習題答案(第三章)

2010年06月15日星期二下午03:51

算法設計與分析(第二版)

主編：呂國英

習題答案

第三章：

1.

#include<stdlib.h>

#include<stdio.h>

intmain(intargc,char**argv)

(

intn;

inti,j,k;

int*buf;

printf("請輸入n的數(shù)值：”)；

scanf("%d",&n);

buf=(int*)malloc(n*sizeof(int));

for(i=0;i<n;i++)

[

buf[i]=2;

for(i=n-2;i>=0;i一)

for(j=i;j>=0;j—)

buf[j]+=2;

)

)

for(k=0;k<=n-2;k++)

{

if(buf[k]>=10)

(

buf[k+l]+=buf[k]/10;

buf[k]%=10;

}

)

for(i=n-l;i>=0;i一)

printfbuf[i]);

printf(〃\n〃);

return0;

)

2.

#include<stdio.h>

intmain(intargc,char**argv)

intbuf[6][6];

inti,j;

printf("任意輸入6個數(shù)字:");

for(i=0;i<6;i++)

scanf("%d”,&buf[0][i]);

for(i=0;i<5;i++)

{

for(j=0;j<5;j++)

(

buf[i+1][j+l]=buf[i][j];

}

buf[i+1][0]=buf[i][j];

)

for(i=0;i<6;i++)

]

for(j=0;j<6;j++)

printf("%d”,buf[i][j]);

printf(〃\n");

return0;

3.

#include<stdio.h>

ttdefineN7

intmain(intargc,char**argv)

intbuf[N][N];

inti,j,k,m,n;

inta=0,b=NT;

intcount=l;

for(i=0;i<(N/2)+(N%2);i++)

(

for(j=a;j<=b;j++)

(

buf[a][j]=count++;

)

for(k=a+l;k<=b;k++)

(

buf[k][b]=count++;

}

for(m=b-l;m>=a;m一)

buf[b][m]=count++;

for(n=b-l;n>a;n一)

buf[n][a]=count++;

)

a++;

b一;

)

for(i=0;i<N;i++)

(

for(j=0;j<N;j++)

printf("%5d”,buf[i][j]);

printf('\n");

)

return0;

)

4.

#include<stdio.h>

#defineN5

intmain(intargc,char**argv)

intbuf[N][N];

inti,j,k;

intcounts1;

intn=0;

for(i=0;i<N;i++)

for(k=0,j=n;j>=0;j—,k++)

buf[j][k]=count++;

n++;

)

for(i=0;i<N;i++)

(

for(j=0;j<N-i;j++)

printf("%5d”,buf[i][j]);

printf(〃\n〃);

}

return0;

)

5.

#include<stdio.h>

#defineN5

intmain(intargc,char**argv)

intbuf[N][N];

inti,j;

inta=0,b=NT;

intcount=l;

for(i=0;i<N/2+N%2;i++)

for(j=a;j<=b;j++)

buf[a][j]=count;

for(j=a+l;j〈=b;j++)

buf[j][b]=count;

for(j=b-l;j>=a;j—)

buf[b][j]=count;

for(j=b-l;j>a;j—)

buf[j][a]=count;

count++；

a++;

b一;

)

for(i=0;i<N;i++)

for(j=0;j<N;j++)

，/，，

printf(%5d,buf[i][j]);

printf('\n");

return0;

}

6.

#include<stdio.h>

#include<stdlib.h>

typedefstructsnodeslist;

typedefslist*link;

structs_node

(

charch;

intflag;

linknext;

}；

linktop;

voidpush(charch,intflag)

(

linknewnode;

newnode=(link)malloc(sizeof(s_list));

newnode->ch=ch;

newnode->flag=flag;

newnode->next=NULL;

if(top==NULL)

(

top=newnode;

)

else

{

newnode->next=top;

top=newnode;

)

)

intpop()

[

intflag;

linkstack;

if(top!=NULL)

(

stack=top;

top=top->next;

f1ag=stack->flag;

free(stack);

returnflag;

intop(charch)

(

switch(ch)

{

case'+':

return1;

break;

case'-':

return2;

break;

case'*':

return3;

break;

case'/':

return4;

break;

default:

return5;

voidnirnava(char*buf,intcount)〃count個數(shù)，buf數(shù)組

intbool=l;

intmin;

intj;

inti;

intk;

intflag;

for(i=0;i<count;i++)

{

if(buf[i]=-(*)

push(buf[i],i);

if(buf[i]=-),)

[

flag=pop();

if(flag!=0)

(

if((buf[flag-l]—'(')&&(buf[i+l]==')’))

{

buf[flag]=，!';

buf[i]='!';

min=op(buf[flag]);

for(j=flag+l;j<i;j++)

if(buf[j]=，(')

(

push(buf[j],j);

bool=0;

continue;

)

else

if(buf[j]==')’)

{

pop();

bool=l;

continue;

)

if(bool==l)

{

if(min>op(buf[j]))

min=op(buf[j]);

if(i<count-l)

if((buf[i+l]=='+')||(buf[i+l]=='-'))

(

if(flag==O)

(

buf[i]='!';

buf[flag];

)

else

if(op(buf[flag-1])<=min)

(

buf[i]='!';

buf[flag]='!';

}

}

else

if((buf[i+l]=-*')||(buf[i+l]==，/'))

if(flag-O)

buf[i]='!';

buf[flag]='!';

)

else

if((min>=op(buf[i+l])&&op(buf[flag-1])<=min))

{

buf[i]='!';

buf[flag];

)

)

)

else

if(i==count-l)

{

if(flag-0)

{

buf[i]='!';

buf[flag]='!';

)

else

if(op(buf[flag-1])<=min)

buf[i]='!';

buf[flag]=>!

for(k=0;k<count;k++)

{

if(buf[k]!='!')

printfbuf[k]);

)

printf('\n");

)

intmain(void)

(

charbuf[255];

inti;

for(i=0;i<255;i++)

(

scanf("%c”,&buf[i]);

if(buf[i]=='\n)

break;

buf[i]='\0’;

nirnava(buf,i);

return0;

)

7.

#include<stdio.h>

#include<stdlib.h>

intack(intm,intn);

intcount=0;

intmain(intargc,char**argv)

(

intm,n;

scanf("%d%d”,&m,&n);

printf("%d\n”,ack(m,n));

printf("%d\n",count);

return0;

)

intack(intm,intn)

(

count++;

if(m==0)

returnn+1;

else

if(n==0)

returnack(m-l,1);

else

returnack(m-l,ack(m,n-1));

)

8.

#include<stdio.h>

charbuf[1024];

intis_huiwen(inta,intcount)

(

if(a==count/2)

(

return1;

)

else

if(buf[a]==buf[count-a-1])

return(is_huiwen(a-l,count))&&1;

else

return0;

intmain(void)

intcount;

inti;

for(i=0;i<1024;i++)

{

scanf("%c”,&buf[i]);

if(buf[i]==，\n')

break;

)

count=i;

i一；

printf("%d”,ishuiwen(i,count));

return0;

)

9.

#include<stdio.h>

charbuf[100];

intpos(inta,intb)

if(b-a==l)

return1;

else

if(b-a==0)

return1;

else

returnpos(a,b-l)+pos(a,b-2);

)

intmain(void)

(

inta,b;

scanf("%d%d”,&a,&b);

printfpos(a,b));

return0;

}

10.

#include<stdio.h>

#defineMAX1024

intbuf[MAX];

intmain(void)

intm,n;

inti;

scanf("%d%d”,&m,&n);

for(i=0;i<MAX;i++)

buf[i]=0;

i=0;

while(buf[i%m]==0)

{

buf;

i+=n;

)

for(i=0;i<m;i++)

{

if(buf[i]==0)

printf(z/%d”,i);

)

return0;

)

11.

#include<stdio.h>

intmain(void)

inttemp,tempi;

intcount=0;

intn;

inti;

scanf("%d",&n);

for(i=l;i〈=n;i++)

(

temp=i%10;

if(temp-5)

count++;

else

if(temp==0)

(

templ=i;

while((templ%10)==0)

(

templ=templ/10;

count++;

printfcount);

return0;

12.

#include<stdio.h>

intmain(void)

intcount=0;

intbuf[53];

inti,n;

for(i=l;i<53;i++)

{

buf[i]=l;

)

for(n=2;;n++)

(

for(i=n;i<53;i+=n)

]

buf[i]=l-buf[i];

count++;

if(count>=104)

break;

if(count>=104)

break;

for(i=l;i<53;i++)

{

if(buf[i]==l)

printf(/z%d",i);

)

printf;

return0;

)

13.

#include<stdio.h>

intmain(void)

[

inta,b,c,d,e;

for(a=l;a<=5;a++)

for(b=l;b<=5;b++)

if(a!=b)

for(c=l;c<=5;c++)

if(c!=a&&c!=b)

for(d=l;d<=5;d++)

if(d!=a&&d!=b&&d!=c)

e=15-a-b-c-d;

if(e!=a&&e!=b&&e!=c&&e!=d)

if(((b=3)+(c==5)==1)&&((d==2)+(e==4)==1)&&((b==l)+(e==

4)==1)&&((c==l)+(b==2)==1)&&((d==2)+(a==3)—1))

printf("a=%d,b=%d,c=%d,d=%d,e=%d”,a,b,c,d,e);

)

return0;

)

14.

#include<stdio.h>

intmain(void)

[

intbuf[3];

inti;

intmul;

inttemp;

for(i=10;i<=31;i++)

(

mul=i*i;

temp=mul;

buf[0]=temp%10;

temp=temp/10;

buf[l]=temp%10;

temp=temp/lO;

buf[2]=temp;

if((buf[O]==buf[1])||(buf[O]==buf[2])||(buf[l]==buf[2])

)

[

printf("，%d2=%d\n，/,i,mul);

)

)

return0;

}

15.

#include<stdio.h>

intmain(void)

]

inta,b,c;

for(a=l;a〈=3;a++)

for(b=l;b<=3;b++)

if(a!=b)

c=6-a-b;

if(c!=a&&c!=b)

if((a!=l)&&((c!=l)&&(c!=3))==l)

printf("a=%d,b=%d,c=%d”,a,b,c);

}

return0;

)

16.

#include<stdio.h>

intmain(void)

(

intk;

intn;

scanf("%d",&n);

k=(n%4==0)+(n%7==0)*2+(n%9==0)*4;

switch(k)

{

case7:

printf("all");

break;

case6:

printf(“7and9");

break;

case5:

printf(“4and9");

break;

case4:

printf(〃9");

break;

case3:

printf("4and7");

break;

case2:

printf("7");

break;

case1:

printf；

break;

case0:

printf("none");

break;

)

return0;

17.

#include<stdio.h>

intmain(void)

1

inta,b,c,d;

printf("pleasethinkofanumberbetween1and100.\n");

printf(/zyournumberdividedby3hasaremainderof");

scanf&a);

printf("yournumberdividedby4hasaremainderof");

scanf("%d",&b);

printf(z/yournumberdividedby7hasaremainderof");

scanf("%d",&c);

printf("letmethinkamoment...\n");

d=36*c+28*a+21*b;

while(d>84)

d=d-84;

printf(z/yournumberwas%d\n',d);

return0;

)

18.

#include<stdio.h>

intmain(void)

intbuf[10];

inti,j;

intmul;

inttempi,temp2;

intbool;

for(i=5000;i<=9999;i++)

{

bool=0;

for(j=0;j<10;j++)

buf[j]=0;

templ=i;

while(templ>0)

[

if((++buf[templ%10])>1)

(

bool=l;

break;

)

templ/=10;

)

if(bool-l)

continue;

mul=i*2;

temp2=mul;

while(temp2>0)

(

if((++buf[temp2%10])>l)

(

bool=l;

break;

)

temp2/=10;

)

if(bool-l)

continue;

printf("2*%d=%d\n”,i,mul);

)

return0;

)

19.

#include<stdio.h>

#include<stdlib.h>

intppow(inta,intb)

intmul=l;

inti;

for(i=0;i<b;i++)

{

mul=a*mul;

)

returnmul;

)

intmain(void)

(

intt;

charbuf[10];

inti,j,k;

intsum=0;

for(i=0;i<10;i++)

{

scanf("%c”,&buf[i]);

if(buf[i]=='\n)

break;

)

buf[i]='\0';

for(j=0;j<i;j++)

if((buf[j]>=’0')&&(buf[j]<=，9,))

buf[j]=buf[j]-48;

else

if((buf[j]>=)&&(buf[j]<=F?))

buf[j]=buf[j]-55;

else

exit(1);

)

k=0;

for(j=i-l;j>=0;j—)

{

t=ppow(16,k);

sum=sum+t*(int)buf[j];

k++;

)

printf("%d\n",sum);

return0;

)

20.

#include<stdio.h>

intmain(void)

inta;

intb;

intc;

inti;

intbuf[10];

for(a=10;a<=99;a++)

{

for(i=0;i<10;i++)

buf[i]=0;

if((++buf[a%10]>l)|(++buf[a/10%10]>D)

continue;

for(b=100;b<=999;b++)

[

for(i=0;i<10;i++)

{

if((i!=a%10)&&i!=a/10%10)

buf[i]=0;

)

if((++buf[b%10]>l)|I(++buf[b/10%10]>l)||(++buf[b/100%10]>l

))

continue;

c=a*b;

if(c<10000&ac>999)

(

if((++buf[c%10]>l)||(++buf[c/10%10]>l)||(++buf[c/100%1

0]>l)|)(++buf[c/1000%10]>l))

continue;

else

printf("%d*%d=%d\n”,a,b,c);

return0;

)

21.

#include<stdio.h>

intmain(void)

(

inta;

intb;

inti;

intt;

intbuf[10];

intbool;

for(a=317;a<1000;a++)

(

bool=0;

for(i=0;i<10;i++)

buf[i]=0;

if((++buf[a%10]>l)||(++buf[a/10%10]>l)!|(++buf[a/100%10

]>D)

continue;

b=a*a;

t=b;

for(i=0;i<6;i++)

[

if(++buf[t%10]>l)

(

bool=l;

break;

)

t=t/10;

)

if(bool-l)

continue;

printf("%(T2=%d\n”,a,b);

return0;

}

22.

#include<stdio.h>

intmain(void)

{

intbuf[100];

inti;

intn;

intmax;

inttemp;

for(i=l;i<100;i++)

{

scanf("%d”,&buf[i]);

if(buf[i]==0)

break;

)

n=i;

max=buf[l]+buf[2]+buf[3]+buf[4];

for(i=2;i%10!=l;i++)

temp=buf[i%10]+buf[(i+l)%10]+buf[(i+2)%10]+buf[(i+3)%10

];

if(temp>max)

max=temp;

)

printf(/，max=%d\n，/,max);

return0;

)

23.

#include<stdio.h>

voidnirnava(intn)

[

if(n<10)

printf(/7%d”,n);

else

(

nirnava(n/10);

printf("%d”,n%10);

intmain(void)

intcount=0;

intn;

inti;

intt;

scanf("%d",&n);

t=n;

while(t>0)

{

printfC%d”,t%10);

t=t/10;

count++;

)

printf("\n〃);

nirnava(n);

printf("\n%d位數(shù)\n”,count);

)

24.

#include<stdio.h>

intmain(void)

intbuf[4]={2,3,5,7};

inti,j,k,temp,m;

intbool;

intmul;

for(i=0;i<4;i++)

for(j=0;j<4;j++)

for(k=0;k<4;k++)

for(m=0;m<4;m++)

{

bool=0;

mul=(buf[i]+buf[j]*10+buf[k]*100)*buf[m];

if(mul<1000)

continue;

temp=mul;

while(temp>0)

{

if((temp%10==2)|(temp%10—3)|(temp%10==5)||(temp%10==7))

()

else

(

bool=l;

break;

temp/=10;

if(boo1=0)

{

printf(/z%d%d%d*%d

=%d\n，，>buf[k],buf[j],buf[i],buf[m],mul);

)

)

return0;

)

25.

#include<stdio.h>

intmain(void)

[

intbuf[4]={2,3,5,7);

inti,j,k,m,n;

intbool;

intmul,mull,mul2;

inttemp,tempi,temp2;

for(i=0;i<4;i++)

for(j=0;j<4;j++)

for(k=0;k<4;k++)

for(m=0;m<4;m++)

for(n=0;n<4;n++)

(

bool=0;

mul=(buf[i]+buf[j]*10+buf[k]*100)*(buf[m]+buf[n]*10);

mul1=(buf[i]+buf[j]*10+buf[k]*100)*buf[m];

mul2=(mul-mul1)/10;

if((mul<10000)|(mulKlOOO)|(mul2<1000))

continue;

temp=mul;

templ=mul1;

temp2=mul2;

while(temp>0)

{

if((temp%10—2)||(temp%10==3);|(temp%10==5)|(temp%10==7)

)

()

else

{

bool=l;

break;

temp/=10;

if(bool==0)

(

while(templ>0)

(

if((templ%10==2)|i(templ%10==3)||(templ%10==5)||(temp

l%10=7))

()

else

(

bool=l;

break;

)

templ/=10;

)

}

if(bool==0)

while(temp2>0)

{

if((temp2%10—2)||(temp2%10—3)||(temp2%10==5)||(temp2%

10==7))

{)

else

(

bool=l;

break;

)

temp2/=10;

)

if(bool-0)

(

printf("第一行：％d%d%d\n第二行：％d%d\n第三行：％d\n第四

行:%d\n第五

行:%d\n\n\n\n\n，/,buf[i],buf[j],buf[k],buf[m],buf[n],mull,mu

12,mul);

}

)

return0;

)

26.

#include<stdio.h>

〃從a到b是不是循環(huán)節(jié)

intis_xunhuan(int*buf,inta,intb)

inti;

if(a==b)

{

for(i=l;i<10;i++)

if(buf[a]==buf[a+i])

(}

else

return0;

)

)

else

for(i=a;i<=b;i++)

(

if(buf[i]==buf[i+b-a+1])

(}

else

return0;

return1;

intmain(void)

(

intbuf[1024];

intyushu;

intm,n;

inti,j,k;

scanf("%d%d”,&m,&n);

yushu=m;

buf[0]=0;

i=l;

while(yushu!=0)

(

yushu=yushu*10;

buf[i]=yushu/n;

yushu=yushu%n;

i++；

if(i==1024)

break;

if(i<1024)

printf("有限小數(shù)\n");

printf("%d.”,buf[0]);

for(j=l;j<i;j++)

printf('%d”,buf[j]);

printf('\n");

)

else

{

printf("循環(huán)小數(shù)\n");

for(i=l;i<100;i++)

for(j=i;j<200;j++)

(

if(is_xunhuan(buf,i,j))

{

printf("%d.",buf[0]);

if(i>l)

{

for(k=l;k<i;k++)

printf("%d”,buf[k]);

printf("(");

for(k=i;k〈=j;k++)

printf("%d”,buf[k]);

printf(")");

printf(〃\n〃);

return0;

return0;

)

27.

#include<stdio.h>

intmain(void)

[

intn;

chareng[⑵[10]={〃一月〃，〃二月〃，〃三月〃，〃四月〃，〃五月〃，〃六月〃,〃

七月〃，〃八月〃，〃九月〃，〃十月〃，〃十一月〃，〃十二月〃}；

scanf("%d",&n);

printf("%s\n",eng[n-l]);

return0;

算法設計與分析（第二版）

主編：呂國英

習題答案

第四章

1.

#include<stdio.h>

intmain(void)

{

intbuf[100];

intn;

inti,j,k;

scanf(，z%d，z,&n);

for(i=0;i<n;i++)

buf[i]=2;

for(i=0;i<n-l;i++)

(

for(j=0;j<n-i-l;j++)

(

buf[j]+=2;

)

)

for(j=0;j<n;j++)

{

if(buf[j]>=10)

(

buf[j+l]+=buf[j]/10;

buf[j]=buf[j]%10;

)

}

for(i=n-l;i>=0;i--)

printfbuf[i]);

printf(〃\n〃)；

return0;

}

2.

#include<stdio.h>

intmain(void)

intn=2;

inti;

for(i=l;i<=9;i++)

(

n=(n+2)*2;

)

printf(〃％d\n〃，n);

return0;

)

3.

#include<stdio.h>

intmain(vold)

(

inta=54;

intn;

intm;

printf("計算機先拿3張牌\n");

a=a-3;

while(a>=0)

(

printf("還剩%d張牌\n〃，a);

printf(〃你拿幾張?請輸入：〃);

scanf&n);

if(n>4||n<l||n>a)

(

printf(〃錯誤！重新拿牌\n〃)；

continue;

)

a=a-n;

prinlf(〃還剩%d張牌\n〃，a);

if(a==0)

break;

m=5-n;

printf(〃計算機拿%d\n〃,m);

a=a-m;

)

return0;

)

4.

#include<stdio.h>

intd;

intal,a2;

intfun(intn);

intmain(vold)

intn;

printf("n=？，d=？，al=?,a2=？〃);

scanfC%d%d%d%d\n",&n,&d,&al,&a2);

printf(/，%d\n，/,fun(n));

return0;

}

intfun(intn)

(

if(n==l)

returnal;

if(n==2)

returna2;

returnfun(n-2)-(fun(n'l)-d)*2;

)

5.

#include<stdio.h>

charchess[8][8];

intis_safe(introw,intcol);

intqueen(introw,intcol,intn);

intmain(void)

(

inti,j;

for(i=0;i<8;i++)

for(j=0;j<8;j++)

chessti][j]-X,;

queen(0,0,0);

for(i=0;i<8;i++)

(

for(j=0;j<8;j++)

printf(〃%c，z,chessti][j]);

printf(〃\n〃)；

)

return0;

)

intissafe(introw,intcol)

(

inti,j;

for(i=0;i<8;i++)

(

if(chess[row][i]='Q')

return0;

if(chess[i][col]==，Q?)

return0;

i=row;

j=col;

while(i!=-l&&j!=-l)

(

if(chess[i—][j—]==*Q')

return0;

)

i=row;

j=col;

whiled!=8)

(

if(chess[i―][j++]==，Q')

return0;

)

i=row;

j=col;

while(i!=8&&j!=-l)

(

if(chess[i++][j—]==,Q')

return0;

)

i=row;

j=col;

while(i!=8&&j!=8)

(

if(chess[i++][j++]==，Q')

return0;

}

return1;

)

intqueen(introw,intcol,intn)

(

inti,j;

intresult=0;

if(n==8)

return1;

else

if(is_safe(row,col))

(

chess[row][col]=，Q,;

for(i=0;i<8;i++)

for(j=0;j<8;j++)

result+=queen(i,j,n+1);

if(result>0)

break;

)

if(result>0)

return1;

else

(

chess[row][col]=，X';

return0;

)

)

else

return0;

}

6.

#include<stdio.h>

intmain(void)

(

inti,j,k;

for(i=l;i<=33;i++)

for(j=l;j<=50;j++)

(

k=100-i-j;

if(k%2==0)

(

if(3*i+2*j+k/2==100)

printf("大馬%d\n中馬%d\n小馬％d\n\n\n”,i,j,k);

}

}

return0;

)

7.

#include<stdio.h>

intmain(void)

(

inti;

for(i=l;i<=10000;i++)

(

if(i%2=1&&i%3==2&&i%5==4&&i%6==5&&i%7==0)

printf("%d\n",i);

)

return0;

8.

#include<stdio.h>

intmain(void)

{

inti;

intsum;

intal,a2,a3,a4;

for(i=1000;i<=9999;i++)

(

al=i%10;

a2=i/10%10;

if(al!=a2)

(

a3=i/100%10;

if(al!=a3&&a2!=a3)

(

a4=i/1000;

if(al!=a4&&a2!=a4&&a3!=a4)

(

sum=(al+a2+a3+a4)*(al+a2+a3+a4);

if(i%sum=0)

printf(〃%d\n〃，i);

)

)

)

)

return0;

}

9.

#include<stdio.h>

#defineN10

voidmax_min(int*a,intm,intn,int*minl,int*min2,int*maxl,int*max2);

intmain(void)

{

inta[N]={2,3,4,5,34,7,9,6,43,21);

intmini,min2;

intmaxi,max2;

max_min(a,0,N-l,&minl,&min2,&maxl,&max2);

printf(/zminl=%d\nmin2=%d\nmaxl=%d\nmax2=%d\n，/,mini,min2,maxi,max2);

return0;

)

voidmax_min(int*a,intm,intn,int*minl,int*min2,int*maxl,int*max2)

intIminl,lmin2,Imaxl,lmax2;

intrminl,rmin2,rmaxl,rmax2;

intmid;

if(m==n)

*minl=*min2=*maxi=*max2=a[m];

)

else

if(m==n-l)

(

if(a[m]<a[n])

(

*minl=a[m];

*min2=a[n];

*maxl=a[n];

*max2=a[m];

)

else

(

*minl=a[n];

*min2=a[m];

*maxl=a[m];

*max2=a[n];

)

)

else

(

mid=(m+n)/2;

maxmin(a,m,mid,&lmin2,&lmaxl,&Imax2);

max_min(a,mid+1,n,ftrminl,&rmin2,&rmaxl,&rmax2);

if(IminKrminl)

(

if(lmin2<rminl)

(

*minl=lminl;

*min2=lmin2;

)

else

(

*minl=lminl;

*min2=rminl;

)

)

else

if(rmin2<lminl)

*minl=rminl;

*min2=rmin2;

)

else

(

*minl=rminl;

*min2=lminl;

}

if(lmaxl>rmaxl)

(

if(lmax2>rmaxl)

(

*maxl=lmaxl;

*max2=lmax2;

)

else

(

*maxl=lmaxl;

*max2=rmaxl;

)

)

else

if(rmax2>lmaxl)

(

*maxl=rmaxl;

*max2=rmax2;

}

else

(

*maxl=rmaxl;

*max2=lmaxl;

}

)

)

10.

#include<stdio.h>

intadd(int*a,intflag,intright);

intmain(void)

(

inta[10]={l,2,3,4,5,6,7,8,9,10};

intsum=add(a,0,9);

printf(〃%d\n〃,sum);

return0;

)

intadd(int*a,intflag,intright)

(

intmid;

if(flag==right)

(

returna[flag];

}

else

if(flag==right-l)

(

returna[flag]+a[right];

}

else

(

mid=(flag+right)/2;

returnadd(a,flag,mid)+add(a,mid+1,right);

}

}

11.

#include<stdio.h>

intmain(void)

{

inta[5][3]={

{-50,17,-42),

{-47,-19,-3),

{36,-34,-43},

{-30,-43,34),

{-23,-8,-45}

}；

inti,j;

intmax,n;

intsum=0;

for(i=0;i<5;i++)

(

max=a[i][0];

n=0;

for(j=l;j<3;j++)

(

if(a[i][j]>max)

{

max=a[i][j];

n=j;

}

)

sum+=max;

printfCa[%d][%d]=%d\n/z,i,n,max);

)

printf(〃%d\n〃,sum);

return0;

)

12.

/*

*File:newmain.c

*Author:nirnava

*

*Createdon2010年4月22凡下午5:21

*/

#include<stdio.h>

#include<stdlib.h>

/defineN4

voidmatrix_mul(intint*mul2,int*mul3,intlength);

voidmatrix_add_sub(int*A,int*B,int*C,intm,charch);

voidupdate_ha1f_value(int*A,int*B,intm);

voidget_half_value(int*A,int*B,intm);

intmain(void)

(

inti,j;

intmull[N*N]={l,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6};

intmul2[N*N]={7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2};

intmu13[N*N];

matrix_mul(mull,mul2,mu13,N);

for(i=0;i<N*N;i++)

{

printf("%5d”,mul3[i]);

if((i+l)%N==0)

printf(〃\n〃)；

)

return0;

)

voidmatrix_add_sub(int*A,int*B,int*C,intm,charch)

(

inti;

for(i=0;i++)

(

if(ch='+')

C[i]=A[i]+B[i];

else

C[i]=A[i]-B[i];

voidupdate_half_value(int*A,int*B,intm)

{

inti,j;

for(i=0;i<m/2;i++)

(

for(j=0;j<m/2;j++)

{

B[i*m+j]=A[i*m/2+j];

)

}

)

voidgethalfvalue(int*A,int*B,intm)

(

inti,j;

for(i=0;i<m/2;i++)

(

for(j=0;j<m/2;j++)

(

A[i*m/2+j]=B[i*m+j];

}

)

}

voidmatrix_mul(int*A,int*B,int*C,intm)

{

if(m==2)

(

intD.E.F,G,H,I,J;

D=A[0]*(B[l]-B[3]);

E=A[3]*(B[2]-B[0]);

F=(A[2]+A[3])*B[0];

G=(A[0]+A[l])*B[3];

H=(A[2]-A[0])*(B[0]+B[l]);

I=(A[1]-A[3])*(B[2]+B[3]);

J=(A[0]+A[3])*(B[0]+B[3]);

C[O]=E+I+J-G;

C[1]=D+G;

C[2]=E+F;

C[3]=D+H+J-F;

return;

)

else

intA1,A2[m*m/4],A3,A4[m*m/4];

intBl[m*m/4],B2[m*m/4],B3[m*m/4],B4[m*m/4];

intCl,C2,C3,C4[m*m/4];

intD[m*m/4],E[m*m/4],F[m*m/4],G,I,J[m*m/4];

inttempitemp2[m*m/4];

get_half_value(Al,&A[O],m);

get_half_value(A2,&A[m/2],m);

gethalfvalue(A3,&A,m);

get_half_value(A4,&A,m);

get_half_value(Bl,&B[0],m);

get_half_value(B2,m);

get_half_value(B3,&B,m);

get_half_value(B4,&B[m*m/2+m/2],m);

matrixaddsub(B2,B4,tempi,m/2,'」)；

matrix_mul(Al,tempi,D,m/2);

matrixaddsub(B3,Bl,tempi,m/2,'」)；

matrix_mul(A4,tempi,E,m/2);

matrix_add_sub(A3,A4,tempi,m/2,';

matrixmul(tempi,Bl,F,m/2);

matrixaddsub(Al,A2,tempi,m/2,';

matrixmul(tempi,B4,G,m/2);

matrixaddsub(A3,Al,tempi,m/2,'」)；

matrix_add_sub(Bl,B2,temp2,m/2,';

matrix_mul(tempi,temp2,H,m/2);

matrix_add_sub(A2,A4,tempi,m/2,1-);

matrix_add_sub(B3,B4,temp2,m/2,';

matrixmul(tempi,temp2,I,m/2);

matrix_add_sub(Al,A4,tempi,m/2,';

matrix_add_sub(Bl,B4,temp2,m/2,';

matrix_mul(tempi,temp2,J,m/2);

matrix_add_sub(E,I,tempi,m/2,';

matrix_add_sub(J,G,temp2,m/2,',)；

matrix_add_sub(tempi,temp2,Cl,m/2,';

matrixaddsub(D,G,C2,m/2,';

matrix_add_sub(E,F,C3,m/2,';

matrix_add_sub(D,H,tempi,m/2,';

matrix_add_sub(J,F,temp2,m/2,'」)；

matrixaddsub(tempi,temp2,C4,m/2,';

updatehalfvalue(Cl,&C[0],m);

updatehalfvalue(C2,&C[m/2],m);

update_half_value(C3,&C,m);

update_half_va1ue(C4,&C[m*m/2+m/2],m);

return;

}

13.

#include<stdio.h>

intmain(void)

(

inta[6][7]={

{16,4,3,12,6,0,3},

{4,-5,6,7,0,0,2},

{6,0,-1,-2,3,6,81,

{5,3,4,0,0,-2,7},

{-1,7,4,0,7,-5,6},

{0,-1,3,4,12,4,2}

}；

intb[6][7],c[6][7];

inti,j,k;

intmax;

intflag;

inttemp;

for(i=0;i<6;i++)

for(j=0;j<7;j++)

{

b[i][j]=a[i][j]：

c[i][j]=-l;

}

for(i=l;i<5;i++)

(

for(j=0;j<7;j++)

(

max=0;

for(k=j-2;k<=j+2;k++)

(

if(k<0)

continue;

else

if(k>6)

break;

else

{

if(b[i][j]+b[i-l][k]>max)

max=b[i][j]+b[i-l][k];

flag=k;

)

}

}

b[i][j]=max;

c[i][j]=flag;

}

)

for(j=l;j<=5;j++)

(

max=O;

for(k=j-2;k<=j+2;k++)

(

if(k<0)

continue;

else

if(k>6)

break;

else

(

if(b[i][j]+b[i-l][k]>max)

(

max=b[i][j]+b[i-l][k];

flag=k;

)

)

)

b[i][j]=max;

c[i][j>flag;

)

max=0;

for(j=l;j<=5;j++)

(

if(b[i][j]>max)

{

max=b[i][j];

flag=j;

}

)

printf(繪d\n〃,max);

temp=c[i][flag];

printf(〃%5d〃,a[i][temp]);

for(j=i;j>0;j—)

temp=c[j][temp];

printf(〃％5d",a[j-l][temp]);

)

printf(z，\nz/);

return0;

}

14.

#include<stdio.h>

intmain(void)

(

intA[6]={0,3,7,9,12,13);

intB[6]={0,5,10,11,11,11);

intC[6]={0,4,6,11,12,12);

intAB[6][6];

inttemp[6];

intabc[6];

intmax;

intflag;

inti,j,k;

for(i=0;i<=5;i++)

(

max=0;

for(j=0;j<=i;j++)

(

if(AB[i][j]>max)

max=AB[i][j];

}

temp[i]=max;

)

max=0;

for(i=0;i<=