|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
13.10.2008, 02:24 | #1 |
Новичок
Джуниор
Регистрация: 07.10.2008
Сообщений: 2
|
объясните, пожалуйста
пожалуйста, объясните чайнику как решать задачи такого типа:
Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца. взято с Алголист.ру, даже если там и есть объяснение, я все равно не могу написать код |
13.10.2008, 09:28 | #2 |
Пользователь
Регистрация: 10.10.2008
Сообщений: 30
|
var
N, K,P: integer; begin writeln('Введите длину пути'); readln(N); writeln('Введите длину хода фишки'); readln(K); P:=N/K; writeln('Число путей равно ',P); readln(); Это код Паскаля. |
13.10.2008, 10:25 | #3 |
*
Старожил
Регистрация: 22.11.2006
Сообщений: 9,201
|
Думается, не все так просто. Дело в том, что N может не делиться без остатка на К... Это - раз.
Второе - ходы могут и должны быть различной длины. Задача, насколько я понимаю, состоит именно в том, чтобы найти все сочетания ходов с учетом наложенных ограничений по длине хода и общей длине пути. |
13.10.2008, 10:43 | #4 |
Пользователь
Регистрация: 10.10.2008
Сообщений: 30
|
Какие могут быть сочетания ходов, если движение только вперёд? Т.е. задача выполняется один раз с известными переменными. Число найдено, другое дело, если были бы заданы другие условия задачи.
|
13.10.2008, 10:59 | #5 | |
*
Старожил
Регистрация: 22.11.2006
Сообщений: 9,201
|
Цитата:
Вариант 1: 3,3,3,2 Вариант 2: 1,1,1,1,1,1,1,1,1,1,1 Вариант 3: 2,3,2,3,1 и так далее... Дальше объяснять? Или дошло? |
|
13.10.2008, 13:01 | #6 |
Пользователь
Регистрация: 10.10.2008
Сообщений: 30
|
Всем извинения приношу! Упустил в задаче НЕ БОЛЕЕ ))
|
13.10.2008, 13:35 | #7 |
Пользователь
Регистрация: 10.10.2008
Сообщений: 30
|
Теперь труднее... Может массив создать и в нём подсчёт вести?
|
13.10.2008, 14:28 | #8 |
*
Старожил
Регистрация: 22.11.2006
Сообщений: 9,201
|
Делаете процедурку вычисления очередной комбинации ходов и поехали...
Берете первую комбинацию и проверяете сумму ходов на равенство суммарному пути. Равно - в правильные результаты, не равно - вычисляете следующую комбинацию. Примерно так: 1 1 1 1 1 1 1 1 1 1 1 подходит 1 1 1 1 1 1 1 1 1 1 2 не подходит 1 1 1 1 1 1 1 1 1 2 подходит 1 1 1 1 1 1 1 1 2 1 подходит 1 1 1 1 1 1 1 2 1 1 подходит .... Правда, из условия не совсем ясно, нужно ли учитывать все перестановки. Вполне возможно, что итоговый результат может выглядеть и таким образом: 1. Одиннадцать единиц 2. Девять единиц и одна двойка 3. Восемь единиц и одна тройка ... N. Три тройки и одна двойка. Последний раз редактировалось mihali4; 13.10.2008 в 14:32. |
14.10.2008, 09:39 | #9 |
Пользователь
Регистрация: 13.10.2008
Сообщений: 17
|
Стандартный подход конечно это банальный перебор и без рекурсий не обойтись, хотя некоторые умельцы могут и циклами обойтись. Главная идея перебрать все варианты, че и предлагает Михалыч.
Ну а другой вариант это нехилое знание построения рекурсивных алгоритмов. Вот сижу я дома думаю че это моя рекурсия по перебору путей не работает(выпендриться млин захотел), а тут папа с работы приходит и "бэмс" решение за 15-20 минут вывел(сам выводил, потому что не его специализация и подобным не занимаеться), а я спрограмировал его идею где-то за столько же... Сканера у мя нету, так что просто код, а сам объяснить почему оно именно так слабо... В целом принцип тот же что и у Фибоначчи. Код:
Последний раз редактировалось Vladko; 14.10.2008 в 09:43. |
14.10.2008, 21:30 | #10 |
Новичок
Джуниор
Регистрация: 07.10.2008
Сообщений: 2
|
спасибо огромное!
принцип использования рекурсии понятен, попробую разобраться в коде и решить несколько задач такого типа. может тогда дойдет. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Объясните пожалуйста | TheHerd | Паскаль, Turbo Pascal, PascalABC.NET | 12 | 04.04.2008 21:33 |
Объясните, пожалуйста смысл строки - res=d.year > year ? -1: (d.year < year? 0:1) | Fynj | Помощь студентам | 2 | 17.12.2007 17:50 |