returnsearch(left,mid-1,mask,a);
if(mask>a[mid])
returnsearch(mid+1,right,mask,a);
if(mask==a[mid])return1;
}
elsereturn0;
}
voidmain()
{
intn,i,k,m,r=0;
inta[10000];intmask[50000];
scanf("%d\n",&n);
for(i=0;iscanf("%d",&a[i]);
scanf("%d",&m);
for(k=0;kscanf("%d",&mask[k]);
for(r=0;r{
if(search(0,n-1,mask[r],a))printf("Yes\n");
elseprintf("No\n");
}
}
归并排序
#include
intb[10000];
voidCombine(int*a,int*b,intleft,intmid,intright)
{
inti=0,j,k,M;
intt=left;
M=mid+1;
while(left<=mid&&M<=right)
{
if(a[left]<=a[M])
b[i++]=a[left++];
elseb[i++]=a[M++];
if(left>mid)
{
for(j=M;j<=right;j++)
b[i++]=a[j];
}
if(M>right)
{
for(j=left;j<=mid;j++)
b[i++]=a[j];
}
}
for(k=0;k
a[t+k]=b[k];
}
voidMsort(int*a,intleft,intright)
{
intmid;
if(left{
mid=(left+right)/2;
Msort(a,left,mid);
Msort(a,mid+1,right);
Combine(a,b,left,mid,right);
}
}
voidmain()
{
intn,a[10000],i;
scanf("%d",&n);
for(i=0;iscanf("%d",&a[i]);
Msort(a,0,n-1);
for(i=0;iprintf("%d\n",b[i]);
}
快速排序
#include
inta[10000];
intsqort(intr,intp)
{
inti=r+1,j=p;
inttemp;
while(i<=j)
{
while(a[i]<=a[r])
i++;
while(a[j]>a[r])
j--;
if(itemp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[j];
a[j]=a[r];
a[r]=temp;
returnj;
}
voidquiksqort(intr,intp)
{
if(r
{
intq=sqort(r,p);
quiksqort(r,q-1);
quiksqort(q+1,p);
}
}
intmain()
{
intn,i,j;
scanf("%d",&n);
for(i=0;iscanf("%d",&a[i]);
quiksqort(0,n-1);
for(j=0;jprintf("%d\n",a[j]);
}
穷举n位二进制数
#include
#include
#include
interjinzhi(intn);
intmain()
{
intn;
scanf("%d",&n);
erjinzhi(n);
return0;
}
interjinzhi(intn)
{
int*a;
a=(int*)malloc(n*sizeof(int));
inti;
intj;
ints=0;
for(i=0;i{
a[i]=0;
printf("%d",a[i]);
}
printf("\n");
for(i=0;i{
s=s+a[i];
}
for(;s{
s=0;
a[n-1]=a[n-1]+1;
if(a[n-1]==1||a[n-1]==0)
{
for(i=0;iprintf("%d",a[i]);
printf("\n");
for(i=0;i{
s=s+a[i];
}
}
else
{
for(j=0;j{
if(a[n-1-j]==1||a[n-1-j]==0)
break;
else
{
a[n-1-j]=0;
a[n-1-j-1]=a[n-1-j-1]+1;
}
}
for(i=0;iprintf("%d",a[i]);
printf("\n");
for(i=0;i{
s=s+a[i];
}
}
}
return0;
}
穷举所有排列
#include
voidsearch(chara[],intm,intn)
{
inti;
chartemp;
if(m==n)
{
for(i=0;i{
printf("%c",a[i]);
}
printf("\n");
}
else
{
for(i=m;i{
temp=a[i];
a[i]=a[m];
a[m]=temp;
search(a,m+1,n);
temp=a[i];
a[i]=a[m];
a[m]=temp;
}
}
}
intmain()
{
inti;
intn;
chara[20];
scanf("%d",&n);
for(i=0;i{
a[i]='a'+i;
}
search(a,0,n);
return0;
}
01背包问题
#include
inta[11],b[11],w[11],n,c,best_value;
voidSesearch(intm,intr_v,intcw,intcv)
{
inti=0;
if(m>=n)
{
if(cv>best_value&&cw<=c)
best_value=cv;
}
else
{
a[m]=1;
if(cw+w[m]<=c)
Sesearch(m+1,r_v-b[m+1],cw+w[m],cv+b[m]);
a[m]=0;
if(cv+r_v>=best_value)
Sesearch(m+1,r_v-b[m+1],cw,cv);
}
}
voidmain()
{
inttemp_c,i,total_weight,num,j=0,result[1000],total_value;
scanf("%d%d",&num,&temp_c);
while(num!
=0||temp_c!
=0)
{
total_value=0;
total_weight=0;
for(i=0;i<=10;++i)
{
a[i]=0;
b[i]=0;
w[i]=0;
}
c=temp_c;
n=num;
for(i=0;i{
scanf("%d",&w[i]);
total_weight+=w[i];
}
for(i=0;i{
scanf("%d",&b[i]);
total_value+=b[i];
}
if(total_weight<=c)
result[j]=total_value;
else
{
best_value=0;
Sesearch(0,total_value-b[0],0,0);
result[j]=best_value;
}
scanf("%d%d",&num,&temp_c);
++j;
}
for(i=0;iprintf("%d\n",result[i]);
}
八皇后问题
#include
intn=1;
intcanplace(intm,inti,inta[8])
{//m行,i列
intj;
for(j=0;j{
if((a[j]+j)==(m+i)||((a[j]-j)==(i-m))||(a[j]==i))
return0;
}
return1;
}
voidoutput(inta[8])
{
inti,j;
printf("No%d:
\n",n);
for(i=0;i<8;++i)
{
for(j=0;j<8;++j)
{
if(a[i]==j)
printf("A");
else
printf(".");
}
printf("\n");
}
}
voidsesearch(intm,inta[8])
{
inti;
if(m>=8)
{
output(a);
++n;
}
else
{
for(i=0;i<8;++i)
{
if(canplace(m,i,a))
{
a[m]=i;
sesearch(m+1,a);
a[m]=100;
}
}
}
}
voidmain()
{
inta[8],i;
for(i=0;i<8;++i)
a[i]=100;
sesearch(0,a);
}
堡垒问题
#include
intn;
intmax(inta,intb)
{
if(a>b)
return(a);
else
return(b);
}
inttrys(inta,intb,chars[6][6])
{
inti,j,m;
chars0[6][6];
if((s[a][b]=='X')||(s[a][b]=='+'))
{
return(0);
}
for(i=1;i<=4;i++)
{
for(j=1;j<=4;j++)
{
s0[i][j]=s[i][j];
}
}
s0[a][b]='+';
for(i=a+1;i<=n;i++)
{
if(s0[i][b]=='X')
{
break;
}
else
{
s0[i][b]='+';
}
}
for(i=a-1;i>=1;i--)
{
if(s0[i][b]=='X')
{
break;
}
else
{
s0[i][b]='+';
}
}
for(i=b+1;i<=n;i++)
{
if(s0[a][i]=='X')
{
break;
}
else
{
s0[a][i]='+';
}
}
for(i=b-1;i>=1;i--)
{
if(s0[a][i]=='X')
{
break;
}
else
{
s0[a][i]='+';
}
}
m=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
m=max(m,trys(i,j,s0));
}
}
return(m+1);
}
intmain()
{
inti,j,m;
charmap[6][6];
charch[10];
scanf("%d",&n);
while(n>0)
{
for(i=1;i<=n;i++)
{
scanf("%s",ch);
for(j=0;j{
map[i][j+1]=ch[j];
}
}
m=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
m=max(m,trys(i,j,map));
}
}
printf("%d\n",m);
scanf("%d",&n);
getchar();
}
}
踩气球
#include
intt[101]={0};
intjudge(longn)
{
inti;
if(n==0)
return
(1);
if(n==1)
return
(1);
for(i=100;i>=2;i--)
{
if(n%i==0)
{
if(t[i]==1)
{
t[i]=0;
return(judge(n/i));
}
}
}
return(0);
}
intmain()
{
longa,b,i;
scanf("%ld%ld",&a,&b);
while((a!
=0)||(b!
=0))
{
if(a>b)
{
i=a;
a=b;
b=i;
}
for(i=1;i<=100;i++)
{
t[i]=1;
}
if(judge(a)==1)
{
if(judge(b)==0)
printf("%ld\n",a);
else
{
if(a>b)
printf("%ld\n",a);
else
printf("%ld\n",b);
}
}
else
{
if(judge(b)==1)
printf("%ld\n",b);
else
{
if(a>b)
printf("%ld\n",a);
else
printf("%ld\n",b);
}
}
scanf("%ld%ld",&a,&b);
}
return(0);
}
迷宫问题
#include
intmain()
{
intmap[500]={0};
charch[30];
intk,n=20,m=20,i,j,l,a,b,x,y,s,e,t=0;
intd[500]={0};
scanf("%d",&k);
for(l=0;l{
scanf("%d%d%d%d",&a,&b,&x,&y);
a++;
b++;
x++;
y++;
getchar();
for(i=1;i<=n;i++)
{
gets(ch);
for(j=1;j<=m;j++)
{
if(ch[j-1]=='.')
map[i*m+j]=1;
else
map[i*m+j]=0;
}
}
s=0;
e=1;
d[0]=a*m+b;
map[d[0]]=0;
t=0;
while(s{
if(d[s]==x*m+y)
{
t=1;
break;
}
if(map[d[s]-1]==1)
{
d[e]=d[s]-1;
map[d[e]]=0;
e++;
}
if(map[d[s]-m]==1)
{
d[e]=d[s]-m;
map[d[e]]=0;
e++;
}
if(map[d[s]+1]==1)
{
d[e]=d[s]+1;
map[d[e]]=0;
e++;
}
if(map[d[s]+m]==1)
{
d[e]=d[s]+m;
map[d[e]]=0;
e++;
}
s++;
}
if(t==0)
{
printf("No\n");
}
else
{
printf("Yes\n");
}
for(i=0;id[i]=0;
}
return(0);
}
农场灌溉问题
#include
intn,m;
intx[11][11]={0},y[11][11]={0};
intfloodfill(charmap[100][100],intb[100][100])
{
intdx[10000]={0},dy[10000]={0};
intnum=0,sum=0,i,j,aa,bb,s=0,e=0;
while(sum{
for(i=0;i{
for(j=0;j{
if(b[i][j]==0)
break;
}
if(jbreak;
}
s=0;e=0;
dx[0]=i;
dy[0]=j;
b[i][j]=1;
while(s<=e)
{
aa=dx[s];
bb=dy[s];
sum++;
if(aa>0)
{
if((y[map[aa-1][bb]-'A'][map[aa][bb]-'A']==1)&&(b[aa-1][bb]==0))
{
b[aa-1][bb]=1;
e++;
dx[e]=aa-1;
dy[e]=bb;
}
}
if(bb>0)
{
if((x[map[aa][bb-1]-'A'][map[aa][bb]-'A']==1)&&(b[aa][bb-1]==0))
{
b[aa][bb-1]=1;
e++;
dx[e]=aa;
dy[e]=bb-1;
}
}
if(aa{
if((y[map[aa][bb]-'A'][map[aa+1][bb]-'A']==1)&&(b[aa+1][bb]==0))
{
b[aa+1][bb]=1;
e++;
dx[e]=aa+1;
dy[e]=bb;
}
}
if(bb{
if((x[map[aa][bb]-'A'][map[aa][bb+1]-'A']==1)&&(b[aa][bb+1]==0))
{
b[aa][bb+1]=1;
e++;
dx[e]=aa;
dy[e]=bb+1;
}
}
s++;
}
for(i=0;i<=e;i++)
{
dx[i]=0;
dy[i]=0;
}
num++;
}
return(num);
}
intmain()
{
charmap[100][100];
intb[100][100]={0};
charch[100];
inti,j,num;
x[1][0]=1;
x[1][2]=1;
x[1][5]=1;
x[1][6]=1;
x[1][7]=1;
x[1][8]=1;
x[1][10]=1;
for(j=0;j<=10;j++)
{
x[3][j]=x[1][j];
x[5][j]=x[1][j];
x[6][j]=x[1][j];
x[8][j]=x[1][j];
x[9][j]=x[1][j];
x[10][j]=x[1][j];
}
y[2][0]=1;
y[2][1]=1;
y[2][4]=1;
y[2][6]=1;
y[2][7]=1;
y[2][9]=1;
y[2][10]=1;
for(j=0;j<=10;j++)
{
y[3][j]=y[2][j];
y[4][j]=y[2][j];
y[7][j]=y[2][j];
y[8][j]=y[2][j];
y[9][j]=y[2][j];
y[10][j]=y[2][j];
}
scanf("%d%d",&n,&m);
getchar();
while(n!
=-1)
{
for(i=0;i{
gets(ch);
for(j=0;j{
map[i][j]=ch[j];
b[i][j]=0;
}
}
num=floodfill(map,b);
printf("%d\n",num);
scanf("%d%d",&n,&m);
getchar();
}
}
求图像的周长
#include
intmain()
{
intx[8]={-1,0,1,0,-1,-1,1,1};