Просмотр полной версии : IT пятнашки (от игра 15) но совсем не похоже
Условия задачи
В базу данных внесено 15 прямоугольных фигур разных размеров
Есть прямоугольное поле, площадью на 20% больше общей площади отдельных прямоугольников
Задача: обозначить подход к разработке алгоритма случайного построения фигур в поле, путем их выборки из базы данных, чтобы они оставались в границах поля, но их относительное местоположение каждый раз менялось в случайном порядке.
Доп условия: Пустые места оставлять можно, незадействованных фигур быть не должно
Условия задачи В базу данных внесено 15 прямоугольных фигур разных размеров Есть прямоугольное поле, площадью на 20% больше общей площади отдельных прямоугольников Задача: обозначить подход к разработке алгоритма случайного построения фигур в поле, путем их выборки из базы данных, чтобы они оставались в границах поля, но их относительное местоположение каждый раз менялось в случайном порядке. Доп условия: Пустые места оставлять можно, незадействованных фигур быть не должно
Можете попробовать перебрать все возможные варианты...:biggrin: , найти все возможные решения (если такие существуют) и каждый раз выбирать из этих решений случайно одно::)
Vitaliy Fioktistov
27.11.2009, 17:28
Мысль пошла в следующем направлении:
Расчерчиваем поле и прямоугольники на клетки 1x1, если допустим расположение их с меньшим шагом, то просто умножим все размеры на 10, 100 и т.п.
Итак, закладываем размерности фигур в массив, бд и т.п., берем поле определенных размеров и радуемся :)
function next_level ($level,$field)
{
global $polygons,$array_width,$array_height,$polygons_cou nt,$results_array;
$level++;
$cur_width=$polygons[$level][0]; // ширина текущей фигуры
$cur_height=$polygons[$level][1]; // высота текущей фигуры
$cur_dim_width=$array_width+1-$cur_width; // Предел возможности установки фигуры горизонтальный
$cur_dim_height=$array_height+1-$cur_height;// Предел возможности установки фигуры вертикальный
for ($i=1;$i<=$cur_dim_height;$i++)
{
for ($j=1;$j<=$cur_dim_width;$j++)
{
$tempfield=$field;
$flag=true;
for ($h=0;$h<$cur_height;$h++)
{
for ($v=0;$v<$cur_width;$v++)
{
if ($tempfield[$i+$h][$j+$v]>0)
{
$flag=false;
break 2;
}
else
$tempfield[$i+$h][$j+$v]=$level;
}
}
if ($flag)
{
if ($polygons_count==$level)
$results_array[]=$tempfield;
else
next_level($level,$tempfield);
}
}
}
}
$field=array(); // поле
$results_array=array(); // результаты
// вносим размерности фигур
$polygons=array(
1=>array(3,2),array(2,4),array(3,4),array(2,3),array( 5,1),
array(2,2),array(4,3),array(3,3),array(2,3),array( 4,1),
array(4,2),array(4,1),array(2,2),array(3,2),array( 2,3)
);
$polygons_count=count($polygons); // количество фигур
$array_width=12; // ширина поля
$array_height=10; // высота поля
// начальная инициализация поля
for ($i=1;$i<=$array_height;$i++)
{
for ($j=1;$j<=$array_width;$j++)
{
$field[$i][$j]=0;
}
}
next_level(0,$field);
Пара комментов.
Сделано на скорую руку, но работает корректно. Язык реализации - php.
Используется рекурсия. Все оптимизировано для наибольшего быстродействия. Общая площадь прямоугольников в данном примере - 100 единиц, размер игрового поля - 120.
Мой комп ниасилил подсчитать за разумное время ВСЕ комбинации на поле 12x10 с 15 прямоугольниками. На поле 8x8 с 9 прямоугольниками подсчет шел 254 сек.
Nadir Zaitov
27.11.2009, 18:44
Можете попробовать перебрать все возможные варианты... , найти все возможные решения (если такие существуют) и каждый раз выбирать из этих решений случайно одноЦелочисленности в задаче нет. Иррациональное местоположение квадратов учтено? Любой допустимый люфт и у Вас ровно один континиум решений. :)
Мой комп ниасилил подсчитать за разумное время ВСЕ комбинации на поле 12x10 с 15 прямоугольниками. На поле 8x8 с 9 прямоугольниками подсчет шел 254 сек. Простите за дурацкий вопрос, на компе апач должен стоят (XAMMP) чтобы РНР файл заработал?
Целочисленности в задаче нет. Иррациональное местоположение квадратов учтено? Любой допустимый люфт и у Вас ровно один континиум решений.Да, континуум :biggrin: в условии так ведь не сказано, что алгоритм должен выдавать ответ когда нибудь:biggrin: -только подход...:) а вариант реализации у Vitaliy Fioktistov ::)
Vitaliy Fioktistov
28.11.2009, 06:03
Мой комп ниасилил подсчитать за разумное время ВСЕ комбинации на поле 12x10 с 15 прямоугольниками. На поле 8x8 с 9 прямоугольниками подсчет шел 254 сек. Простите за дурацкий вопрос, на компе апач должен стоят (XAMMP) чтобы РНР файл заработал?
В общем случае не обязан, но это самый распространенный вариант.
Может быть использован как альтернативный сервер, так и просто в качестве скрипта командной строки. Но чаще конечно используется локальный сервер apache+php+mysql
У меня, к примеру дома стоит пакет Denwer (http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BD%D0%B2%D0%B5%D1%80_(%D0%BF%D1%80 %D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0)).
Ойбек Ибрагимов
28.11.2009, 06:08
В общем случае не обязан
В 6 утра в субботу все задачки решаем...
Nadir Zaitov
28.11.2009, 12:09
в условии так ведь не сказано, что алгоритм должен выдавать ответ когда нибудь Так это предполагает иметь хоть один вариант, если он есть. пример - 15 прямоугольников равного размера 1x2 и вытянутый прямоугольник, повернутый на 45 градусов с длинной 1x36. При переблре без подгонки одной из сторон не получится.
Vitaliy Fioktistov
28.11.2009, 17:47
В общем случае не обязан
В 6 утра в субботу все задачки решаем...
СБ не дремлет? ;)
Vitaliy Fioktistov
28.11.2009, 17:53
в условии так ведь не сказано, что алгоритм должен выдавать ответ когда нибудь Так это предполагает иметь хоть один вариант, если он есть. пример - 15 прямоугольников равного размера 1x2 и вытянутый прямоугольник, повернутый на 45 градусов с длинной 1x36. При переблре без подгонки одной из сторон не получится.
Мля, так их еще и на произвольный угол поворачивать можно? :038:
Nadir Zaitov
29.11.2009, 21:32
Мля, так их еще и на произвольный угол поворачивать можно? а хотябы на 90 градусов вы поворачивали?
Ildar Valiev
29.11.2009, 23:30
Кол-во ячеек конечно? Насколько большое?
Фигуры действительно нужно поворачивать?
Кол-во ячеек конечно? Насколько большое? Фигуры действительно нужно поворачивать? Не ограничено, но пустые места не должны превалировать (их можно иметь). Поворачивать не обязательно (не желательно, честно говоря).
Ildar Valiev
30.11.2009, 00:32
Кол-во ячеек конечно? Насколько большое? Фигуры действительно нужно поворачивать? Не ограничено, но пустые места не должны превалировать (их можно иметь)
То есть размеры прямоугольников может быть, к примеру, 14.2 х 3.8 ?
Не ограничено, но пустые места не должны превалировать (их можно иметь). Поворачивать не обязательно (не желательно, честно говоря).
тогда для практического применения Вам прекрасно подойдет алгоритм
Vitaliy Fioktistov :) -если конечно в самом начале банально расставить фигурки в случайном порядке...:)
ЗЫ Интересно, если в алгоритме вместо
if ($flag)
{
if ($polygons_count==$level)
$results_array[]=$tempfield;
else
next_level($level,$tempfield);
}
прописатьif ($flag)
{
if ($polygons_count==$level)
{
$results_array[]=$tempfield;
break 2;
}
else
next_level($level,$tempfield);
}
будет ли алгоритм хоть чуточку быстрее работать?:)
Vitaliy Fioktistov
30.11.2009, 04:07
Мля, так их еще и на произвольный угол поворачивать можно? а хотябы на 90 градусов вы поворачивали?
Добавить 3 строчки в прогу - цикл от 1 до 2 и своп cur_height и cur_width
Vitaliy Fioktistov
30.11.2009, 04:28
ЗЫ Интересно, если в алгоритме вместо
if ($flag)
{
if ($polygons_count==$level)
$results_array[]=$tempfield;
else
next_level($level,$tempfield);
}
прописатьif ($flag)
{
if ($polygons_count==$level)
{
$results_array[]=$tempfield;
break 2;
}
else
next_level($level,$tempfield);
}
будет ли алгоритм хоть чуточку быстрее работать?:)
Проверил. Быстрее где-то на 1%.
vBulletin® v3.8.5, Copyright ©2000-2026, Jelsoft Enterprises Ltd. Перевод: zCarot