Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Любой ЯП] мячик прыгает по лестнице 
V
    Опции темы
14SatanA88
Дата 25.7.2011, 22:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 393
Регистрация: 13.5.2010

Репутация: 1
Всего: 5
Доброго времени суток, уважаемые форумчане.

Помогите с алгоритмом решения задачи или, если есть, дайте код.

Условие
мячик прыгает по лестнице из N ступенек по не более M ступенек за раз; необходимо посчитать, сколькими способами он может спуститься без вывода самих вариантов прыжков ( O(n*m) )

Обязательно нужно соблюсти сложность алгоритма.

Это сообщение отредактировал(а) 14SatanA88 - 25.7.2011, 22:34
PM MAIL ICQ   Вверх
Silent
Дата 26.7.2011, 12:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 6
Всего: 9
Код

#include <stdio.h>

int N, M;
int a[44];

inline int max(int a, int b){ return (a > b) ? a : b; }

int main()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) a[i] = 1;
    for (int i = 1; i < N; i++)
        for (int j = max(0, i-M); j < i; j++)
            a[i] += a[j];
    printf("%d",a[N-1]);
    return 0;
}

обращаю внимание, что последовательность растет очень быстро, и 44х значений хватит лишь для M=2, N=44. Если ограничения задачи выше - используй длинную арифметику, благо тут только сложения.
PM MAIL   Вверх
14SatanA88
Дата 26.7.2011, 13:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 393
Регистрация: 13.5.2010

Репутация: 1
Всего: 5
Silent, за код спасибо.
а ты не мог бы мне алгоритм объяснить?
PM MAIL ICQ   Вверх
DeMoNN
Дата 26.7.2011, 14:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 179
Регистрация: 21.3.2008

Репутация: 1
Всего: 2
Это простая одномерная динамика. В массиве а храним число способов попасть на данную ступеньку. За первый ход мы можем попасть на каждую из М ступенек, так что заполняем первые М элементов массива единицами. А потом пробегаем циклом с первой ступеньки до последней и добавляем к каждой ступеньке, на которую мы можем попасть из текущей, число способов, которыми мы можем попасть в текущую ячейку (т.е. "переходим" на каждую ступеньку из текущей всеми возможными способами). Легко видеть, что этот алгоритм переберет все возможные способы спуститься на последнюю ступеньку.
PM MAIL ICQ   Вверх
14SatanA88
Дата 26.7.2011, 14:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 393
Регистрация: 13.5.2010

Репутация: 1
Всего: 5
DeMoNN, Silent, спасибо.
PM MAIL ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0498 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.