三、优雅的点
题目描述
小易有一个圆心在坐标原点的圆，小易知道圆的半径的平方。小易认为在圆上的点而且横纵坐标都是整数的点是优雅的，小易现在想寻找一个算法计算出优雅的点的个数，请你来帮帮他。例如：半径的平方如果为25优雅的点就有：(+/-3, +/-4), (+/-4, +/-3), (0, +/-5) (+/-5, 0)，一共12个点。
输入描述
输入为一个整数，即为圆半径的平方,范围在32位int范围内
输出描述
输出为一个整数，即为优雅的点的个数
示例
输入：25
输出：12
第一种解法
#include <stdio.h> #include <math.h> int main() { int r_2, r, count = 0; scanf("%d", &r_2); r = (size_t)sqrt(r_2); int a = r_2, b = r_2 - a; while (a != 0) { if ((sqrt(a)+sqrt(b)) == r || (int)sqrt(a)* (int)sqrt(a) + (int)sqrt(b)* (int)sqrt(b) == r_2) count += 4; a--,b= r_2 - a; } printf("%d\n", count); return 0; }
这种算法效率低。是由0遍历到输入的半径的平方，每一次循环都判断一次是否满足优雅的点的条件，遇到数值大的通常要计算很长时间
第二种解法
#include <stdio.h> #include <math.h> int main() { int r_2, r, count = 0;//变量r_2为r的平方，r为半径，count为优雅的点的数量 scanf("%d", &r_2); r = (size_t)sqrt(r_2);//尝试求出r_2的算术平方根 int flag = 0; if (r == sqrt(r_2))//判断整数算术平方根是否存在 { flag = 1;;//存在则证明其一定有四个优雅的点（0，+/-r）、（+/-r，0） r -= 1;//由上已知r点处是优雅的点，这里就可以排除r的情况，故r-1 } int x;//建立变量x来进行循环,可以当成坐标系中圆的x坐标 for (x = 1; x <= r; x++) { double y = sqrt(r_2 - x * x);//由圆的定义求出圆的y坐标，其在圆上，但不一定为整数值 int y0 = (int)y;//建立变量y0来记录y坐标的整数部分 if (y0 == y)//如果y坐标的整数部分等于y0，则证明这组数（x，y）满足优雅的点 count++;//我们这里只求一组优雅的点的一个坐标，知道其中一个坐标就可以求出点的数量 } count *= 4;//例如知道坐标（3，4） //那么其优雅的点就为（+3，+4）、（+3，-4）、（-3、+4）、（-3，-4） if (1 == flag) count += 4; printf("%d\n", count); return 0; }
这种算法效率较高。先判断是否有（0，r）型的优雅的点，再由1遍历到半径r。
