目录
Problem A 众数问题
题目描述
输入
输出
样例输入
样例输出
思路分析
代码实现
思路优化
Problem B 半数集问题
题目描述
输入
输出
样例输入
样例输出
思路分析
代码实现
Problem C 查找数组拐点
题目描述
输入
输出
样例输入
样例输出
思路分析
代码实现
思路优化
Problem A 众数问题
题目描述
所谓众数，就是对于给定的含有N个元素的多重集合，每个元素在S中出现次数最多的成为该元素的重数， 多重集合S重的重数最大的元素成为众数。例如：S={1,2,2,2,3,5}，则多重集S的众数是2，其重数为3。 现在你的任务是：对于给定的由m个自然数组成的多重集S，计算出S的众数及其重数。
输入
第一行为n，表示测试数据组数。(n<30) 每组测试的第一行是一个整数m，表示多重集S中元素的个数为m 接下来的一行中给出m(m<100)个不大于10万的自然数 （不会出现不同元素出现的次数相同的情况，如：S={11,11,22,22,33,33}）。
输出
每组测试数据输出一行，包含两个数，第一个是众数，第二个是其重数，中间以空格隔开。
样例输入
1 6 1 2 2 2 3 5样例输出
2 3
思路分析
当然我们首先排除暴力建数组的解法，太占用空间时间了。事实上我第一反应是用一个结构体记录元素值和出现次数。这里取巧（恰好给的用例都是非递减序列，如果不是可能还需要排序，此时代码量就增加特别多了，所以只能是取巧），我就直接用一个指针实现了记录和更新，最后再进行一个遍历取出个数最大的两个数据即可。这样写显然与实验目的不符，但目前我能想到的就是这样，试了一下也是可以过的，因此也记录在这里。
代码实现
#includeusing namespace std; struct Elements { int cnt = 0; long long val = 0; Elements* next = NULL; }; int main() { int N; cin >> N; while (N--) { int num; cin >> num; Elements* head = NULL, * p = NULL, * r = NULL; while (num--) { long long value; cin >> value; if (!head) { head = new Elements; head->val = value; head->cnt = 1; p = head; } else if (p->val == value) { p->cnt++; } else { Elements* q = new Elements; q->val = value; q->cnt = 1; p->next = q; p = q; } } r = head; int maxnum = 0; long long maxval = 0; while (r) { if (r->cnt >= maxnum) { maxnum = r->cnt; maxval = r->val; } r = r->next; } cout << maxval << " " << maxnum << endl; while (head) { p = head->next; delete head; head = p; } } return 0; }
思路优化
我们第一眼就可以看出这个代码十分繁杂，而且涉及到结构体，调试耗费的时间也较长。因此，我们思考如何用递归策略实现改题目要求的功能。这里我们主要思考给出的数字序列的数学特征：众数。我们假设这个序列是非递减的，以没有重复数字的序列中位数为基准：左侧出现众数，中位数的值减小；右侧出现众数，中位数的值增加。因此，我们可以通过中位数的比较来确定众数的位置。用递归的思想，我们先确定递归的出口，能确定“重数在本次规模中最大”的情况，比如[1, 1, 2]众数是1，也就是中位数的个数大于左侧所有元素的个数时；因此出口就是判断中位数的重数是否大于左侧个数。把大问题划分为小问题的方法可以用中位数二分。
代码如下：
#include# define N 100 using namespace std; void Split(int a[], int n, int& l, int& r) { int mid = n / 2; for (l = 0; l <= mid; ++l) if (a[l] == a[mid]) break; for (r = mid + 1; r < n; ++r) if (a[r] != a[mid]) break; } void getMaxNum(int& num, int& maxnum, int a[], int n) { int l, r, s; int mid = n / 2; Split(a, n, l, r); s = r - l; if (s > maxnum) { num = a[mid]; maxnum = s; } if (s == maxnum) if (num > a[mid]) { num = a[mid]; maxnum = s; } if (l + 1 > maxnum) getMaxNum(num, maxnum, a, l + 1); if (n - r > maxnum) getMaxNum(num, maxnum, a + r, n - r); } int main() { int i, n, a[N]; int num = 0; int maxnum = 0; int T = 0; cin >> T; while (T--) { int n; cin >> n; for (i = 0; i < n; i++) cin >> a[i]; getMaxNum(num, maxnum, a, n); cout << num << " " << maxnum << endl; return 0; } }
Problem B 半数集问题
题目描述
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n)； (2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； (3) 按此规则进行处理，直到不能再添加自然数为止。 例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。 注意半数集是多重集。
输入
对于给定的自然数n，计算半数集set(n)中的元素个数。
输出
程序运行结束时，将计算结果输出。输出只有1 行，给出半数集set(n)中的元素个数。
样例输入
6样例输出
6
思路分析
这个问题是很明显的递归问题，还只要求计数，就很简单了。我们首先明确递归出口，也就是只剩一个1的时候没办法再加数字，只有1本身在半数集里，因此这种情况返回值为1。而多位的数字就可以用递归了，直到最后一位，计数只需要从n/2到1循环调用递归即可。
代码实现
#includeusing namespace std; int CreateSet(int n) { int sum = 1; if (n == 1) return 1; int max = n / 2; for (int i = max; i >= 1; i--) { sum += CreateSet(i); } return sum; } int main() { int n; cin >> n; cout << CreateSet(n) << endl; return 0; }
Problem C 查找数组拐点
题目描述
设T[0:n-1]是包含n个正整数的数组(1<=n<=200)，其中从第1个元素到第m个元素采用增序排序，从第m+1个元素到第n个元素采用减序排序，注意：数组中有重复数字，但每个重复数最多出现4个。请设计一个分治算法，找到该数组的拐点（即第m个元素），输出该拐点元素的值。
输入
第1行为数组S中元素个数n；接下来的n行中，每行有一个正整数。
输出
输出该拐点元素的值
样例输入
12 1 2 3 3 3 5 5 7 5 5 3 2样例输出
7
思路分析
其实我第一反应是双指针法，并不是题目要求的分治策略。两个指针一头一尾，比较大小不断靠拢，直到找到拐点，当然拐点位置无关紧要，其实只要值相等输出值就可以了，其实还挺简单的哈？
代码实现
#includeusing namespace std; int main() { int T[205] = { 0 }; int N; cin >> N; for (int i = 0; i < N; i++) { cin >> T[i]; } int p = 0, q = N - 1; while (p < q) { if (T[p] < T[q]) p++; else q--; } cout << T[p] << endl; return 0; }
思路优化
我真看不出来哪里有用递归的必要，如果说一定要用递归分治策略，我只能想到二分查找，找到最大值？因为先递增后递减，所以我们的递归出口设置成比前一位大、比后一位小就输出，但是仔细看题的话，如果拐点的值恰好重复了呢？如果都加上可等，那在前面出现重复时就输出了，也不符合题意。唉，我真的想不到应该怎么用递归分治来实现了，我先把自加过程换成递归形式或许姑且算满足要求，这里就不用双指针了。如果大家有思路欢迎提出，我来补充。
以下是对应的代码：
#includeusing namespace std; int FindInflection(int T[], int k) { if (T[k] > T[k + 1]) return k; else FindInflection(T, k + 1); } int main() { int T[205] = { 0 }; int N; cin >> N; for (int i = 0; i < N; i++) { cin >> T[i]; } int k = FindInflection(T, 0); cout << T[k] << endl; return 0; }
这里补充一点题外话，在学习计组的过程中，按照0000 0000到1111 1111的顺序，我们学习的补码就是一个先递增再递减的形式 ：0000 0000代表±0，0111 1111代表+127，1000 0000代表-128，1000 0001代表-127，直到1111 1111代表-1。这也是为什么会有移码的发明，补码不能根据机器数很好地反映数据的大小，移码通过不区分正负给真值加上
达到能够比较大小、并且是完整编码的效果。当然这里仅是我对这个题的无端联想，或许这个题目并不是毫无意义。