算法练习
1.计算三角形的边
题目描述
给出三个正整数，计算最小的数加上次小的数与最大的数之差。
输入
每一行包括三个数据a, b, c，并且都是正整数，均小于10000。
*/
1 2 3
6 5 4
10 20 15
1 1 100
0 0 0
输出
对于输入的每一行，在单独一行内输出结果s。s=min(a,b,c)+mid(a,b,c)-max(a,b,c)。上式中，min为最小值，mid为中间值，max为最大值。
*/
0
3
5
-98
代码
int min(int a,int b,int c){
int x;
if(a<=b){
x=b;
}
if(x<=c){
x=c;
}
return x;
}
// run this program using the console pauser or add your own getch, system("pause") or input loop
int main() {
int a,b,c,temp;
scanf("%d %d %d",&a,&b,&c);
int min_x=min(a,b,c);
if(min_x==a){
temp=(b+c)-a;
}else if(min_x==b){
temp=(a+c)-b;
}else{
temp=(a+b)-c;
}
printf("%d",temp);
return 0;
}
2.指定矩阵相乘
题目描述
输入为两个矩阵，其中一个为2×3的矩阵，另一个为3×2的矩阵
输入
/*
输入为两个矩阵，其中一个为2*3的矩阵，另一个为3*2的矩阵
*/
1 2 3
3 4 5
6 7
8 9
10 11
输出
/*
一个2*2的矩阵（每一个数字后都跟一个空格）
*/
52 58
100 112
代码
void Mult_A_B(int A[][3],int B[][2]){
int c[2][2]={0};
int i,j,k;
for(i=0;i<2;i++){
for(j=0;j<2;j++){
for(k=0;k<3;k++){
c[i][j]+=A[i][k]*B[k][j]; //将 c[i][j]+=A[i][k]*B[k][j]写成c[i][j]+=A[i][k]*B[k][i]
}
}
}
for(i=0;i<2;i++){
for(j=0;j<2;j++){
printf("%d ",c[i][j]);
}
printf("\n");
}
}
int main(){
int A[2][3];
int B[3][2];
int i,j;
for(i=0;i<2;i++){
for(j=0;j<3;j++){
scanf("%d",&A[i][j]);
}
}
printf("A=\n");
for(i=0;i<2;i++){
for(j=0;j<3;j++){
printf("%d ",A[i][j]);
}
printf("\n");
}
printf("\n");
for(i=0;i<3;i++){
for(j=0;j<2;j++){
scanf("%d",&B[i][j]);
}
}
printf("B=\n");
for(i=0;i<3;i++){
for(j=0;j<2;j++){
printf("%d ",B[i][j]);
}
printf("\n");
}
printf("A和B相乘之后的矩阵为：\n");
Mult_A_B(A,B);
return 0;
}
3.去掉s中所有的c字符
题目描述
输入字符串s和字符c，要求去掉s中所有的c字符，并输出结果。
输入
/*
测试数据有多组，每组输入字符串s和字符c。
*/
heallo
a
输出
对于每组输入,输出去除c字符后的结果。
*/
hello
代码
void sub_c(char s[],char c){
int i,k;
int len=strlen(s);
printf("len(s)=%d\n",len);
char p[101];
int j=0;
for(i=0;i<len;i++){
if(s[i]!=c){
p[j++]=s[i];
}
}
int leng=strlen(p);
printf("leng(p)=%d\n",leng);
for(k=0;k<leng;k++){
printf("%c",p[k]);
}
printf("\n");
}
int main(){
char s[101];
char c;
scanf("%s %c",&s,&c);
sub_c(s,c);
return 0;
}
4.十个数里的最大值
题目
测试数据有多组，每组10个整数。
输入
/*
测试数据有多组，每组10个整数。
*/
10 22 23 152 65 79 85 96 32 1
输出
/*
对于每组输入,请输出其最大值（有回车）。
*/
max=152
代码
//10个数里的最大值
void max_value(int A[]){
int temp=A[0];
for(int i=0;i<10;i++){
if(temp<=A[i]){
temp=A[i];
}
}
printf("%d\n",temp);
}
int main(){
int A[10];
for(int i=0;i<10;i++){
scanf("%d",&A[i]);
}
max_value(A);
return 0;
}
5.字符串排序
题目
输入一个字符串，长度小于等于200，然后将输出按字符顺序升序排序后的字符串。
输入
/*
测试数据有多组，输入字符串。
*/
bacd
输出
/*
对于每组输入,输出处理后的结果。
*/
abcd
代码
void strSort(char s[201]){
int len=strlen(s);
sort(s,s+len);
printf("%s",s);
}
int main(){
char s[201];
while(scanf("%s",&s)!=EOF){
strSort(s);
}
return 0;
}
6.棋盘问题
题目
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
输入
3
1 2
输出
3 3 4 4 8 8 9 9
3 2 0 4 8 7 7 9
5 2 2 6 10 10 7 11
5 5 6 6 1 10 11 11
13 13 14 1 1 18 19 19
13 12 14 14 18 18 17 19
15 12 12 16 20 17 17 21
15 15 16 16 20 20 21 21
代码
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include <algorithm>
#include <math.h>
using namespace std;
int matrix[200][200];
int num=0;
int chessBord(int tr,int tc,int dr,int dc,int size){
if(size==1) return 0;
int t=++num;
int s=size/2;
if(dr<tr+s&&dc<tc+s){
chessBord(tr,tc,dr,dc,s); //如果特殊方格在左上角，调用递归
}else{
matrix[tr+s-1][tc+s-1]=t; //如果特殊方格不在左上角，先对右下角的表格做标记；
chessBord(tr,tc,tr+s-1,tc+s-1,s); //调用递归处理剩下的表格
}
if(dr<tr+s&&dc>tc+s-1){
chessBord(tr,tc+s,dr,dc,s);
}else{
matrix[tr+s-1][tc+s]=t;
chessBord(tr,tc+s,tr+s-1,tc+s,s);
}
if(dr>tr+s-1&&dc<tc+s){
chessBord(tr+s,tc,dr,dc,s);
}else{
matrix[tr+s][tc+s-1]=t;
chessBord(tr+s,tc,tr+s,tc+s-1,s);
}
if(dr>tr+s-1&&dc>tc+s-1){
chessBord(tr+s,tc+s,dr,dc,s);
}else{
matrix[tr+s][tc+s]=t;
chessBord(tr+s,tc+s,tr+s,tc+s,s);
}
}
int main(){
int size,k,tr,tc,dr,dc; //size为棋牌的尺寸 tr为棋盘的行数 tc为棋盘的列数 dr为特殊方格的行数 dc为特殊方格的列数
scanf("%d",&k);
scanf("%d %d",&dr,&dc);
size=int (pow(2,k));
tr=0,tc=0;
chessBord(tr,tc,dr,dc,size);
for(tr=0;tr<size;tr++){
for(tc=0;tc<size;tc++){
printf("%4d",matrix[tr][tc]);
}
printf("\n");
}
return 0;
}
7.过河卒
题目
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下或向右。同时在棋盘上的任一点有一个对方的马(如图中的C点)，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如图中C点上的马可以控制9个点。卒不能走到对方马的控制点。
棋盘用坐标表示，A点坐标(0,0)、B点坐标(n, m) (n,m为不超过20的整数,并由键盘输入),同样马的位置坐标C是需要给出的(C≠A,且C≠B)。现在要求你计算出卒从A点能够到达B点的路径条数。
输入
6 6 3 2
输出
17
#include<iostream>
using namespace std;
#define int long
#define maxsize 21
int dr[8][2] = {{2,1},{1,2},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
int dp[maxsize][maxsize];
int mp[maxsize][maxsize];
int n,m,x,y;
int main()
{
int i,j;
cin>>n>>m>>x>>y;
mp[x][y] = 1;
dp[0][0] = 1;
for(i=0;i<8;i++){
mp[x+dr[i][0]][y+dr[i][1]] = 1;
}
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
{
if(!mp[i+1][j]) dp[i+1][j] += dp[i][j];
if(!mp[i][j+1]) dp[i][j+1] += dp[i][j];
}
cout<<dp[n][m]<<endl;
return 0;
}
8.铺设地砖
题目
小明最近新买了一个房间，为了给它做装修，想要给它铺上地砖。然而现有的地砖只有两种规格分别为1米1米、2米2米，由于小明买的房间有点小，宽度只有3米，长度为N米。当然这样一个房间也足够他自己一个人住了。那么如果要给这个房间铺设地砖，且只用以上这两种规格的地砖，请问有几种铺设方案。
输入
2
2
3
输出
3
5
代码
using namespace std;
int a[31];
int main()
{
int n=0,k=0;
int i=0;
a[1]=1;
a[2]=3;
for(i=3;i<=30;i++)
{
a[i] = 2*a[i-2]+a[i-1];
}
cin>>n;
for(i=n;i>0;i--){
cin>>k;
cout<<a[k]<<endl;
}
return 0;
}
9.找数字
题目
给定一组无序数值，数值的大小在1到百万之间，数值的个数在10-50万个之间。现需要找出其中第5到第10小的整数。
输入
1
2
3
4
5
6
7
8
9
10
0
输出
5
6
7
8
9
10
代码
#include <stdio.h>
#include <string.h>
//using namespace std;
int a[500001];
int find(int low,int high,int k){
int temp=a[low];
int low_temp=low;
int high_temp=high;
while(low<high){
while(low<high&&a[high]>=temp){
high--;
}
a[low]=a[high];
while(low<high&&a[low]<=temp){
low++;
}
a[high]=a[low];
}
a[low]=temp;
if(low==k){
return a[low];
}
else if(low>k){
return find(low_temp,low-1,k);
}
else return find(low+1,high_temp,k);
}
void main(){
int x, num;
for(num=0;;num++){
scanf("%d",&x);
if(x==0) break;
a[num]=x;
}
for(int i=5;i<=10;i++){
x=find(0,num-1,i-1);
printf("%d\n",x);
}
}