一、众数问题：
| 1. | 众数问题 问题描述： 给定含有n 个元素的多重集合S，每个元素在S 中出现的次数称为该元素的重数。多重集S 中重数最大的元素称为众数。 例如，S={1，2，2，2，3，5}。 多重集S 的众数是2，其重数为3。 编程任务： 对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。 数据输入： 输入数据由文件名为input.txt 的文本文件提供。文件的第1 行多重集S 中元素个数n；接下来的n 行中，每行有一个自然数。 结果输出: 程序运行结束时，将计算结果输出到文件output.txt 中。输出文件有2 行，第1 行给出众数，第2 行是重数。 输入文件示例 输出文件示例 input.txt output.txt 6 2 1 3 2 2 2 3 5 |
代码如下：
#include <iostream> #include <algorithm>//sort()函数头文件 using namespace std; #define N 10000 bool cmp(int a,int b){ return a<b; } int MaxNum=0; //存储众数大小 int MaxNumCount=0; //存储众数个数 int num[10000]; void split(int left,int right){ if (left >=right) return;//越界跳出 int FirstLeft=left;//记录初始最左侧 int FirstRight=right;//记录初始最右侧 int mid=(left+right)/2; for(;left<mid &&num[left]!=num[mid];left++);//找到中位数的左临界 for(;right>mid&&num[right]!=num[mid];right--);//找到中位数的右临界 if(MaxNumCount<right-left+1){MaxNum=num[mid];MaxNumCount=right-left+1;} //若此中位数个数大于众数个数，则更新 //若中位数左临界左边数字个数小于众数个数，则不需要执行下述操作；中位数右临界数字亦然 if(left-FirstLeft>MaxNumCount )split(FirstLeft,left-1); if(FirstRight-right>MaxNumCount)split(right+1,FirstRight); } int main() { int n;cin>>n; for(int i=0;i<n;i++){ cin>>num[i]; } sort(num,num+n,cmp);//将数组从小到大排序 int left0=0;int right0=n-1; split(left0,right0); cout<<MaxNum<<endl; cout<<MaxNumCount<<endl; return 0; }
二、邮局选址问题
| 2. | 邮局选址问题 问题描述： 在一个按照东西和南北方向划分成规整街区的城市里，n 个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y 坐标表示南北向。各居民点的位置可以由坐标(x,y) 表示。街区中任意2 点(x1,y1) 和(x2,y2) 之间的距离可以用数值|x1-x2|+|y1-y2| 度量。 居民们希望在城市中选择建立邮局的最佳位置，使n 个居民点到邮局的距离总和最小。 编程任务： 给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。 数据输入： 由文件input.txt 提供输入数据。文件的第1 行是居民点数n，1<=n<=10000。接下来n 行是居民点的位置，每行2 个整数x 和y，-10000<=x，y<=10000。 结果输出: 程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是n 个居民点到邮局的距离总和的最小值。 输入文件示例 输出文件示例 input.txt output.txt 5 10 1 2 2 2 1 3 3 -2 3 3 |
代码如下：
#include <iostream> #include <algorithm>//sort()函数头文件 using namespace std; #define N 10000 bool cmp(int a,int b){ return a<b; } int main() { int n;cin>>n; int X=0, Y=0;//（X,Y）记录邮局位置 int MinDis=0; int x[N],y[N]; for(int i=0;i<n;i++){ cin>>x[i]>>y[i]; } //街区中任意2 点(x1,y1) 和(x2,y2) 之间的距离可以用数值|x1-x2|+|y1-y2| 度量。 //所以可将x，y分开计算 sort(x,x+n,cmp);//排序 sort(y,y+n,cmp);//排序 X=x[n/2];Y=y[n/2]; //下图有解释，为何取[n/2]，以及坐标数为奇/偶数此取值皆满足 //邮局位置找法思想，两边之和大于第三边，x取值必须在以两点为一组，在其连线上 for(int i=0;i<n;i++){ int dis1=x[i]-X;int dis2=y[i]-Y; if(dis1<0) dis1=-1*dis1;//距离为正值，若作差为负数，则取相反数 if(dis2<0) dis2=-1*dis2;//距离为正值，若作差为负数，则取相反数 MinDis=MinDis+dis1+dis2;//求和 } cout<<MinDis<<endl; return 0; }
编辑
三、集合划分问题
| 3. | 集合划分问题 问题描述： n 个元素的集合{1,2,., n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2， 3，4}可以划分为15 个不同的非空子集如下： {{1}，{2}，{3}，{4}}， {{1，2}，{3}，{4}}， {{1，3}，{2}，{4}}， {{1，4}，{2}，{3}}， {{2，3}，{1}，{4}}， {{2，4}，{1}，{3}}， {{3，4}，{1}，{2}}， {{1，2}，{3，4}}， {{1，3}，{2，4}}， {{1，4}，{2，3}}， {{1，2，3}，{4}}， {{1，2，4}，{3}}， {{1，3，4}，{2}}， {{2，3，4}，{1}}， {{1，2，3，4}} 其中，集合{{1，2，3，4}} 由1 个子集组成；集合{{1，2}，{3，4}}，{{1，3}，{2， 4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2， 3，4}，{1}} 由2 个子集组成；集合{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}， {2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}} 由3 个子集组成；集合{{1}，{2}，{3}，{4}} 由4 个子集组成。 编程任务： 给定正整数n 和m，计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。 数据输入： 由文件input.txt 提供输入数据。文件的第1 行是元素个数n 和非空子集数m。 结果输出: 程序运行结束时，将计算出的不同的由m个非空子集组成的集合数输出到文件output.txt 中。 输入文件示例 输出文件示例 input.txt output.txt 4 3 6 |
代码如下：
#include <iostream> using namespace std; int num(int n, int m){ if(n==m||m==1) return 1; else{return num(n-1,m-1)+num(n-1,m)*m;} } int main() { int n,m;cin>>n>>m; cout<<num(n,m)<<endl; return 0; }
对{1,2,3}进行划分：
（1）、1个子集：{1,2,3} 即num(3,1)=1
（2）、2个子集：{1,2},{3} {1,3},{2} {2,3},{1} 即num(3,2)=3
（3）、3个子集：{1},{2},{3} 即num(3,3)=1
对{1,2,3,4}进行划分为3个子集：
（1），在对{1,2,3}划分为两个子集的结果中加入{4}: {1,2},{3},{4} {1,3},{2},{4} {2,3},{1},{4} 此个数为num(3,2)
（2）,在对{1,2,3}划分为三个子集的结果中加入元素4:{1,4},{2},{3} {1},{2,4},{3} {1},{2},{3,4} 此个数为num(3,3)*3
综上所述：
num(4,3)=num(3,2)+num(3,3)*3
推广至num(n,m)为： num(n,m)=num(n-1,m-1)+num(n-1,m)*m
且当 n==m或者m==1时，num(n,m)=1
四、输油管道问题
| 4. | 输油管道问题 问题描述： 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置, 即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。 编程任务： 给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。 数据输入： 由文件input.txt 提供输入数据。文件的第1 行是油井数n，1<=n10000。接下来n 行是油井的位置，每行2 个整数x 和y，-10000<=x，y<=10000 。 结果输出: 程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是油井到主管道之间的输油管道最小长度总和。 输入文件示例 输出文件示例 input.txt output.txt 5 6 1 2 2 2 1 3 3 -2 3 3 |
代码如下：
#include <iostream> #include <algorithm> using namespace std; #define N 10000 bool cmp(int a,int b){ return a<b; } int main() { int n;cin>>n; int X=0, Y=0;//（X,Y）记录邮局位置 int MinDis=0; int x[N],y[N]; for(int i=0;i<n;i++){ cin>>x[i]>>y[i]; } sort(x,x+n,cmp); sort(y,y+n,cmp); X=x[n/2];Y=y[n/2];//邮局位置找法思想，两边之和大于第三边 //将坐标两两分组，距离两点最近距离肯定在其两点间连线上，取交集即可； for(int i=0;i<n;i++){ int dis1=x[i]-X;int dis2=y[i]-Y; if(dis1<0) dis1=-1*dis1; if(dis2<0) dis2=-1*dis2; MinDis=MinDis+dis2; //只需要y坐标距离差的绝对值（与第二题不同，此题为东西走向管道，不需考虑X坐标） } cout<<MinDis<<endl; return 0; }
五、 整数因子分解问题
| 5. | 整数因子分解问题 问题描述： 大于1 的正整数n 可以分解为：n=x1*x2*…*xm。 例如，当n=12 时，共有8 种不同的分解式： 12=12； 12=6*2； 12=4*3； 12=3*4； 12=3*2*2； 12=2*6； 12=2*3*2； 12=2*2*3 。 编程任务： 对于给定的正整数n，编程计算n 共有多少种不同的分解式。 数据输入： 由文件input.txt 给出输入数据。第一行有1 个正整数n (1≤n≤2000000000)。 结果输出: 将计算出的不同的分解式数输出到文件output.txt 。 输入文件示例 输出文件示例 input.txt output.txt 12 8 |
代码如下：
#include <iostream> using namespace std; int factor(int n){ int sum=0; for(int i=n;i>1;i--){ if(n%i==0){//i是n的因子 int j=n/i; if(factor(j)==0) sum++; else{ sum=sum+factor(j); } } } return sum; } int main() { int n;cin>>n; cout<<factor(n)<<endl; return 0; }
