nixp.ru v3.0

28 марта 2024,
четверг,
19:39:10 MSK

Alexander_ написал 21 ноября 2013 года в 23:55 (2385 просмотров) Ведет себя неопределенно; открыл 1 тему в форуме, оставил 1 комментарий на сайте.

Условие:
План прямоугольного сада размером mxn состоит из квадратных зон. В каждой зоне растёт по дереву. С каждого дерева любой зоны могут упасть несколько яблок.
В левом верхнем квадратике находится ёжик, который должен дойти до правого нижнего квадратика. В саду существуют ограничения относительно способа передвижения: ёжик может двигаться из текущего квадратика только в один из двух соседних правый либо нижний.
Составьте программу, которая вычисляет максимальное количество яблок, которое может собрать ёжик, передвигаясь к нужному квадратику.

Технические условия:
План сада задан таблицей apples содержащей m строк и n столбиков. Элемент apples[i,j] таблицы указывает количество яблок, упавших с дерева в зону с координатами i,j.
Текстовый файл «input.txt» содержит в первой строке числа m,n разделённые пробелом. В каждой из следующих m строк содержится по n чисел apples[i,j] разделённых пробелами.
Файл «output.txt» должен содержать одно натуральное число.

Примеры файлов:

Input.txt<o:p></o:p>

Output.txt<o:p></o:p>

3 3

1 2 3

1 2 3

1 2 3<o:p></o:p>

12<o:p></o:p>

rgo

Перебрать все возможные пути от (0,0) до (m-1, n-1) и выбрать из них самый зачётный. Перебирать, проще всего, рекурсией. То есть написать функцию path, которая будет возвращать максимальное количество яблок, которое можно насобирать на пути от from до to, передаваемых ей в качестве аргументов. Работать же эта функция будет следующим образом, проверять попадание from в границы допустимости, возвращая какой-нибудь некорректный результат если это не так; проверять совпадение from и to, если оно то возвращать количество яблок в to; в третьем варианте вызывать себя рекурсивно дважды, высчитывая максимальное количество яблок, которые можно насобирать на пути к to, от клетки справа от from, и от клетки снизу от from, после чего выбирать максимальный результат, приплюсовывать к нему количество яблок в from и возвращать.

Писать псевдокод лень. Могу именно это изложить на lisp’е:

(defun in-bounds (pos bounds)

(destructuring-bind (x. y) pos

(destructuring-bind (min-x min-y max-x max-y) bounds

(and

(>= x min-x) (<= x max-x)

(>= y min-y) (<= y max-y)))))

(defun move-right (pos)

(cons (+ (car pos) 1) (cdr pos)))

(defun move-down (pos)

(cons (car pos) (+ (cdr pos) 1)))

(defun path (apples from to bounds)

(cond

((not (in-bounds from bounds)) -1)

((equal from to) (aref apples (car from) (cdr from)))

(t (let ((right-price (path apples (move-right from) to bounds))

(down-price (path apples (move-down from) to bounds))

(here-price (aref apples (car from) (cdr from))))

(if (or (>= right-price 0) (>= down-price 0)); это условие по-моему лишнее, но на всякий случай

(+ here-price

(if (> right-price down-price)

right-price

down-price))

-1)))))

(with-open-file (s «input.txt» :direction :input)

(let* ((m (read s))

(n (read s))

(apples (make-array `(,m ,n)

:initial-contents (loop

for i from 0 below m

collect (loop

for i from 0 below n

collect (read s))))))

(with-open-file (s «output.txt» :direction :output)

(print (path apples '(0. 0) `(,(- m 1). ,(- n 1)) `(0 0 ,(- m 1) ,(- n 1))) s))))

Разметку перекосячило, но тут нету способа воткнуть fixed шрифт, и пробелы в принудительном порядке выводить.

Alexander_

почему не получается инициализировать массив следующим образом:

int[][] apples = new int[4][] { { 3, 3 }, { 1, 2, 3 }, { 1, 2, 3 }, { 1, 2, 3 } };

fhunter

У меня сразу есть вопросы — а почему в первой строке 2 элемента а не 3?

msdn.microsoft.com/en-us/library/vstudio/2yd9wwz4.aspx :-)

Последние комментарии

ecobeingecobeing.ru
Экология и вегетарианство на благо всем живым существам Планеты.