PTA基础编程题目集(函数题13)

1、简单输出整数

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

 1 #include <stdio.h>
 2 void PrintN ( int N );
 3 int main ()
 4 {
 5     int N;
 6     scanf("%d", &N);
 7     PrintN( N );
 8     return 0;
 9 }
10 void PrintN ( int N ){
11     for(int i=1; i<=N; ++i)
12         printf("%d
",i);
13 }

2、多项式求值

本题要求实现一个函数，计算阶数为n，系数为a[0] ... a[n]的多项式

 1 #include <stdio.h>
 2 
 3 #define MAXN 10
 4 
 5 double f( int n, double a[], double x );
 6 
 7 int main()
 8 {
 9     int n, i;
10     double a[MAXN], x;
11     
12     scanf("%d %lf", &n, &x);
13     for ( i=0; i<=n; i++ )
14         scanf(“%lf”, &a[i]);
15     printf("%.1f
", f(n, a, x));
16     return 0;
17 }
18 double f( int n, double a[], double x ){
19     double sum = 0;
20     for(int i=0; i<=n; ++i){
21         sum += a[i]*pow(x,i);
22     }
23     return sum;
24 }

3、简单求和

本题要求实现一个函数，求给定的N个整数的和。

 1 #include <stdio.h>
 2 
 3 #define MAXN 10
 4 
 5 int Sum ( int List[], int N );
 6 
 7 int main ()
 8 {
 9     int List[MAXN], N, i;
10 
11     scanf("%d", &N);
12     for ( i=0; i<N; i++ )
13         scanf("%d", &List[i]);
14     printf("%d
", Sum(List, N));
15 
16     return 0;
17 }
18 int Sum ( int List[], int N ){
19     int sum=0;
20     for(int i=0; i<N; ++i)
21         sum += List[i];
22     return sum;
23 }

4、求自定类型元素的平均

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

 1 #include <stdio.h>
 2 
 3 #define MAXN 10
 4 typedef float ElementType;
 5 
 6 ElementType Average( ElementType S[], int N );
 7 
 8 int main ()
 9 {
10     ElementType S[MAXN];
11     int N, i;
12 
13     scanf("%d", &N);
14     for ( i=0; i<N; i++ )
15         scanf("%f", &S[i]);
16     printf("%.2f
", Average(S, N));
17 
18     return 0;
19 }
20 ElementType Average( ElementType S[], int N ){
21     ElementType sum = 0;
22     for(int i=0; i<N; ++i)
23         sum +=S[i];
24     return sum/N;
25 }

5、求自定类型元素的最大值

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

 1 #include <stdio.h>
 2 
 3 #define MAXN 10
 4 typedef float ElementType;
 5 
 6 ElementType Max( ElementType S[], int N );
 7 
 8 int main ()
 9 {
10     ElementType S[MAXN];
11     int N, i;
12 
13     scanf("%d", &N);
14     for ( i=0; i<N; i++ )
15         scanf("%f", &S[i]);
16     printf("%.2f
", Max(S, N));
17 
18     return 0;
19 }
20 ElementType Max( ElementType S[], int N ){
21     ElementType max = S[0];
22     for(int i=1; i<N; ++i)
23         if(max < S[i])
24             max = S[i];
25     return max;
26 }

6、求单链表结点的阶乘和

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

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef struct Node *PtrToNode;
 5 struct Node {
 6     int Data; /* 存储结点数据 */
 7     PtrToNode Next; /* 指向下一个结点的指针 */
 8 };
 9 typedef PtrToNode List; /* 定义单链表类型 */
10 
11 int FactorialSum( List L );
12 
13 int main()
14 {
15     int N, i;
16     List L, p;
17 
18     scanf("%d", &N);
19     L = NULL;
20     for ( i=0; i<N; i++ ) {
21         p = (List)malloc(sizeof(struct Node));
22         scanf("%d", &p->Data);
23         p->Next = L;  L = p;
24     }
25     printf("%d
", FactorialSum(L));
26 
27     return 0;
28 }
29 int FactorialSum( List L ){
30     int sum = 0;
31     while(L)
32     { 
33         int fac=1;
34         for(int i=1; i<=L->Data; ++i) fac *= i;
35         sum += fac;
36         L = L->Next;
37     }
38     return sum;
39 }

7、统计某类完全平方数

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

 1 #include <stdio.h>
 2 #include <math.h>
 3 
 4 int IsTheNumber ( const int N );
 5 
 6 int main()
 7 {
 8     int n1, n2, i, cnt;
 9     
10     scanf("%d %d", &n1, &n2);
11     cnt = 0;
12     for ( i=n1; i<=n2; i++ ) {
13         if ( IsTheNumber(i) )
14             cnt++;
15     }
16     printf("cnt = %d
", cnt);
17 
18     return 0;
19 }
20 int IsTheNumber ( const int N ){
21     int i,ret=0;
22     for (i = 0; i <= N / 2; i++) 
23         if (i*i == N){
24             ret++;
25             break;
26         }
27     int key[10] = {0};
28     int t = N;
29     while(t)
30     {
31         key[t%10]++;
32         t /= 10;
33     }
34     for(int j=0; j<=9; ++j)
35         if(key[j]>=2){
36             ret++;
37             break;
38         }        
39     return ret == 2;
40 }

8、简单阶乘计算

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

 1 #include <stdio.h>
 2 
 3 int Factorial( const int N );
 4 
 5 int main()
 6 {
 7     int N, NF;
 8     
 9     scanf("%d", &N);
10     NF = Factorial(N);
11     if (NF)  printf("%d! = %d
", N, NF);
12     else printf("Invalid input
");
13 
14     return 0;
15 }
16 int Factorial( const int N ){
17     if(N<0) return 0;
18     int fac=1;
19     for(int i=1; i<=N; ++i)
20         fac *=i;
21     return fac;
22 }

9、统计个位数字

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

 1 #include <stdio.h>
 2 
 3 int Count_Digit ( const int N, const int D );
 4 
 5 int main()
 6 {
 7     int N, D;
 8     
 9     scanf("%d %d", &N, &D);
10     printf("%d
", Count_Digit(N, D));
11     return 0;
12 }
13 int Count_Digit ( const int N, const int D ){
14     if(!N&&!D) return 1;
15     int count=0,t = N;
16     if(t<0) t = -t;
17     while(t)
18     {
19         if(t%10==D)
20             count++;
21         t /= 10;
22     }
23     return count;
24 }

10、阶乘计算升级版

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

 1 #include <stdio.h>
 2 
 3 void Print_Factorial ( const int N );
 4 
 5 int main()
 6 {
 7     int N;
 8     
 9     scanf("%d", &N);
10     Print_Factorial(N);
11     return 0;
12 }
13 void Print_Factorial ( const int N ){
14     if(N<0){
15         printf("Invalid input");
16         return;
17     }
18     int a[100000] = {0,1},index=1;
19     for(int n = 1; n<=N; ++n)
20     {
21         int carry = 0;/**< 进位数 */
22         for(int j=1; j<=index; j++)/**< 乘数与被乘数，从第一位开始，逐位相乘 */
23         {
24             int temp = n*a[j] + carry;/**< 乘积 + 进位数 */
25             a[j] = temp%10;/**< 乘积 + 进位数,保留个位 */
26             carry = temp/10;/**< 进位 */
27         }
28         while(carry > 0)/**< 进位数大于0，最高位++，最高位保留进位数个位 */
29         {
30             a[++index] = carry%10;
31             carry /= 10;
32         }
33     }
34     for(int i=index; i>0;--i)
35         printf("%d",a[i]);
36 }

11、求自定类型元素序列的中位数

本题要求实现一个函数，求N个集合元素A[]的中位数，即序列中第

 1 #include <stdio.h>
 2 
 3 #define MAXN 10
 4 typedef float ElementType;
 5 
 6 ElementType Median( ElementType A[], int N );
 7 
 8 int main ()
 9 {
10     ElementType A[MAXN];
11     int N, i;
12 
13     scanf("%d", &N);
14     for ( i=0; i<N; i++ )
15         scanf("%f", &A[i]);
16     printf("%.2f
", Median(A, N));
17 
18     return 0;
19 }
20 void HeapAdjust(ElementType array[], int i, int nlength)
21 {    
22     ElementType nTemp;
23     for (int nChild; 2 * i + 1 < nlength; i = nChild)
24     {
25         nChild = 2 * i + 1;
26         //得到子节点中较大的节点
27         if (nChild < nlength - 1 && array[nChild + 1] > array[nChild])
28             nChild++;
29         //如果较大的子节点大于父节点那么把较大的子节点往上移动，替换它的父节点
30         if (array[i] < array[nChild])
31         {
32             nTemp = array[i];
33             array[i] = array[nChild];
34             array[nChild] = nTemp;
35         }
36         else
37             break;
38     }
39 }
40 void Heapsort(ElementType array[], int length)
41 {
42     int i;//调整序列的前半部分元素，调整完之后第一个元素是序列的最大元素
43     ElementType temp;
44     for (i = length/2 - 1; i >= 0; i--)
45         HeapAdjust(array, i, length);
46     //从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
47     for (i = length - 1; i >= 0; i--)
48     {
49         //把第一个元素和当前的最后一个元素交换
50         //保证当前的最后一个位置的元素都是现在这个序列中最大的
51         temp = array[0];
52         array[0] = array[i];
53         array[i] = temp;
54         //不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
55         HeapAdjust(array, 0, i);
56     }
57 }
58 ElementType Median(ElementType A[], int N)
59 {
60     Heapsort(A, N);
61     return A[N / 2];
62 }

12、判断奇偶性

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

 1 #include <stdio.h>
 2 
 3 int even( int n );
 4 
 5 int main()
 6 {    
 7     int n;
 8 
 9     scanf("%d", &n);
10     if (even(n))
11         printf("%d is even.
", n);
12     else
13         printf("%d is odd.
", n);
14 
15     return 0;
16 }
17 int even( int n ){
18     if(n%2)
19         return 0;
20     return 1;
21 }

13、折半查找

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

 1 #include <iostream>
 2 using namespace std;
 3 
 4 #define MAXSIZE 50
 5 typedef int KeyType;
 6 
 7 typedef  struct                     
 8 { 
 9     KeyType  key;                                             
10 } ElemType;  
11 
12 typedef  struct
13 { 
14     ElemType  *R; 
15     int  length;
16 } SSTable;                      
17 
18 void  Create(SSTable &T)
19 { 
20     int i;
21     T.R=new ElemType[MAXSIZE+1];
22     cin>>T.length;
23     for(i=1;i<=T.length;i++)
24         cin>>T.R[i].key;   
25 }
26 
27 int  Search_Bin(SSTable T, KeyType k);
28 
29 int main () 
30 {  
31     SSTable T;  KeyType k;
32     Create(T);
33     cin>>k;
34     int pos=Search_Bin(T,k);
35     if(pos==0) cout<<"NOT FOUND"<<endl;
36     else cout<<pos<<endl;
37     return 0;
38 }
39 int  Search_Bin(SSTable T, KeyType k){
40     int left, right, mid, NotFound=0;
41     left = 1; /*初始左边界*/
42     right = T.length; /*初始右边界*/
43     while ( left <= right )
44     {        
45         mid = (left+right)/2; /*计算中间元素坐标*/
46         if( k < T.R[mid].key) right = mid-1; /*调整右边界*/
47         else if( k > T.R[mid].key) left = mid+1; /*调整左边界*/
48         else return mid; /*查找成功，返回数据元素的下标*/
49     }
50     return NotFound; /*查找不成功，返回-1*/
51 }