|
| |
|
|
| |
для: BinLaden
(07.02.2009 в 02:42)
| | | Остаток исчезает при кратной длине хвостов.
В принципе, возможны два решения.
Одно, когда можно распределить вспомогательную память размером в два элемента массива.
<?
function swapreg(&$arr, $start, $center, $fin)
{
for(;;)
{
$left = $center - $start;
$right = $fin - $center;
if($left <= 0 || $right <= 0) return;
$down = $left <= $right;
$huge = $down ? $right : $left;
$tiny = $down ? $left : $right;
$rem = $huge % $tiny;
$quot = ($huge - $rem) / $tiny;
if($down)
{
$kfrom=$start;
$mfrom = $center+$rem;
$stop = $fin;
$step = $tiny;
}
else
{
$kfrom = $center;
$mfrom = $center-$tiny-$rem;
$stop = $start-$tiny;
$step = -$tiny;
}
for($i = 0; $i < $tiny; $i++, $arr[$k] = $temp)
for($temp = $arr[$k = $kfrom+$i], $m=$mfrom; $m != $stop; $m += $step, $k = $l)
$arr[$k] = $arr[$l = $m+$i];
if($down)
$fin = $center+$rem;
else
$start = $center - $rem;
}
}
?>
|
Другое, когда реализована операция обмена между двумя элементами массива
(а значит и операция обмена двух произвольных равных по длине участков).
<?
function swapreg(&$arr, $start, $center, $fin)
{
for(;;)
{
$left = $center - $start;
$right = $fin - $center;
if($left <= 0 || $right <= 0) return;
$down = $left <= $right;
$huge = $down ? $right : $left;
$tiny = $down ? $left : $right;
$rem = $huge % $tiny;
$quot = ($huge - $rem) / $tiny;
if($down)
{
$kfrom = $start;
$mfrom = $center+$rem;
$stop = $fin;
$step = $tiny;
}
else
{
$kfrom = $center;
$mfrom = $center-$tiny-$rem;
$stop = $start-$tiny;
$step = -$tiny;
}
$k = $kfrom;
for($m=$mfrom; $m != $stop; $m += $step, $k = $m)
swapeq($arr, $k, $m, $tiny);
if($down)
$fin = $center+$rem;
else
$start = $center - $rem;
}
}
function swapeq(&$arr, $a, $b, $len)
{
for($i = 0; $i < $len; $i++, $a++, $b++)
$arr[$b] ^= $arr[$a] ^= $arr[$b] ^= $arr[$a];
}
?>
|
при обращении к swapreg() используется указание трех индексов - начала левого участка, начала правого участка, и индекса за концом правого участка.
Позволяет абстрагироваться от того, как считаются элементы массива- от нуля ли, от единицы или еще как-то. | |
| |
|
|
| |
|
|
| |
для: BinLaden
(07.02.2009 в 02:42)
| | | Вот ОН - момент истины!
Наконец-то мы увидим "хвост" Trianon'a. | |
| |
|
|
| |
|
|
| |
для: Trianon
(07.02.2009 в 01:41)
| | | Ну покажите, пожалуйста. Остаток исчезает при равной длине "хвостов", насколько я понимаю. | |
| |
|
|
| |
|
|
| |
для: OLi
(06.02.2009 в 19:35)
| | | Укладываете малый хвост внутрь большого столько раз сколько помещается. Иногда остается остаток.
Гоните элементы по кольцу.
Для малого хвоста и остатка от него повторяете процедуру заново.
И так пока остаток не исчезнет.
PS. Эстет увидит и применит рекурсию.
PPS. Профессионал увидит рекурсию, пожалеет, что реально она не требуется, и перепишет алгоритм иттеративно. | |
| |
|
|
| |
|
|
| |
для: Trianon
(07.02.2009 в 01:36)
| | | Покажите:) | |
| |
|
|
| |
|
|
| |
для: BinLaden
(07.02.2009 в 00:24)
| | | вообще-то сходимость у задачи - как при расчете наибольшего общего делителя, и вычислительная сложность - пропорциональная. А не такой кошмар. | |
| |
|
|
| |
|
|
| |
для: OLi
(06.02.2009 в 19:35)
| | |
{ ... }
for i := 1 to m do
begin
for j := m - i + 1 to n - i do
begin
t := a[j];
a[j] := a[j + 1];
a[j + 1] := t;
end;
end;
{ ... }
|
P.S. Временная сложность алгоритма -- m x (n - m) | |
| |
|
|
| |
|
|
| |
для: OLi
(06.02.2009 в 19:35)
| | | - | |
| |
|
|
| |
|
|
| | «Дан массив A из n элементов и число m, где 1<m<n. Не используя дополнительных массивов, переставить первые m элементов в конец массива, а элементы с (m+1)-го по n-й – в начало, сохраняя порядок элементов».
Помогите найти решение, срочно нужно до утра!
Спасибо! | |
| |
|
|
|
