I would like to know some solutions to such a problem.
It is given a number lets say 16 and you have to arrange a matrix this way
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
the language doesn't matter, (preferably PHP);
可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):
问题:
回答1:
[EDIT: Update] If language doesn't matter:
Go to: http://rosettacode.org/wiki/Spiral_matrix
In PHP:
Here you go:
<?php
function getSpiralArray($n)
{
$pos = 0;
$count = $n;
$value = -$n;
$sum = -1;
do
{
$value = -1 * $value / $n;
for ($i = 0; $i < $count; $i++)
{
$sum += $value;
$result[$sum / $n][$sum % $n] = $pos++;
}
$value *= $n;
$count--;
for ($i = 0; $i < $count; $i++)
{
$sum += $value;
$result[$sum / $n][$sum % $n] = $pos++;
}
} while ($count > 0);
return $result;
}
function PrintArray($array)
{
for ($i = 0; $i < count($array); $i++) {
for ($j = 0; $j < count($array); $j++) {
echo str_pad($array[$i][$j],3,' ');
}
echo '<br/>';
}
}
$arr = getSpiralArray(4);
echo '<pre>';
PrintArray($arr);
echo '</pre>';
?>
回答2:
In python:
from numpy import *
def spiral(N):
A = zeros((N,N), dtype='int')
vx, vy = 0, 1 # current direction
x, y = 0, -1 # current position
c = 1
Z = [N] # Z will contain the number of steps forward before changing direction
for i in range(N-1, 0, -1):
Z += [i, i]
for i in range(len(Z)):
for j in range(Z[i]):
x += vx
y += vy
A[x, y] = c
c += 1
vx, vy = vy, -vx
return A
print spiral(4)
回答3:
Looks like the snake game might work. Track a direction vector, and turn right 90 degrees every time you hit a side or a populated square. The tail keeps extending indefinitely :)
Edit : Snakey v0.1 in C#. Works for non square grids too ;)
using System;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
public enum Direction
{
Up,
Down,
Left,
Right
}
static void Main(string[] args)
{
int[,] maze;
Direction currentDirection = Direction.Right;
bool totallyStuck = false;
bool complete = false;
int currentX = 0;
int currentY = 0;
int boundX = 4;
int boundY = 5;
int currentNumber = 1;
int stuckCounter = 0;
bool placeNumber = true;
maze = new int[boundY, boundX];
while ((!totallyStuck) && (!complete))
{
if (placeNumber)
{
maze[currentY, currentX] = currentNumber;
currentNumber++;
stuckCounter = 0;
}
switch (currentDirection)
{
case Direction.Right:
// Noted short Circuit Bool Evan
if ((currentX + 1 < boundX) && (maze[currentY, currentX + 1] == 0))
{
placeNumber = true;
currentX++;
stuckCounter = 0;
}
else
{
placeNumber = false;
stuckCounter++;
}
break;
case Direction.Left:
if ((currentX - 1 >= 0) && (maze[currentY, currentX - 1] == 0))
{
placeNumber = true;
currentX--;
stuckCounter = 0;
}
else
{
placeNumber = false;
stuckCounter++;
}
break;
case Direction.Down:
if ((currentY + 1 < boundY) && (maze[currentY + 1, currentX] == 0))
{
placeNumber = true;
currentY++;
stuckCounter = 0;
}
else
{
placeNumber = false;
stuckCounter++;
}
break;
case Direction.Up:
if ((currentY - 1 >= 0) && (maze[currentY - 1, currentX] == 0))
{
placeNumber = true;
currentY--;
stuckCounter = 0;
}
else
{
placeNumber = false;
stuckCounter++;
}
break;
}
// Is Snake stuck? If so, rotate 90 degs right
if (stuckCounter == 1)
{
switch (currentDirection)
{
case Direction.Right:
currentDirection = Direction.Down;
break;
case Direction.Down:
currentDirection = Direction.Left;
break;
case Direction.Left:
currentDirection = Direction.Up;
break;
case Direction.Up:
currentDirection = Direction.Right;
break;
}
}
else if (stuckCounter > 1)
{
totallyStuck = true;
}
}
// Draw final maze
for (int y = 0; y < boundY; y++)
{
for (int x = 0; x < boundX; x++)
{
Console.Write(string.Format("{0:00} ",maze[y, x]));
}
Console.Write("\r\n");
}
}
}
}
回答4:
OK, I'm just posting this answer for fun.
The other solutions use variables to accumulate information iteratively. I wanted to try a functional solution, where the number of any table cell (or alternatively, the table cell for any number) could be known without iterating through any others.
Here it is in javascript. I know, it's not pure functional programming, nor is it extremely elegant, but the computation of the number for each table cell is done without reference to prior iterations. So it's multi-core friendly.
Now we just need somebody to do it in haskell. ;-)
BTW this was written before the comment that the 1 should end up in a certain location that is not necessarily the northwest corner (still unspecified as of now).
Since somebody mentioned the Ulam spiral, just for kicks I added code to put a red border around the primes (even though the spiral is inside out). Interestingly enough, there do seem to be diagonal streaks of primes, though I don't know if it's significantly different from the streaks you'd get with random odd numbers.
The code:
// http://stackoverflow.com/questions/3584557/logical-problem
/* Return a square array initialized to the numbers 1...n2, arranged in a spiral */
function spiralArray(n2) {
var n = Math.round(Math.sqrt(n2));
if (n * n != n2) {
alert('' + n2 + ' is not a square.');
return 0;
}
var h = n / 2;
var arr = new Array(n);
var i, j;
for (i = 0; i < n; i++) {
arr[i] = new Array(n);
for (j = 0; j < n; j++) {
// upper rows and lower rows of spiral already completed
var ur = Math.min(i, n - i, j + 1, n - j, h),
lr = Math.min(i, n - i - 1, j + 1, n - j - 1, h);
// count of cells in completed rows
// n + n-2 + n-4 ... n - 2*(ur-1) = ur*n - (ur*2*(ur - 1)/2) = ur * (n - ur + 1)
// n-1 + n-3 + ... n-1 - 2*(lr-1) = lr*(n-1) - (lr*2*(lr - 1)/2) = lr * (n - 1 - lr + 1)
var compr = ur * (n - ur + 1) + lr * (n - lr);
// e.g. ur = 2, cr = 2*(5 - 2 + 1) = 2*4 = 8
// left columns and right columns of spiral already completed
var rc = Math.min(n - j - 1, i, n - i, j + 1, h),
lc = Math.min(n - j - 1, i, n - i - 1, j, h);
// count of cells in completed columns
var compc = rc * (n - rc) + lc * (n - lc - 1);
// offset along current row/column
var offset;
// Which direction are we going?
if (ur > rc) {
// going south
offset = i - (n - j) + 1;
} else if (rc > lr) {
// going west
offset = i - j;
} else if (lr > lc) {
// going north
offset = n - i - 1 - j;
} else {
// going east
offset = j - i + 1;
}
arr[i][j] = compr + compc + offset;
}
}
return arr;
}
function isPrime(n) {
// no fancy sieve... we're not going to be testing large primes.
var lim = Math.floor(Math.sqrt(n));
var i;
if (n == 2) return true;
else if (n == 1 || n % 2 == 0) return false;
for (i = 3; i <= lim; i += 2) {
if (n % i == 0) return false;
}
return true;
}
// display the given array as a table, with fancy background shading
function writeArray(arr, tableId, m, n) {
var tableElt = document.getElementById(tableId);
var s = '<table align="right">';
var scale = 1 / (m * n);
var i, j;
for (i = 0; i < m; i++) {
s += '<tr>';
for (j = 0; j < n; j++) {
var border = isPrime(arr[i][j]) ? "border: solid red 1px;" : "";
s += '<td style="' + border + '" >' + arr[i][j] + '</td>';
}
s += '</tr>';
}
s += '</table>';
tableElt.innerHTML = s;
}
function tryIt(tableId) {
var sizeElt = document.getElementById('size');
var size = parseInt(sizeElt.value);
writeArray(spiralArray(size * size), 'spiral', size, size);
}
The HTML page to exercise it:
<html>
<head>
<style type="text/css">
td {
text-align: right;
font-weight: bold;
}
</style>
<script type="text/javascript" src="so3584557.js" ></script>
</head>
<body>
<form action="javascript:tryIt('spiral')">
Size of spiral: <input type='text' id='size' />
</form>
<table id="spiral">
</table>
</body>
</html>
回答5:
in java
public static void main(final String args[]) {
int numbercnt = 16;
int dim = (int) Math.sqrt(numbercnt);
int[][] numbers = new int[dim][dim];
ArrayList < Integer > ref = new ArrayList < Integer >();
for (int i = 0; i < numbercnt; i++) {
ref.add(i);
}
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers[i].length; j++) {
int pos = (int) (Math.random() * ref.size());
numbers[j][i] = ref.get(pos);
ref.remove(pos);
}
}
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers[i].length; j++) {
System.out.print(numbers[j][i] + " ");
}
System.out.println();
}
}
回答6:
In PHP, but with recursion. You can set the size of the square box to be filled by specifying the length of a side.
The way this works is that the function initially fills in the value at the array location specified. Then it tries to keep moving in the direction it was moving. If it can't, it turns clockwise 90 degrees. If there are no moves left, it stops. This is handled with a switch() statement for the direction variable and recursion.
This can be adapted to rectangular shaped grids quite easily (just specify 2 constants instead of 1 for the side lengths).
Live Example with an 8x8 and your 4x4
The code:
<?php
// Size of edge of matrix
define("SIZE", 4);
// Create empty array
$array = array();
// Fill array with a spiral.
fillerUp($array);
// Start at 0 / 0 and recurse
function fillerUp(& $array, $x = 0, $y = 0, $count = 1, $direction = "right")
{
// Insert value
$array[$x][$y] = $count;
// Try to insert next value. Stop if matrix is full.
switch ($direction)
{
case "right":
if (! $array[($x + 1) % SIZE][$y])
fillerUp($array, $x + 1, $y, ++$count, "right");
elseif (! $array[$x][($y + 1) % SIZE])
fillerUp($array, $x, $y + 1, ++$count, "down");
break;
case "down":
if (! $array[$x][($y + 1) % SIZE])
fillerUp($array, $x, $y + 1, ++$count, "down");
elseif (! $array[($x - 1) % SIZE][$y])
fillerUp($array, $x - 1, $y, ++$count, "left");
break;
case "left":
if (! $array[abs(($x - 1) % SIZE)][$y])
fillerUp($array, $x - 1, $y, ++$count, "left");
elseif (! $array[$x][abs(($y - 1) % SIZE)])
fillerUp($array, $x, $y - 1, ++$count, "up");
break;
case "up":
if (! $array[$x][abs(($y - 1) % SIZE)])
fillerUp($array, $x, $y - 1, ++$count, "up");
elseif (! $array[($x + 1) % SIZE][$y])
fillerUp($array, $x + 1, $y, ++$count, "right");
break;
}
}
// Show answer.
echo "<pre>";
for ($y = 0; $y < SIZE; ++$y)
{
for ($x = 0; $x < SIZE; ++$x)
{
echo str_pad($array[$x][$y], 4, " ", STR_PAD_BOTH);
}
echo "\n";
}
echo "</pre>";
?>
