n шагов с 1, 2 или 3 шагами. Сколько способов добраться до вершины?

Ответ 1

Я бы сказал, что формула будет выглядеть следующим образом:

K(1) = 1
K(2) = 2
k(3) = 4
K(n) = K(n-3) + K(n-2) + K(n - 1)

Формула гласит, что для достижения n-го шага мы должны сначала достичь:

• n-3'-й шаг, а затем выполнить 3 шага одновременно, т.е. K (n-3)
• или n-2'-й шаг, а затем выполнить 2 шага одновременно, т.е. K (n-2)
• или n-1'-й шаг, а затем выполнить 1 шаг одновременно, т.е. K (n-1)

K (4) = 7, K (5) = 13 и т.д.

Вы можете использовать рекурсивную формулу или использовать динамическое программирование.

Ответ 2

Решения Python:

Рекурсивный O (n)

Это основано на ответе Майкла. Это требует O (n) процессора и O (n) памяти.

import functools

@functools.lru_cache(maxsize=None)
def recursive(n):
    if n < 4:
        initial = [1, 2, 4]
        return initial[n-1]
    else:
        return recursive(n-1) + recursive(n-2) + recursive(n-3)

Рекурсивный O (log (n))

Это за комментарий к этому ответу. Это tribonacci его удвоения раствора аналогично Фибоначчи с помощью удвоения раствора в алгоритмах по Наюкам. Обратите внимание, что умножение имеет более высокую сложность, чем константа. Это не требует или извлекает выгоду из кэша.

def recursive_doubling(n):
    def recursive_tribonacci_tuple(n):
        """Return the n, n+1, and n+2 tribonacci numbers for n>=0.

        Tribonacci forward doubling identities:
        T(2n)   = T(n+1)^2 + T(n)*(2*T(n+2) - 2*T(n+1) - T(n))
        T(2n+1) = T(n)^2 + T(n+1)*(2*T(n+2) - T(n+1))
        T(2n+2) = T(n+2)^2 + T(n+1)*(2*T(n) + T(n+1))
        """
        assert n >= 0
        if n == 0:
            return 0, 0, 1  # T(0), T(1), T(2)

        a, b, c = recursive_tribonacci_tuple(n // 2)
        x = b*b + a*(2*(c - b) - a)
        y = a*a + b*(2*c - b)
        z = c*c + b*(2*a + b)

        return (x, y, z) if n % 2 == 0 else (y, z, x+y+z)
    return recursive_tribonacci_tuple(n)[2]  # Is offset by 2 for the steps problem.

Итеративный O (n)

Это мотивировано ответом 太極 者 無極 而 生. Это модифицированное расширение трибоначчи итерационного решения Фибоначчи. Он модифицирован от tribonacci тем, что возвращает c, а не a.

def iterative(n):
    a, b, c = 0, 0, 1
    for _ in range(n):
        a, b, c = b, c, a+b+c
    return c

Итеративный O (log (n)) (слева направо)

Это за комментарий к этому ответу. Это модифицированное итеративное решение трибоначчи за удвоением получается из соответствующего рекурсивного решения. Для некоторого фона, смотрите здесь и здесь. Он модифицирован от tribonacci тем, что возвращает c, а не a. Обратите внимание, что умножение имеет более высокую сложность, чем константа.

Биты n итерируются слева направо, то есть от MSB к LSB.

def iterative_doubling_l2r(n):
    """Return the n+2 tribonacci number for n>=0.

    Tribonacci forward doubling identities:
    T(2n)   = T(n+1)^2 + T(n)*(2*T(n+2) - 2*T(n+1) - T(n))
    T(2n+1) = T(n)^2 + T(n+1)*(2*T(n+2) - T(n+1))
    T(2n+2) = T(n+2)^2 + T(n+1)*(2*T(n) + T(n+1))
    """
    assert n >= 0
    a, b, c = 0, 0, 1  # T(0), T(1), T(2)
    for i in range(n.bit_length() - 1, -1, -1):  # Left (MSB) to right (LSB).
        x = b*b + a*(2*(c - b) - a)
        y = a*a + b*(2*c - b)
        z = c*c + b*(2*a + b)
        bit = (n >> i) & 1
        a, b, c = (y, z, x+y+z) if bit else (x, y, z)
    return c

Заметки:

• list(range(m - 1, -1, -1)) == list(reversed(range(m)))
• Если бит нечетный (1), последовательность продвигается за одну итерацию. Это интуитивно понятно после понимания того же самого для задачи эффективного целочисленного возведения в степень.

Итеративный O (log (n)) (справа налево)

Это за комментарий к этому ответу. Биты n итерируются справа налево, то есть от LSB до MSB. Этот подход, вероятно, не является предписывающим.

def iterative_doubling_r2l(n):
    """Return the n+2 tribonacci number for n>=0.

    Tribonacci forward doubling identities:
    T(2n)   = T(n+1)^2 + T(n)*(2*T(n+2) - 2*T(n+1) - T(n))
    T(2n+1) = T(n)^2 + T(n+1)*(2*T(n+2) - T(n+1))
    T(2n+2) = T(n+2)^2 + T(n+1)*(2*T(n) + T(n+1))

    Given Tribonacci tuples (T(n), T(n+1), T(n+2)) and (T(k), T(k+1), T(k+2)),
    we can "add" them together to get (T(n+k), T(n+k+1), T(n+k+2)).

    Tribonacci addition formulas:
    T(n+k)   = T(n)*(T(k+2) - T(k+1) - T(k)) + T(n+1)*(T(k+1) - T(k)) + T(n+2)*T(k)
    T(n+k+1) = T(n)*T(k) + T(n+1)*(T(k+2) - T(k+1)) + T(n+2)*T(k+1)
    T(n+k+2) = T(n)*T(k+1) + T(n+1)*(T(k) + T(k+1)) + T(n+2)*T(k+2)
    When n == k, these are equivalent to the doubling formulas.
    """
    assert n >= 0
    a, b, c = 0, 0, 1  # T(0), T(1), T(2)
    d, e, f = 0, 1, 1  # T(1), T(2), T(3)
    for i in range(n.bit_length()):  # Right (LSB) to left (MSB).
        bit = (n >> i) & 1
        if bit:
            # a, b, c += d, e, f
            x = a*(f - e - d) + b*(e - d) + c*d
            y = a*d + b*(f - e) + c*e
            z = a*e + b*(d + e) + c*f
            a, b, c = x, y, z
        # d, e, f += d, e, f
        x = e*e + d*(2*(f - e) - d)
        y = d*d + e*(2*f - e)
        z = f*f + e*(2*d + e)
        d, e, f = x, y, z
    return c

приближения

Аппроксимации, конечно, полезны в основном для очень больших n. Операция возведения в степень используется. Обратите внимание, что возведение в степень имеет более высокую сложность, чем константа.

def approx1(n):
    a_pos = (19 + 3*(33**.5))**(1./3)
    a_neg = (19 - 3*(33**.5))**(1./3)
    b = (586 + 102*(33**.5))**(1./3)
    return round(3*b * ((1./3) * (a_pos+a_neg+1))**(n+1) / (b**2 - 2*b + 4))

Вышеприведенное приближение проверялось на корректность до n = 53, после чего оно отличалось. Конечно, возможно, что использование арифметики с плавающей точкой с более высокой точностью приведет к лучшему приближению на практике.

def approx2(n):
    return round((0.618363 * 1.8392**n + \
                  (0.029252 + 0.014515j) * (-0.41964 - 0.60629j)**n + \
                  (0.029252 - 0.014515j) * (-0.41964 - 0.60629j)**n).real)

Вышеприведенное приближение проверялось на корректность до n = 11, после чего оно отличалось.

Ответ 3

Это мое решение в Ruby:

# recursion requirement: it returns the number of way up
# a staircase of n steps, given that the number of steps
# can be 1, 2, 3

def how_many_ways(n)
  # this is a bit Zen like, if 0 steps, then there is 1 way
  # and we don't even need to specify f(1), because f(1) = summing them up
  # and so f(1) = f(0) = 1
  # Similarly, f(2) is summing them up = f(1) + f(0) = 1 + 1 = 2
  # and so we have all base cases covered
  return 1 if n == 0

  how_many_ways_total = 0
  (1..3).each do |n_steps|
    if n >= n_steps
      how_many_ways_total += how_many_ways(n - n_steps)
    end
  end
  return how_many_ways_total
end

0.upto(20) {|n| puts "how_many_ways(#{n}) => #{how_many_ways(n)}"}

и более короткая версия:

def how_many_ways(n)
  # this is a bit Zen like, if 0 steps, then there is 1 way
  # if n is negative, there is no way and therefore returns 0
  return 1 if n == 0
  return 0 if n < 0
  return how_many_ways(n - 1) + how_many_ways(n - 2) + how_many_ways(n - 3)
end

0.upto(20) {|n| puts "how_many_ways(#{n}) => #{how_many_ways(n)}"}

и как только вы знаете, что это похоже на ряд фибоначчи, вы не будете использовать рекурсию, но используйте итеративный метод:

# 
# from 0 to 27: recursive: 4.72 second
#               iterative: 0.03 second
#

def how_many_ways(n)
  arr = [0, 0, 1]
  n.times do
    new_sum = arr.inject(:+)    # sum them up
    arr.push(new_sum).shift()
  end
  return arr[-1]
end

0.upto(27) {|n| puts "how_many_ways(#{n}) => #{how_many_ways(n)}"}

вывод:

how_many_ways(0) => 1
how_many_ways(1) => 1
how_many_ways(2) => 2
how_many_ways(3) => 4
how_many_ways(4) => 7
how_many_ways(5) => 13
how_many_ways(6) => 24
how_many_ways(7) => 44
how_many_ways(8) => 81
how_many_ways(9) => 149
how_many_ways(10) => 274
how_many_ways(11) => 504
how_many_ways(12) => 927
how_many_ways(13) => 1705
  .
  .
how_many_ways(22) => 410744
how_many_ways(23) => 755476
how_many_ways(24) => 1389537
how_many_ways(25) => 2555757
how_many_ways(26) => 4700770
how_many_ways(27) => 8646064

Мне нравится объяснение @MichałKomorowski и комментарий @rici. Думаю, я думаю, что если это зависит от знания K(3) = 4, то это связано с подсчетом вручную.

Ответ 4

Легко получить интуицию для проблемы:

Подумайте, что вы поднимаетесь по лестнице, и возможные шаги, которые вы можете предпринять, - 1 & 2

Общий №. способов достижения шага 4 = общее количество. способов достижения шага 3 + Общее количество способов достижения шага 2

Как?

В принципе, есть только два возможных шага от того, где вы можете достичь шага 4.

1. Либо вы на третьем шаге, либо сделайте один шаг
2. Или вы на шаге 2 и совершите двухэтапный прыжок

Эти два являются единственными возможностями, с помощью которых вы можете когда-либо достичь шага 4

Аналогично, существует только два возможных способа достижения шага 2

1. Либо вы на первом шаге, либо сделайте один шаг
2. Или вы на шаге 0 и совершите двухэтапный прыжок

F (n) = F (n-1) + F (n-2)

F (0) = 0 и F (1) = 1 являются базовыми случаями. Отсюда вы можете начать строить F (2), F (3) и так далее. Это похоже на ряд Фибоначчи.

Если количество возможных шагов увеличивается, скажем [1,2,3], теперь для каждого шага у вас есть еще один вариант, т.е. Вы можете прямо прыгать с трех шагов до него

Следовательно, формула будет

F (n) = F (n-1) + F (n-2) + F (n-3)

Посмотрите это видео для понимания проблемы лестницы Серия Фибоначчи

Простое понимание кода: проблема с лестницей geeksforgeeks

Ответ 5

Подсчитайте способы достижения n- ^й лестницы, используя шаги 1, 2, 3.

Мы можем рассчитывать с использованием простых рекурсивных методов.

// Header File
#include<stdio.h>
// Function prototype for recursive Approch
int findStep(int);
int main(){
    int n;
    int ways=0;
    ways = findStep(4);
    printf("%d\n", ways);
return 0;
}
// Function Definition
int findStep(int n){
    int t1, t2, t3;
    if(n==1 || n==0){
        return 1;
    }else if(n==2){
        return 2;
    }
    else{
        t3 = findStep(n-3);
        t2 = findStep(n-2);
        t1 = findStep(n-1);
        return t1+t2+t3;
    }
}

Ответ 6

def count(steps):
  sol = []
  sol.append(1)
  sol.append(1 + sol[0])
  sol.append(1 + sol[1] + sol[0])


  if(steps > 3):
    for x in range(4, steps+1):
        sol[(x-1)%3] = sum(sol)


return sol[(steps-1)%3]

Ответ 7

Мое решение находится в java. Я решил решить эту проблему.

Я начинаю с пустого массива текущих путей []. Каждый шаг я добавлю все возможные размеры шагов {1,2,3}

Первый шаг [] → [[1], [2], [3]]
Второй шаг [[1], [2], [3]] → [[1,1], [1,2], [1,3], [2,1], [2,2], [ 2,3], [3,1] [3,2], [3,3]]

Итерация 0: []
Итерация 1: [[1], [2], [3]]
Итерация 2: [[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2 ], [3,3]]
Итерация 3 [[1,1,1], [1,1,2], [1,1,3]....]

Длины последовательности следующие: 1 2 3 5 8 13 21

Моя функция шага называется build

public class App {



public static boolean isClimedTooHigh(List<Integer> path, int maxSteps){
    int sum = 0;
    for (Integer i : path){
        sum+=i;
    }
    return sum>=maxSteps;
}

public static void modify(Integer x){
    x++;
    return;
}

///  1    2   3

/// 11 12 13
/// 21 22 23
/// 31 32 33

///111 121
public static boolean build(List<List<Integer>> paths, List<Integer> steps, int maxSteps){
    List<List<Integer>> next = new ArrayList<List<Integer>>();
    for (List<Integer> path : paths){
        if (isClimedTooHigh(path, maxSteps)){
            next.add(path);
        }
        for (Integer step : steps){
            List<Integer> p = new ArrayList<Integer>(path);
            p.add(step);
            next.add(p);
        }
    }
    paths.clear();
    boolean completed = true;
    for (List<Integer> n : next){
        if (completed && !isClimedTooHigh(n, maxSteps))
            completed = false;
        paths.add(n);
    }

    return completed;
}

public static boolean isPathEqualToMax(List<Integer> path, int maxSteps){
    int sum = 0;
    for (Integer i : path){
        sum+=i;
    }
    return sum==maxSteps;
}

public static void calculate( int stepSize, int maxSteps ){
    List<List<Integer>> paths = new ArrayList<List<Integer>>();
    List<Integer> steps = new ArrayList<Integer>();
    for (int i =1; i < stepSize; i++){
        List<Integer> s = new ArrayList<Integer>(1);
        s.add(i);
        steps.add(i);
        paths.add(s);
    }
    while (!build(paths,steps,maxSteps));
    List<List<Integer>> finalPaths = new ArrayList<List<Integer>>();
    for (List<Integer> p : paths){
        if (isPathEqualToMax(p, maxSteps)){
            finalPaths.add(p);
        }
    }

    System.out.println(finalPaths.size());
}
public static void main(String[] args){
    calculate(3,1);
    calculate(3,2);
    calculate(3,3);
    calculate(3,4);
    calculate(3,5);
    calculate(3,6);
    calculate(3,7);

    return;
}

}

Ответ 8

Ниже приведена реализация O (N k) Java с использованием динамического программирования:

public class Sample {
    public static void main(String[] args) {
        System.out.println(combos(new int[]{4,3,2,1}, 100));
    }

    public static int combos(int[] steps, int stairs) {
        int[][] table = new int[stairs+1][steps.length];
        for (int i = 0; i < steps.length; i++) {

            for (int n = 1; n <= stairs; n++ ) {
                int count = 0;
                if (n % steps[i] == 0){
                    if (i == 0)
                        count++;
                    else {
                        if (n <= steps[i])
                            count++;
                    }
                }

                if (i > 0 && n > steps[i]) {
                    count += table[n - steps[i]][i];
                }

                if (i > 0)
                    count += table[n][i-1];

                table[n][i] = count;
            }
        }

        for (int n = 1; n < stairs; n++) {
            System.out.print(n + "\t");
            for (int i = 0; i < steps.length; i++) {
                System.out.print(table[n][i] + "\t");
            }
            System.out.println();
        }
        return table[stairs][steps.length-1];
    }
}

Идея состоит в том, чтобы заполнить следующую таблицу 1 столбцом слева направо:

N    (4)    (4,3)  (4,3,2) (4,3,2,1)
1   0   0   0   1   
2   0   0   1   2   
3   0   1   1   3   
4   1   1   2   5   
5   0   0   1   6   
6   0   1   3   9   
7   0   1   2   11  
8   1   1   4   15  
9   0   1   3   18  
10  0   1   5   23  
11  0   1   4   27  
12  1   2   7   34  
13  0   1   5   39  
..
..
99  0   9   217 7803
100             8037

Ответ 9

Подсчитайте общее количество способов покрытия расстояния 1, 2 и 3 шага.

Временная сложность рекурсивного решения является экспоненциальной, т.е. O (3n).

Поскольку такие же подвыборы снова решены, эта проблема имеет перекрывающееся свойство подзадач. Таким образом, проблема минимальной суммы квадратов имеет оба свойства проблемы динамического программирования.

public class MaxStepsCount {

     /** Dynamic Programming. */
     private static int getMaxWaysDP(int distance) {

           int[] count = new int[distance+1];
           count[0] = 1;
           count[1] = 1;
           count[2] = 2;

           /** Memorize the Sub-problem in bottom up manner*/
           for (int i=3; i<=distance; i++) {
                count[i] = count[i-1] + count[i-2] + count[i-3];               
           }
           return count[distance];
     }


     /** Recursion Approach. */
     private static int getMaxWaysRecur(int distance) {
           if(distance<0) {
                return 0;
           } else if(distance==0) {
                return 1;
           }
           return getMaxWaysRecur(distance-1)+getMaxWaysRecur(distance-2)
                     +getMaxWaysRecur(distance-3);
     }

     public static void main(String[] args) {
           // Steps pf 1, 2 and 3.
           int distance = 10;

           /** Recursion Approach. */
           int ways = getMaxWaysRecur(distance);
           System.out.println(ways);

           /** Dynamic Programming. */
           ways = getMaxWaysDP(distance);
           System.out.println(ways);
     }
}

Мое сообщение в блоге об этом:

http://javaexplorer03.blogspot.in/2016/10/count-number-of-ways-to-cover-distance.html

Ответ 10

Рекурсивное решение на основе memoization C++: спросите ли вы, сколько способов мы можем достичь? Если это не самая верхняя ступень, она собирается спросить всех своих соседей и подвести итог и вернуть результат. Если его верхняя лестница скажет 1.

vector<int> getAllStairsFromHere(vector<int>& numSteps,  int& numStairs, int currentStair)
{
    vector<int> res;

    for(auto it : numSteps)
        if(it + currentStair <= numStairs)
            res.push_back(it + currentStair);

    return res;
}


int numWaysToClimbUtil(vector<int>& numSteps, int& numStairs, int currentStair, map<int,int>& memT)
{
    auto it = memT.find(currentStair);
    if(it != memT.end())
        return it->second;

    if(currentStair >= numStairs)
        return 1;

    int numWaysToClimb = 0;
    auto choices = getAllStairsFromHere(numSteps,  numStairs, currentStair);
    for(auto it : choices)
        numWaysToClimb += numWaysToClimbUtil(numSteps, numStairs, it, memT);


    memT.insert(make_pair(currentStair, numWaysToClimb));
    return memT[currentStair];
}


int numWaysToClimb(vector<int>numSteps, int numStairs)
{
    map<int,int> memT;
    int currentStair = 0;
    return numWaysToClimbUtil(numSteps, numStairs, currentStair, memT);
}

Ответ 11

Ниже приведено несколько способов использования 1, 2 и 3 шагов

1: 1
2: 11   2
3: 111 12 21 3
4: 1111 121 211 112 22 13 31
5: 11111 1112 1121 1211 2111 122 212 221 113 131 311 23 32
6: 111111 11112 11121 11211 12111 21111 1113 1131 1311 3111 123 132 312 321 213 231 33 222 1122 1221 2211 1212 2121 2112

Таким образом, согласно вышеприведенной комбинации, soln должен быть:

K(n) = K(n-3) + K(n-2) + K(n - 1)
k(6) = 24 which is k(5)+k(4)+k(3) = 13+7+4

Ответ 12

Рекурсивная реализация Java на основе ответа Michał:

public class Tribonacci {
    // k(0) = 1
    // k(1) = 1
    // k(2) = 2
    // k(3) = 4
    // ...
    // k(n) = k(n-3) + k(n-2) + k(n - 1)

    static int get(int n) {
        if (n == 0) {
            return 1;
        } if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        //} else if (n == 3) {
        //    return 4;
        } else {
            return get(n - 3) + get(n - 2) + get(n - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println("Tribonacci sequence");
        System.out.println(Tribonacci.get(1));
        System.out.println(Tribonacci.get(2));
        System.out.println(Tribonacci.get(3));
        System.out.println(Tribonacci.get(4));
        System.out.println(Tribonacci.get(5));
        System.out.println(Tribonacci.get(6));
    }
}

Ответ 13

Может быть, его просто 2 ^ (n-1), где n - количество шагов?

Это делает меня для меня, потому что с 4 шагами у вас есть 8 возможностей:

4,
3+1,
1+3,
2+2,
2+1+1,
1+2+1,
1+1+2,
1+1+1+1,

Я думаю, это шаблон