我正在嘗試撰寫程式，該程式將找到在圓內具有整數坐標的點。程式應該從用戶那里讀取圓的半徑。
正確答案示例如下圖
我需要使用迭代和遞回來撰寫它。對于半徑 = 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;
}
uj5u.com熱心網友回復：
我認為您可以FindPointsByIteration通過只接受一個引數來簡化：radius. 問題描述表明它是一個圓形（不是橢圓形），它只有一個半徑。此外，半徑是標量而不是向量。它從任何方向都有相同的數量。因此，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 為例。我們通過自下而上、從右到左的方法計算分數。從 [1,5] 開始（[1,6] 已知超出范圍）。如果 [1,5] 在范圍內，則 x:1 的點數為 5。這是因為任何小于 5 的點都必須在范圍內（例如 [1,4]、[1,3] 等）。然后我們可以在 [2,5] 處向上移動一行并再次開始迭代。直到遇到超出范圍 [4,5] 的點，然后向左移動 1 列 [4,4] 并再次開始迭代。這樣我們可以大大減少遞回的次數。
例子
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
uj5u.com熱心網友回復：
在四分之一中計算點數是一個非常好的主意，但我想我找到了更簡單的解決方案（當然在你的幫助下）。這是第一次呼叫方法的代碼：
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;
}
它只需要一種方法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/478776.html