Форумы портала PHP.SU :: Версия для печати

1. EuGen - 28 Сентября, 2010 - 14:42:46 - перейти к сообщению

Здесь предлагаю публиковать задачи по программированию - те из них, что наиболее интересны, или же требуют применения определенных парадигм (к слову, "Hello World" не тот случай) - по аналогии с темой о математических задачах.
Пока что в разделе "Прочее", но если материал будет интересным, подумаю о перемещении темы и в "Уроки".
Решения - предпочтительно на PHP или на другом языке серверного программирования (у нас же есть раздел о Perl, Python и других). Если задача затрагивает вопросы web - тем ценнее она будет для читателей.
Заранее благодарю всех авторов.

Первой задачей опубликую классическую вещь:
Дана матрица N*M размерности. Заполнена случайными числами от 0 до 9. Например:
4 9 2 0
7 3 3 1
6 9 2 5
Нужно пройтись из левого верхнего угла в нижний правый так, чтобы набрать максимальное число суммируемых элементов матрицы. Движение разрешается только или вправо или вниз. Один и тот же элемент нельзя посещать дважды
Вторая задача - модификация первой. Дана все та же матрица, но числа в ее элементах могут быть любыми (например, от -100000 до 100000). Направление движения, которое разрешено - любое (вверх, вниз, влево, вправо, по диагонали нельзя). Задача та же - набрать максимальное число в сумме (суммируются все посещенные элементы, повторения элементов не допускаются).
Решением обеих задач можно назвать информацию о пройденном пути в любом виде (например, в виде последовательного списка посещенных элементов с координатами каждого из них. Или, к примеру, графическое представление).

Спойлер (Отобразить)

2. garvey - 28 Сентября, 2010 - 17:17:10 - перейти к сообщению

Решение задачи №1. Возможно есть лучше алгоритм.

PHP:
скопировать код в буфер обмена

<?PHP 
function createMatrix($m, $n) {
    echo '<table>';
    for ($i = 0; $i < $m; $i++) {
        echo '<tr>';
        for ($j = 0; $j < $n; $j++) {
           $matrix[$i][$j] = rand(0,9);
           echo '<td>' . $matrix[$i][$j] . '</td>';
        }
        echo '</tr>';
    }
    echo "</table>";
    return $matrix;
}
 
function runByMatrix($matrix, $i = 0, $j = 0) {
    $result = $matrix[$i][$j];
    echo $result.'('.$i.','.$j.')<br>';
    if (isset($matrix[$i + 1][$j]) && isset($matrix[$i][$j + 1])) {
        if ($matrix[$i + 1][$j] > $matrix[$i][$j + 1]) {
            $ii = $i + 1;
            $jj = $j;
        }
        else {
            $ii = $i;
            $jj = $j + 1;
        }
        $result += runByMatrix($matrix, $ii, $jj);
    }
    else {
        if (!isset($matrix[$i + 1][$j]) && isset($matrix[$i][$j + 1])) {
            $ii = $i;
            $jj = $j + 1;
            $result += runByMatrix($matrix, $ii, $jj);
        }
        elseif (isset($matrix[$i + 1][$j]) && !isset($matrix[$i][$j + 1])) {
            $ii = $i + 1;
            $jj = $j;
            $result += runByMatrix($matrix, $ii, $jj);
        }
    }
    return $result;
}
 
$matrix = createMatrix(5, 5);
echo runByMatrix($matrix);
?>