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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
boom299
2 / 2 / 0
Регистрация: 08.04.2011
Сообщений: 23
#1

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

08.05.2011, 22:25. Просмотров 908. Ответов 1
Метки нет (Все метки)

Фишка может двигаться по полю длины N только вперёд. Длина хода фишки не более K. Найти число различных путей, по которым фишки может пройти поле от начала до конца.

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

Поиск всех различных путей в графе - C++
Задан ориентированный ациклический связный граф. Найдите различные пути, по которым из вершины под номером 1 можно добраться до вершины с...

Вычислить количество различных путей между всеми парами вершин графа - C++
Задан граф с N вершинами вычислить количество различных путей между всеми парами вершин графа

Найти число различных элементов массива - C++
написать программу для нахождения числа различных элементов массива)

Найти число различных членов последовательности - C++
Даны целые числа A1,…,An (в этой последовательности могут быть повторяющиеся члены). Найти число различных членов последовательности.

Найти слово, в котором число различных символов минимально - C++
Добрый вечер! Помогите, пожалуйста. Ввести n слов с консоли. Найти слово, в котором число различных символов минимально. Если таких...

Даны целые числа a[1],.,a[n]. Найти число различных членов последовательности - C++
много мыслей, и все никуда: Даны целые числа a,...,a (в этой последовательности могут быть повторяющиеся члены). Найти число...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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];
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.05.2011, 22:37
Привет! Вот еще темы с ответами:

Строки: найти слово, в котором число различных символов максимально - C++
Всем привет. Помогите, пожалуйста, написать программу по этой задаче: "Строка состоит из слов, разделенных одним или несколькими...

Найти количество различных чисел в последовательности. Число действий должно быть порядка n*log(n) - C++
Необходима помощь в сортировке. Последовательность хранится в файле. Необходимо найти количество различных чисел в последовательности....

Найти количество всех путей и контуров графа длиной S - C++
Требуется найти количество всех путей и контуров графа длиной 7. Граф: 1 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 0 1 1...

Шахматы: найти количество путей для попадания в точку n - C++
Напишите пожалуйста программу,а то сам С++ почти не знаю,а скоро сдавать. Шахматная фигура может двигаться на 1 шаг,на 2 или на 3. найти...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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