练习题 幸运数

题目

问题描述

小蓝认为如果一个数含有偶数个数位，并且前面一半的数位之和等于后面一半的数位之和，则这个数是他的幸运数字。例如?23142314?是一个幸运数字, 因为它有?44?个数位, 并且?2+3=1+42+3=1+4?。现在请你帮他计算从?11?至?100000000100000000?之间共有多少个不同的幸运数字。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

运行限制

提交代码

提交代码1

//幸运数

//填空题
//小蓝的幸运数字：整数，偶数位，前一半数位之和等于后一半数位之和
//求1-1e8之间有多少幸运数字
//每个数位开始的数字1000......0
//可以从头到尾遍历各个数字判断每一个是否符合
//可以组成幸运数字判断是否在范围内 
//偶数位最多为8位 

#include<iostream>
using namespace std;

int cnt = 1;//数位个数
int result = 0;//结果 
int t = 1;

int main(){
	int temp;//暂存当前数
	int l = 0,r = 0;//前后数位之和 
	 
	for(int i = 1;i < (int)(1e8);i++){
		if(cnt % 2 == 1){
			//奇数位
			i *= 10;
			t *= 100;
			cnt++; 
		}else{
			//偶数位
			temp = i;//暂存当前数
			l = 0,r = 0;//前后数位之和 
			
			//计算后面的数位之和
			for(int j = 0;j < cnt / 2;j++){
				r += temp % 10;
				temp /= 10;
			}
			
			//计算前面的数位之和
			for(int j = 0;j < cnt / 2;j++){
				l += temp % 10;
				temp /= 10;
			}
			
			//判断是否是幸运数
			if(l == r){
				result++;
			}
			
			//判断是否下一个数会多一位
			if(t == i + 1){
				cnt++;
			}
		}
	} 
	
	//输出结果
	printf("%d",result); 
	
	return 0;
} 

?解题思路：暴力枚举，容易想到，但会超时，适合填空题。

提交代码2

//幸运数

//填空题
//小蓝的幸运数字：整数，偶数位，前一半数位之和等于后一半数位之和
//求1-1e8之间有多少幸运数字
//每个数位开始的数字1000......0
//可以从头到尾遍历各个数字判断每一个是否符合
//可以组成幸运数字判断是否在范围内 
//偶数位最多为8位 
//两个二维数组存各种可能位数之和 

#include<iostream>
using namespace std;

int result = 0;//结果
//最多前后各有四位，位数之和最大为36 
int sum1[5][37],sum2[5][37];

int main(){
	int temp;//暂存遍历的数 
	int t = 1;//位数
	int sum = 0; 
	
	//判断前面的位数之和的情况 
	//遍历1-9999
	for(int i = 1;i < 10000;i++){
		temp = i;
		sum = 0;
		
		//求数位之和 
		while(temp != 0){
			sum += temp % 10;
			temp /= 10;
		}
		
		sum1[t][sum]++;
		
		//更改位数 
		if(i == 9 || i == 99 || i == 999){
			t++;
		}
	}
	
	t = 1;
	//判断后面的位数之和的情况
	for(int i = 1;i < 10000;i++){
		temp = i;
		sum = 0;
		
		//求数位之和 
		while(temp != 0){
			sum += temp % 10;
			temp /= 10;
		}
		
		//后面的数位前面可以补0
		for(int j = t;j < 5;j++){
			sum2[j][sum]++;
		} 
		
		//更改位数 
		if(i == 9 || i == 99 || i == 999){
			t++;
		}
	} 
	
	//计算结果
	for(int i = 1;i < 5;i++){
		for(int j = 1;j < 37;j++){
			result += sum1[i][j] * sum2[i][j];
		}
	} 
	
	//输出结果
	printf("%d",result); 
	
	return 0;
} 

解题思路：对逻辑进行优化，利用空间换时间，增加两个二维数组，记录前面位数之和各种和的可能个数和后面位数之和各种和的可能个数，二者相乘并相加，得到结果，不会超时。