基础编程题目集 函数题部分（下）

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

分数 15

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

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

函数接口定义：

int FactorialSum( List L );

其中单链表List的定义如下：

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

裁判测试程序样例：

#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; scanf("%d", &N); L = NULL; for ( i=0; i<N; i++ ) { p = (List)malloc(sizeof(struct Node)); scanf("%d", &p->Data); p->Next = L; L = p; } printf("%d\n", FactorialSum(L)); return 0; } /* 你的代码将被嵌在这里 */

输入样例：

1. 3
2. 5 3 6

输出样例：

846

1. int FactorialSum( List L )
2. {
3.  int sum=0,i;
4.  while(L!=NULL)
5.  {
6.    int m=1;
7.    if(L->Data!=0)
8.    for(i=1;i<=L->Data;i++)
9.      m=m*i;
10.     sum=sum+m;
11.     L=L->Next;
12.   }
13.   return sum;
14. }

6-7 统计某类完全平方数

分数 20

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

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

函数接口定义：

int IsTheNumber ( const int N );

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

裁判测试程序样例：

#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; } /* 你的代码将被嵌在这里 */

输入样例：

105 500

输出样例：

cnt = 6

1. int IsTheNumber ( const int N )
2. {
3. int n=sqrt(N);
4. int num[10]={0};
5. int temp=N,t,flag=0;
6. while(temp)
7.     {
8.         t=temp%10;
9.         num[t]++;
10.         temp=temp/10;
11.     }
12. for(int i=0;i<10;i++)
13.     {
14. if(num[i]>=2)
15.         {
16.             flag=1;
17.         }
18.     }
19. if(N<=0)
20.     {
21. return 0;
22.     }
23. else if(n*n==N)
24.     {
25. if(flag==1)
26.         {
27. return 1;
28.         }
29. else
30.         {
31. return 0;
32.         }
33.     }
34. else
35.     {
36. return 0;
37.     }
38. }

6-8 简单阶乘计算

分数 10

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

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

函数接口定义：

int Factorial( const int N );

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

裁判测试程序样例：

#include <stdio.h> 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

1. int Factorial( const int N )
2. {
3. if(N<=1&&N>=0)
4.     {
5. return 1;
6.     }
7. if(N<0)
8.     {
9. return 0;
10.     }
11. else
12.     {
13. return N*Factorial(N-1);
14.     }
15. }

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 <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; } /* 你的代码将被嵌在这里 */

输入样例：

-21252 2

输出样例：

3

1. int Count_Digit ( const int N, const int D )
2. {
3. int a[1000];
4. int n,num=0,cnt=0;
5. if(N>0)
6.     {
7.         n=N;
8.     }
9. else if(N<0)
10.     {
11.         n=-1*N;
12.     }
13. else if(N==0)
14.     {
15. return 1;
16.     }
17. while(n)
18.     {
19.         a[num]=n%10;
20.         num++;
21.         n=n/10;
22.     }
23. for(int i=0;i<num;i++)
24.     {
25. if(a[i]==D)
26.         {
27.             cnt++;
28.         }
29.     }
30. return cnt;
31. }

6-10 阶乘计算升级版

分数 20

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

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

函数接口定义：

void Print_Factorial ( const int N );

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

裁判测试程序样例：

#include <stdio.h> void Print_Factorial ( const int N ); int main() { int N; scanf("%d", &N); Print_Factorial(N); return 0; } /* 你的代码将被嵌在这里 */

输入样例：

15

输出样例：

1307674368000

1. void Print_Factorial ( const int N )
2. {
3.  int num[10000]={0};
4.  int ans=1,temp=0,k=0,carry=0;
5.  if(N<0)
6.     {
7. printf("Invalid input\n");
8.     }
9.  else if(N==0)
10.     {
11. printf("1\n");
12.     }
13.   else if(N>0&&N<12)
14.   {
15.     for(int i=1;i<=N;i++)
16.     ans=ans*i;
17.     printf("%d\n",ans); 
18.     } 
19.    else
20.      {
21.     num[0]=1;
22.     for(int i=2;i<=N;i++)
23.      {
24.       for(int j=0;j<=k;j++)
25.        {
26.         temp=num[j]*i+carry;
27.         num[j]=temp%10;
28.         carry=temp/10;
29.         } 
30.         while(carry)
31.         {
32.           num[++k]=carry%10;
33.           carry=carry/10;
34.         }
35.       } 
36.       for(int i=k;i>=0;i--)
37.       printf("%d",num[i]);
38.       printf("\n");
39.    }
40. }

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

分数 25

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

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

函数接口定义：

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

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

裁判测试程序样例：

#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; } /* 你的代码将被嵌在这里 */

输入样例：

1. 3
2. 12.3 34 -5

输出样例：

12.30

1. ElementType Median( ElementType A[], int N )
2. {
3.   ElementType temp;
4. for(int gap= N/2; gap> 0; gap= gap/ 2)                                      
5.   {
6. for(int i= gap; i< N; i++)
7.     {
8. for(int j= i- gap; j>= 0 && A[j]> A[j+ gap]; j= j- gap)
9.       { 
10.         temp= A[j];
11.         A[j]= A[j+ gap];
12.         A[j+ gap]= temp;
13.       }
14.     }
15.   }
16. return A[N/ 2];
17. }

6-12 判断奇偶性

分数 10

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

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

函数接口定义：

int even( int n );

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

裁判测试程序样例：

#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; } /* 你的代码将被嵌在这里 */

输入样例1：

-6

输出样例1：

-6 is even.

输入样例2：

5

输出样例2：

5 is odd.

1. int even( int n )
2. {
3. if(n%2==0)
4.     {
5. return 1;
6.     }
7. else
8.     {
9. return 0;
10.     }
11. }

6-13 折半查找

分数 15

全屏浏览题目

切换布局

作者 王群芳

单位 合肥师范学院

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

函数接口定义：

int Search_Bin(SSTable T, KeyType k)

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

裁判测试程序样例：

#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; } /* 请在这里填写答案 */

###输入格式：

第一行输入一个整数n，表示有序表的元素个数，接下来一行n个数字，依次为表内元素值。 然后输入一个要查找的值。

###输出格式：

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

输入样例：

1. 5
2. 1 3 5 7 9
3. 7

输出样例：

4

输入样例：

1. 5
2. 1 3 5 7 9
3. 10

输出样例：

NOT FOUND

1. int  Search_Bin(SSTable T, KeyType k)
2. {
3. int low=0,high=T.length,mid;
4. while(low<=high)
5.     {
6.         mid=(low+high)/2;
7. if(T.R[mid].key==k)
8.         {
9. return mid;
10.         }
11. else if(T.R[mid].key>k)
12.         {
13.             high=mid-1;
14.         }
15. else
16.         {
17.             low=mid+1;
18.         }
19.     }
20. return 0;
21. }