Matrix вопросы размещения в php
Я хотел бы знать некоторые решения такой проблемы.
Дано число, скажем, 16, и вы должны расположить матрицу таким образом
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
язык не имеет значения, (желательно PHP);
6 ответов
[EDIT: Update] Если язык не неважно:
Перейдите по адресу: http://rosettacode.org/wiki/Spiral_matrix
В PHP:
Вот:
<?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>';
?>
В питоне:
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)
в 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();
}
}
Похоже, игра в змейку может сработать. Отслеживайте вектор направления и поворачивайте направо на 90 градусов каждый раз, когда сталкиваетесь со стороной или населенным квадратом. Хвост продолжает расширяться до бесконечности :)
Редактировать: Snakey v0.1 на C#. Работает и для неквадратных сеток ;)
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");
}
}
}
}
В PHP, но с рекурсией. Вы можете установить размер квадратного поля, которое будет заполнено, указав длину стороны.
Это работает так, что функция сначала заполняет значение в указанном месте массива. Затем он пытается продолжить движение в том же направлении, в котором двигался. Если это невозможно, он поворачивается по часовой стрелке на 90 градусов. Если не осталось ходов, он останавливается. Это обрабатывается оператором switch() для переменной direction и рекурсии.
Это можно легко адаптировать к сеткам прямоугольной формы (просто укажите 2 константы вместо 1 для длин сторон).
Живой пример с 8x8 и вашим 4x4
Код:
<?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>";
?>
Хорошо, я публикую этот ответ просто для развлечения.
Другие решения используют переменные для итеративного накопления информации. Я хотел попробовать функциональное решение, в котором номер любой ячейки таблицы (или, альтернативно, ячейка таблицы для любого числа) можно было бы узнать без повторения каких-либо других.
Вот это в javascript. Я знаю, что это не чистое функциональное программирование и не очень элегантное, но вычисление числа для каждой ячейки таблицы выполняется без привязки к предыдущим итерациям. Так что это многоядерный дружественный.
Теперь нам просто нужен кто-то, кто сделает это на Haskell. ;-)
Кстати, это было написано до комментария о том, что 1 должна заканчиваться в определенном месте, которое не обязательно является северо-западным углом (на данный момент все еще не указано).
Так как кто-то упомянул спираль Улама, просто ради интереса я добавил код, чтобы поместить красную рамку вокруг простых чисел (даже несмотря на то, что спираль вывернута наизнанку). Интересно, что, похоже, есть диагональные полосы простых чисел, хотя я не знаю, значительно ли они отличаются от полос, которые вы получили бы со случайными нечетными числами.
Код:
// 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);
}
HTML-страница для его применения:
<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>