上机实验：过程的封装：函数（下）& 指针（上）

组合数

任务描述

本关任务：编写一个求n!的函数，并用于求从n个物体中取m个物体的组合数（0<=m<=n<=20）。

编程要求

根据提示，在右侧编辑器补充代码，使之符合要求。

测试说明

平台会对你编写的代码进行测试，每个测试样例的输入包括两个数字，第一个n，第二个是m：

测试输入1： 4 1 预期输出1： 4

测试输入1： 3 2 预期输出1： 3

参考代码

#include<iostream>
using namespace std;

long long factorial(int n)
{
    // write your code here
    long long ans=1;
    for (int i=1;i<=n;i++) ans = ans * i;
    return ans;
}

int main()
{
    // write your code here
    int n, m; cin >> n >> m;
    cout << factorial(n)/factorial(m)/factorial(n-m) << endl;
    return 0;
}

计算最大的三位约数

任务描述

本关任务：从键盘任意输入一个数n（1000<=n<=1000000），编程计算并输出n的所有约数中最大的一个三位数（即最大的三位约数）。如果n小于1000或者大于1000000，则输出“Input error!”。如果没有三位数的约数，则输出“Not found!”。

函数原型：int Func(int n)；函数功能：计算n的所有约数中最大的三位数，如果不存在返回-1。

编程要求

根据提示，在右侧编辑器补充代码，编写函数使之符合要求。

测试说明

平台会对你编写的代码进行测试：

测试输入： 555555 预期输出： 777

测试输入： 1000 预期输出： 500

测试输入： 800 预期输出： Input error!

测试输入： 121123 预期输出： Not found!

参考代码

#include<iostream>
using namespace std;

int Func(int n)
{
    // start your code here
    for (int i=999;i>=100;i--) if (n%i==0) return i;
    return -1;
}

int main()
{
    // start your code here
    int n; cin >> n;
    if (n < 1000 || n > 1000000)
        cout << "Input error!\n";
    else {
        int res = Func(n);
        if (~res) cout << res << '\n';
        else cout << "Not found!\n";
    }
    return 0;
}

递归法计算两个数的最大公约数

任务描述

本关任务：编写一个用递归法计算两个数的最大公约数的程序。

编程要求

函数原型：int Gcd(int a, int b);

利用最大公约数的性质计算。对正整数a和b，当a>b时，若a中含有与b相同的公约数，则a中去掉b后剩余的部分a-b中也应含有与b相同的公约数，对a-b和b计算公约数就相当于对a和b计算公约数。反复使用最大公约数的上述性质，直到a和b相等为止，这时，a或b就是它们的最大公约数。这三条性质，也可以表示为：

性质1 如果a>b，则a和b与a-b和b的最大公约数相同，即Gcd(a, b) = Gcd(a-b, b)
性质2 如果b>a，则a和b与a和b-a的最大公约数相同，即Gcd(a, b) = Gcd(a, b-a)
性质3 如果a=b，则a和b的最大公约数与a值和b值相同，即Gcd(a, b) = a

根据提示，在右侧编辑器补充代码，计算并输出最大公约数。

测试说明

输入为两个正整数a b ($1\leq a,b\leq 10^4$)，以一个空格分隔。输出为一个正整数，表示答案。

平台会对你编写的代码进行测试：

测试输入：16 24 预期输出：8

参考代码

#include<iostream>
using namespace std;

int Gcd(int a, int b)
{
    // write your code here
    if (a > b) return Gcd(a-b, b);
    if (b > a) return Gcd(a, b-a);
    return a;
}

int main()
{
    // write your code here
    int a, b; cin >> a >> b;
    cout << Gcd(a, b) << endl;
    return 0;
}

字符串对调

任务描述

设计一个程序，让用户输入两串字符，存入两个字符数组中，然后将它们中下标相同的非空字符对调，再输出这两个新的字符串。用户输入的两串字符数量都小于20个，以回车完成输入。

限制条件

除了<iostream>之外不可包含其它库；
只能使用已定义的两个长度为20的字符数组、一个字符变量、两个字符指针，不能定义别的变量、数组或其它对象（包括 for (int i;…;…) 也算定义了新的变量 i）。

输入输出示例

Input: ABCDEFGH abcde Output: abcdeFGH ABCDE

参考代码

#include <iostream>
using namespace std;

int main()
{
    char str1[20];
    char str2[20];
    char tmp, *p1, *p2;

    cin.getline(str1,20);
    cin.getline(str2,20);

    /*Start your code here*/
    for (p1=str1, p2=str2; *p1 && *p2; p1++, p2++)
        tmp = *p1, *p1 = *p2, *p2 = tmp;
    cout << str1 << endl;
    cout << str2 << endl;

    /*end your code*/
    return 0;
}

插入排序的递归实现（附加题，选做）

任务描述

本关任务：插入排序的递归实现

一个数组有n个元素，假如前面n-1个元素已经排序好了，那么把第n个元素插入到前面n-1个元素中，使得数组有序排列，就是插入排序了。

至于n-1个元素如何已经先排序好，那么我们可以假设前面n-2个元素已经排序好，把第n-1个元素插入到前面n-2个元素中。

依次类推，直到只剩下一个元素，也就是第一个元素。排序完成。伪代码如下：

void Insert_Sort(int A[], int n)
{
	// 递归的出口是n=0
	if (n == 0) return ;

	Insert_Sort(A, n-1); //递归实现，将前面n-1个元素排序好

    // 把第n个元素插入到前面n-1个元素中
	// ...
}

测试样例数组长度范围为1~1000，输入数组限整数，范围不超过int。

编程要求

先输入数组元素的个数；再输入数组元素；输出排序后的数组元素根据提示，在右侧编辑器补充代码，递归实现插入排序，使之符合要求。

测试说明

平台会对你编写的代码进行测试：

测试输入： 4 2 3 1 4 预期输出： 1 2 3 4

参考代码

#include<iostream>
using namespace std;

void Insert_Sort(int A[], int n)
{
    if (n == 0) return ;
    Insert_Sort(A, n-1);
    for (int i=n-2;i>=0;i--) if (A[i]>A[i+1]) {
        int tmp = A[i];
        A[i] = A[i+1];
        A[i+1] = tmp;
    }
}

int main()
{
    int n, a[1010]; cin >> n;
    for (int i=0;i<n;i++) cin >> a[i];
    Insert_Sort(a, n);
    for (int i=0;i<n;i++) cout << a[i] << ' ';
    return 0;
}

组合数

任务描述

相关知识

编程要求

测试说明

参考代码

计算最大的三位约数

任务描述

编程要求

测试说明

参考代码

递归法计算两个数的最大公约数

任务描述

编程要求

测试说明

参考代码

字符串对调

任务描述

限制条件

输入输出示例

参考代码

插入排序的递归实现（附加题，选做）

任务描述

编程要求

测试说明

参考代码