PTA 基础编程题目集题解

前言：
一枚刚刚起步的计算机萌新，想学好编程，定时发出自己做的题和一些感想，需要改进的地方，望大佬指点。

文章目录

PTA 基础编程题目集题解
- 函数类
- - 6-1 简单输出整数 (10 分)
  - 6-2 多项式求值 (15 分)
  - 6-3 简单求和 (10 分)
  - 6-4 求自定类型元素的平均 (10 分)
  - 6-5 求自定类型元素的最大值 (10 分)
  - 6-6 求单链表结点的阶乘和 (15 分)
  - 6-7 统计某类完全平方数 (20 分)
  - - 总结：
  - 6-8 简单阶乘计算 (10 分)
  - 6-9 统计个位数字 (15 分)
  - 6-10 阶乘计算升级版 (20 分)
  - - 解题思路：
  - 6-11 求自定类型元素序列的中位数 (25 分)
  - 6-12 判断奇偶性 (10 分)
  - - 结论：
  - 6-13 折半查找 (15 分)

函数类
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;
}

输入样例：

输出样例：

1
2
3

打印从1到N，直接for 循环输出

void PrintN ( int N )
    {
        for(int i=1;i<=N;++i)
            printf("%dn",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 10
double 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("%.1fn", f(n, a, x));
    return 0;
}

输入样例：

2 1.1
1 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 10

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

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

    scanf("%d", &N);
    for ( i=0; i 
输入样例： 
3
12 34 -5
 
输出样例： 
41
 
解题思路：
 题目求和，用 for 循环枚举法，直接加 

 
AC代码： 
int Sum ( int List[], int N )
{
    long long int sum = 0;
    for(int i = 0;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 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 
输入样例： 
3
12.3 34 -5
 
输出样例： 
13.77
 
解题思路： 
求平均值，先求和，再除总数；
求和思路与 6-3 思路相同，而在返回时，直接返回 总和/总个数 ，当然，也可以先算出平均值再返回平均值。 
AC代码： 
ElementType Average( ElementType S[], int N )
{
    ElementType pj = 0;
    for(int i = 0;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 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 
输入样例： 
3
12.3 34 -5
 
输出样例： 
34.00
 

 
解题思路：
 要比较大小，不妨挨个挨个比较 ，可以先定义一个变量，让这个变量的初始值无限小，如 -100860 ，而只要在比较中，发现有比这个变量大的，就将这个变量的值等于这个值。最后直接输出，这个变量的值，即可。 

 
AC代码： 
    ElementType Max( ElementType S[], int N )
    {
        ElementType max = -100860;
        for(int i =0;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("%dn", FactorialSum(L));

    return 0;
}


 
输入样例： 
3
5 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 = %dn", 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! = %dn", N, NF);
    else printf("Invalid inputn");

    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("%dn", 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<=l;j++) 
            {
                int temp=a[j]*i+c ;
                a[j]=temp%10;       //该位数上的数
                c =temp/10;         //需要进位的数
            }
            
            while(c) 
            {                       //拓展结果的总位数记录进位的数，直到进位为0
                a[j++]=c %10;       //该位数上的数
                c /=10;             //需要进位的数
                l++;
            }
        }
        for(;l>=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 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 
输入样例： 
3
12.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 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"< 
输入格式：
 第一行输入一个整数n，表示有序表的元素个数，接下来一行n个数字，依次为表内元素值。 然后输入一个要查找的值。 
输出格式：
 输出这个值在表内的位置，如果没有找到，输出"NOT FOUND"。 
输入样例： 
5
1 3 5 7 9
7
 
输出样例： 
4
 
输入样例： 
5
1 3 5 7 9
10
 
输出样例： 
NOT FOUND

PTA 基础编程题目集 题解

C/C++/C#相关栏目本月热门文章

PTA 基础编程题目集题解