从标准输入中读取一个自然数 n.找到小于或等于 n 的最大完美平方

Question

#include <stdio.h>
#include <stdlib.h>
int main() {
int i, j, n, maxi = 0;
printf("n Introduce the number:n");
scanf("%d", &n);
for (j = 1; j <= n; j++)
{
i = 0;
while (i < j) {
i++;
if (j == i * i) {
if (j > maxi) {
maxi = j;
printf("%d", maxi);
}
}
}
}
return 0;
}

我必须找到小于数字的最大完美正方形n，我成功地找到了所有小于数字n的完美正方形，但由于每次它找到一个完美的正方形时，它都会显示它，我想不出任何方法来比较找到的所有完美正方形(或者至少我认为这就是问题所在(，所以我将不胜感激。 我已经知道您也可以使用更简单的方法(如下(解决此问题，如果您对如何解决它有任何其他想法，我想听听。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int n,j;
printf("n Your number:n");
scanf("%d",&n);
j=(int)sqrt(n);
printf("%d",j*j);
return 0;
}

Answer 1

这里只需要一个循环。 检查是否i*i <= n。 如果是这样，请将maxi设置为i*i并递增i：

int n, i = 1, sq = 1;
printf("n Introduce the number:n");
scanf("%d", &n);
while (i*i <= n) {
sq = i*i;
i++;
}
printf("sq=%dn", sq);

Answer 2

求小于

或等于 n 的最大完美平方

对于n>=0，这类似于求n的整数平方根。

unsigned greatest_perfect_square(unsigned x) {
unsigned root = usqrt(x);
return root * root;
}

---

如果您对如何解决它有任何其他想法，我想听听。

找到平方根的复杂程度顺序是 O(type-n-的位宽(。 例如 16 次迭代。

#include <limits.h>
unsigned usqrt(unsigned x) {
unsigned y = 0;
unsigned xShifted = 0;
const unsigned MSBit = UINT_MAX - UINT_MAX/2;
// This  constant relies on no padding and bit width even
const unsigned TwoBitCount_N = sizeof(x) * CHAR_BIT / 2;
for (unsigned TwoBitCount = TwoBitCount_N; TwoBitCount > 0; TwoBitCount--) {
// Shift `xShifted` 2 places left while shifting in the 2 MSbits of x
xShifted <<= 1;
if (x & MSBit) {
xShifted |= 1;
}
x <<= 1;
xShifted <<= 1;
if (x & MSBit) {
xShifted |= 1;
}
x <<= 1;
// Shift the answer 1 bit left
y <<= 1;
// Form test value as y*2 + 1
unsigned Test = (y << 1) | 1;
// If xShifted big enough ...
if (xShifted >= Test) {
xShifted -= Test;
// Increment answer
y |= 1;
}
}
return y;
}

---

OP的方法要慢得多。 甚至内部循环也需要O(sqrt(n((时间。

注意：
OP的代码：j == i * i容易溢出，当j较大时会导致答案不正确。
j/i == i执行类似测试而不会溢出。

---

@Jonathan Leffler提出了牛顿-拉夫森近似方法。 下面一些经过轻度测试的代码运行速度非常快，通常只需要几次迭代。
我怀疑这对主要部分来说是O(log(bit-width-of-type-n))，但当然仍然O(log(bit-width-of-type-n))bit_width().
这两个功能都可以改进。

unsigned bit_width(unsigned x) {
unsigned width = 0;
while (x) {
x /= 2;
width++;
}
return width;
}
unsigned usqrt_NR(unsigned x) {
if (x == 0) {
return 0;
}
unsigned y = 1u << bit_width(x)/2;
unsigned y_previous;
unsigned diff;
unsigned diff1count = 0;;
do {
y_previous = y;
y = (y + x/y)/2;
diff = y_previous < y ? y - y_previous : y_previous - y;
if (diff == 1) diff1count++;
} while (diff > 1 || (diff == 1 && diff1count <= 1));
y = (y_previous + y)/2;
return y;
}

Answer 3

这最大限度地减少了乘法的次数：它寻找大于 n 的第一个正方形，这意味着紧接在前面的完美正方形是解决方案。

for (i = 1; i <= n; i++) {
if (i*i > n) {
break;
}
}
i--;
// i*i is your answer

在某些平台上，利用以下事实可能很有用：(i+1)*(i+1) = i*i + 2*i + 1，或者换句话说，如果你已经有 i^2，(i+1(^2 是通过将 i 添加到它两次并递增 1 来获得的;在开始时，0^2 是 0 来启动循环。

for (i = 0, sq = 0; i < n; i++) {
sq += i; // Or on some platforms sq += i<<1 instead of two sums
sq += i; // Some compilers will auto-optimize "sq += 2*i" for the platform
sq++;    // Or even sq += ((2*i)|1) as adding 1 to even numbers is OR'ing 1
if (sq > n) {
break;
}
// if sq is declared as signed integer, a possible overflow will
// show it as being negative. This way we can still get a "correct" result
// with i the smallest root that does not overflow.
// In 16-bit arithmetic this is 181, root of 32761; next square would be
// 33124 which cannot be represented in signed 16-bit space.
if (sq < 0) {
break;
}
}
// (i*i) is your answer