时间戳

首页 > 解决方案 > 代码战任务。如何通过条件找到简单的平方数？

c# - 代码战任务。如何通过条件找到简单的平方数？

问题描述

我试图在 Codewar 上解决这个问题，但我不明白如何找到异常。

在这个 Kata 中，你将得到一个数字 n (n > 0)，你的任务是返回最小的平方数 N (N > 0)，使得 n + N 也是一个完美的平方。如果没有答案，则返回 -1（在 Clojure 中为 nil，在 Haskell 中为 Nothing）。

这是我写的代码：

using System;

public class SqNum
{
    public static long solve(long n){  
       int N = 1;
            long lTemp = n;
            double sum, result;
            bool isSqare;
            while(true)
            {
                sum = lTemp + N;
                result = Math.Sqrt(sum);
                isSqare = result % 1 == 0;
                if(n == 4)
                {
                  return -1;
                }

                if(isSqare == true)
                {
                    return Convert.ToInt32(result);
                }
                N++;
            }
            return -1;
      }
}

标签： c#algorithm

解决方案

如果N(square) 是p^2, 并且n+N=r^2, 你可以写

n + p^2 = r^2
n = r^2 - p^2
n = (r - p) * (r + p)

如果我们表示n为一对除数的乘积：

n = a * b     // let a<=b
a * b = (r - p) * (r + p)

我们有系统

r - p = a
r + p = b

和

p = (b - a) / 2

什么时候p最小？在最大关闭因子b和的情况下a。所以我们可以尝试从 的平方根开始计算除数n。还要注意a和b应该具有相同的奇偶性（使p整数）

伪代码：

int N = -1;
for (int a = Math.Ceiling(Math.Sqrt(n)) - 1; a > 0; a--) {
   if (n % a == 0) {
      int bma = n / a - a;
      if (bma % 2 == 0) {
         int p = bma / 2;
         int N = p * p;
         break;
      }
   }
}

例子：

n = 16
first divisor below sqrt(16) a = 2, b=8
p = 3, 16 + 9 = 25

n = 13
first divisor below sqrt(13) a = 1, b=13
p = 6, 13 + 36 = 49

n = 72
first divisor below sqrt(72) is a = 8, b= 9 - but distinct parity!
so the next suitable pair is a = 6, b = 12
p = 3, 72 + 9 = 81

推荐阅读