PTA程序辅助设计平台—2023年软件设计综合实践_4(数组及字符串)

6-1 找最小元素/选择排序 - C/C++ 数组及字符串

（找最小元素）对于给定的包含10个元素的整数数组，设计一个函数，从数组给定的下标范围[i,j]里找到值最小的元素，返回其下标。该函数的原型可以是int findMin(int a[], int i, int j)，参数int a[]代表被搜索的数组。

以这个函数为基础，可以演化出一种称之为选择排序的算法。该算法从a[0..N]中找出最小元素并与a[0]交换，然后再从a[1..N]中找出最小元素并与a[1]交换，然后再从a[2..n]中找出最小元素并与a[2]交换，... 最终得到一个递增有序的数组。

下述程序从键盘读入10个整数，然后使用选择排序算法进行排序并输出。请设计findMin()函数，使得该程序可以正确运行。

输入样例：

78 1 7 2 24 35 77 89 10 567

输出样例：

1,2,7,10,24,35,77,78,89,567

注意：本题只需要提交findMin()函数的定义代码，不要将整个程序提交。

int findMin(int a[], int i, int j) {
    int t=i;
    for (i; i < j; i++) {
        if (a[t] <= a[i + 1]) {
            continue;
        }
        else {
            t = i + 1;
        }
    }
    return t;
};

6-2 字符串匹配 - C/C++ 数组及字符串

函数findSubStr()用于从以0结尾的字符数组s中查找其子串s1的位置，如果找到，返回起始下标，否则返回-1。

举例：字符串'tri'在字符串'string'中的起始下标为1；在字符串'tom&jerry'中找不到子串'jack'，函数应返回-1。

请定义上述findSubStr()函数，使得下述程序可以运行并产生正确的执行结果。

int findSubStr(char s[], char s1[]) {
    int len_s=strlen(s);
    int len_s1=strlen(s1);
    for(int i=0;i<len_s-len_s1;i++){
        int j;
        for(j=0;j<len_s1;j++){
            if(s[i+j]!=s1[j]){
                break;
            }
        }
        if(j==len_s1) return i;
    }
    return -1;
};

7-1 大月与小月 - C/C++ 数组及字符串

（大月与小月）定义一个长度为12的整数数组days，其中days[i]表示i+1月的天数（平年）。编写一个程序，从键盘读入月份，然后从days数组查得该月天数并打印。

输入格式:

月份(1-12)

输出格式:

参考输出样例

输入样例:

11

输出样例:

There are 30 days in 11th month.

#include<bits/stdc++.h>
using namespace std;
int main()
{   int n,i;
    int a[]={31,28,31,30,31,30,31,31,30,31,30,31};
    cin>>i;
    n=a[i-1];
    cout<<"There are "<<n<<" days in "<< i <<"th month.";
 return 0;
}

7-2 数组累积和 - C/C++ 数组及字符串 

（数组累积和）对于给定的包含5个元素的浮点数数组a，请编写程序求数组a的累积和数组b，数组b也应包含5个元素，其中b[i]等于sum(a[0..i])。

输入格式：

以空格为分隔的5个浮点数

输出格式：

对应的累积和数组的值，保留2位小数以逗号分隔，请参考输出样例

输入样例:

0.01 0.04 0.20 0.45 0.15

输出样例:

0.01,0.05,0.25,0.70,0.85

#include <bits/stdc++.h>
using namespace std;
int main() {
	double a[5];
	double b[5];
	for (int i = 0; i < 5; i++) {
		cin >> a[i];
	}
	b[0] = a[0];
	for (int i = 1; i < 5; i++) {
		b[i] = a[i] + b[i - 1];
	}
	printf("%.2f,%.2f,%.2f,%.2f,%.2f", b[0], b[1], b[2], b[3], b[4]);
	return 0;
}

 7-3 回文数 - C/C++ 数组及字符串

数字121从左往右读与从右往左读是一样的，这种数称为回文数。请使用for循环设计一个程序，
找出>=0并且<=n的全部回文数。

注意：单个的数字0，数字1，... 数字9也认为是回文数。

提示：将一个整数转换成一个C风格字符串可以通过sprintf()函数完成。

输入格式:

n

输出格式:

多行输出，一行一个数

输入样例:

13

输出样例:

0
1
2
3
4
5
6
7
8
9
11

#include <bits/stdc++.h>
using namespace std;
int ishuiwen(int a) {
	int reserved = 0;
	int num = a;
	while (num > 0) {
		reserved = reserved * 10 + num % 10;
		num /= 10;
	}
	return reserved == a;
}
void print_all(int n) {
	for (int i = 0; i <= n; i++) {
		if (ishuiwen(i)) {
			printf("%d\n", i);
		}
	}
}
int main() {
	int n;
	scanf("%d",&n);
	print_all(n);
 
	return 0;
}
 

 7-4 进制转换 - C/C++ 数组及字符串

（进制转换）从键盘读入一个表示16进制整数的字符串，逐一将全部16进制位乘以其位权并求和，将该字符串转换成整数并按10进制输出其值。

输入格式:

符合十六进制格式要求的字符串

输出格式:

对应的十进制整数值

输入样例:

7Ba1

输出样例:

31649

 

#include <bits/stdc++.h>
using namespace std;
 
int trans(char a[]) {
	int len_a = strlen(a);
	int t=0;
	int wei=0;
	int base = 1;
	for (int i = len_a-1; i >=0; i--) {
		if (a[i] >= '0' && a[i] <= '9') {
			wei = a[i] - '0';
		}
		else if (a[i] >= 'A' && a[i] <= 'F') {
			wei = a[i] - 'A' + 10;
		}
		else if (a[i] >= 'a' && a[i] <= 'f') {
			wei = a[i] - 'a' + 10;
		}
		t += wei * base;
		base *= 16;
	}
	return t;
}
int main() {
	char a[100];
	cin >> a;
	cout << trans(a);
	return 0;
}

 7-5 凯撒密码 - C/C++ 数组及字符串

 

（凯撒密码）是一个简单的替换加密技术，它简单地将明文字符串中的全部字母在字母表上偏移n项。当n大于0时，表示向后偏移，小于0则表示向前偏移。当n为2时，字母A变C，c变e，y变a, Z变B；当n为-2时，字母A变Y，c变a，y变w，Z变X。请编写程序，依次读入明文字符串及整数偏移量n，然后输出加密后的密文字符串。提示：C语言可用gets()函数，C++语言可用getline()函数读入整行字符串。

输入样例:

No One Can Stop Us
2

输出样例:

Encrypted message:Pq Qpg Ecp Uvqr Wu

#include <bits/stdc++.h>
using namespace std;
void trans(char line[],int n) {
	int len = strlen(line);
	char linetrans[100];
	n %= 26;
	for (int i = 0; i < len; i++) {
		if (line[i] >= 'A' && line[i] <= 'Z') {
			if (line[i] - 'A' + n>=0&&line[i] - 'A' + n < 26)
				linetrans[i] = line[i] + n ;
			else
				linetrans[i] = line[i] + n - 26;
		}
		else if (line[i] >= 'a' && line[i] <= 'z') {
			if (line[i] - 'a' + n >= 0 && line[i] - 'a' + n < 26)
				linetrans[i] = line[i] + n ;
			else
				linetrans[i] = line[i] + n - 26;
		}
		else {
			linetrans[i] = line[i];
		}
		cout<<linetrans[i];
	}
	return ;
}
int main() {
	char line[100];
	int n;
	cin.getline(line,100);
	cin >> n;
	cout << "Encrypted message:";
	trans(line, n);
	return 0;
}

 7-6 矩阵运算 - C/C++ 数组及字符串

读入一个正整数n（1≤n≤20），再读入n行n列共n²个整数并存入由二维数组表示的方阵m；计算并输出每一行的元素和；计算并输出每一列的元素和；计算并输出对角线上的元素和（即所有m[i][i]的和, i取0~n-1）。

输入样例:

3
1 2 3
4 5 6
7 8 10

输出样例:

sum of row 1 = 6.
sum of row 2 = 15.
sum of row 3 = 25.
sum of column 1 = 12.
sum of column 2 = 15.
sum of column 3 = 19.
sum of elements on the diagonal = 16.

#include <bits/stdc++.h>
using namespace std;
int n;
int firm[20][20];
void acum(int n, int firm[][20]) {
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum = 0;
		for (int j = 0; j < n; j++) {
			sum += firm[i][j];
		}
		cout << "sum of row " << i + 1 << " = " << sum << "." << endl;
	}
	for (int i = 0; i < n; i++) {
		sum = 0;
		for (int j = 0; j < n; j++) {
			sum += firm[j][i];
		}
		cout << "sum of column " << i + 1 << " = " << sum << "." << endl;
	}
	sum = 0;
	for (int i = 0; i < n; i++) {
		sum += firm[i][i];
	}
	cout << "sum of elements on the diagonal = " << sum << ".";
	return;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> firm[i][j];
		}
	}
	acum(n, firm);
	return 0;
}

 7-7 百钱买百鸡 - C/C++ 数组及字符串

我国古代数学家张丘建在《算经》一书中提出了下述数学问题：
鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

请使用三重或者二重循环求解N块钱买N只鸡的问题：计算并输出所有可行的解（须按公鸡，母鸡，小鸡递增排序），以及全部可行解的数量。

输入格式:

整数N

输出格式:

公鸡数,母鸡数,小鸡数 （第1个可行解）
公鸡数,母鸡数,小鸡数 （第2个可行解）
...
公鸡数,母鸡数,小鸡数 （最后1个可行解）
Solution count: 可行解个数.

输入样例:

100

输出样例:

0,25,75
4,18,78
8,11,81
12,4,84
Solution count: 4.

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int sum=0;
    for(int i=0;i<n/5;i++)
    {
        for(int j=0;j<n/3;j++)
        {
            for(int r=0;r<n*3;r+=3)
            {
                (i+j+r==n&&5*i+3*j+r/3==n)?(sum++):1;
                (i+j+r==n&&5*i+3*j+r/3==n)?(printf("%d,%d,%d\n",i,j,r)):1;
            }
        }
    }
    cout<<"Solution count: "<<sum<<"."<<endl;
    return 0;
}
 

 7-8 最长对称子串

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

输入格式：

输入在一行中给出长度不超过1000的非空字符串。

输出格式：

在一行中输出最长对称子串的长度。

输入样例：

Is PAT&TAP symmetric?

输出样例：

11

#include <iostream>
#include <string>
using namespace std;
 
int longestPalindrome(string s) {
    int n = s.length();
    int maxLength = 1;
    int start = 0;
    bool dp[n][n] = {false};
 
    // 所有长度为1的子串都是对称的
    for(int i = 0; i < n; i++)
        dp[i][i] = true;
 
    // 判断长度为2的子串是否对称
    for(int i = 0; i < n - 1; i++) {
        if(s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            maxLength = 2;
            start = i;
        }
    }
 
    // 判断长度大于2的子串是否对称
    for(int k = 3; k <= n; k++) {
        for(int i = 0; i < n - k + 1; i++) {
            int j = i + k - 1;
 
            if(dp[i + 1][j - 1] && s[i] == s[j]) {
                dp[i][j] = true;
 
                if(k > maxLength) {
                    maxLength = k;
                    start = i;
                }
            }
        }
    }
 
    return maxLength;
}
 
int main() {
    string str;
    getline(cin, str);
    int result = longestPalindrome(str);
    cout << result << endl;
 
    return 0;
}