Форум программистов, компьютерный форум CyberForum.ru

Найти число различных путей - C++

Войти
Регистрация
Восстановить пароль
 
boom299
2 / 2 / 0
Регистрация: 08.04.2011
Сообщений: 23
08.05.2011, 22:25     Найти число различных путей #1
Фишка может двигаться по полю длины N только вперёд. Длина хода фишки не более K. Найти число различных путей, по которым фишки может пройти поле от начала до конца.

Пример: N=3, K=2
Возможные пути:
1,1,1
1,2
2,1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.05.2011, 22:25     Найти число различных путей
Посмотрите здесь:

C++ Найти количество всех путей и контуров графа длиной S
C++ Даны целые числа a[1],.,a[n]. Найти число различных членов последовательности
C++ Найти число различных членов последовательности
C++ Из скольких различных чисел состоит введенное число.
Найти слово, в котором число различных символов минимально C++
C++ Найти количество различных чисел в последовательности. Число действий должно быть порядка n*log(n)
C++ Шахматы: найти количество путей для попадания в точку n
Поиск всех различных путей в графе C++
C++ Вычислить количество различных путей между всеми парами вершин графа
Строки: найти слово, в котором число различных символов максимально C++
C++ Определить число различных элементов в массиве
Найти число различных элементов массива C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
08.05.2011, 22:37     Найти число различных путей #2
Динамическое программирование. Заводишь массив A c кол-вом различных путей для каждой длины поля(длина поля-индекс), зануляешь, и в цикле по i=1 до N заполняешь, A[0]=1
для конкретного i вычитаешь все возможные длины путей из i (чтоб получившееся число было неотрицательным, например,для i=1 можно вычесть только длину хода 1, получаем 0. И далее A[i]+=A[0], так как добавляется 1 ход
для i=2 A[2]=A[0]+A[1], а A[1]=A[0];
Yandex
Объявления
08.05.2011, 22:37     Найти число различных путей
Ответ Создать тему
Опции темы

Текущее время: 10:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru