32 / 34 / 21
Регистрация: 31.03.2018
Сообщений: 472
1

Динамическое программирование. Задача с лестницей

16.05.2019, 14:12. Показов 6113. Ответов 14

Доброго времени суток!

Нужна помощь с решением вот такой вот задчи:

Человек поднимается по ступенькам, ступая на следующую ступеньку или перепрыгивая через одну или же через две. Найти количество способов, которыми человек может поднятся на n-ю ступеньку.

n - задается с клавиатуры.

P. S. Если кидаете готовый код, то с объяснениями, пожалуйста.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.05.2019, 14:12
Ответы с готовыми решениями:

Динамическое программирование: задача о черепашке
Задача о черепашке. Дан 2х мерный массив с очками (длиной пути ну и.т.д.). Найти кротчайший путь...

Задача на динамическое программирование
Узник пытается бежать из замка, который состоит из N×M квадратных комнат, расположенных в виде...

Динамическое программирование - задача
Добрый вечер! На днях попалась такая задача: Миша записывает 2 числа: n и m, а Маша должна...

Задача на динамическое программирование.
Что не правильно? #include <fstream> #include <iostream> using namespace std; int main()...

14
Нарушитель
3120 / 2216 / 1095
Регистрация: 14.08.2016
Сообщений: 7,588
16.05.2019, 15:20 2
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
 
namespace ConsoleApp1
{
    class Program
    {
        static int Ladder(int n)
        {
            return n < 0 ? 0 : n == 0 ? 1 : Enumerable.Range(1, 3).Sum(x => Ladder(n - x));
        }
        static void Main(string[] args)
        {
            Console.Write("number of stairs = ");
            Console.WriteLine($"answer = {Ladder(int.Parse(Console.ReadLine()))}");
        }
    }
}
Цитата Сообщение от Iangyl Посмотреть сообщение
Если кидаете готовый код, то с объяснениями, пожалуйста.
а что, на счет, подумать самостоятельно?
1
1115 / 786 / 219
Регистрация: 15.08.2010
Сообщений: 2,167
16.05.2019, 15:44 3
Diamante, чую не дождусь я результата для 37 ступеньки сегодня
0
32 / 34 / 21
Регистрация: 31.03.2018
Сообщений: 472
18.05.2019, 17:07  [ТС] 4
Цитата Сообщение от Diamante Посмотреть сообщение
а что, на счет, подумать самостоятельно?
да я думал, я пока сам не попробую "обсосать" задачу я не пишу на форум. Я по-разному пробовал, даже пробовал прибегнуть к комбинаторике, но у меня никак не получалось, а до LINQ запросов я еще не дошёл(я Шилда читаю), но уже давно понял, что очень полезная и удобная тема. Правда, я знаю, что можно обычными вычислениями достигнуть ответа - алгоритм, но он слишком заумный я ни грама не понял(может из-за того, что мне на слух объясняли, а мне удобнее, когда я вижу, что происходит).
0
Модератор
Эксперт .NET
10440 / 7413 / 2033
Регистрация: 21.04.2018
Сообщений: 22,394
Записей в блоге: 2
18.05.2019, 18:16 5
Лучший ответ Сообщение было отмечено Iangyl как решение

Решение

Цитата Сообщение от Iangyl Посмотреть сообщение
Правда, я знаю, что можно обычными вычислениями достигнуть ответа
Давайте попробуем реализовать какой-то алгоритм.
Начальные данные у нас это неотрицательное число - количество ступеней и сколько ступеней за один шаг может проходить человек.
Вернуть нужно список всех возможных вариантов прохождения лестницы.
При этом будем считать, что варианты 2+1 и 1+2 - это разные варианты.

Назовём метод ClimbingStairs. Возвращать он должен список вариантов подъёма по лестнице. Каждый вариант это сочетание шагов разной длины. Для такого типа данных подойдёт список List<List<int>>.
Параметры метода это длина лестницы и максимальная длина одного шага назовём и типизируем эти параметры: uint stairLength и uint stepLength.
Получаем такое объявление метода List<List<int>> ClimbingStairs (uint stairLength, uint stepLength)

В самом методе в первую очередь анализируем полученные параметры:
Если stepLength = 0, то генерация исключения new ArgumentException()
Создаём список для возврата результатов List<List<int>> сlimbing = new List<List<int>>();
Если stairLength = 0, то возвращаем пустой список return сlimbing;.
Если stairLength = 1, то возвращаем список с одним значением сlimbing.Add(new List<int>(){1}); return сlimbing;

Теперь надо проверить остальные варианты, для этого перебираем все возможные варианты первого шага по лестнице for (int step=1; step <= stepLength && step <= stairLength; step++)

Добавлено через 4 минуты
Что теперь делать в теле цикла?
У нас есть длина шага. Можем получить остаток ступенек в лестнице после этого шага. Вызвав рекурсивно наш метод для остатка ступенек получаем все варианты для этого остатка. И нам останется добавить для каждого из этих вариантов текущий шаг.
Реализуем это в коде.

Добавлено через 4 минуты
C#
1
2
3
4
5
6
7
{
   foreach (List<int> combin in ClimbingStairs (stairLength-step, stepLength))
   {
         combin.Add(step);
         сlimbing.Add(combin);
   }       
}
Добавлено через 37 секунд
Всё наш метод создан. Осталось только собрать всё это в общий код.
1
32 / 34 / 21
Регистрация: 31.03.2018
Сообщений: 472
20.05.2019, 09:45  [ТС] 6
Элд Хасп, а как его вывести?
Динамическое программирование. Задача с лестницей
0
Модератор
Эксперт .NET
10440 / 7413 / 2033
Регистрация: 21.04.2018
Сообщений: 22,394
Записей в блоге: 2
20.05.2019, 09:52 7
Лучший ответ Сообщение было отмечено Iangyl как решение

Решение

Цитата Сообщение от Iangyl Посмотреть сообщение
а как его вывести?
Метод возвращает перечисление всех вариантов. А количество членов перечисления возвращает метод Count().
C#
1
2
var combin = ClimbingStairs (10, 3); // Получение всех комбинаций
int combinCount = combin.Count(); // Подсчёт количества комбинаций
Добавлено через 3 минуты
Вместе с выводом
C#
1
2
3
4
5
var combin = ClimbingStairs (10, 3); // Получение всех комбинаций
int combinCount = combin.Count(); // Подсчёт количества комбинаций
Console.WriteLine("Вывод всех комбинаций:");
Console.WriteLine(string.Join("\r\n", combin.Select(item=>string.Join(", ", item))));
Console.WriteLine($"Всего комбинаций {combinCount}");
1
Модератор
Эксперт .NET
10440 / 7413 / 2033
Регистрация: 21.04.2018
Сообщений: 22,394
Записей в блоге: 2
20.05.2019, 10:02 8
Iangyl, потестируйте - но возможно мелкая ошибка в алгоритме.
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Если stairLength = 0, то возвращаем пустой список return сlimbing;.
Здесь может быть надо возвращать не пустой список, а список с пустым вариантом шагов сlimbing.Add(new List<int>()); return сlimbing;
1
32 / 34 / 21
Регистрация: 31.03.2018
Сообщений: 472
20.05.2019, 15:13  [ТС] 9
Элд Хасп, значит у меня должно получится вот это:
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
25
26
static void Main(string[] args)
        {
            var combine = ClimbingStairs(5, 3);
            int count = combine.Count();
            Console.WriteLine(count);
        }
        static List<List<uint>> ClimbingStairs(uint stairLength, uint stepLength)
        {
            if (stepLength == 0) new ArgumentException();
            List<List<uint>> climbing = new List<List<uint>>();
            if (stairLength == 0) return climbing;
            else if (stairLength == 1)
            {
                climbing.Add(new List<uint>() { 1 });
                return climbing;
            }
            for (uint step = 1; step <= stairLength; step++)
            {
                foreach(List<uint> combine in ClimbingStairs(stairLength - step, stepLength))
                {
                    combine.Add(step);
                    climbing.Add(combine);
                }
            }
            return climbing;
        }
0
1515 / 413 / 125
Регистрация: 09.01.2018
Сообщений: 906
20.05.2019, 16:36 10
Лучший ответ Сообщение было отмечено Iangyl как решение

Решение

Задача математическая. Это ряд, где первый член равен единице, а каждый последующий равен сумме трех предыдущих. Только мне не нравится вычислять его рекурсивно.
Поэтому так:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
        static long NumOfWays(int n)
        {
            if (n <= 0) return 0;
 
            var que = new Queue<long>(new long[] { 0, 0, 1 });
            long sum = 0;
 
            for (int i = 0; i < n; i++)
            {
                sum = checked(que.Sum());
                que.Dequeue();
                que.Enqueue(sum);
            }
 
            return sum;
        }
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
        static void Main(string[] args)
        {
            var nums = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 12, 27, 44, 56, 72, 96, 104, 263, -5, -12};
            foreach (var item in nums)
            {
                try
                {
                    var res = NumOfWays(item);
                    Console.WriteLine($"{item} - {res.ToString("N0")}");
                }
                catch (Exception e)
                {
 
                    Console.WriteLine($"{item} - {e.Message}");
                }
            }
 
            Console.ReadKey();
        }
Код
0 - 0
1 - 1
2 - 2
3 - 4
4 - 7
5 - 13
6 - 24
7 - 44
8 - 81
12 - 927
27 - 8 646 064
44 - 272 809 183 135
56 - 408 933 139 743 937
72 - 7 015 254 043 203 144 209
96 - Arithmetic operation resulted in an overflow.
104 - Arithmetic operation resulted in an overflow.
263 - Arithmetic operation resulted in an overflow.
-5 - 0
-12 - 0
2
1115 / 786 / 219
Регистрация: 15.08.2010
Сообщений: 2,167
20.05.2019, 16:39 11
Цитата Сообщение от escoult Посмотреть сообщение
Это ряд,
это трибоначчи
3
1515 / 413 / 125
Регистрация: 09.01.2018
Сообщений: 906
20.05.2019, 16:41 12
Цитата Сообщение от КОП Посмотреть сообщение
это трибоначчи
Новый термин, но суть верная
0
1115 / 786 / 219
Регистрация: 15.08.2010
Сообщений: 2,167
20.05.2019, 16:45 13
Цитата Сообщение от escoult Посмотреть сообщение
Новый термин, но суть верная
в русской вики первая правка 2007 год
1
1515 / 413 / 125
Регистрация: 09.01.2018
Сообщений: 906
20.05.2019, 16:47 14
Цитата Сообщение от КОП Посмотреть сообщение
в русской вики первая правка 2007 год
Уже загуглил. Никогда раньше не слышал.
0
Модератор
Эксперт .NET
10440 / 7413 / 2033
Регистрация: 21.04.2018
Сообщений: 22,394
Записей в блоге: 2
20.05.2019, 18:51 15
Цитата Сообщение от Iangyl Посмотреть сообщение
значит у меня должно получится вот это:
C#
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
        static List<List<uint>> ClimbingStairs(uint stairLength, uint stepLength)
        {
            if (stepLength == 0) new ArgumentException();
            List<List<uint>> climbing = new List<List<uint>>();
            if (stairLength == 0)
            {
                climbing.Add(new List<uint>());
                return climbing;
            }
            else if (stairLength == 1)
            {
                climbing.Add(new List<uint>() { 1 });
                return climbing;
            }
            for (uint step = 1; step <= stairLength && step <= stepLength; step++)
            {
                foreach (List<uint> combine in ClimbingStairs(stairLength - step, stepLength))
                {
                    combine.Add(step);
                    climbing.Add(combine);
                }
            }
            return climbing;
        }
Но имейте ввиду - ряд растёт очень быстро.
Для больших чисел будет считать нереально долго.
https://ru.wikipedia.org/wiki/... 1%87%D0%B8
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.05.2019, 18:51

задача на динамическое программирование
На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом...

задача динамическое программирование
В город N приехал цирк с комндой атлетов. Они хотят удивить горожан города N -- выстроить из своих...

Задача на динамическое программирование
Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали...

Задача на динамическое программирование
Требуется решить задачу на динамическое программирование. Условия:На планете Олимпия очень...


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

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

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