PTA 基础编程题目集 题解

输入样例：

3
12.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;
    }

原题链接

题意：
本题要求实现一个函数，求单链表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;
}

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

输入样例：

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 就是使当前地址变为原先的下一个节点的地址
  • 这就是遍历的要点所在

原题链接

题意：
本题要求实现一个函数，判断任一给定整数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
		以此类推......

原题链接

题意
本题要求实现一个计算非负整数阶乘的简单函数。

函数接口定义：

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;
}

原题链接

题意：
本题要求实现一个函数，可统计任一整数中某个位数出现的次数。例如-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;
}

原题链接

题意：
本题要求实现一个打印非负整数阶乘的函数。

函数接口定义：

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]);
    }
}

原题链接

题意：
本题要求实现一个函数，求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

int even( int n );

#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;
}

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

-6

-6 is even.

5

5 is odd.

int even( int n )
{
    if(n%2)            // 偶数  
        return 0;
    else
        return 1;
}

int even( int n)
{
   if(n&1)	
   	return 1;
   else 
   	return 0;
}

bool even( int n)
{
	if(n&1)
		return 1;
	else 
		reurn 0;
}

int  Search_Bin(SSTable T, KeyType 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"<<endl;
   else cout<<pos<<endl;
   return 0;
}

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

5
1 3 5 7 9
7

4

5
1 3 5 7 9
10

NOT FOUND