2

我正在寻找想法/代码（最好是 C#，但其他语言也可以）来创建无限大的 Ulam 的 Spiral（受程序运行时间长度的限制，或直到停止）。

替代文字

现在这些数字都是素数，所以它们的代码是无关紧要的。有趣的部分是如何对不断增长的（无限）螺旋中的排列进行编码，什么样的数据结构可以很好地支持它，以及输出的想法（图形文件，文本文件？）。

你会怎么做？

4

4 回答 4

8

考虑每边的长度：1, 1, 2, 2, 3, 3, 4, 4, ...

直接的事情是遍历每一面，渲染那一面。您可以使用 LOGO 样式渲染原语：

Angle = 0;
x=0; y = 0;
int number = 1;
int sideLength = 1;

StartLine();
for (int side = 1; side < maxSize; side++) {
 for (int k = 0; k < sideLength; k++) {
  Forward(1);
  number++;

  if (isPrime(number)) {
   StopLine();
   Ouput(number);
   StartLine();
  }
 }
 TurnLeft();
 if (side % 2 == 0) sideLength++;
}

您可以通过仅在一侧迭代素数来改进这一点：

于 2009-08-20T19:48:40.673 回答
6

以下程序通过直接计算数字的坐标来工作。该方法NumberToPoint()执行以下映射。

0 => (x0    , y0    )
1 => (x0 + 1, y0    )
2 => (x0 + 1, y0 - 1)
3 => (x0    , y0 - 1)
4 => (x0 - 1, y0 - 1)
5 => (x0 - 1, y0    )
6 => ...

剩下的就是一个非常简单的素数测试和一个小型控制台应用程序。

为了保存图像，我会考虑两种解决方案。如果你可以为整个图像创建一个缓冲区，你可以使用下面的程序来填充缓冲区。

如果缓冲区太大，我将创建一个方法PointToNumber()并反转计算 - 该方法采用两个坐标并返回此时的数字。使用这种方法，您可以从上到下和从左到右迭代并计算此时的数字，检查它是否为素数，并在没有缓冲区的情况下输出像素。但是对于这两种解决方案，在开始之前应该知道图像大小，因为在顶部和左侧添加像素非常昂贵（但可能是原因）。

问题

  1. NumberToPoint()在不使用模数、整数除法和符号一千次的情况下将系数查找转换为坚如磐石的数学有什么好的想法吗？
  2. 有什么好主意可以缩短或加快质数测试？

代码

using System;
using System.Drawing;
using System.Linq;
using System.Threading;

namespace UlamsSpiral
{
   public static class Program
   {
      public static void Main()
      {
         Int32 width = 60;
         Int32 height = 60;

         Console.SetWindowSize(Math.Min(width, 120), Math.Min(height, 60));
         Console.SetBufferSize(width, height);
         Console.CursorVisible = false;

         Int32 limit = (Int32)Math.Pow(Math.Min(width, height) - 2, 2);

         for (Int32 n = 1; n <= limit; n++)
         {
            Point point = NumberToPoint(n - 1, width / 2 - 1, height / 2);

            Console.ForegroundColor = n.IsPrime() ? ConsoleColor.DarkBlue : ConsoleColor.DarkGray;

            Console.SetCursorPosition(point.X, point.Y);
            Console.Write('\u25A0');

            Console.SetCursorPosition(0, 0);
            Console.Write(n);

            Thread.Sleep(10);
         }

         Console.ReadLine();
      }

      private static Point NumberToPoint(Int32 n, Int32 x0, Int32 y0)
      {
         Int32[,] c = { { -1, 0, 0, -1, 1, 0 }, { -1, 1, 1, 1, 0, 0 }, { 1, 0, 1, 1, -1, -1 }, { 1, -1, 0, -1, 0, -1 } };

         Int32 square = (Int32)Math.Floor(Math.Sqrt(n / 4));

         Int32 index;
         Int32 side = (Int32)Math.DivRem(n - 4 * square * square, 2 * square + 1, out index);

         Int32 x = c[side, 0] * square + c[side, 1] * index + c[side, 2];
         Int32 y = c[side, 3] * square + c[side, 4] * index + c[side, 5];

         return new Point(x + x0, y + y0);
      }

      private static Boolean IsPrime(this Int32 n)
      {
         if (n < 3) return (n == 2);
         return Enumerable.Range(2, (Int32)Math.Sqrt(n)).All(m => n % m != 0);
      }
   }
}
于 2009-08-20T22:15:37.427 回答
0

一种可能的方法是创建一个线性数组或一个列表来存储数字并使用公式来确定何时需要改变方向。至于输出，我喜欢维基百科上的示例，即为素数绘制黑色像素，为所有其他数字绘制白色像素。

于 2009-08-20T19:23:51.533 回答
0

为什么没有一个创建数字的“生成器”进程/线程和一个显示它们的“读取器/显示”进程/线程，那么您可以将创建与显示分开，然后程序将仅受数据量的限制“阅读器/显示器”消耗。因为我会假设“生成器”需要一组相当恒定大小的数据才能使用。

于 2009-08-20T22:49:55.457 回答