Задача на сообразительность

[white phoenix]

Задача на сообразительность

Дан массив из чисел, NхN, расставить числа по примеру:
01 16 15 14 13
02 17 24 23 12
03 18 25 22 11
04 19 20 21 10
05 06 07 08 09

Сосчитать сумму чисел по диагонали ((1,1)-(N,N)).

* предпочтительно решение для ограниченного объема памяти (вся матрица в
память не помещается).

Решение: посчитанная сумма для N=1000, исходник на любом языке
программирования.

Прошлую ночь не спал нифига, тем не менее вот что получилось:
Я не стал искать зависимость (между N и числом), которая несомненно существует, а просто решил "пройти" весь путь заполнив массив.

$array = array();
$k = 5; // кол-во цифр на стороне

$x = 1; // начальные
$y = 1; // координаты

$d = 0; // начальное направление (0 - вниз)

$m = $k; // кол-во цифр на стороне, которое уменьшается
$i = 1; // начальное N
$j = 0; // пробегающая переменная по стороне
echo "<table border=1 width=40%><tr><td><b>X.Y</b></td><td><b>i</b></td><td><b>d</b></td><td><b>j</b></td></tr>";
while ($i < 25)
{
 $t = $x.".".$y;
 echo "<tr><td>".$t."</td><td>".$i."</td><td>".$d."</td><td>".$j."</td></tr>";
 $array[$t] = $i;

 $u = $j == $m-1;
 if ($u) {if ($d == 3) {$d = 0;} else {$d++;} $j = 0;}
 if ($d == 0) {$y++;}
 if ($d == 1) {$x++;}
 if ($d == 2) {$y--;}
 if ($d == 3) {$x--;}
 $i++;
 $j++;
}
echo "</table>";
//var_dump($array);
exit;
$n = 100;
$s = 0;
for($i=0;$i<$n;$i++)
{
 $t = $i.".".$i;
 $s += $array[$t];
}
echo $s;

Результат:
X.Y i d j
1.1 1 0 0
1.2 2 0 1
1.3 3 0 2
1.4 4 0 3
1.5 5 0 4
2.5 6 1 1
3.5 7 1 2
4.5 8 1 3
5.5 9 1 4
5.4 10 2 1
5.3 11 2 2
5.2 12 2 3
5.1 13 2 4
4.1 14 3 1
3.1 15 3 2
2.1 16 3 3
1.1 17 3 4
1.2 18 0 1
1.3 19 0 2
1.4 20 0 3
1.5 21 0 4
2.5 22 1 1
3.5 23 1 2
4.5 24 1 3

Сначала верно, а потом начинает врать.

Помогите люди добрые ибо сам я уже в конец задолбался.

 

[SiMM]

> а просто решил "пройти" весь путь заполнив массив.
А не надо проходить весь путь, достаточно пройти по элементам главной диагонали. И, кстати, координаты для решения задачи не требуется.
А закономерности искать придётся (правда не для результата, а для вспомогательных значений). Для начала нарисуй ручками несколько квадратов для N=1..7, нарисуй суммируемый ряд для каждого из нарисованных квадратов и попробуй найти закономерность между соседними слагаемыми (располагая слагаемые в порядке их следования в спирали, т.е. для вышеприведённого примера имеем 1+9+17+21+25). Ну а дальше всё должно пойти как по маслу.
PS: а вообще, форум по PHP не место, где решают свои домашние задания - они потому и домашние, что решать их надо самостоятельно Хотя толчок тебе тут дать могут.

 

[white phoenix]

не получается

 

[SiMM]

> не получается
Видишь ли, слово "не получается" - оно даже не отражает того, что ты УЖЕ сделал. Поэтому для начала всё же выполни то, на что я явно указал. Т.е. создай таблицу вида:
N ряд
1:
2:
3:
4:
5:1+9+17+21+25 (уже подсказал)
6:
7:
После того, как создашь, постарайся всё же найти закономерность между соседними слагаемыми.

 

[Popoff]

Это случайно не тестовое задание для приема на работу?

 

[white phoenix]

я вот и решил аналитически. спасибо всем за ответы.

$N = 1000;
function getA($A,$j,$N)
{
 $r = $A + 2 * ($N - 2 * $j - 1);
 //echo "A: ".$r." j: ".$j." N: ".$N."<br>";
 return $r;
}
$j = 0;
$i = 0;
$A = 1;
$k = 0;
$sum = 1;
while ($i < $N-1)
{
 if ($k == 2) {$k = 0; $j++;}
 $A = getA($A,$j,$N);
 $sum += $A;
 $i++;
 $k++;
}
echo "Сумма: ".$sum." для N = ".$N.".";

И без всякого заполнения массива =)
Popoff
нет

 

[SiMM]

Ответ сошёлся

function calc($n){
  $s = 0; $ds = 1; $dds = ($n-1)*2;
  for ($i=0; $i<$n; $i++){
    $s += $ds;
    $ds += $dds;
    if ($i&1) $dds -= 4;
  }
  return $s;
}
echo calc(1000);

 

[white phoenix]

ну дык

 

[Popoff]

Тю %) Ясно же написано: "Задача на сообразительность" %)

function calc($n)
{
  return ($n*$n*$n*2+$n)/3-($n*$n-$n%2)/2;
}

echo calc(1000);

 

[white phoenix]

Popoff
мозг =)

 

[SiMM]

Глубоко копал
PS: надо будет попробовать повторить выкладки