C++（阶段练习二）

有点。

313人浏览 · 2026-06-18 11:04:28

有点。 · 2026-06-18 11:04:28 发布

分享内容

阶乘数码
Pell 数列
最大乘积

浮点数的比较

由于浮点数在计算机中是以二进制形式近似表示的,因此它们可能存在微小的误差。直接使用 == 或 != 进行比较可能会导致意外的结果。为了避免这些问题,通常需要引入一个“误差范围”(epsilon)来进行比较。如果两个浮点数的差值小于epsilon,则认为它们“足够接近”,可以认为相等。根据问题的精度要求选择合适的epsilon是关键。

阶乘数码

求n!中某个数码出现的次数。例如20 != 2432902008176640000,其中0出现7次。
【输入格式】
输入一行,一个正整数n(n≤100)和正整数a(0≤a≤9)。
【输出格式】
输出一个整数,表示n!中a出现的次数。
【输入样例】200
【输出样例】7
1、输入n,a

2、计算n!

3、统计a出现的次数

当n>20,n!计算结果long long保存不了。所以需要进行高精度的阶乘计算。

#define MAXN 160
int s[MAXN]={0};// 保存阶乘结果

阶乘计算只涉及乘法,而高精度乘法的数据一般逆序存储。
在这里插入图片描述
算法步骤:

输入n,a
计算阶乘(结果逆序保存在s[])

1 初始化s[0]=1,其他元素值=0。
2 循环进行累乘计算(k=2~n)
初始进位up=0;
从低位到高位(i=0~MAXN-1)逐位处理:
a) 计算:t=s[i]*k+up。
b)保存个位数:s[i]=t%10。
c)更新进位:up=t/10。

统计数码a出现的次数
(先逆序去前导0,再逐位比较)

完整代码

#include<iostream>
using namespace std;

#define MAXN 160
int s[MAXN]={0};// 保存阶乘结果
int n,a;
int main() {
	cin >> n >> a;
	// 计算阶乘
	s[0] = 1;
	for(int k = 2;k <= n;k++) {
		int up=0;//进位初始为0
		for(int i= 0;i <MAXN;i++){//从个位到最高位,处理进位
			int t=s[i]*k+up;//逐位*k+进位
			s[i] = t%10;// 保存个位
			up = t/10;// 留下进位部分
		}
	}
	
	//逆序去前导0
	int i = MAXN-1;
	while (s[i] == 0)
		i --;
	
	// 统计数码
	int ans=0;// 数码出现的次数
	while (i >= 0) {
		if (s[i] == a)
			ans++;
		i --;
	}
	cout << ans;
	return 0;
}

在这里插入图片描述

Pell 数列

有一种数列,它的前10项的值分别为:125 12 29 70 169 408 985 2378,这个数列被称为Pell数列,请问该数列的第n项的值是多少?(0<n <= 1000)
【输入描述】一个整数n
【输出描述】Pell数列第n项的值
【输入样例】10
【输出样例】2378
Pell 数列的10项的值分别为:1 2 5 12 29 70 169 408 985 2378
通过找规律可以得出:
初始条件
Pell[1] = 1,

Pell[2]= 2,
Pell[n]=2*Pell[n-1]+Pelln-2-递推公式

适用递推法,由第1、2项开始,逐步依次求出第3~第n项。
如果Pell数列的值都在基本数据类型能表示的范围,代码很简单,如下:

long long p[1001];
p[1] = 1;
p[2] = 2;
for(int i=3;i <= n; i++)
	p[i] = 2*p[i-1]+p[i-2];
cout << p[n];

但是本题中n <= 1000,以上代码不能通过所有测试。比如n=100时,这一项值是
66992092050551637663438906713182313772,超出了long long的范围,发生溢出,结果不
再正确。所以本题需要进行高精度计算。

#define MAXS 501
// a数组 存放 Pell数列n-2项的值
// b数组 存放 Pell数列n-1项的值
// sum 存放 Pell数列n项的值,由公式
int a[MAXS]={0},b[MAXS]={0},sum[MAXS]={0};

sum =2*b+a 计算得到

在这里插入图片描述
算法步骤:

输入n
n<3时,直接输出第1或2项的值
n>=3时,初始化a[0]=1,b[0]=2,进行n-2次递推计算:sum=2*b +a
①从0~MAXS-1,逐位套公式并处理进位
②b内容交给a,sum内容交给b,以备下一次递推

a[0]=1; // 初始化 pel1第1项
b[0]=2; //pell第2项
// 进行递推
for(int i = 3;i <= n;i++) {
	int up = 0;
	for(int j= 0;j<MAXS;j++){//高精度计算
		int temp = 2*b[j] + a[j] + up;
		sum[j] = temp%10;
		up = temp/10;
	}
	// b内容交给a,sum内容交给b

}

逆序输出结果

完整代码

#include<iostream>
using namespace std;

#define MAXS 501
//a数组 存放 Pell数列n-2项的值
// b数组 存放 Pel1数列n-1项的值
// sum 存放 Pell数列项的值,由公式 sum=2*b+a 计算得到
int a [MAXS]={0],b[MAXS]={0],sum [MAXS]={0];

int main () {
	int n;
	cin >> n;
	
	if(n == 1){// 第1项
		cout << 1;
		return 0;
	}
	if(n == 2){//第2项
		cout << 2;
		return 0;
	}
	a[0]=1;//初始化 pe1l第1项
	b[0]=2; //pell第2项
	//进行递推计算
	for(int i = 3;i <= n;i++) {
	
		int up = 0;
		for(int j= 0;j<MAXS;j++){//逐位高精度计算
			int temp = 2*b[j] + a[j] + up;
			sum[j]= temp%10;//保存个位数
			up=temp/10;//更新进位数
		}
	//b内容交给a,sum内容交给b,以备下一项的计算使用
		for(int j = 0;j < MAXS; j++) {
			a[j] = b[j];
			b[j] = sum[j];
		}
	}
	int i = MAXS-1;
	while(sum[i] == 0)//逆序去前导0
		i --;
	while(i>=0)//逆序输出结果
		cout << sum[i -- ];
	return 0;
}

【注意】本示例中数组长度501是经过估算的值。实际编程中,你可以用数学方法进行准确估算,也可以先给一个大概的长度,如果发现小一些的测试数能通过测试,但是大的测试数不能,再试着增加数组长度。
在这里插入图片描述

最大乘积

一个正整数一般可以分为几个互不相同的自然数的和,如3=1+2,4=1+3,5=1+4=2+3,
6=1+5=2+4。现在你的任务是将指定的正整数n分解成若干个互不相同的自然数(也可以不
分解,就是这个数字本身)的和,且使这些自然数的乘积最大。
【输入描述】
只一个正整数n,(3≤n≤10000)。
【输出描述】
第一行是分解方案,相邻的数之间用一个空格分开,并且按由小到大的顺序。
第二行是最大的乘积。
【输入样例】10
【输出样例】2 3 5
30
【分析】这个问题明显需要找到一个贪心策略,使得乘积最大,然后再用高精度乘法求积。

分出来的数不重复的情况下,n分成更多份,那样乘积最大。若1作因数,则显然乘积不会最大,
所以从2开始分。

以2004为例,为了使因数个数尽可能地多,我们把2004分成2+3 … +x直到和大于等于2004。
若和比2004大1,则因数个数至少减少1个,为了使乘积最大,应去掉最小的2,并将最后一个(最大)数加上1。
若和比2004大k(k>1),则去掉等于k的那个数,便可使乘积最大。
例如15:s=2+3+4+5+6=20,大于15,s-15=5,所以把5去掉。
又例如13:s=2+3+4+5=14,大于13,s-13=1,所以去掉2,并把5加1,即346。
题目要求的3≤n≤10000,需要注意的是,当n=3、4时,不分解就是最优解。

使得乘积最大的贪心策略如下:

当n=3、4时,不分解;
对于n>=5的情况:
● 先把n分成2+3 … +x直到和大于等于n;
● 进行调整:
1若和比n大1,为了使乘积最大,应去掉最小的2,并将最后一个数(最大的数)加上1;
2若和比n大k(k>1),则去掉等于k的那个数,便可使乘积最大。

算法步骤:

int a[10001]={0};//保存拆分数
int s[10001]={0};//保存所有数的乘积

输入n;
如果n小于5,自己本身就是最优解;
否则试着拆分n,拆分数2~x逐个放入a[];

int sum = 0, index = 0;
int x = 2;
while (sum < n) {
	index++;
	a [index] = x;
	sum += x; // 求和
	x++;
}

若和比n大1,为了使乘积最大,应去掉最小的2,
并将最后一个数(最大的数)加上1;
若和比n大k(k>1),则去掉等于k的那个数,便
可使乘积最大;

if(sum-n == 1){//和比n只差1时
	a[index] ++;
	a[1] = 0;
}else if ( sum-n > 1)// 和比n大起码2时
	a [sum-n-1] = 0;

把a数组中非o的数进行累乘,结果保存在s数组;

s[1] = 1;

slen=1;//s的有效长度
for(int i=1;i <= index; i++){
	if(a[i])
	//高精度数s *单精度输a[i]
	for(int j=1;j <= slen;j++) //所有有效位逐位做乘法
		s[j] *= a[i];
	for(int i=1;i <= slen;i++){//有效位处理进位
		s[i+1] += s[i]/10;
		s[i] %= 10;
	}
	while (s [slen+1]>0) {//新生成的有效位处理进位
		slen++;
		s [slen+1] += s[slen]/10;
		s [slen] %= 10;
	
	
	
	}
}

输出分解方案(非0的元素值);
输出乘积;

在这里插入图片描述

完整代码

#include<iostream>
using namespace std;
int a[10001]={0};// 保存拆分数
int s[10001]={0};//保存所有数的乘积
int n, slen=1;

// 高精度s*单精度x,结果保存在s[],有效长度保存在slen
void mul(int x) {
	for (int i=1;i <= slen; i++)// 逐位乘

		s[i] *= x;
	for(int i=1;i <= slen;i++){//逐位处理进位
		s[i+1] += s[i]/10;
		s[i] %= 10;
	}
// 处理目前最高位的进位,并更新有效长度,直到没有进位
	while (s [slen+1]>0) {
		slen++;
		s[slen+1] += s[slen]/10;
		s[slen] %= 10;
	}
}


int main(){
	cin > n;
	//如果n小于5,自己本身就是最优解。
	if (n < 5){
		cout << n << endl << n << endl;
		return 0;
	}
	//试若拆分n,拆分数2~x 逐个放入a[],从下标1开始放
	int sum=0,index=0;/*index:最后放入的数的下标*/
	int x = 2;
	while (sum < n) {
		index++;
		a [index] = x;
		sum += x;// 求和
		x++;
	}
	if(sum-n == 1){//和比n只差1时
		a[index]++; //最后出现的数+1
		a[1] = 0;//并把第一个(值是2)数清0
	}else if(sum-n>1) //和比n大起码2时
		a[sum-n-1]=0;//去掉这个多的数,例如数2放在a[1]
	
	//把非的数进行累乘
	s[1] = 1;
	slen = 1;
	for(int i=1;i <= index;i++){
		if (a[i])
			mul(a[i]);
	}
	//输出分解方案(非0的元素值)
	for(int i=1;i <= index;i++){
		if (a[i])
			cout << a[i] << ' ';
	cout << endl;
	// 输出乘积
	for(int i=slen;i>=1;i -- )
		cout << s[i];
	cout << endl;
	return 0;
}

在这里插入图片描述
本次分享的知识点

习题:阶乘数码
Pell数列
最大乘积
1、如果要找出整数a、b中较大一个,通常要用下面哪种程序结构?C

A、顺序结构

B、循环结构

C、分支结构

D、跳转结构
在这里插入图片描述

修补计算

输入两个字符串a,b,长度都不超过100位。其中a字符串都是数字字符,b
字符串由*和数字组成,*代表5。求a-b的值。数据保证a>b。

【输入】两个非负整数,每行一个。

【输出】a-b的值

【输入样例】123456789012345

234*678901234

【输出样例】121111110111111
在这里插入图片描述

#include<iostream>
#include<cstring>
using namespace std;
int a[101];// 被减数
int b[101] ; // dekk
int c[101]; //

int main() {
	char ac[101]={}, bc[101]={};
	cin >> ac >> bc;
	// 字符转整数,并逆序保存
	int lena = strlen (ac) ;
	for (int i=0; i<lena; i++)
		a[lena-1-i] = ac[i]-'0';
	
	int lenb = strlen (bc) ;
	for (int i=0; i<lenb; i++) {
		if (bc[i] == '*')//替换*为5
			b[lenb-1-i] = 5;
		else
			b[lenb-1-i] = bc[i]-'0';
	}
	// 逐位相减求差
	for (int i=0; i<lena; i++) {
		if(a[i] <b[i]){ //借位
			a[i] += 10;
			a[i+1] --;
		}
		c[i] = a[i] - b[i];
	}
	int i = lena-1;
	while(c[i] == 0)//去前导0
		i --;
	while(i>=0)//输出结果
		cout << c[i -- ];
	return 0;
}