圆内的整数点 - 递归问题

Question

我正在尝试编写程序来查找圆内具有整数坐标的点。程序应该从用户那里读取圆的半径。

正确答案示例如下图

我需要使用迭代和递归来编写它。对于 radius=100:

迭代工作正常

 static int FindPointsByIteration(double minusRadius, double radius)
    {
        int result = 0;
        for (int x = (int)minusRadius; x <= (int)radius; x += 1)
        {
            for (int y = (int)minusRadius; y <= (int)radius; y += 1)
            {
                if (((x * x) + (y * y)) < (radius * radius)) result++;

            }
        }
        return result;
    }

如果我打开 EXE 文件，没有堆栈溢出的最大半径是 69。 VS里面是62，可以优化一下吗？

static int FindPointsByRecursion(double x, double y, double radius, int result)
    {
        //Console.WriteLine($"x: {x}, y: {y},radius: {radius}, result: {result}");
        if (((x * x) + (y * y)) < (radius * radius)) result++;
        if (y >= -1 * (int)radius)
        {
            if (x <= (int)radius)
            {
                x++;
                return FindPointsByRecursion(x, y, radius, result);
            }
            
            x = -1 * (int)radius;
            y--;
            return FindPointsByRecursion(x, y, radius, result);
        }
        return result;
    }

Answer 1

我认为您可以通过只接受一个参数 radius 来简化 FindPointsByIteration。问题描述指出它是一个圆形（不是椭圆形），它只有一个半径。此外，半径是标量而不是向量。它从任何方向都有相同的数量。因此，radius也可以表示minusRadius。例如

static int FindPointsByIteration(double radius)
{
    int points = 0;

    for (int x = (int)-radius; x <= radius; x++)
    {
        for (int y = (int)-radius; y <= radius; y++)
        {
            if (((x * x) + (y * y)) < (radius * radius))
            {
                points++;
            }
        }
    }
    return points;
}

以上函数执行 (2R)^2 次迭代。 FindPointsByIteration(2) 需要 16 次迭代。 FindPointsByIteration(100) 需要 40,000 次迭代。对于迭代，没问题。对于递归，它可能太多了。我们需要考虑另一种策略。

因为是圆，我们可以把它分成4个象限。我们只计算象限 I 中的点并乘以 4，结果应该接近于解决方案。但是，有一个陷阱。我们不应该将原点和位于轴上的点相乘，例如（[0,y] 和 [x,0]），因为它们在象限之间共享。

考虑一个半径为 6 的圆：

其整数坐标主要有3类

起源（红色）。

总是[0,0]。任何圈子都应该有一个

轴上的点（绿色）。

这取决于半径。半径 > 1 的圆会有。该数字等于小于半径乘以 4 的最大整数。

象限内的点（蓝色）

以象限I为例。我们通过bottom-up、right-to-left的方法来计算点数。从 [5,1] 开始（[6,1] 已知 out-of-scope）。如果 [5,1] 在范围内，则 y:1 的点数为 5。这是因为 [5, 1

示例

static int FindPointsByRecursion(double radius)
{

    if (radius < 0) { return 0; }

    int points = 0;
    // origin
    if (radius > 0) { points++; }
    // points on axis
    int longestEdge = IntegerSmallerThan(radius);
    points += longestEdge * 4;
    // points contained in quadrant
    points += FindPointsInQuadrant(1, longestEdge, radius) * 4;

    return points;
}

// return the greatest integer just smaller then n
static int IntegerSmallerThan(double n)
{
    int i = (int)n;
    return (n == i) ? --i : i;
}

static int FindPointsInQuadrant(int x, int y, double radius)
{
    // out of bound,  return 0
    if (x >= radius || y < 1) return 0;

    if ((x * x) + (y * y) < (radius * radius))
    {
        // if inside scope, move 1 row up
        return y + FindPointsInQuadrant(x + 1, y, radius);
    }
    else
    {
        // if outside scope, move 1 column left
        return FindPointsInQuadrant(x, y - 1, radius);
    }
}

主要

Console.WriteLine("FindPointsByIteration");
Console.WriteLine(FindPointsByIteration(1));
Console.WriteLine(FindPointsByIteration(2));
Console.WriteLine(FindPointsByIteration(2.1));
Console.WriteLine(FindPointsByIteration(2.5));
Console.WriteLine(FindPointsByIteration(5));
Console.WriteLine(FindPointsByIteration(100));
Console.WriteLine("\nFindPointsByRecursion");
Console.WriteLine(FindPointsByRecursion(1));
Console.WriteLine(FindPointsByRecursion(2));
Console.WriteLine(FindPointsByRecursion(2.1));
Console.WriteLine(FindPointsByRecursion(2.5));
Console.WriteLine(FindPointsByRecursion(5));
Console.WriteLine(FindPointsByRecursion(100));

输出

FindPointsByIteration
1
9
13
21
69
31397

FindPointsByRecursion
1
9
13
21
69
31397

Answer 2

四分之一的分数是个好主意，但我想我找到了更简单的解决方案（当然有你的帮助）。这是第一次调用方法的代码：

points=4* FindPointsByRecursion(radius, 1, (int)radius, points);
points+= ((int)radius - 1) * 4 + 1;

这里还有一个计数方法：

static int FindPointsByRecursion(double radius, int x, int y, int points)
    {
        if (y < 1) return points;
        if ((x * x) + (y * y) < (int)(radius * radius))
        {
            points++;
            return FindPointsByRecursion(radius, x + 1, y, points);
        }
        else
        {
            x = 1;
            return FindPointsByRecursion(radius, x, y - 1, points);
        }
        return points;
    }

只需要一种方法

圆内的整数点 - 递归问题

Integer points inside a circle - problem with recursion

c#

stack-overflow

recursion