Подскажите алгоритм
11416 сообщений
#14 лет назад
Здравствуйте. Хотел спросить у спецов как лучше сделать. Нужен алгоритм подсчета одной штуки, а именно:Есть матрица 15 на 15. В ячейках могут быть 0, 1 или она может быть пустой (ну или вместо пустой можно поставить какое-то значение - особо не принципиально)
Нужно найти ряд из 5 ячеек по вертикали, горизонтали или диагонали либо нулей, либо единиц.
Перефразируя проще что бы было понятно - как в крестиках ноликах, есть поле 15 на 15, надо найти победителя кто сложил комбинацию из 5 ячеек.
Реализация PHP + JS...
Вот думаю над оптимальным алгоритмом подсчета, что бы считал быстро и особо не грузил. Посоветуйте что почитать, тыкнете куда надо, я дальше сам разберусь.
Ну или подскажите какой лучше алгоритм реализации использовать.
Спасибо.
5330 сообщений
#14 лет назад
Делов то... каждый раз при клике проверять горизонтали с столбцы на предмет:000101010110001111100 - это типа строка (столбец).. пусть 0 - это пробел, 1 - это "буква"
режем строку на слова и находим все слова где число символов более X
1649 сообщений
#14 лет назад
Вот примерный альгоритм:1. Начинаешь с ячейкой 1:1 и делаешь рекурсивный обход всей матрицы пока не нашел что тебе нужно.
2. для каждой ячейки делаешь 8 проверок циклом while.
а. ячейка = значение и 4 верхних соседей=значение
б. ячейка = значение и 4 верхних-правых соседей=значение(по диагонали)
....итд
3. для оптимизации, например имеешь матрицу 15*15. Ищешь линейку из 5. Значит для первых 5-1 линий нет смысла делать проверку вверх. Также для первых 5 колонок, нет смысла делать проверку левее. итд.
5330 сообщений
#14 лет назад
$words = explode('0', $string);$words - массив слов
по нему пробежаться $words и посмотреть "длину" слова
15*15 = это всего 30 проверок
1649 сообщений
#14 лет назад
Наверное еще более оптимальный алгоритм будет, если сделаешь проверку для всех ячеек при обходе, а только для тех в которых записано нужное значение.
1649 сообщений
#14 лет назад
ArtPro, ваш метод не пойдет. Ту матрица. Проверка делается и по диагонали и по вертикали и по горизонтали.
11416 сообщений
#14 лет назад
WebDesignStudio,ArtPro спасиб 
Цитата ("WebDesignStudio"):
ArtPro, ваш метод не пойдет. Ту матрица. Проверка делается и по диагонали и по вертикали и по горизонтали.
Ну можно также строки составлять и с учетом горизонталей... Тогда выходит вроде 50 строк и их проверять...
Мне кажется у ArtPro способ проще
1649 сообщений
#14 лет назад
Цитата ("Hungry_Hunter"):Тогда выходит вроде 50 строк и их проверять..это как?
кстати еще одня оптимизация. при проверку циклом в кукую то сторону от ячейки, начать не от соседней ячейки а от удаленной от нее на, на 4 позиции. И если последняя не соответствует, значит линия закрыватся не будет, и выходим из цикла сразу.
В ходе разработки могут возникать еще идеи по оптимизацию.
5330 сообщений
#14 лет назад
Цитата ("WebDesignStudio"):это как?
15х15 - это 30 горизонталей и вертикалей + 2 пакета диагоналей, причем крайние короткие не берем. на тетрадном листе посчитать недолго сколько их
все равно их мало
1649 сообщений
#14 лет назад
Если без диагоналей, возможно алгоритм ArtPro будет работать быстрее. А вот с диагоналями не знаю. Ну вобщем можешь пробовать оба варианта, и потом дат и нам знать какой быстрее работает. Лучше всего наверное делать это на PHP, что бы скорость не зависло от компа клиента а от сервера.
5330 сообщений
#14 лет назад
Цитата ("WebDesignStudio"):В ходе разработки могут возникать еще идеи по оптимизацию.
на JS половину сделать можно в принципе.... а в php пихать "остатки"
11416 сообщений
#14 лет назад
Цитата ("WebDesignStudio"):это как?
Ну вот как он предложил делаем строки и столбцы + делаем из диагоналей такие же строки и их проверяем. Диагоналей будет 20 (или 21) если не ошибаюсь...
1172 сообщения
#14 лет назад
for($x=0;$x<15;++$x) {
for($y=0;$y<15;++$y) {
if($y>=4) {
...проверка вверх
if($x>=4)
проверка вверх-влево
if($x<=11) {
проверка вверх-вправо
проверка вправо
}
}
elseif($x<=11)
проверка вправо
}
}Если совсем без оптимизаций и навскидку
11416 сообщений
#14 лет назад
Lisio спс, что-то типа такого ага...
3240 сообщений
#14 лет назад
Вот, пример решения (делал навскидку из головы, без проверки, так что может содержать опечатки):Тут был код с ошибками.
Удалено, чтобы никто себе не скопировал это ошибочное решение.
Исправленный и проверенный пример — ниже в этой теме.
11416 сообщений
#14 лет назад
tvv спасибо большое, интересно... Попробую обязательно.
1172 сообщения
#14 лет назад
tvv, я либо ошибась, либо у вас проверка только одной диагонали вправо-вниз, а вправо-вверх не проверяется.Мой примитивный вариант:
<?php
$matrix=array();
for($x=0;$x<15;++$x) {
$matrix=array();
for($y=0;$y<15;++$y)
$matrix=rand(-1,1);
}
function check_line($x,$y,$d1,$d2,$z) {
global $matrix;
for($i=0;$i<5;++$i)
if($matrix!=$z)
return false;
return true;
}
function check_matrix() {
for($x=0;$x<15;++$x) {
for($y=0;$y<15;++$y) {
if($y>=4) {
if(check_line($x,$y,0,-1,0)) return 0;
if(check_line($x,$y,0,-1,1)) return 1;
if($x>=4) {
if(check_line($x,$y,-1,-1,0)) return 0;
if(check_line($x,$y,-1,-1,1)) return 1;
}
if($x<=11) {
if(check_line($x,$y,1,0,0)) return 0;
if(check_line($x,$y,1,0,1)) return 1;
if(check_line($x,$y,1,-1,0)) return 0;
if(check_line($x,$y,1,-1,1)) return 1;
}
}
elseif($x<=11) {
if(check_line($x,$y,1,0,0)) return 0;
if(check_line($x,$y,1,0,1)) return 1;
if(check_line($x,$y,1,-1,0)) return 0;
if(check_line($x,$y,1,-1,1)) return 1;
}
}
}
return -1;
}
echo check_matrix();
?>
1649 сообщений
#14 лет назад
М-размер матрицы
L-нужная длина линии(у тебя 5)
function checkCell($i,$j){
$found=false;
if($i<=M-L){//проверка на право
$ii=$i+1;
while((!$found)and($ii<M)){
if($A==$A) $found=true;
$ii++;
}
}
if($i>=L){//проверка на лево
$ii=$i-1;
while((!$found)and($ii>1)){
if($A==$A) $found=true;
$ii--;
}
...
также вверх и вниз, только по $j
...
if(($i<=M-L)and($j<=M-L)){//проверка правый верхний угол
$ii=$i+1;
$jj=$i-1;
while((!$found)and($ii<M)){
if($A==$A) $found=true;
$ii++;
$jj--;
}
}
...
также для других углов
...
}
function parseMatrix(){
$i=1;
$j=1;
$found=checkCell($i,$j);
while((!$found)and($i<=M)){
while((!$found)and($i<=M)){
$found=checkCell($i,$j);
$j++;
}
$i++;
}
return $found;
}
Вот примерно так. Остается делать вызов $f=parseMatrix();
Возможно допустил какие то ошибки, так как не запустил алгоритм.
задача немного усложнится если матрица не квадратная.