8

Один мой знакомый занимается составлением олимпиадных задач, которые впоследствии иногда дают на собеседованиях. Возникли затруднения с решением данной задачи:

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

Хотелось бы узнать, что предложите вы. Мне интересен сам алгоритм, код далеко не так важен, но в любом случае это будет только плюсом =)

1
  • 3
    А разве в этой задаче нельзя аналитическим путем вывести формулу для вычисления количества маршрутов?
    – gecube
    21 июн 2012 в 12:12

4 ответа 4

8

Простейшая динамика (в которой я очень слаб, к сожалению)

Заведем массив dp размерностью n+1 (каждый i-й элемент будет хранить количество если бы было i ступенек)

dp[0]=1 //ступенек нет

Остальные рассчитываются как сумма всех предыдущих на расстоянии не больших k

Ответ в dp[n].

upd тоже код с acmp.ru

a[0] = BigInteger.ONE;
        int start;
        for (int i=1; i<=n; i++)
        {
            start = Math.max(0, i-k);
            a[i] = BigInteger.ZERO;
            for (int j=start; j<i; j++)
            {
                a[i] = a[i].add(a[j]);
            }
        }
5
  • Большое спасибо. Только вот можно поподробнее насчет этого: >остальные рассчитываются как сумма всех предудыщих на расстоянии не больших k
    – Free_man
    20 июн 2012 в 19:24
  • Например если ступенек 5(N), а максимальный прыжок на 2 ступеньки(K) То на ступеньку 1 можно прыгнуть с 0й На ступеньку 2 из 1,0 На ступеньку 3 из 2,1 (0 уже нельзя, как раз расстояние больше чем в 2 ступеньки) То есть мы смотрим все ступеньки из которых можем припрыгать и добавляем то количество вариантов с которыми можем припрыгать в предыдущую ступеньку то есть одним способом мы можем остаться на 0й ступеньке на 1ю ступеньку мы можем прыгнуть из 0й только (а это один вариант) на 2ю из 0(1 вариант) и из 1й(1 вариант), в сумме 2 на 3ю из 1 (1 в-т) и из 2 (2 в-та), в сумме 3 и т.д
    – misha_m
    20 июн 2012 в 19:30
  • Спасибо за разжевывание! Стало понятнее.
    – Free_man
    20 июн 2012 в 19:37
  • "Заяц может одним прыжком преодолеть не более К ступенек", вот это сбивает =), а если заяц может 5 ступенек перепрыгнуть, а будет только по 4? =)
    – Gorets
    20 июн 2012 в 19:39
  • Алгоритм неплохой!
    – AseN
    21 июн 2012 в 8:29
5

Вот эта задача на сервере acmp.ru. Решал её несколько лет назад. Там динамика действительно очень простая, но дополнительная сложность была в ограничениях на K и N (1 ≤ K ≤ N ≤ 300). Для граничных значений K и N результат не помещался даже в 64-битной переменной, поэтому приходилось привлекать длинную арифметику.

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

#include<stdio.h>

#define INFILE "INPUT.TXT"
#define OUTFILE "OUTPUT.TXT"

int m[400][100];

int main()
{
    FILE *fin, *fout;
    long k, n, i, j, t, z, w;

    fin = fopen(INFILE, "r");
    fscanf(fin, "%d%d", &k, &n);
    fclose(fin);

    fout = fopen(OUTFILE, "w");
    for (i = 0; i < n; i++)
    {
        if (i < k) m[i][0] = 1; else m[i][0] = 0;
        for (j = (0 > i - k ? 0 : i - k) ; j <= i - 1 ; j++)
        {
            z = 0;
            for(t = 0 ; t < 100; t++)
            {
                w = m[i][t] = m[i][t] + m[j][t] + z;
                m[i][t] = w % 10;
                z = w / 10;
            }
        }

    }
    t = 99;
    while (m[n - 1][t] == 0) t--;
    for(;t >= 0; t--) fprintf(fout, "%d", m[n - 1][t]);
    fclose(fout);
}
0
0

Мой порядок рассуждений...

  1. случай 1, считаем минимальное кол-во прыжков, вводим н и к
  2. н делим на к - получаем минимальное кол-во прижков + остаток
  3. остаток можно разбить или на единици или на 1 + часть < k, а они точно меньше будет, тут надо еще додумать...

  4. случай 2, когда заяц всю н проскачет по 1

  5. случай 3, когда заяц не будет прыгать свое к

помогайте дальше... =)

2
  • Ну так все случае не разобрать! Представьте, что ступенек 10, то случаев становится более 200!
    – AseN
    20 июн 2012 в 19:45
  • да, ты прав, вариантов тогда станет ооочень много и на бумаге их не посчитать, но мне кажется, что можно упорядочить алгоритм их появления и тогда комп посчитает... хотя бы для 10 ступенек =)
    – Gorets
    20 июн 2012 в 19:52
0
#include <fstream>
#include <iostream>

static int result = 0;
static int k;
static int n;

void tryCount(int a)
{
    if (a == n)
    {
        ++result;
        return;
    }

    for (int i = 1; i <= k; ++i)
    {
        if (a < n)
        {
            a += i;
            tryCount(a);
            a -= i;
        }
    }
}

int main()
{
    std::ifstream in("INPUT.TXT", std::ios::in);
    std::ofstream out("OUTPUT.TXT", std::ios::out);

    in >> k;
    in >> n;
    in.close();

    tryCount(0);

    out << result;
    out.close();
}

Своего рода бектрекинг. Вот только сдать этот ответ на сайте с заданием не получиться. Время на затрат рекурсии ~ 1,350 sec c данными сайта. На моей машине это время приблизительно соответствует значению k = 5, n = 20. Пробовал занести в регистр процессора int a, int i - время сократилось чуть больше чем на 30% (~ 0,95 sec), вот только эта функция отлючена в компиляторе на сервере(

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.