蓝桥杯2014年第五届真题——拼接平方数(C/C++)

拼接平方数

一、题目内容 

题目描述 

小明发现49很有趣,首先,它是个平方数。它可以拆分为4和9,拆分出来的部分也是平方数。169也有这个性质,我们权且称它们为:拼接平方数。
    100可拆分1 00,这有点勉强,我们规定,0 00 000 等都不算平方数。
    小明想:还有哪些数字是这样的呢?
    你的任务出现了:找到某个区间的所有拼接平方数。

输入

 两个正整数  a b (a<b<10^6)

输出

 若干行,每行一个正整数。表示所有的区间[a,b]中的拼接平方数

样例输入

1 200

样例输出

49
169 

二、思路分析

        看完题目和样例,可以发现题目中蕴含了一个隐藏的条件,那就是拼接的数是由两段数字构成的,那么就可以通过拆分的方式分成两段数字进行操作。

判断思路:

1. 首先去除自身无法拆分的,即小于10的数。

2. 判断自身是否是平方数。

3. 拆分后的两段数字是否都是平方数。

        判断是否是平方数其中关键是判断开方后的数字是否是整数,这里提供一种方法:

floor(sqrt(n) + 0.5) != sqrt(n)

        floor()为向下取整函数,sqrt()为开方函数,一个数字开方后加上0.5后向下取整,如果等于其开方后的自己,则自己的开方数字为整数。这是一种无视类型直接求出需求的方法,此外这个方法还同样适用于一些判断计算结果是否有小数的计算。


三、代码实现

#include <bits/stdc++.h> //万能头文件
using namespace std;

int numberLength(int number) { //判断数字的位数
	int length = 1; 
	while (number /= 10) {
		++length;
	}
	return length;
}

int main() {
	int a, b;
	cin >> a >> b;
	for (int n = a; n <= b; n++) {
		if (n < 10) //无法拆分
			continue;
		if (floor(sqrt(n) + 0.5) != sqrt(n)) //自身开平方不是整数
			continue;
		int l, r; //l r 分别为拆分后的左右两部分数字
		int L = numberLength(n);
		while (L >= 2) {
			l = n / (pow(10, L - 1));
			r = n % (int)(pow(10, L - 1)); //注意强制转换为int,否则会报错
			if (l != 0 && r != 0 && floor(sqrt(l) + 0.5) == sqrt(l)
			        &&  floor(sqrt(r) + 0.5) == sqrt(r)) { //判断是否满足拼接平方数
				cout << n << endl;
				break;
			}
			L--;
		}
	}
	return 0;
}

注:因水平有限,如有错误和需要改进完善之处,欢迎大家纠正指教,不胜感激。


上一篇:敲代码的第五天:不知名(c++)


下一篇:《算法零基础》第10讲:因子分解和枚举(部分)