PTA 基础编程题目集 题解
PTA 基础编程题目集 题解
文章目录
- PTA 基础编程题目集 题解
函数类
6-1 简单输出整数 (10 分)
原题链接
题意：
本题要求实现一个函数，对给定的正整数N，打印从1到N的全部正整数。
函数接口定义：
void PrintN ( int N );其中N是用户传入的参数。该函数必须将从1到N的全部正整数顺序打印出来，每个数字占1行。
裁判测试程序样例：
#include void PrintN ( int N );int main (){ int N; scanf("%d", &N); PrintN( N ); return 0;}/* 你的代码将被嵌在这里 */输入样例：
3输出样例：
123打印从1到N，直接for 循环输出
void PrintN ( int N ) { for(int i=1;i<=N;++i) printf("%d\n",i); }
6-2 多项式求值 (15 分)
原题链接
题意：
本题要求实现一个函数，计算阶数为n，系数为a[0] … a[n]的多项式
在x点的值。
函数接口定义：
double f( int n, double a[], double x );其中n是多项式的阶数，a[]中存储系数，x是给定点。函数须返回多项式f(x)的值。
裁判测试程序样例：
#include #define MAXN 10double f( int n, double a[], double x );int main(){ int n, i; double a[MAXN], x; scanf("%d %lf", &n, &x); for ( i=0; i<=n; i++ ) scanf("%lf", &a[i]); printf("%.1f\n", f(n, a, x)); return 0;}/* 你的代码将被嵌在这里 */输入样例：
2 1.11 2.5 -38.7输出样例：
-43.1思路：
- 因为题目要求的是 连加的结果，可以用 for 循环暴力解出
- 观察公式中，存在幂的关系，所以可以用 pow 函数，但用pow函数的时候，需要加上头文件 #include 才能使用
AC代码如下：
double f( int n, double a[], double x ){ double ret = 0,xi; for(int i =0;i<=n;++i) { xi = pow(x,i); ret += a[i]*xi; } return ret; // （1） 自定义的double型函数，所以要用 return 返回一个结果 }
6-3 简单求和 (10 分)
原题链接
题意：
本题要求实现一个函数，求给定的N个整数的和。
函数接口定义：
int Sum ( int List[], int N );其中给定整数存放在数组List[]中，正整数N是数组元素个数。该函数须返回N个List[]元素的和。
裁判测试程序样例：
#include #define MAXN 10int 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;}/* 你的代码将被嵌在这里 */输入样例：
312 34 -5输出样例：
41解题思路：
题目求和，用 for 循环枚举法，直接加
AC代码：
int Sum ( int List[], int N ){ long long int sum = 0; for(int i = 0;i<N;++i) { sum += List[i]; } return sum；}
6-4 求自定类型元素的平均 (10 分)
原题链接
题意：
本题要求实现一个函数，求N个集合元素S[]的平均值，其中集合元素的类型为自定义的ElementType。
函数接口定义：
ElementType Average( ElementType S[], int N );其中给定集合元素存放在数组S[]中，正整数N是数组元素个数。该函数须返回N个S[]元素的平均值，其值也必须是ElementType类型。
裁判测试程序样例：
#include #define MAXN 10typedef 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;}/* 你的代码将被嵌在这里 */输入样例：
312.3 34 -5输出样例：
13.77解题思路：
- 求平均值，先求和，再除总数；
- 求和思路与 6-3 思路相同，而在返回时，直接返回 总和/总个数 ，当然，也可以先算出平均值再返回平均值。
AC代码：
ElementType Average( ElementType S[], int N ){ ElementType pj = 0; for(int i = 0;i<N;++i) { pj += S[i]; } return pj/N; }
6-5 求自定类型元素的最大值 (10 分)
原题链接
题意：
本题要求实现一个函数，求N个集合元素S[]中的最大值，其中集合元素的类型为自定义的ElementType。
函数接口定义：
ElementType Max( ElementType S[], int N );其中给定集合元素存放在数组S[]中，正整数N是数组元素个数。该函数须返回N个S[]元素中的最大值，其值也必须是ElementType类型。
裁判测试程序样例：
#include #define MAXN 10typedef 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;}/* 你的代码将被嵌在这里 */输入样例：
312.3 34 -5输出样例：
34.00
解题思路：
要比较大小，不妨挨个挨个比较 ，可以先定义一个变量，让这个变量的初始值无限小，如 -100860 ，而只要在比较中，发现有比这个变量大的，就将这个变量的值等于这个值。最后直接输出，这个变量的值，即可。
AC代码：
ElementType Max( ElementType S[], int N ) { ElementType max = -100860; for(int i =0;i<N;++i) { if(max < S[i]) max = S[i]; } return max; }
6-6 求单链表结点的阶乘和 (15 分)*
原题链接
题意：
本题要求实现一个函数，求单链表L结点的阶乘和。这里默认所有结点的值非负，且题目保证结果在int范围内。
函数接口定义：
int FactorialSum( List L );
其中单链表List的定义如下：
typedef struct Node *PtrToNode;struct Node { int Data; /* 存储结点数据 */** PtrToNode Next; /* 指向下一个结点的指针 */};typedef PtrToNode List; /* 定义单链表类型 */
裁判测试程序样例：
#include #include 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; scanf("%d", &N); L = NULL; for ( i=0; iData); p->Next = L; L = p; } printf("%d\n", FactorialSum(L)); return 0;}/* 你的代码将被嵌在这里 */输入样例：
35 3 6输出样例：
846解题思路：
- 本题求阶乘和 其实和求链表内元素总和差不多 遍历就成
AC代码：
int FactorialSum( List L ){int s=0;int i,u;//i存放当前阶乘值 s存放总和 u存放当前元素值 List p=L; // (1) //为方便表示创建一个p 其地址与L相同 for (;p != NULL;) {u=p->Data;i=1;//就是遍历元素的时候 顺带来个循环求出阶乘 while (u) {i*=u;u--;}s+=i;p=p->Next; 然后指针指向下一个节点 使遍历能够进行 }return s;}- 对不会遍历链表的同学 做出解释
- 链表 由节点组成 一个节点内通常有一个值和一个指向下一个节点的指针
- 本题 Data是值的名字 Next是下一个节点的指针名字
- L->Data L->Next 才能访问到值和指针 （L是本题的链表首地址）
- L=L->Next 就是使当前地址变为原先的下一个节点的地址
- 这就是遍历的要点所在
6-7 统计某类完全平方数 (20 分)
原题链接
题意：
本题要求实现一个函数，判断任一给定整数N是否满足条件：它是完全平方数，又至少有两位数字相同，如144、676等。
函数接口定义：
int IsTheNumber ( const int N );其中N是用户传入的参数。如果N满足条件，则该函数必须返回1，否则返回0。
裁判测试程序样例：
#include #include 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;}/* 你的代码将被嵌在这里 */输入样例：
105 500输出样例：
cnt = 6解题思路：
- 首先，要先判断输入的数是否是完全平方数 ，要满足 这个数开方后，相乘是否等于原来这个数 ，如果符合，则进行下一步；否则，直接结束判断。
- 判断是否存在，有两个数相同的情况，直接用 桶排序 进行记录，如果读取到至少存在两个，则符合题意，不必继续进行计算，此时直接返回即可。
AC代码：
int IsTheNumber ( const int N ){ int b = 0; int c = sqrt(N); // c 表示 N 开放后的数 if(c*c != N)// (1) 判断是否为完全平方数 { return 0; } int a[10] = {0}; // (2) 桶数组，在进行统计时，先全部初始化 int sum = N，i; while(sum) { i = sum %10; // （3）i 表示 sum 的最后一位数 a[i]++; if(a[i]==2) // （4）如果其中一个数出现两次，则符合题意，直接输出 { b = 1; break; } sum = sum/10; // （5） 见结论 } return b; }- （3） 要求出一个数的个位数，则令这个数 %10 即可求出最后一位数。
如果要 求出 十分位的数 则 先除10 再 %10；
总结：
求个位数上的数： N /1%10 （此时 ， 1 可以省略）求十位数上的数： N/10%10求百位数上的数 ： N/100%10以此类推......
6-8 简单阶乘计算 (10 分)
原题链接
题意
本题要求实现一个计算非负整数阶乘的简单函数。
函数接口定义：
int Factorial( const int N );其中N是用户传入的参数，其值不超过12。如果N是非负整数，则该函数必须返回N的阶乘，否则返回0。
裁判测试程序样例：
#include int Factorial( const int N );int main(){ int N, NF; scanf("%d", &N); NF = Factorial(N); if (NF) printf("%d! = %d\n", N, NF); else printf("Invalid input\n"); return 0;}/* 你的代码将被嵌在这里 */输入样例：
5输出样例：
5! = 120
解题思路：
- 一个数，小于0 ，则不存在阶乘
- 0！ = 1、1！ = 1；
- 大于1的数，枚举法，用 for 循环 ，挨个挨个“点名” ，乘上去。这里用，ret 来表示最后的结果，为了防止结果溢出，直接用 long long int 类型，而非 int 类型。
AC代码：
int Factorial( const int N ){ if(N<0) return 0; if(N == 0||N == 1) return 1; long long int ret = 1; for(int i =2;i<=N;++i) { ret *= i; } return ret;}
6-9 统计个位数字 (15 分)
原题链接
题意：
本题要求实现一个函数，可统计任一整数中某个位数出现的次数。例如-21252中，2出现了3次，则该函数应该返回3。
函数接口定义：
int Count_Digit ( const int N, const int D );其中N和D都是用户传入的参数。N的值不超过int的范围；D是[0, 9]区间内的个位数。函数须返回N中D出现的次数。
裁判测试程序样例：
#include 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;}/* 你的代码将被嵌在这里 */输入样例：
-21252 2输出样例：
3
解题思路：
- 用测试用例可知 ，-2也是2，所以不妨都当成整数来算，遇到负数，直接转换为正数。
- 挨个挨个的找出它每个位上的数，结论详见 6-7 如果这个数，是要记录的数，则计数器 tmp 加一
AC代码：
int Count_Digit ( const int N, const int D ){ int sum = N,tmp = 0,i; if(N < 0) sum = -N; if(N == 0&&D == 0)//（1） 特殊情况，特殊判断 return tmp = 1; while(sum) { i = sum % 10; if(i == D) tmp++; sum = sum/10; } return tmp;}
6-10 阶乘计算升级版 (20 分)*
原题链接
题意：
本题要求实现一个打印非负整数阶乘的函数。
函数接口定义：
void Print_Factorial ( const int N );其中N是用户传入的参数，其值不超过1000。如果N是非负整数，则该函数必须在一行中打印出**N!**的值，否则打印“Invalid input”。
裁判测试程序样例：
#include void Print_Factorial ( const int N );int main(){ int N; scanf("%d", &N); Print_Factorial(N); return 0;}/* 你的代码将被嵌在这里 */输入样例：
15输出样例：
1307674368000
解题思路：
- 同 6-8 的题解不同，因为这题的N<=1000，而 15！以后 会溢出，因此 无法用 6-8的传统做法，需要用数组。
- 这种方法的原理就是将数字的每一位拆分出来存到数组，在求阶乘时，每一次乘法都分解为数组的每一位乘这个数，例如：
- 在定义 a[3010] 时，要先将 a[0] 初始化为 a[0] = 1 ；
- 1! = 1，a[0] = a[0] * 1 % 10 = 1;
- 2! = 2，a[0] = a[0] * 2 % 10 = 2;
- 3! = 6，a0] = a[0] * 3 % 10 = 6；
- 4! = 24, a[0] = a[0 ] *4 % 10 = 4，而此时产生了进位，进位为2，所以a[1]=进位=2；
- 5! = 120，a[0] = a[0] * 5 % 10 = 0 ，进位为2，a[1]=(a[1]*5+进位)%10=2；进位为1，a[2]=进位=1；得到5的阶乘为120。
AC代码：
void Print_Factorial ( const int N ) { if(N<0) printf("Invalid input"); else { int a[3010]={0},j,n=N; //数组 a[3010] 记录各个位上的数字，全初始化为0 a[0]=1;//个位初始化为1 int l=0,c = 0;//l,记录结果的位数共有多少位，便于结果输出 ; c,低位向高位的进位 for(int i=2;i<=n;i++) { for(j=0;j=0;l--)//因为数组按照从地位到高位的方式存储结果，所以需要逆向输出结果 printf("%d",a[l]); }}
6-11 求自定类型元素序列的中位数 (25 分)
原题链接
题意：
本题要求实现一个函数，求N个集合元素A[]的中位数，即序列中第⌊(N+1)/2⌋大的元素。其中集合元素的类型为自定义的ElementType。
函数接口定义：
ElementType Median( ElementType A[], int N );其中给定集合元素存放在数组A[]中，正整数N是数组元素个数。该函数须返回N个A[]元素的中位数，其值也必须是ElementType类型。
裁判测试程序样例：
#include #define MAXN 10typedef 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;}/* 你的代码将被嵌在这里 */输入样例：
312.3 34 -5输出样例：
12.30
解题思路：
- 首先
AC代码：
6-12 判断奇偶性 (10 分)
原题链接
题意：
本题要求实现判断给定整数奇偶性的函数。
函数接口定义：
int even( int n );其中n是用户传入的整型参数。当n为偶数时，函数返回1；n为奇数时返回0。注意：0是偶数。
裁判测试程序样例：
#include 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;}/* 你的代码将被嵌在这里 */
输入样例1：
-6输出样例1：
-6 is even.输入样例2：
5输出样例2：
5 is odd.
解题思路：
- 由测试样例可知，even是偶数，odd 是奇数。即 当even（）函数，输出的值不为 0 ，则这个数是 偶数，否则 为 奇数；
AC代码：
int even( int n ){ if(n%2) // 偶数 return 0; else return 1;}这里还可以优化：
- 可以用逻辑运算符号 &（位于） 来判断 一个数 的奇偶，效率更高。
- 位与：&：按位与运算，在二进制表示中，两个数当且仅当都为1的时候结果才为1。
即1&1 == 1， 1 & 0 == 0、0&1==0、0&0 == 0。
结论：
奇数&1 == 1。
偶数&1 == 0。
- 此时代码应为：
int even( int n){ if(n&1) return 1; else return 0;}- 因为这个函数是一个非1即0的函数，即非错即正（计算机中，为0，表示错；非0表示 对）。不妨将这个函数 改为 bool 型 函数 ，效率更高。（当然这题因为题目给出的函数已经是 int 类型的了 ，所以无法改.因此这步优化思想在本题不适用）
但对于其他题，同样可以用；
bool even( int n){if(n&1)return 1;else reurn 0;}
6-13 折半查找 (15 分)*
原题链接
题意：
给一个严格递增数列，函数int Search_Bin(SSTable T, KeyType k)用来二分地查找k在数列中的位置。
函数接口定义：
int Search_Bin(SSTable T, KeyType k)其中T是有序表，k是查找的值。
裁判测试程序样例：
#include using namespace std;#define MAXSIZE 50typedef 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;}/* 请在这里填写答案 */输入格式：
第一行输入一个整数n，表示有序表的元素个数，接下来一行n个数字，依次为表内元素值。 然后输入一个要查找的值。
输出格式：
输出这个值在表内的位置，如果没有找到，输出"NOT FOUND"。
输入样例：
51 3 5 7 97输出样例：
4输入样例：
51 3 5 7 910输出样例：
NOT FOUND