avatar

目录
PTA a题

算法原理要花时间好好摸一下,推荐一个大佬的数据结构算法详解
手把手撕LeetCode题目,扒各种算法套路的裤子

基础编程题目集

6-1 简单输出整数 (10分)

本题要求实现一个函数,对给定的正整数 N,打印从1到N的全部正整数。
函数接口定义:

c
1
void PrintN ( int N );

其中N是用户传入的参数。该函数必须将从1到N的全部正整数顺序打印出来,每个数字占1行。

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>

void PrintN ( int N );

int main ()
{
int N;

scanf("%d", &N);
PrintN( N );

return 0;
}

/* 你的代码将被嵌在这里 */
Code
1
2
3
4
5
6
输入样例:
3
输出样例:
1
2
3

解答

c
1
2
3
4
5
6
void PrintN ( int N ) {
int i;
for (i=1; i<=N; i++) {
printf("%d\n", i);
}
}

6-2 多项式求值 (15分)

本题要求实现一个函数,计算阶数为 n,系数为a[0]a[n]的多项式
$$f(x)=\sum_{i=0}^n(a[i]×x^i
)$$在x点的值。

函数接口定义:

c
1
double f( int n, double a[], double x );

其中 n 是多项式的阶数,a[] 中存储系数,x 是给定点。函数须返回多项式 f(x) 的值。

Code
1
2
3
4
5
输入样例:
2 1.1
1 2.5 -38.7
输出样例:
-43.1

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

#define MAXN 10 // 定义最多10个a项

double f( int n, double a[], double x );

int main()
{
int n, i;
double a[MAXN], x;
// double 就是比 float 精度更高的浮点数表示类型
scanf("%d %lf", &n, &x);
// %lf 双精度浮点型数据的输入格式控制符
for ( i=0; i<=n; i++ )
scanf("%lf", &a[i]);
printf("%.1f\n", f(n, a, x));
return 0;
}

/* 你的代码将被嵌在这里 */

解答:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
double f( int n, double a[], double x ) {
double sum = a[0];
double res = 1.0;
int i;
for(i=1; i<=n; ++i) {
/*
int i = 3 ;
a = i++; -> a=3 -> 先让a变成i的值,再让i加1
b = ++i; -> b=4 -> 先让i加1, 再让b变成i的值
*/
res *= x; // res = x, x^2, x^3... // res = res*x
sum += a[i] * res; // sum = sum + a[i]*res
/*
printf("i=: %d", i);
echo "i=1 / i=2"
*/
}
return sum;
}

6-3 简单求和 (10分)

本题要求实现一个函数,求给定的 N 个整数的和。
函数接口定义:

c
1
int Sum ( int List[], int N );

其中给定整数存放在数组 List[] 中,正整数N是数组元素个数。该函数须返回N个 List[] 元素的和。

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

#define MAXN 10

int Sum ( int List[], int N );

int main ()
{
int List[MAXN], N, i;

scanf("%d", &N);
for ( i=0; i<N; i++ )
scanf("%d", &List[i]);
printf("%d\n", Sum(List, N));

return 0;
}

/* 你的代码将被嵌在这里 */

然后是输入输出样式:

Code
1
2
3
4
5
输入
3
12 34 -5
输出
41

解答

c
1
2
3
4
5
6
7
8
int Sum ( int List[], int N ) {
int i;
int sum =0;
for ( i=0; i<N; i++ ) {
sum += List[i];
}
return sum;
}

6-4 求自定类型元素的平均 (10分)

本题要求实现一个函数,求N个集合元素 S[] 的平均值,其中集合元素的类型为自定义的 ElementType
函数接口定义:

c
1
ElementType Average( ElementType S[], int N );

其中给定集合元素存放在 数组S[]中,正整数N是数组元素个数。该函数须返回N个 S[]元素的平均值,其值也必须是ElementType类型

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

#define MAXN 10
typedef float ElementType;

ElementType Average( ElementType S[], int N );

int main ()
{
ElementType S[MAXN];
int N, i;

scanf("%d", &N);
for ( i=0; i<N; i++ )
scanf("%f", &S[i]);
printf("%.2f\n", Average(S, N));

return 0;
}

/* 你的代码将被嵌在这里 */

然后是输入输出样式:

Code
1
2
3
4
5
输入
3
12.3 34 -5
输出
13.77

解答

c
1
2
3
4
5
6
7
8
9
ElementType Average( ElementType S[], int N ){
int i;
ElementType sum, average;
for (i=0; i<N; i++) {
sum += S[i];
}
average = sum/N;
return average;
}

6-5 求自定类型元素的最大值 (10分)

本题要求实现一个函数,求N个集合元素 S[] 中的最大值,其中集合元素的类型为自定义的 ElementType

函数接口定义:

c
1
ElementType Max( ElementType S[], int N );

其中给定集合元素存放在 数组S[] 中,正整数N是数组元素个数。该函数须返回N个S[]元素中的最大值,其值也必须是 ElementType类型

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

#define MAXN 10
typedef float ElementType;

ElementType Max( ElementType S[], int N );

int main ()
{
ElementType S[MAXN];
int N, i;

scanf("%d", &N);
for ( i=0; i<N; i++ )
scanf("%f", &S[i]);
printf("%.2f\n", Max(S, N));

return 0;
}

/* 你的代码将被嵌在这里 */

然后是输入输出样式:

Code
1
2
3
4
5
输入
3
12.3 34 -5
输出
34.00

解答

c
1
2
3
4
5
6
7
8
9
10
ElementType Max( ElementType S[], int N ) {
int i;
ElementType max = S[0];
for(i=0; i<N; i++) {
if (max < S[i]) {
max = S[i];
}
}
return max;
}

6-6 求单链表结点的阶乘和 (15分)

本题要求实现一个函数,求 单链表L 结点的阶乘和。这里默认所有结点的值非负,且题目保证结果在 int 范围内。
函数接口定义:

c
1
int FactorialSum( List L );

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <stdlib.h>

typedef struct Node *PtrToNode;
struct Node {
int Data; /* 存储结点数据 */
PtrToNode Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

int FactorialSum( List L );

int main()
{
int N, i;
List L, p;
// 定义2个链表

scanf("%d", &N);
L = NULL;
// 赋初值为 Null
for ( i=0; i<N; i++ ) {
p = (List)malloc(sizeof(struct Node));
// 申请node变量对应大小的内存
scanf("%d", &p->Data);
p->Next = L; L = p;
}
printf("%d\n", FactorialSum(L));

return 0;
}

/* 你的代码将被嵌在这里 */

然后是输入输出样式:

Code
1
2
3
4
5
6
7
输入
3
5 3 6
输出
846

阶乘 5!+3!+6!

解答

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int FactorialSum( List L ){
int sum = 0, i;
List p = L;
// L 赋值给 p, p 变成 null, L不变
while(p) {
int n = 1;
for(i = 1; i <= p->Data; i++){
n *= i; // n = n*i
}
sum += n;
p = p->Next;
// p->next 赋值给 p
}
return sum;
}

6-7 统计某类完全平方数 (20分)

本题要求实现一个函数,判断任一给定整数N是否满足条件:它是完全平方数,又至少有两位数字相同,如144、676等。
函数接口定义:

c
1
int IsTheNumber ( const int N );

其中 N 是用户传入的参数。如果 N 满足条件,则该函数必须返回1,否则返回0。

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <math.h>

int IsTheNumber ( const int N );

int main()
{
int n1, n2, i, cnt;

scanf("%d %d", &n1, &n2);
cnt = 0;
for ( i=n1; i<=n2; i++ ) {
if ( IsTheNumber(i) )
cnt++;
}
printf("cnt = %d\n", cnt);

return 0;
}

/* 你的代码将被嵌在这里 */

然后是输入输出样式:

Code
1
2
3
4
输入
105 500
输出
cnt = 6

解答

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int IsTheNumber ( const int N ) {
int a, temp[500], count=0, i, n=N;
if (N<=0) { // 输入值为负数
return 0;
}
a = (int)sqrt(N); // 开根号
// 强制转换整型
if (a*a==N) {
// 判断是否为完全平方数
while(n>0) {
temp[count] = n%10; // 取个位
n = n/10; // 取是百十位
for(i=0; i<count; i++) {
if (temp[count] == temp[i]) {
// 存在与之前取出的数字相同的返回为 1
return 1;
}
}
count += 1; // count = count + 1;
}
return 0;
}
return 0;
}

6-8 简单阶乘计算 (10分)

本题要求实现一个计算非负整数阶乘的简单函数。
函数接口定义:

c
1
int Factorial( const int N );

其中 N 是用户传入的参数,其值不超过12。如果 N 是非负整数,则该函数必须返回N的阶乘,否则返回0。

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

int Factorial( const int N );

int main()
{
int N, NF;

scanf("%d", &N);
NF = Factorial(N);
// 阶乘函数 Factorial(5) = 5!
if (NF) printf("%d! = %d\n", N, NF);
else printf("Invalid input\n");

return 0;
}

/* 你的代码将被嵌在这里 */

然后是输入输出样式:

Code
1
2
3
4
输入
5
输出
5! = 120

解答

c
1
2
3
4
5
6
7
8
9
10
11
12
13
int Factorial( const int N ) {
int i, sum=1;
if (N<0) {
return 0;
}
if (N>12) {
return 0;
}
for (i=1; i<=N; i++) {
sum *= i;
}
return sum;
}

6-9 统计个位数字 (15分)

本题要求实现一个函数,可统计任一整数中某个位数出现的次数。例如-21252中,2出现了3次,则该函数应该返回3。
函数接口定义:

c
1
int Count_Digit ( const int N, const int D );

其中 ND 都是用户传入的参数。 N 的值不超过int的范围;D是[0, 9]区间内的个位数。函数须返回N中D出现的次数。

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

int Count_Digit ( const int N, const int D );

int main()
{
int N, D;

scanf("%d %d", &N, &D);
printf("%d\n", Count_Digit(N, D));
return 0;
}

/* 你的代码将被嵌在这里 */

然后是输入输出样式:

Code
1
2
3
4
输入
-21252 2
输出
3

解答

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Count_Digit ( const int N, const int D ){
int M=N,cnt=0;
if ( N==0 && D==0 )
return 1;

if ( N<0 ) {
M = -N;
}

while( M!=0 ) {
if ( D == M%10 ) // M 除以10的余数(求当前个位的数字)
cnt++;
M/=10; // M 减少最后一位
}
return cnt;
}

6-10 阶乘计算升级版 (20分)

本题要求实现一个打印非负整数阶乘的函数。
函数接口定义:

c
1
void Print_Factorial ( const int N );

其中 N 是用户传入的参数,其值不超过 1000。如果 N 是非负整数,则该函数必须在一行中打印出 N! 的值,否则打印“Invalid input”

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

void Print_Factorial ( const int N );

int main()
{
int N;

scanf("%d", &N);
Print_Factorial(N);
return 0;
}

/* 你的代码将被嵌在这里 */

然后是输入输出样式:

Code
1
2
3
4
输入
15
输出
1307674368000

解答

易错点有2个

  1. 当N过大时,long int 也无法满足解的要求
  2. 用数组存放结果时,要注意 进位 在进行最高位计算完毕后,进位可能是多位数;结果在数组中存放的是0~k-1位且高位在后,低位在前
c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void Print_Factorial ( const int N ) {
int i;
if(N<0) {
printf("Invalid input");
} else {
long int sum=1;
if(N<=12) {
for(i=1; i<=N; i++) {
sum *= i;
}
printf("%ld",sum);
}
else if (N > 12 && N <= 1000) {
int sum[3000] = {0};
/* 确保保存最终运算结果的数组足够大:
1-9相乘最多有9位,10-99相乘最多有2*90=180位
100-999相乘最多有3*900=2700位,1000是4*1=4位
总计2893位 */

int temp, i, j;
int k = 1; // 位数
int n = 0; // 进位
sum[0] = 1; //将结果先初始化为1
for(i=2;i<=N;i++) { //开始阶乘,阶乘元素从2开始
//和平时乘法方法相同,将临时结果的每位与阶乘元素相乘
for(j=0;j<k;j++) {

temp = sum[j]*i + n;
//相应阶乘中的一项与当前所得临时结果的某位相乘(加上进位)

sum[j] = temp%10;
//更新临时结果的位上信息

n = temp/10;
//看是否有进位

if(n!=0 && j==k-1){ //如果有进位
k++; //处理最后进位为两位
}
}
}
for(i=k-1;i>=0;i--) {
printf("%d",sum[i]);
}
}
}
}

因为long数据类型表示的数字范围到 2147483647
12!正好是9位数,所以从12为分界点

采用数组方法存储,设置进位、位数、临时值。

临时值一定要每一位都与第i个元素相乘。


6-11 求自定类型元素序列的中位数 (25分)

本题要求实现一个函数,求 N 个集合元素 A[] 的中位数,即序列中第⌊(N+1)/2⌋大的元素。其中集合元素的类型为自定义的 ElementType
函数接口定义:

c
1
ElementType Median( ElementType A[], int N );

其中给定集合元素存放在数组A[]中,正整数N是数组元素个数。该函数须返回N个A[]元素的中位数,其值也必须是 ElementType类型。

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

#define MAXN 10
typedef float ElementType;

ElementType Median( ElementType A[], int N );

int main ()
{
ElementType A[MAXN];
int N, i;

scanf("%d", &N);
for ( i=0; i<N; i++ )
scanf("%f", &A[i]);
printf("%.2f\n", Median(A, N));

return 0;
}

/* 你的代码将被嵌在这里 */

然后是输入输出样式:

Code
1
2
3
4
5
输入
3
12.3 34 -5
输出
12.30

解答

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
ElementType Median( ElementType A[], int N ) {
ElementType temp;
for(int gap=N/2; gap>0; gap=gap/2) {
//gap是每次排序分组的间隔,每次间隔缩小1/2

for(int i=gap; i<N; i++) {
//相当于在同一组内采用直接插入排序

for(int j=i-gap; j>=0 && A[j]>A[j+gap]; j=j-gap) {
//如果同一组内前一个元素大于相隔gap个位置的元素,则两者交换位置
temp = A[j];
A[j] = A[j+gap];
A[j+gap] = temp;
}
}
}
return A[N/2]; // 返回中间元素
}

/*
input:
5
5 2 1 3 6
output:
i=2, gap=2, j=0
temp: 5.00
A[j]: 1.00
A[j+gap]: 5.00
i=3, gap=1, j=2
temp: 5.00
A[j]: 3.00
A[j+gap]: 5.00
3.00
*/

6-12 判断奇偶性 (10分)

本题要求实现判断给定整数奇偶性的函数。
函数接口定义:

c
1
int even( int n );

其中 n 是用户传入的整型参数。当 n为偶数 时,函数返回1;n为奇数 时返回0。注意:0是偶数。

裁判测试程序样例:

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

int even( int n );

int main()
{
int n;

scanf("%d", &n);
if (even(n))
printf("%d is even.\n", n);
else
printf("%d is odd.\n", n);

return 0;
}

/* 你的代码将被嵌在这里 */

然后是输入输出样式:

Code
1
2
3
4
5
6
输入
-6
5
输出
-6 is even.
5 is odd.

解答

c
1
2
3
4
5
6
7
int even( int n ) {
return !(n%2);
/* N除2取余数,将余数值的非返回即成立
3%2 = 1
6%2 = 0
*/
}

6-13 折半查找 (15分)

给一个严格递增数列,函数 int Search_Bin(SSTable T, KeyType k) 用来二分地查找k在数列中的位置。
函数接口定义:

c++
1
int  Search_Bin(SSTable T, KeyType k)

其中T是有序表,k是查找的值。

裁判测试程序样例:

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;

#define MAXSIZE 50
typedef int KeyType;

typedef struct
{ KeyType key;
} ElemType;

typedef struct
{ ElemType *R;
int length;
} SSTable;

void Create(SSTable &T)
{ int i;
T.R=new ElemType[MAXSIZE+1];
cin>>T.length;
for(i=1;i<=T.length;i++)
cin>>T.R[i].key;
}

int Search_Bin(SSTable T, KeyType k);

int main ()
{ SSTable T; KeyType k;
Create(T);
cin>>k;
int pos=Search_Bin(T,k);
if(pos==0) cout<<"NOT FOUND"<<endl;
else cout<<pos<<endl;
return 0;
}

/* 请在这里填写答案 */

然后是输入输出样式:

Code
1
2
3
4
5
6
7
8
9
10
第一行输入一个整数n,表示有序表的元素个数
接下来一行n个数字,依次为表内元素值。
然后输入一个要查找的值。
5
1 3 5 7 9
7

输出这个值在表内的位置
如果没有找到,输出"NOT FOUND"。
4

解答

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int  Search_Bin(SSTable T, KeyType k) {
int left = 1; //左边起始点
int right = T.length; // 链表最后一位
int mid;
while (left < right) {
mid = (left + right) / 2;
if(T.R[mid].key == k) { // 找到k, k为T.R[mid].key
return mid; // 返回mid即k的位置
}
if(T.R[mid].key > k) { // k在中间偏左
right = mid-1; // 使右边界收缩到 中间左一
} else { // k在中间偏右
left = mid+1; // 使左边界收缩到 中间右一
}
//重复以上操作,直至左右边界相遇
}
return 0;
}
文章作者: 晓黑
文章链接: https://www.suk1.top/2020/03/02/PTAbasic/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Manayakko - 微笑才是王道
打赏
  • 微信
    微信