破解平方数-题解(C语言代码)

1241 阅读 1 评论 1 点赞

大家好，本人第一次写题解，可能会写得不好，见谅。（~~第一次写不知道写什么开场白~~）

------------

首先，要知道怎么判断平方数。这个挺简单的，只要
`int a2 = sqrt(a);`然后再用`if (a == a2*a2)`就可以判断a是否为平方数了。。
（~~我不会告诉你们我一开始是用，平方数的约数个数为奇数个，这个性质来判断的，饶了一大圈。。。~~）做完第1228题的后遗症，看到质数、约数相关的，满脑子骚操作(￣_￣|||)
再稍微吐槽一下，（~~输入数据中的t是没有用的~~），不！t可以约束数据的大小！(☆▽☆)

------------

接着，遍历所有情况。这道题，如果直接用for（）循环遍历，会发现有点难实现。因为，它的出循环条件，会随着输入的数据改变。所以，要用稍微灵活的方法遍历。

你会发现题目中的有个“非空子集合”这个字符串（~~为什么这个人说话这么奇怪，好想打他~~）

我自己比较习惯用2进制数来处理遍历子集，大概说说原理：

比如，{500 20 9}的子集就可以用2进制数表示
{}  -----对应------   000（2进制）--0（10进制）
{9}------对应-----001（2进制）--1（10进制）
{20}-----对应-----010（2进制）--2（10进制）
{20 9}----对应----011（2进制）--3（10进制）
{500}-----对应----100（2进制）--4（10进制）
{500 9}----对应---101（2进制）--5（10进制）
{500 20}--对应----110（2进制）--6（10进制）
{500 20 9}--对应--111（2进制）--7（10进制）

现在应该很明朗了吧，只要从0遍历到2^m-1(上面的例子是m=3)，再把它翻译成二进制数就OK了。

原题中，要求“非空子集合”，所以把空集的情况去掉，就是从1遍历到2^m-1。
有更好的方法，请一定要评论告诉我（~~写这个文章的人真的奇怪，为什么别人要告诉你。。。~~）

------------

最后，遍历判断，打印结果

附上AC代码
```c
#include<stdio.h>
#include<math.h>

void count( int a[100], int m)
//a[]为存放数据的数组，m为数组有多少数据
{
	int sum = 0;//用于计算符合条件的数目

int i = 1;
	int j = pow(2, m) - 1;
	//从1遍历到2^m-1，至于为什么细品一下
	while (i <= j)
	{
		int q = i;//q是用来接受每次要翻译的数
		int k = 0;//记录翻译到二进制哪一位
		int judge = 1;//计算每个子集的乘积
		while (q)
		{
			//若值为1，就是在这一轮的子集中，直接累乘
			if (q % 2)
				judge *= a[k];
			q /= 2;
			k++;
		}
		//判断是否符合条件
		int judge2 = sqrt(judge);
		if (judge == judge2*judge2)
			sum++;

i++;//很关键( $ _ $ )
	}
	printf("%d\n", sum);//直接打印结果
}

int main()
{
	int  m, a[100];
	scanf("%*d%d", &m);//不需要输入t，故第一个数据用%*d省略

while (1)
	{
		int i;
		for (i = 0; i < m; i++)
			if (scanf("%d", &a[i]) == EOF)//发现eof退出
				return 0;//直接结束程序
		count( a, m);
	}
}
```

最后的最后，中国加油！武汉加油！我相信我们一定能打赢抗击武汉肺炎的战役

0.0分

3 人评分

本文分类：题解列表
浏览次数：1241 次浏览
发布日期：2020-02-26 14:51:46
本文链接：https://blog.dotcpp.com/a/67011

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

破解平方数-题解(C语言代码)

评论列表共有 1 条评论

发表评论取消回复

破解平方数-题解(C语言代码)

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 1 条评论

发表评论 取消回复

评论列表共有 1 条评论

发表评论取消回复