全部知识点
#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');
}输出： ___________
（格雷码， GrayCode ） 格雷码是对十进制数的一种二进制编码。编码顺序与相应的十进制数的大小不一致。其特点是：对于 两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数之间也仅有一个 二进制位不同，以 4 位二进制数为例，编码如下：
如果把每个二进制的位看作一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。因此， 格雷码广泛用于信号处理、数 - 模转换等领域。
下面程序的任务是：由键盘输入二进制数的位数 n(n<16) ，再输入一个十进制数 m(0 ≤m<2n) ，然 后输出对应于 m 的格雷码（共 n 位，用数组 gr[] 存放）。
为了将程序补充完整，你必须认真分析上表的规律，特别是对格雷码固定的某一位，从哪个十进制数 起，由 0 变为 1，或由 1 变为 0。
#include<stdio.h>
int main()
{
int bound=1,m,n,i,j,b,p,gr[15];
printf("inputn,m\n");
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)bound= ①;
if(m<0||m>=bound)
{
printf("Dataerror!\n");
② ;
}
b=1;
for(i=1;i<=n;i++)
{
p=0;b=b*2;
for( ③;j<=m;j++)
if( ④ )
p=1-p;
gr[i]=p;
}
for(i=n; ⑤ )
printf("%1d",gr[i]);/* 在"%1d" 中出现的是数字 1，不是字母 l*/
printf("\n");
}
（连续邮资问题）某国发行了 n 种不同面值的邮票，并规定每封信最多允许贴 m 张邮票，在这 些约束下，为了能贴出 {1 ， 2，3, …，maxvalue} 连续整数集合的所有邮资，并使 maxvalue 的值最 大，应该如何设计各邮票的面值？例如，当 n=5 、m=4 时，面值设计为 {1 ， 3，11 ，15 ，32} ，可使 maxvalue 达到最大值 70 （或者说，用这些面值的 1 至4 张邮票可以表示不超过 70 的所有邮资，但无 法表示邮资 71 。而用其他面值的 1 至4 张邮票如果可以表示不超过 k 的所有邮资，必有 k ≤70 ）。
下面是用递归回溯求解连续邮资问题的程序。数组 x[1:n] 表示 n 种不同的邮票面值，并约定各元 素按下标是严格递增的。数组 bestx[1:n] 存放使 maxvalue 达到最大值的邮票面值（最优解）， 数组 y[maxl] 用于记录当前已选定的邮票面值 x[1:i] 能贴出的各种邮资所需的最少邮票张数。请将程 序补充完整。
#include<stdio.h>
#defineNN20
#definemaxint30000
#definemaxl500/* 邮资的最大值 */
int n,m,bestx[NN],x[NN],y[maxl],maxvalue=0;
void result()
{
输出结果：最大值： maxvalue 及 最优解： bestx[1:n] （略）
}
void backtrace(inti,intr)
{
int j,k,z[maxl];
for(j=0;j<= ① ;j++)
if(y[j]<m)
for(k=1;k<=m-y[j];k++)
if(y[j]+k<=y[ ② ])
y[ ③ ]=y[j]+k;
while(y[r]<maxint)r++;
if(i>n)
{
if(r-1>maxvalue)
{
maxvalue= ④ ;
for(j=1;j<=n;j++)
bestx[j]=x[j];
}
return;
}
for(k=0;k<maxl;k++)
z[k]=y[k];
for(j= ⑤ ;j<=r;j++)
{
x[i]=j;
⑥ ;
for(k=0;k<maxl;k++)
y[k]=z[k];
}
}
void main()
{
int j;
printf("inputn,m:\n");
scanf( "%d%d",&n,&m);
for(j=1;j<maxl;j++)
y[j]=maxint;
y[0]=0;x[0]=0;x[1]=1;
backtrace(2,1);
result();
}书架上有 4 本不同的书 A、B、C、D。其中 A 和 B 是红皮的， C和 D 是黑皮的。把这 4 本书摆在书 架上，满足所有黑皮的书都排在一起的摆法有 _____ 种。满足 A 必须比 C 靠左，所有红皮的书要摆放在 一起，所有黑皮的书要摆放在一起，共有 ______ 种摆法。
有 6 个城市，任何两个城市之间都有一条道路连接， 6 个城市两两之间的距离如下表所示，则城 市 1 到城市 6 的最短距离为 _____________ 。
#include<iostream>
using namespace std;
int main()
{
int i, a, b, c, d, f[4];
for(i = 0; i < 4; i++) cin >> f[i];
a = f[0] + f[1] + f[2] + f[3];
a = a / f[0];
b = f[0] + f[2] + f[3];
b = b / a;
c = (b * f[1] + a) / f[2];
d = f[(b / c ) % 4];
if(f[(a + b + c + d) % 4] > f[2])
cout << a + b<< endl;
else
cout << c + d << endl;
return 0;
}输入： 9 19 29 39
输出： _______________
#include<iostream>
using namespace std;
void foo(int a, int b, int c)
{
if(a > b)
foo(c, a, b);
else
cout<<a<<','<<b<<','<<c<<endl;
}
int main()
{
int a, b, c;
cin >> a >> b >> c;
foo(a, b, c);
return 0;
}输入: 3 1 2
输出: __________
#include <iostream>
using namespace std;
void func(int ary[], int n )
{
int i=0, j, x;
j=n-1;
while(i<j)
{
while (i<j&&ary[i]>0) i++;
while (i<j&&ary[j]<0) j--;
if (i<j)
{
x=ary[i];
ary[i++]=ary[j];
ary[j--]=x;
}
}
}
int main()
{
int a[20], i, m;
m=10;
for(i=0; i<m; i++)
{
in>>a[i];
}
func(a, m);
for (i=0; i<m; i++)
cout<<a[i]<<" ";
cout<< endl;
return 0;
}输入： 5 4 -6 -11 6 -59 22 -6 1 10
输出： ___________________________________
#include<iostream>
#include<cstring>
using namespace std;
#define MAX 100
void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m)
{
int i, root_m;
if(spos_f > epos_f)
return;
for(i = spos_m; i <= epos_m; i++)
if(first[spos_f] == mid[i])
{
root_m = i;
break;
}
solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);
solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);
cout << first[spos_f];
}
int main()
{
char first[MAX], mid[MAX];
int len;
cin >> len;
cin >> first >> mid;
solve(first, 0, len - 1, mid , 0, len - 1);
cout << endl;
return 0;
}输入： 7 ABDCEGF BDAGECF
输出： ______________________________
（字符串替换） 给定一个字符串 S（S 仅包含大小写字母） ，下面的程序将 S 中的每个字母用规定的 字母替换，并输出 S 经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串 S， 第二个字符串 S’由 26 个字母组成，它是 a-z 的任一排列，大小写不定， S’规定了每个字母对应的替 换字母： S’中的第一个字母是字母 A 和 a 的替换字母，即 S 中的 A 用该字母的大写替换， S 中的 a 用 该字母的小写替换； S’中的第二个字母是字母 B 和 b 的替换字母， 即 S 中的 B用该字母的大写替换， S 中的 b 用该字母的小写替换；…… 以此类推。
#include <iostream>
#include <string.h>
char change[26], str[5000];
using namespace std;
void CheckChangeRule()
{
int i;
for (i = 0;i < 26;i ++)
{
if ( ① )
change[i] -= 'A' - 'a';
}
}
void ChangeString()
{
int i;
for (i = 0;i <strlen(str);i ++)
{
if ( ② )
str[i] = change[str[i] - 'A'] -'a' + 'A';
else
③
}
}
int main()
{
int i;
cin >> str ;
cin >> change;
CheckChangeRule();
④
cout << str << endl;
return 0;
}( 找第 k 大的数 ) 给定一个长度为 1,000,000 的无序正整数序列 , 以及另一个数 n (1<=n<=1000000), 然后以类似快速排序的方法找到序列中第 n 大的数（关于第 n 大的数：例 如序列 {1 ，2，3，4，5，6} 中第 3 大的数是 4）。
#include <iostream>
using namespace std;
int a[1000001],n,ans = -1;
void swap(int &a,int &b)
{
int c;
c = a; a = b; b = c;
}
int FindKth(int left, int right, int n)
{
int tmp,value,i,j;
if (left == right) return left;
tmp = rand()% (right - left) + left;
swap(a[tmp],a[left]);
value = ①
i = left;
j = right;
while (i < j)
{
while (i < j && ② ) j --;
if (i < j) {a[i] = a[j]; i ++;} else break;
while (i < j && ③ ) i ++;
if (i < j) {a[j] = a[i]; j - -;} else break;
}
④
if (i < n) return FindKth( ⑤ );
if (i > n) return ⑥
return i;
}