NOIP真题
#include <stdio.h>
int main()
{
int i,u[4],v[4],x,y=10;
for(i=0;i<=3;i++)
scanf("%d", &u[i]);
v[0]=(u[0]+u[1]+u[2]+u[3])/7;
v[1]=u[0]/((u[1]-u[2])/u[3]);
v[2]=u[0]*u[1]/u[2]*u[3];
v[3]=v[0]*v[1];
x=(v[0]+v[1]+2)-u[(v[3]+3)%4];
if(x>10) 由 OIFans.c 收集
y+= (v[2]*100-v[3])/(u[u[0]%3]*5);
else
y+=20+(v[2]*100-v[3])/(u[v[0]%3]*5);
printf("%d,%d\n", x,y);
return 0;
} /* 注：本例中，给定的输入数据可以避免分母为 0 或下标越界。 */输入：9 3 9 4
输出：_______________
#include <stdio.h>
int main()
{
int i,j,m[]={2,3,5,7,13};
long t;
for (i=0;i<=4;i++)
{
t=1;
for(j=1;j<m[i];j++) t*=2;
printf("%ld ",(t*2-1)*t);
}
printf("\n");
}输出:____________________
#include "stdio.h"
#define N 7
int fun1(char s[],char a,int n)
{
int j;
j=n;
while(a<s[j] && j>0) j--;
return j;
}
int fun2(char s[],char a,int n)
{
int j;
j=1;
while(a>s[j] && j<=n) j++;
return j;
}
void main()
{
char s[N+1];
int k,p;
for(k=1;k<=N;k++)
s[k]='A'+2*k+1;
p=fun1(s,'M',N);
printf( “%d\n”,p+fun2(s,'M',N));
}输出：_____________
#include <stdio.h>
void digit(long n,long m)
{
if(m>0)
printf("%2ld",n%10);
if(m>1)
digit(n/10,m/10);
printf("%2ld",n%10);
}
int main()
{
long x,x2;
printf("Input a number:\n"); scanf("%ld",&x);
x2=1;
while(x2<x) x2*=10;
x2/=10;
digit(x,x2);
printf("\n");
}输入：9734526
输出：______________________________
（选排列）下面程序的功能是利用递归方法生成从 1 到 n(n<10)的 n 个数中取 k(1<=k<=n)个数的 全部可能的排列（不一定按升序输出）。
例如，当 n=3，k=2 时， 应该输出（每行输出 5 个排列）：
12 13 21 23 32
31
程序：
#include <stdio.h>
int n,k,a[10];
long count=0;
void perm2(int j)
{
int i,p,t;
if( ① )
{
for(i=k;i<=n;i++)
{
count++;
t=a[k]; a[k]=a[i]; a[i]=t;
for( ② )
printf("%1d",a[p]); /* "%1d" 中是数字 1，不是字母 l */
printf(" ");
t=a[k];a[k]=a[i];a[i]=t;
if(count%5==0) printf("\n");
}
return;
}
for(i=j;i<=n;i++)
{
t=a[j];a[j]=a[i];a[i]=t;
③ ;
t=a[j]; ④ ;
}
}
int main()
{
int i;
printf("\nEntryn,k (k<=n):\n");
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++) a[i]=i;
⑤ ;
}（TSP 问题的交叉算子） TSP 问题 (Traveling Salesman Problem) 描述如下： 给定 n 个城市， 构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等） ，现要构造遍历所有 城市的环路，每个城市恰好经过一次，求使总代价达到最小的一条环路。 遗传算法是求解该问题的一个很有效的近似算法。 在该算法中， 一个个体为一条环路， 其编 码方法之一是 1 到 n 这 n 个数字的一个排列， 每个数字为一个城市的编号。 例如当 n=5 时， “ 3 4 2 1 5 表示该方案实施的路线为 ” 3->4->2->1->5->3 。遗传算法的核心是通过两个个体的 交叉操作，产生两个新的个体。下面的程序给出了最简单的一种交叉算法。
具体过程如下：
(1)选定中间一段作为互换段，该段的起止下标为 t1，t2，随机生成 t1，t2 后，互换两段。
(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两 步处理：
(2.1) 将两个互换段中，共同的数字标记为 0，表示已处理完。
(2.2) 将两个互换段中其余数字标记为 1，按顺序将互换段外重复的数字进行替换。
例如： n=12，两个个体分别是：
a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11
a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9 t1=5，t2=8。
上述每一行中，两个星号间的部分为互换段。假定数组的下标从 1 开始，互换 后有：
a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11
a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9
然后，将数字 6,7 对应的项标记为 0，星号内数字 2,9,10,11 对应的项标记为 1，并且按顺序 对应关系为 : 10<->2 ，11<->9。于是，将 a1[9]=10 替换为 a1[9]=2 ，将 a2[2]=2 替换为 a2[2]=10 ， 类似再做第 2 组替换。这样处理后，就得到了两个新个体：
a1: 1 3 5 4 6 7 10 11 2 12 8 9
a2: 3 10 1 12 2 6 7 9 8 5 4 11
（3）输出两个新个体的编码。
程序：
#include <stdio.h>
#include <stdlib.h>
#define N 20
int a1[N],a2[N],kz1[N],kz2[N],n;
int rand1(int k)
{
int t=0;
while(t<2|| t>k)
t=(int)((double)rand()/RAND_MAX*k);
return t;
}
void read1(int a[],int m)
{ 读入数组元素 a[1]至 a[m], a[0]=0 ,略. }
void wrt1(int a[],int m)
{ 输出数组元素 a[1]至 a[m],略. }
void cross(int a1[], int a2[],int t1, int t2, int n)
{
int i,j,k,t,kj;
for(i=t1; i<=t2; i++)
{
t=a1[i]; ①；
}
for(i=1;i<=n;i++)
if(i<t1 || i>t2)
kz1[i]=kz2[i]=-1;
else
②；
for(i=t1;i<=t2;i++)
for(j=t1;j<=t2;j++)
if(a1[i]==a2[j])
{
③ ; break;
}
for(i=t1;i<=t2;i++)
if(kz1[i]==1)
{
for(j=t1;j<=t2;j++)
if(kz2[j]==1)
{
kj=j; break;
}
for(j=1;j<=n;j++)
if( ④ )
{
a1[j]=a2[kj];break;
}
for(j=1;j<=n;j++)
if( ⑤ )
{
a2[j]=a1[i]; break;
}
kz1[i]=kz2[kj]=0;
}
}
int main()
{
int k,t1,t2;
printf("input (n>5):\n"); scanf("%d",&n);
printf("input array 1 (%d'numbers):\n",n); read1(a1,n);
printf("input array 2 (%d'numbers):\n",n); read1(a2,n);
t1=rand1(n-1);
do
{
t2=rand1(n-1);
}while(t1==t2);
if(t1>t2)
{
k=t1; t1=t2; t2=k;
}
⑥
wrt1(a1,n); wrt1(a2,n);
}（子集划分）将 n 个数{1，2，…，n}划分成 r 个子集。每个数都恰好属于一个子集，任何两个 不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为 S(n,r)。例如，S(4,2)=7，这 7 种不同的划分方法依次为{(1),(234)}, {(2),(134)}, {(3),(124)}, {(4),(123)}, {(12),(34)}, {(13),(24)}, {(14),(23)}。当 n=6,r=3 时，S(6,3)= _____________。
（提示：先固定一个数，对于其余的 5 个数考虑 S(5,3)与 S(5,2)，再分这两种情况对原固定的数 进行分析）。
（最短路线）某城市 的街道是一个很规整的矩形网格（见下图），有 7 条南北向的纵街，5 条东 西向的横街。现要从西南角的 A 走到东北角的 B，最短的走法共有多少种？_________________.
#include <iostream.h>
void main()
{
int i,p[5],a,b,c,x,y=20;
for(i=0;i<=4;i++) cin>>p[i];
a=(p[0]+p[1])+(p[2]+p[3]+p[4])/7;
b=p[0]+p[1]/((p[2]+p[3])/p[4]);
c=p[0]*p[1]/p[2];
x=a+b-p[(p[3]+3)%4];
if(x>10)
y+= (b*100-a)/(p[p[4]%3]*5);
else
y+=20+(b*100-c)/(p[p[4]%3]*5);
cout<<x<<","<<y<<endl;
}
// 注：本例中，给定的输入数据可以避免分母为 0 或数组元素下标越界。输入：6 6 5 5 3 输出：_______________
#include <iostream.h>
void fun(int *a,int *b)
{
int *k;
k=a; a=b; b=k;
}
void main( )
{
int a=3, b=6, *x=&a, *y=&b;
fun(x,y);
cout<<a<<","<<b<<endl;
}输出:____________________
#include <iostream.h>
#include <iomanip.h>
#include "math.h"
void main()
{
int a1[51]={0};
int i,j,t,t2,n=50;
for (i=2;i<=sqrt(n);i++)
if(a1[i]==0)
{
t2=n/i;
for(j=2;j<=t2;j++) a1[i*j]=1;
}
t=0;
for (i=2;i<=n;i++)
if(a1[i]==0)
{
cout<<setw(4)<<i; t++;
if(t%10==0) cout<<endl;
}
cout<<endl;
}输出： _______________________________
#include <iostream.h>
#include "ctype.h"
void expand(char s1[],char s2[])
{
int i,j,a,b,c;
j=0;
for(i=0;(c=s1[i])!='\0';i++)
if(c=='-')
{
a=s1[i-1]; b=s1[i+1];
if ( isalpha(a)&&isalpha(b) || isdigit(a)&&isdigit(b) )
//函数 isalpha(a)用于判断字符 a 是否为字母，isdigit(b) 用于判断字符 b 是否为数字，如果是，返回 1，否则返回 0
{
j--;
do
s2[j++]=a++;
while(tolower(a)<tolower(s1[i+1]));
}
else s2[j++]=c;
}
else s2[j++]=c;
s2[j]='\0';
}
void main()
{
char s1[100],s2[300];
cin>>s1;
expand(s1,s2);
cout<<s2<<endl;
}输入：wer2345d-h454-82qqq 输出：____________________________________
（求字符串的逆序）下面的程序的功能是输入若干行字符串，每输入一行，就按逆序输出该行，最后键入-1 终止程序。
请将程序补充完整。
#include <iostream.h>
#include <string.h>
int maxline=200,kz;
int reverse(char s[])
{
int i,j,t;
for(i=0,j=strlen(s)-1; i<j; ① ， ② )
{
t=s[i]; s[i]=s[j]; s[j]=t;
}
return 0;
}
void main()
{
char line[100];
cout<<"continue? -1 for end."<<endl;
cin>>kz;
while( ③ )
{
cin>>line;
④ ;
cout<<line<<endl;
cout<<"continue? -1 for end."<<endl;
cin>>kz;
}
}（棋盘覆盖问题）在一个 k k 2 × 2 个方格组成的棋盘中恰有一个方格与其他方格不同（图中标记为 -1 的方格），称之为特殊方格。现用 L 型（占 3 个小格）纸片覆盖棋盘上除特殊方格的所有部分，各纸 片不得重叠，于是，用到的纸片数恰好是(4 −1)/ 3 k 。在下表给出的一个覆盖方案中，k=2，相同的 3 个数字构成一个纸片。
下面给出的程序是用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角， 递归进行。请将程序补充完整。
#include <iostream.h>
#include <iomanip.h>
int board[65][65],tile; // tile 为纸片编号
void chessboard(int tr,int tc,int dr,int dc,int size)
// dr,dc 依次为特殊方格的行、列号
{
int t,s;
if (size==1)
⑤ ;
t=tile++;
s=size/2;
if( ⑥ )
chessboard(tr,tc,dr,dc,s);
else
{
board[tr+s-1][tc+s-1]=t;
⑦ ;
}
if(dr<tr+s && dc>=tc+s)
chessboard(tr,tc+s,dr,dc,s);
else
{
board[tr+s-1][tc+s]=t;
⑧ ;
}
if(dr>=tr+s && dc<tc+s)
chessboard(tr+s,tc,dr,dc,s);
else
{
board[tr+s][tc+s-1]=t;
⑨ ;
}
if(dr>=tr+s && dc>=tc+s)
chessboard(tr+s,tc+s,dr,dc,s);
else
{
board[tr+s][tc+s]=t;
⑩ ;
}
}
void prt1(int b[][65],int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<setw(3)<<b[i][j];
cout<<endl;;
}
}
void main()
{
int size,dr,dc;
cout<<"input size(4/8/16/64):"<<endl;
cin>>size;
cout<<"input the position of special block(x,y):"<<endl;
cin>>dr>>dc;
board[dr][dc]=-1;
tile++;
chessboard(1,1,dr,dc,size);
prt1(board,size);
}给定 n 个有标号的球，标号依次为 1，2，…，n。将这 n 个球放入 r 个相同的盒子里，不允许 有空盒，其不同放置方法的总数记为 S(n,r) 。例如， S(4,2)=7 ，这 7 种不同的放置方法依次为 {(1),(234)},{(2),(134)},{(3),(124)},{(4),(123)},{(12),(34)},{(13),(24)}, {(14),(23)} 。当 n=7,r=4 时， S(7,4)=_____________
N 个人在操场里围成一圈，将这 N 个人按顺时针方向从 1 到N 编号，然后，从第一个人起，每 隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直 到 操 场 只 剩 下 一 个 人 ， 记 这 个 人 的 编 号 为J(N) ， 例 如 ，J(5)=3 ，J(10)=5 ， 等 等 。 则 J(400)=______________ 。
（提示：对 N=2 m+r 进行分析，其中 0≤r<2 m ）。
#include<stdio.h>
int main()
{
int i,p[5],q[5],x,y=20;
for(i=0;i<=4;i++)
scanf("%d",&p[i]);
q[0]=(p[0]+p[1])+(p[2]+p[3]+p[4])/7;
q[1]=p[0]+p[1]/((p[2]+p[3])/p[4]);
q[2]=p[0]*p[1]/p[2];
q[3]=q[0]*q[1];
q[4]=q[1]+q[2]+q[3];
x=(q[0]+q[4]+2)-p[(q[3]+3)%4];
if(x>10)
y+=(q[1]*100-q[3])/(p[p[4]%3]*5);
else
y+=20+(q[2]*100-q[3])/(p[p[4]%3]*5);
printf("%d,%d\n",x,y);
return 0;
}
/* 注：本例中，给定的输入数据可以避免分母为 0 或数组元素下标越界。 */输入： 66553
输出： _______________
#include<stdio.h>
void fun(int*a,int*b)
{
int*k;
k=a;a=b;b=k;
}
int main()
{
int a=3,b=6,*x=&a,*y=&b;
fun(x,y);
printf("No.1:%d,%d",a,b);
fun(&a,&b);
printf("No.2:%d,%d\n",a,b);
}输出 :___________________
#include"math.h"
#include"stdio.h"
int main()
{
int a1[51]={0};
int i,j,t,t2,n=50;
for(i=2;i<=sqrt(n);i++)
if(a1[i]==0)
{
t2=n/i;
for(j=2;j<=t2;j++)a1[i*j]=1;
}
t=0;
for(i=2;i<=n;i++)
if(a1[i]==0)
{
printf("%4d",i);t++;
if(t%10==0)printf("\n");
}
printf("\n");
}输出： _____________________
#include"stdio.h"
char ch[]={'q','A','S','O','R','T','E','X','A','M','P','L','E'};
int n=12;
void shift(intk,intn)
{
char v;
int j;
v=ch[k];j=k+k;
while(j<=n)
{
if((j<n)&&(ch[j]<ch[j+1])) j++;
if(v<ch[j])
{
ch[j/2]=ch[j];j*=2;
}
else
return;
ch[j/2]=v;
}
}
void hpsrt(void)
{
int k;
char tmp;
for(k=n/2;k>0;k--)shift(k,n);/* 建堆 */
printf("No.1:");
for(k=1;k<=n;k++)putchar(ch[k]);
putchar('\n');
for(k=n;k>0;k--)
{
tmp=ch[1];ch[1]=ch[k];ch[k]=tmp;
shift(1,k-1);
}
}
int main()
{
int k;
hpsrt();
printf("No.2:");
for(k=1;k<=n;k++)putchar(ch[k]);
putchar('\n');
}输出： ___________