0 / 0 / 0
Регистрация: 17.04.2017
Сообщений: 10
1

Найти число различных путей, по которым фишка может пройти поле от позиции 1 до позиции N

30.05.2018, 19:35. Показов 1010. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от позиции 1 до позиции N.
Пример. N=4, K=2
Возможные длины ходов:
1,1,1
1,2
2,1
Ответ: 3.

Подсчёт количества сделан, нужна помощь с выводом всех возможных вариантов которыми может пройти фишка как в примере выше.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include  "iostream"
 
using namespace std;
int main()
{
    cout << "n: ";
    int n=4;
    cin >> n;
    cout << "k: ";
    int k=2;
    cin >> k;
    int* a = new int[n];
    a[0] = 1;
    a[1] = 1;
    for (int i = 2; i < n; i++)
    {
        a[i] = 0;
        for (int j = 1; j <= k && i - j >= 0; j++)
            a[i] += a[i - j];
    }
    cout << a[n - 1] << endl;
    system("pause");
    return 0;
}
0
30.05.2018, 19:35
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
30.05.2018, 19:35
Ответы с готовыми решениями:

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

Найти сумму одного из трёх элементов ряда с позиции m до позиции N
допишите программу, которая высчитывает сумму одного из трёх элементов ряда с позиции m до позиции N. Осталось определить саму сумму ряда....

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

1
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
30.05.2018, 19:53 2
Типичная задача для динамического программирования.

Добавлено через 15 минут
Рекомендую написать функцию

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct DAG_Node{
   int total_paths;
   int current_pos;
   std::vector<DAG_Node*> child_paths;
}
using result_pair = std::pair<int, DAG_Node*>;
using dynamic_pro_mem = std::unordered_map<int, DAG_Node*>;
 
DAG_Node* NumberWays(int remain_path, dynamic_pro_mem& mem, DAG_Node* finish)
{
   if(remain_path<=0) return {0, min(N-remain_path, N), finish};
   if(mem.find(remain_path)!=mem.end())
      return mem[remain_path];
   DAG_Node* result = new DAG_Node();
   for (int i = 1; i<remain_path)
   {
       DAG_Node * r =  NumberWays(remain_path-i, mem, finish);
       result_sum->total_paths += r->total_paths;
       result_sum->child_paths.push(r);
   }
   result->current_pos = N - remain_path;
   mem[remain_path] = result;
  return result;
}
Потом надо лишь обойти DAG (направленный ациклический граф).
Только не забудь потом удалить все value из mem.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
30.05.2018, 19:53
Помогаю со студенческими работами здесь

Найти число по заданному номеру позиции
Написать задачу на языке паскаль которая вводит целое число и по заданному номеру позиции в числе печатает цифру числа,стоящая на этой...

Количество строк, которые одновременно имеют цифру на позиции n1 и букву на позиции n2
У Поликарпа возникла новая идея для занимательной статистики. Поэтому он просит Вас написать функцию fun_strings_stat(n1, n2 , *args),...

Вычислить сумму ряда с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно.
9. Вычислить сумму ряда (-1)в степени 3n/3n! с позиции N до позиции M. Функцию вычисления суммы реализовать рекурсивно. Добавлено...

Удалить из исходного списка элементы, начиная с позиции K до позиции N
Удалить из исходного списка элементы, начиная с позиции K до позиции N

Создать функцию программиста, которая в заданной строке S1 удаляет символы с позиции N1 до позиции N2 и вставляет в это место строку S2
Создать функцию программиста, которая в заданной строке S1 удаляет символы с позиции N1 до позиции N2 и вставляет в это место строку S2....


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

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

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Опции темы

Новые блоги и статьи
Ключевые слова Python
hw_wired 15.02.2025
Ключевые слова в Python - это специальные зарезервированные слова, которые имеют особое значение и функции в языке. В настоящее время Python включает 35 ключевых слов и 4 мягких ключевых слова. Эти. . .
Отличия изменяемых и неизменяемых типов в Python
hw_wired 15.02.2025
В Python существует принципиальное различие между изменяемыми (mutable) и неизменяемыми (immutable) типами данных, которое оказывает существенное влияние на работу программ. Это различие часто. . .
Python: сравнение списков и кортежей
hw_wired 15.02.2025
В Python последовательности являются одними из самых важных и часто используемых типов данных. Они позволяют хранить упорядоченные наборы элементов, к которым можно обращаться по индексу. Среди всех. . .
Как скачивать файлы с URL с помощью Python
hw_wired 15.02.2025
Для скачивания файлов Python предлагает как встроенные средства, так и сторонние библиотеки. Встроенный модуль urllib из стандартной библиотеки обеспечивает базовую функциональность для работы с URL. . .
Использование SQLAlchemy в Python
hw_wired 15.02.2025
SQLAlchemy - мощная библиотека для работы с базами данных в Python, которая предоставляет полноценный набор средств для объектно-реляционного отображения (ORM) и обширные возможности для работы с. . .
Взаимодействие с REST API в Python
hw_wired 15.02.2025
В современном мире разработки программного обеспечения REST API стал неотъемлемой частью архитектуры веб-приложений. API (Application Programming Interface) - это набор правил и протоколов,. . .
Разделение строк в Python
hw_wired 15.02.2025
Python предлагает богатый набор возможностей для работы со строками, и среди них разделение строк занимает особое место. Этот процесс позволяет разбивать текст на отдельные компоненты, что критично. . .
Объединение строк в Python
hw_wired 15.02.2025
При работе с текстовыми данными в Python нередко возникает необходимость объединять несколько строк в одну. Это может потребоваться при форматировании вывода, обработке текстовых файлов или создании. . .
Лучшие игровые движки на Python
hw_wired 15.02.2025
В последнее время разработка игр стала одним из самых популярных направлений программирования, и Python не остался в стороне от этого тренда. Несмотря на то, что Python обычно не ассоциируется с. . .
Декоратор jit в Python
hw_wired 15.02.2025
Если вы достаточно долго изучаете программы и пакеты на Python для машинного обучения, то наверняка замечали, что паттерн "JIT-декоратор" довольно популярен. Этот подход позволяет превратить обычные. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru