[C++知识库] 第十二届蓝桥杯省赛大学B组试题D货物摆放

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 第十二届蓝桥杯省赛大学B组试题D货物摆放 -> 正文阅读

[C++知识库]第十二届蓝桥杯省赛大学B组试题D货物摆放

试题题目：

在这里插入图片描述
本题答案：2430
解题思路：

第一次编写程序：
?? 题目给出的 $n$ 数值为 $16$ 位数字， $C$ 语言中有类型 $l o n g$ ? $l o n g$ ? $i n t$ ，其范围为 $? 9223372036854775808$ ~ $9223372036854775807$ ，为 $19$ 位数值完全可以存储 $n$ ；观察题目给出的例知：不需要进行去重处理。即虽因数相同，但所在位置不同，属于两种不同的方案。编写一个程序计算 $n$ 的所有因数，发现因数个数为 $128$ 个，可以简单地使用暴力的方法（三重循环），当符合 $“ n =$ 因数1 $?$ 因数2 $?$ 因数3 $”$ 式子时，统计变量 $s u m$ 加一。代码如下：

#include<stdio.h>
#include<math.h>
#define n 2021041820210418 
long long int inshu[1000];
int sum = 0;
int main(){
	long long int geshu;
	int i,j,z;
	geshu = factor(n);
	for(i=0;i<geshu;i++){
		for(j=0;j<geshu;j++){
			for(z=0;z<geshu;z++){
				if(inshu[i] * inshu[j] *inshu[z] == n){
					sum++; 
					//printf("%lld * %lld *%lld = %lld  %lld \n",inshu[i],inshu[j],inshu[z],n,sum);//检测代码 
				}
			}
		}
	}
	printf("%d\n",sum);
	return 0;
}

int factor(long long int N){  //寻找N的所有因数的函数； 
	long long int i,k;
	k = 0;
	for(i=1; i<=sqrt(N); i++){  //这里找寻找到了一半的因数 
		if(N%i ==  0){
			inshu[k++] = i;
		}	
	}
	if(sqrt(N) == inshu[k-1]){ i = k-1; }   //当这个数是某个数的平方项时需要在因数中减去一个数，避免因数重复
	else{ i = k; }
	while(--i >= 0){           //把另一半的因数补齐 
		inshu[k++] = N / inshu[i];
	}
	return k;
}

第二次编写程序（第一次优化）：
??暴力求解的方法，其时间复杂度为 $O(n^3)$ ，造成了时间上的消耗，对上一个算法进行优化，优化方法为：通过调用 $f a c t o r ()$ 函数，找出n的所有因数，把 $n$ 拆分为 $“ n =$ 因数1 $?$ 因数2 $?$ 因数3 $”$ 的式子；在对因数2调用 $f a c t o r ()$ 找出因数2的所有因数，把因数2拆分为 $“$ 因数2 $=$ 因数21 $?$ 因数22 $”$ 的式子；把这两个式子合并，便可以得出 $“ n =$ 因数1 $?$ 因数2 $?$ 因数3 $”$ ”，统计式子的个数，便可以得出答案。代码：

#include<stdio.h>
#include<math.h>
#define n 2021041820210418 
int sum = 0;      //统计式子个数的变量 
long long int *factor(long long int N,long long int inshu[1000]);
int main(){
	long long int yinshu[1000] = {0}; //存储n的所有的因数； 
	int i,j;
	factor(n,yinshu);
	for(i=0; i<yinshu[999]; i++){
		long long int zinshu[1000] = {0}; //存储所有因数的因数数组
		factor(n/yinshu[i],zinshu);
		for(j=0;j<zinshu[999]; j++){
			sum++;
			//printf("%lld * %lld * %lld = %lld  %d \n",yinshu[i],zinshu[j],n/yinshu[i]/zinshu[j],n,sum); //检测代码 
		}
	} 
	printf("%d\n",sum);
	return 0;
}

long long int *factor(long long int N,long long int inshu[1000]){
	long long int i,k;
	k = 0;
	for(i=1;i<=sqrt(N);i++){  //这里找寻找到了一半的因素 
		if(N%i == 0){
			inshu[k++] = i;
		}	
	}
	if(sqrt(N) == inshu[k-1]){ i = k-1; }   //当这个数是某个数的平方项时需要在因数中减去一个数 
	else{ i = k; }
	while(--i >= 0){   //把另一半的因数补齐 
		inshu[k++] = N / inshu[i];
	}
	inshu[999] = k;   //计算之前跑一下程序发现n因数不超过900个,可知k就是N的因子个数，并把它储存与inshu数组的最后一个值，目的为了传回到主函数中。 
	return inshu;
}

第三次编写程序（第二次优化）
??通过深度分析，比较上述两个算法，可以对以上算法进一步简化。
??优化过程：因不需要去重，假设 $f 1 ? f 2 ? f 3 = n$ ，根据这一个式子直接可以得出另外五个式子：“ $f 1 ? f 3 ? f 2 = n$ ”、“ $f 2 ? f 1 ? f 3 = n$ ”、“ $f 2 ? f 3 ? f 1 = n$ ”、“ $f 3 ? f 1 ? f 2 = n$ ” 以及 “ $f 3 ? f 2 ? f 1 = n$ ”。
??注意：
??(1)当 $f 1 = f 2 = f 3$ 时， $f 1 ? f 2 ? f 3 = n$ 只能算作一个式子；
??(2)当 $f 1 = f 2$ 或者 $f 1 = f 3$ 或者 $f 2 = f 3$ 时, $f 1 ? f 2 ? f 3 = n$ 改变位置后共得出三个式子；
??(3)当 $\neq f2 \neq f3$ 时， $f 1 ? f 2 ? f 3 = n$ ,可以算作六个不同式子；
??(4)为了避免重复计算，需要保证 $\le f2 \le f3$ ；
??以上两个算法，都使用了函数和数组，求因数再储存因数，消耗大量的存储空间。而求因数的过程特别简单，就是拿这个数( $n$ )除以小于它的数值( $i$ )，如果能够被整除( $\bmod i = 0$ )，那么 $i$ 就是它的第一个因数， $n / i$ 就是它的第二个因数( $j$ )。用一个循环即可实现，循环条件设置为( $\le sqrt(n)$ )，保证了第一个因数小于第二个因数；再对第二个因数使用同样的循环，寻找出第二个因数的因数。第三个因数就是 $n / i / j$ .
具体代码：

#include<stdio.h>
#include<math.h>
#define n 2021041820210418 
int main(){
	long long int i,j;
	int sum = 0;      //统计式子个数的变量 
	for(i=1;i<=sqrt(n);i++){
		if(n%i == 0){  //i是n的第一个因数 
			for(j=i;j<=sqrt(n/i);j++){ //j从i开始循环,保证了i<=j 
				if(n/i%j == 0){  //j是n的第二个因数 
					if(i==j && j==n/i/j){sum++;}
					else if(i==j || j==n/i/j || i==n/i/j){sum+=3;}
					else {sum+=6;}
					//printf("%lld  %lld %lld %d \n",i,j,n/i/j,sum); //检测代码
				}	
			}
		}
	}
	printf("%d",sum);
}