首页 › 题库 › C/C++编程考级 › 1 函数定义与调用

C/C++编程三级 题库

共 49 道题 ,第 3 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 1 函数定义与调用 清除
41 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

Pell数列

Pell数列a1, a2, a3, ...的定义是这样的,a1 = 1, a2 = 2, ... , an = 2 * an − 1 + an - 2 (n > 2)。 给出一个正整数k,要求Pell数列的第k项模上32767是多少。

时间限制:3000

内存限制:65536

输入

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数k (1 ≤ k < 1000000)。

输出

n行,每行输出对应一个输入。输出应是一个非负整数。

样例输入

2
1
8

样例输出

1
408
答案与解析
参考答案
//解法1:递推
#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main()
{
    int n, x; 
 a[1] = 1, a[2] = 2;
 for(int i = 3; i <= 1000000; ++i)
  a[i] = (2*a[i-1] + a[i-2])%32767;
 cin >> n;
 for(int i = 1; i <= n; ++i)
 {
  cin >> x;
  cout << a[x] << endl;
 }
 return 0;
}
//解法2:迭代
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ct, p;
    cin >> ct;
    for(int i = 1; i <= ct; ++i)
    {
        cin >> p;
        if(p <= 2)
            cout << p << endl;//第1项是1,第2项是2 
        else 
        {
            int a = 1, b = 2, t;
            for(int j = 3; j <= p; ++j)
            {
                t = b;
                b = (2*b + a)%32767;
                a = t;
            }
            cout << b << endl;
        }
    }
    return 0;
}
//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1000010
#define k 32767

using namespace std;
int a[N];
int f(int x)
{
 if(a[x]!=0) return a[x];
 if(x==1) return 1;
 if(x==2) return 2;
 return a[x]=(2*(f(x-1))%k+(f(x-2))%k)%k;
}
int main()
{
    int n,a;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>a; 
  cout<<f(a)<<endl;
 }
 return 0;
}
题目详情
42 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

吉利矩阵

所有元素为非负整数,且各行各列的元素和都等于 7 的 3x3 方阵称为“吉利矩阵”,因为这样的矩阵一共有 666 种。

本题就请你统计一下,把 7 换成任何一个 [2, 9] 区间内的正整数 L,把矩阵阶数换成任何一个 [2, 4] 区间内的正整数 N,满足条件“所有元素为非负整数,且各行各列的元素和都等于 L”的 NxN 方阵一共有多少种?

时间限制:6000

内存限制:65535

输入

输入在一行中给出 2 个正整数 L 和 N,意义如题面所述。数字间以空格分隔。

输出

在一行中输出满足题目要求条件的方阵的个数。

样例输入

7 3

样例输出

666
答案与解析
参考答案
//参考代码1 C语言
#include <stdio.h>

int res = 0;
int sum_row[4] = {0};
int sum_col[4] = {0};

void dfs(int x, int sum, int width) {
    if (x == width * width) {
        ++res;
        return;
    }

    for (int i = 0; i <= sum; i++) {
        if (x % width == width - 1 && i != sum - sum_row[x / width]) continue;
        if (x / width == width - 1 && i != sum - sum_col[x % width]) continue;
        if (sum_row[x / width] + i <= sum && sum_col[x % width] + i <= sum) {
            sum_col[x % width] += i;
            sum_row[x / width] += i;
            dfs(x + 1, sum, width);
            sum_col[x % width] -= i;
            sum_row[x / width] -= i;
        }
    }
}

int main() {
    int sum, width;
    scanf("%d %d", &sum, &width);

    dfs(0, sum, width);
    printf("%d\n", res);

    return 0;
}
//参考代码2
#include<iostream>
using namespace std;
const int N=20;
int a[N][N];
int main(){
int l,n;cin>>l>>n;
a[2][2]=3;
a[2][3]=21;
a[2][4]=282;
a[3][2]=4;
a[3][3]=55;
a[3][4]=2008;
a[4][2]=5;
a[4][3]=120;
a[4][4]=10147;
a[5][2]=6;
a[5][3]=231;
a[5][4]=40176;
a[6][2]=7;
a[6][3]=406;
a[6][4]=132724;
a[7][2]=8;
a[7][3]=666;
a[7][4]=381424;
a[8][2]=9;
a[8][3]=1035;
a[8][4]=981541;
a[9][2]=10;
a[9][3]=1540;
a[9][4]=2309384;
cout<<a[l][n];
}
题目详情
43 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

加号放哪里

给定任一个正整数 N,我们要从它开始,经过一系列操作得到一个个位数。操作方法是在 N 的各位数字之间放置一个加号,然后执行这个加法计算,得到一个新的数字 N1,再对 N1 执行同样操作,得到 N2 …… 以此类推,直到最后得到的数字只有 1 位,则停止。

例如我们从 N=1234567890 出发,在 5 和 6 之间放置加号,计算 12345+67890=80235;然后在 0 和 2 之间放置加号,计算 80+235=315;然后在 1 和 5 之间放置加号,计算 31+5=36;最后在 3 和 6 之间放置加号,得到 3+6=9 而停止。这样我们通过 4 次计算得到了一个个位数 9。

本题就请你为任一给定的正整数计算:最少需要多少次加号放置可以得到个位数?

注意:加号必须放置在两个数字之间,不可放置在数字的首尾。

时间限制:7000

内存限制:65536

输入

输入在一行中给出一个正整数 n(≤ 1020)。

输出

在一行中首先输出将输入的整数变为个位数,需要放置加号的最少次数;随后输出最后得到的那个个位数。如果最后得到的个位数不唯一,输出最小的那个。 数字间以 1 个空格分隔,行首尾不得有多余空格。

样例输入

1234567890

样例输出

3 9

提示

样例解释: 最优划分是: 1. 12345678+90=12345768 2. 1234+5768=7002 3. 7+002=9

答案与解析
参考答案
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

long ansfqy = __LONG_MAX__;
int ansnum = 10;

void justdfs(long n, long frequency);
void exceeddfs(char *n, long frequency);

void justdfs(long n, long frequency) {
    if (ansfqy < frequency) {
        return;
    }

    if (n < 10 && (n < ansnum || frequency < ansfqy)) {
        ansnum = n;
        ansfqy = frequency;
        return;
    }

    long temp = 10;
    while (n / temp > 0) {
        long nleft = n / temp;
        long nright = n % temp;
        temp *= 10;
        justdfs(nleft + nright, frequency + 1);
    }
}

void exceeddfs(char *n, long frequency) {
    if (ansfqy < frequency) {
        return;
    }

    for (int i = 1; i < strlen(n); i++) {
        char BIleft[1025], BIright[1025];
        strncpy(BIleft, n, i);
        BIleft[i] = '\0';
        strncpy(BIright, n + i, strlen(n) - i);
        BIright[strlen(n) - i] = '\0';

        long sum = atol(BIleft) + atol(BIright);
        char temp[1025];
        sprintf(temp, "%ld", sum);

        if (strlen(temp) < 19) {
            justdfs(sum, frequency + 1);
        } else {
            exceeddfs(temp, frequency + 1);
        }
    }
}

int main() {
    char n[1025];
    scanf("%s", n);

    if (strlen(n) < 19) {
        justdfs(atol(n), 0);
    } else {
        exceeddfs(n, 0);
    }

    printf("%ld %d\n", ansfqy, ansnum);

    return 0;
}
题目详情
44 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

乘法小宇宙

一个 n 位数的正整数 A=anan-1…a1 和另一个 2 位数的正整数 B=b2b1 相乘,其乘法展开式如下图所示:

其中 C=cn+1cn…c1 是 A 与 b1 相乘的结果,D=dn+1dn…d1 是 A 与 b2 相乘的结果,P=pn+2pn+1…p1 是 A 与 B 相乘的结果。

若上图中的每一位数字都在一个给定的非零个位数字集合 S 里,则称 A 和 B 属于同一个乘法小宇宙 S。

本题给定乘法小宇宙 S 和 A 的位数,请你找出同属于这个乘法小宇宙中的所有 A 和 B。

时间限制:6000

内存限制:65536

输入

输入在一行中给出两个正整数 n(< 8)和 K(≤ 5),分别是 A 的位数和乘法小宇宙 S 中元素的个数。第二行给出 K 个 (0, 10) 区间内的整数,为 S 中的元素。题目保证没有重复元素。数字间以空格分隔。

输出

按照 A 的非递减序输出所有同属于这个乘法小宇宙中的 A 和 B,每行输出一对,数字间以 1 个空格分隔,行首尾不得有多余空格。对同一个 A,按 B 的递增序输出。若没有解,则输出 `No Solution`。


样例输入

样例#1:

4 5

4 2 1 6 5

样例#2:

3 4

9 2 5 6


样例输出

样例#1:

5556 44

6111 24

6111 42

样例#2:

No Solution

答案与解析
参考答案

整理中……

题目详情
45 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

势均力敌

用 n (> 2) 个不同的个位数字组成一个 n 位数,显然有 n! 个不同的结果。可以证明,这 n! 个数字可以被分为势均力敌的两组 —— 即平方和相等、且个数也相等的两组。

本题就请你用程序验证一下这个结论。

因为本题是一道简单题,所以规模很小,只考虑 n ≤ 4 的情况。

时间限制:4000

内存限制:262144

输入

输入第一行给出正整数 n(2 < n ≤ 4),随后一行给出 n 个不同的、在区间 [1, 9] 内的个位数字,其间以空格分隔。

输出

将所有组成的 n! 个不同的 n 位数分为平方和相等、且个数也相等的两组。但你只需要输出其中一组就可以了。每个数字占一行,共输出 n!/2 行。 注意:解可能不唯一,输出任何一组解就可以。


样例输入

3
5 2 1

样例输出

125
512
251
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

int a[10005];
vector<int> v;
long long num = 0, n;
long long cnt, flag;
bool st[10005], stt[10005];
long long pa[10005];

void dfs(int x)
{
    if (x == n) v.push_back(num);

    for (int i = 0; i < n; i++)
    {
        if (!st[a[i]])
        {
            int fa = num;
            st[a[i]] = true;
            num = num * 10 + a[i];
            dfs(x + 1);
            num = fa;
            st[a[i]] = false;
        }
    }
}

void dfs1(int x, int p)
{
    if (flag == 1) return;
    if (x == (int)v.size() / 2)
    {
        num = 0;
        for (int i = 0; i < x; i++) num += pa[i] * pa[i];
        if (num * 2 == cnt)
        {
            for (int i = 0; i < x; i++) cout << pa[i] << '\n';
            flag = 1;
            return;
        }
    }

    for (int i = p; i < (int)v.size(); i++)
    {
        if (!stt[i])
        {
            stt[i] = true;
            pa[x] = v[i];
            dfs1(x + 1, i + 1);
            stt[i] = false;
            pa[x] = 0;
        }
    }
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    dfs(0);

    for (auto t : v) cnt += t * t;

    dfs1(0, 0);
}
题目详情
46 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

颁奖典礼

题目描述

n 个学生参加颁奖典礼,学号为 1 到 n。学生根据比赛排名上台领奖。已知学号为 i 的学生是第 ai 个上去领奖的。请输出学生上台领奖的学号顺序。

输入

第一行,单个整数 n。

第二行,n 个整数a1,a2,...,an。

输出

n 个整数,表示学生上台的顺序。

数据范围

对于100%的数据,1≤n≤100,000,1≤ai≤n。

输入样例1

3
3 1 2

输出样例1

2 3 1
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
bool compare(pair<int,int> a,pair<int,int> b) { //排序比较函数
    return a.second < b.second;
}
int main() {
    int n, k;
    cin >> n;
    vector<pair<int,int>> a;  //学号和领奖顺序数组
    for(int i=0; i<n; i++) {
        cin >> k;
        a.push_back({i+1, k});
    }
    sort(a.begin(), a.end(), compare); //按领奖顺序排序
    for(int i=0; i<n; i++) {
        cout << a[i].first << " ";  //输出学号
    }
    return 0;
}
题目详情
47 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

千位分隔符

题目描述

给定一个正整数 n,请在 n 的十进制表示上每隔三个数字添加一个逗号作为分隔符。

输入格式

第一行:一个整数 n。

输出格式

第一行:一个含有千位分隔符的整数。


输入样例

12345

输出样例

12,345

说明提示

对于 50% 的数据,1≤n≤1010

对于 100% 的数据,1≤n≤101,000

答案与解析
参考答案
#include <iostream>
#include <string>
#include <algorithm> // 用于reverse函数
using namespace std;

int main() {
    string num;
    cin >> num;
    string result;
    int count = 0;
    
    // 从右往左处理每个数字
    for (int i = num.size() - 1; i >= 0; i--) {
        result += num[i]; // 添加当前数字
        count++;
        // 每3位数字加一个逗号,但不要在开头加
        if (count % 3 == 0 && i != 0) {
            result += ',';
        }
    }
    
    // 反转结果字符串
    reverse(result.begin(), result.end());
    
    cout << result << endl;
    return 0;
}
题目详情
48 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

三元组的离心力

三元组 (a,b,c) 的“离心力”定义为 |a-b|+|b-c|+|c-a|。现给定三个非空的整数集合 S1、S2、S3,请你找出所有跨这三个集合的三元组 (a,b,c)(即 a∈ S1,b∈ S2,c∈ S3)的最小离心力。

时间限制:1000

内存限制:65536

输入

输入第一行给出三个不超过 104 的正整数 n1、n2、n3,依次为集合 S1、S2、S3 中元素的个数(注意一个集合内没有相同的元素)。随后三行,顺次给出三个集合的元素,均为 [-104 , 104] 内的整数。同行数字间以空格分隔。

输出

在一行中输出 `LiXinLi(a, b, c) = d`,其中 `(a, b, c)` 是具有最小离心力的三元组,`d` 是对应的离心力。如果解不唯一,输出那个最大的解。 注意:(a1,a2,a3)>(b1,b2,b3) 是指,存在 1 ≤ k ≤ 3 使得 ai=bi 对 1 ≤ i < k 成立,并且 ak > bk。


样例输入

4 4 6
0 9 -1 11
10 -25 11 -10
9 2 41 17 12 30

样例输出

LiXinLi(11, 11, 12) = 2

提示

注意到样例实际上有两组解,另外一组解是 (9, 10, 9)。因为 (11, 11, 12) 比较大,所以输出的是这组解。

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <climits>

using namespace std;

vector<int> find_closest(const vector<int>& arr, int x) {
	vector<int> res;
	int n = arr.size();
	if (n == 0) return res;
	auto it = lower_bound(arr.begin(), arr.end(), x);
	int pos = it - arr.begin();
	if (pos == 0) {
		res.push_back(arr[0]);
	} else if (pos == n) {
		res.push_back(arr.back());
	} else {
		int prev = arr[pos - 1];
		int curr = arr[pos];
		if (x - prev < curr - x) {
			res.push_back(prev);
		} else if (x - prev > curr - x) {
			res.push_back(curr);
		} else {
			res.push_back(prev);
			res.push_back(curr);
		}
	}
	return res;
}

int main() {
	int n1, n2, n3;
	cin >> n1 >> n2 >> n3;
	vector<int> S1(n1), S2(n2), S3(n3);
	for (int i = 0; i < n1; ++i) cin >> S1[i];
	for (int i = 0; i < n2; ++i) cin >> S2[i];
	for (int i = 0; i < n3; ++i) cin >> S3[i];
	
	sort(S1.begin(), S1.end());
	sort(S2.begin(), S2.end());
	sort(S3.begin(), S3.end());
	
	vector<tuple<int, int, int>> candidates;
	
	// Process S1 elements
	for (int a : S1) {
		auto b_list = find_closest(S2, a);
		auto c_list = find_closest(S3, a);
		for (int b : b_list) {
			for (int c : c_list) {
				candidates.emplace_back(a, b, c);
			}
		}
	}
	
	// Process S2 elements
	for (int b : S2) {
		auto a_list = find_closest(S1, b);
		auto c_list = find_closest(S3, b);
		for (int a : a_list) {
			for (int c : c_list) {
				candidates.emplace_back(a, b, c);
			}
		}
	}
	
	// Process S3 elements
	for (int c : S3) {
		auto a_list = find_closest(S1, c);
		auto b_list = find_closest(S2, c);
		for (int a : a_list) {
			for (int b : b_list) {
				candidates.emplace_back(a, b, c);
			}
		}
	}
	
	int min_range = INT_MAX;
	for (const auto& t : candidates) {
		int a = get<0>(t), b = get<1>(t), c = get<2>(t);
		int current_min = min({a, b, c});
		int current_max = max({a, b, c});
		min_range = min(min_range, current_max - current_min);
	}
	
	vector<tuple<int, int, int>> min_candidates;
	for (const auto& t : candidates) {
		int a = get<0>(t), b = get<1>(t), c = get<2>(t);
		int current_min = min({a, b, c});
		int current_max = max({a, b, c});
		if (current_max - current_min == min_range) {
			min_candidates.push_back(t);
		}
	}
	
	tuple<int, int, int> best = min_candidates[0];
	for (const auto& t : min_candidates) {
		if (t > best) {
			best = t;
		}
	}
	
	int a = get<0>(best), b = get<1>(best), c = get<2>(best);
	int d = 2 * (max({a, b, c}) - min({a, b, c}));
	cout << "LiXinLi(" << a << ", " << b << ", " << c << ") = " << d << endl;
	
	return 0;
}
题目详情
49 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

分玩具

已知 n 位小朋友对 m 件玩具的喜好(n ≤ m),现要将 m 件玩具分给 n 位小朋友,每位小朋友只能分到 1 件玩具,每件玩具也最多只能分给 1 位小朋友,并且还要求每位小朋友都能分到自己喜欢的玩具。

本题请你对任意 n 和 m 尝试列出所有满足要求的方案。

时间限制:5000

内存限制:65536

输入

输入第一行给出两个正整数 n 和 m(n ≤ m ≤ 8),即小朋友人数和玩具的数量。 随后 n 行,每行给出 m 个数字。其中第 i 行第 j 个数字为 1 表示第 i 位小朋友喜欢第 j 件玩具,为 0 则表示不喜欢。

输出

按升序列出所有满足要求的方案,格式为 (s1, … , sn)。其中 si 表示第 i 位小朋友分到了第 si 件玩具。 注:方案 (a1, … , an) < (b1, … , bn) 是指存在 1 ≤ k ≤ n,使得 ai = bi 对所有 1 ≤ i< k 成立,并且有 ak < bk。


样例输入

4 5
0 1 0 0 1
1 1 0 1 0
1 0 1 1 0
0 0 0 1 1

样例输出

(2, 1, 3, 4)
(2, 1, 3, 5)
(2, 1, 4, 5)
(2, 4, 1, 5)
(2, 4, 3, 5)
(5, 1, 3, 4)
(5, 2, 1, 4)
(5, 2, 3, 4)
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void backtrack(int k, int mask, vector<int>& path, vector<vector<int>>& res, const vector<vector<int>>& preferences) {
	if (k == preferences.size()) {
		res.push_back(path);
		return;
	}
	for (int j : preferences[k]) {
		if (!(mask & (1 << (j - 1)))) {
			path.push_back(j);
			backtrack(k + 1, mask | (1 << (j - 1)), path, res, preferences);
			path.pop_back();
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> preferences(n);
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			int x;
			cin >> x;
			if (x == 1) {
				preferences[i].push_back(j + 1); // 玩具编号从1开始
			}
		}
		sort(preferences[i].begin(), preferences[i].end()); // 对每个小朋友的喜好进行排序
	}
	
	vector<vector<int>> res;
	vector<int> path;
	backtrack(0, 0, path, res, preferences);
	
	sort(res.begin(), res.end());
	
	for (const auto& vec : res) {
		cout << "(";
		for (size_t i = 0; i < vec.size(); ++i) {
			if (i > 0) {
				cout << ", ";
			}
			cout << vec[i];
		}
		cout << ")" << endl;
	}
	
	return 0;
}
题目详情