Форум программистов, компьютерный форум CyberForum.ru

Задача "Кузнечик" - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ std::string http://www.cyberforum.ru/cpp-beginners/thread48775.html
Господа, подскажите где можно поглядеть методы string-a литературы никакой под рукой нет, а гуглить в лоб что-то результаттов не дает. Спасибо.
C++ Несколько вопросов Здравствуйте. Возникло несколько вопросов: 1. Когда нажимаешь на определённую клавишу происходит определённое действие (типа меню)...Я на этом форуме,вроде, такое видел, но найти не удалось! http://www.cyberforum.ru/cpp-beginners/thread48771.html
C++ Помогите найти русское издание книги
Привет. Вот книга на амазоне http://www.amazon.com/dp/0596004192?tag=cpnonsqueeze-20&link_code=as3&creativeASIN=0596004192&creative=373489&camp=211189 со словами Практическое программирование на С++ облазил весь гугл - только философию Эккеля находите и Стивена Прата. Помогите найти, как эта книга у нас называется, если вообще издавалась в России.
Большая коллекция решенных задач C++
Обработка строк 1. Вывести в алфавитном порядке все буквы, которые входят в текст по одному разу 2. Является ли введенная строка палиндромом Обработка списков 1. Двойной связный список 2. Односвязные списки. Принцип работы. 3. Поместить в стек из динамического списка 4. односвязный линейный список на Си. 5. Однонаправленный список
C++ Очень простой вопрос про циклы http://www.cyberforum.ru/cpp-beginners/thread48662.html
Всем привет! Я только начал изучать с++. Меня интересует такой вопрос: Как сделать цик чтобы к переменной i добавлялась переменная i(Надеюсь понятно =)) что то на подобие for (i=1;i<40;i++){ i = i + i;
C++ Построение лабиринта на Borland С++ 3.01 Здравствуйте... Надо написать программу построения лабиринта...длина и ширина лабиринта вводится с клавиатуры. Желательно, чтобы можно было выбирать сложность лабиринта (easy,medium,hard) Он должен иметь один вход и один выход, должен иметь одно решение, т.е. от входа к выходу должен быть один путь. В лабиринте не должно быть изолированных "комнат". Любая "комната" должна соединятся с... подробнее

Показать сообщение отдельно
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
30.08.2009, 21:06     Задача "Кузнечик"
Все решается в один проход методом динамического программирования.
Прыгать будем с конца - то есть сначала с 20 клетки на 20-ую.
Потом с 19-ой на 20-ой. И так далее.
Считаем что с 20-ой на 20-ую нам требуется один прыжок.
Массив сделаем немного больше, но справа от 20 напишем нули.
Это чтобы не контролировать что прыжок перепрыгивает за 20-ую клетку

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
#include <stdio.h>
 
#define N 20
#define N0 (1+N+3)
 
int main( void ) {
 
int i, k;
int var[N0];
 
 
for ( i= 0; i<N0; i++ ) { var[i]= 0; }
 
var[N]= 1;
for ( k= N-1; k>=0; k-- ) {
    var[k]= var[k+2]+var[k+3];
}
 
printf( "index variants\n" );
for ( i= N; i>=0; i-- ) {
    printf( "%5d %5d\n", i, var[i] );
}
 
return 0;
 
} /* main() */
Вывод программы:
Код
> grig.exe
index variants
   20     1
   19     0
   18     1
   17     1
   16     1
   15     2
   14     2
   13     3
   12     4
   11     5
   10     7
    9     9
    8    12
    7    16
    6    21
    5    28
    4    37
    3    49
    2    65
    1    86
    0   114
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru