Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/24: Рейтинг темы: голосов - 24, средняя оценка - 5.00
tennisru
13 / 13 / 2
Регистрация: 10.09.2011
Сообщений: 179
1

лестница

23.09.2011, 20:02. Просмотров 4377. Ответов 11
Метки нет (Все метки)

C++
1
2
3
4
5
6
7
8
9
int phi(int n)
{int a[100];
a[1]=1;
a[2]=2;
if (n==1) return a[n];
else
a[n]=phi(a[n-1]+n-1);
 
}
как правльно выти из этой рекурсии? алгоритм вроде правильно сделал.

вот задача если кому надо
На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.09.2011, 20:02
Ответы с готовыми решениями:

Платная лестница
Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно...

Неправильная лестница на с++
Нужно сделать лестницу из n-ых элементов чтобы она выгледила вот так : 5 4 5...

Определить сколькими различными способами можно подняться на заданную ступеньку (Лестница в Небо)
Определить сколькими различными способами можно подняться на десятую ступеньку,...

Лестница
Дано натуральное число n.Человек должен подняться по лестнице,имеющей n...

Лестница
Человек поднимается по лестнице один марш которых содержит N ступенек. За один...

11
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.09.2011, 20:12 2
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
 
int Count(int n)
{
   if (n > 0)
      return  Count(n - 1) + Count(n - 2) + Count(n-3);
   else if (n == 0)
      return 1;
   else return 0;
}
 
int main()
{
   printf("%d\n", Count(10));
   getchar();
   return 0;
}
1
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
23.09.2011, 20:20 3
Не очень то понял, что делает твой код, но я бы сделал так
C
1
2
3
4
5
6
7
8
9
10
int sk(int n)
{
  if (n<=0) return(0);
  if (n==1) return(1);
   return sk(n-1) + sk(n-2) + sk(n-3);
}
main()
{
  Marshruts = sk(100);
}
Кажется, так.

Добавлено через 5 минут
Thinker, У тебя элегантнее и, кажется, точнее.
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.09.2011, 20:22 4
Байт, при n=0 не совсем верно возвращать 0, так как это означает, что при проектирования маршрута мячика мы уложились вплоть до последней ступеньки. При n<0 верно, возвращаем 0.

Добавлено через 56 секунд
Цитата Сообщение от Байт Посмотреть сообщение
Thinker, У тебя элегантнее и, кажется, точнее.
Спасибо
1
KuKu
1559 / 1037 / 93
Регистрация: 17.04.2009
Сообщений: 2,995
23.09.2011, 20:26 5
Чет я тоже ничего не понял, но даю уже 4ий результат:
C
1
2
3
4
5
int sk(int n)
{
  if (n<=3) return(n);
  return sk(n-1) + sk(n-2) + sk(n-3);
}
0 - это место назначения)
0
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
23.09.2011, 20:33 6
KuKu, Если n==3, то путей уже 4
0
east
5 / 5 / 0
Регистрация: 23.09.2011
Сообщений: 10
23.09.2011, 20:36 7
C
1
int sk(unsigned int n)
- так лучше, KuKu
0
tennisru
13 / 13 / 2
Регистрация: 10.09.2011
Сообщений: 179
23.09.2011, 21:29  [ТС] 8
Thinker интересный алгоритм щас посомтрю может проверить а мой правильный?
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.09.2011, 11:57 9
Однако делать задачу на динамику через рекурсию - извращение. У меня код из #4 уже при n = 30 больше секунды работает. А ведь можно не париться с рекурсией и написать простенькую динамику за O(n).
Так я решал эту задачу:
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <fstream>
 
long long a[73] = {1, 2, 4}, n, i = 2;
 
int main(){
    std::fstream v("input.txt"), o("output.txt", std::ios::out);
    
    for (v >> n; ++i < n; )
        a[i] = a[i - 3] + a[i - 2] + a[i - 1];
    
    o << a[n - 1];
}
1
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.09.2011, 14:19 10
Цитата Сообщение от diagon Посмотреть сообщение
Однако делать задачу на динамику через рекурсию - извращение.
diagon, эта задача настолько простая, что ее можно методом итераций сделать даже без использования каких либо массивов, это как ряд Фибоначчи вычислить. Изначально о рекурсии речь шла. Добавлю больше. Это хорошо, что вы об итерации заговорили, так как в рекурсивном методе много повторяющихся вычислений будет, то есть рекурсия не будет линейной, это не очень хорошо, даже очень плохо.
Поэтому чтобы ваш алгоритм совсем красивый был, уберите массив. Тогда да, будет оптимальный вариант.
2
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.09.2011, 14:33 11
Цитата Сообщение от Thinker Посмотреть сообщение
Поэтому чтобы ваш алгоритм совсем красивый был, уберите массив. Тогда да, будет оптимальный вариант.
Да ну.. Что там красивого. 70 интов - не так уж и много. А если убрать массив, то код менее понятен станет. Сейчас же сразу видно - для вычисления текущего шага суммируются значения 3х предыдущих.
А вообще более оптимальная реализация - циклом суммировать все элементы c i - k до i, в данном случае k = 3. Просто есть аналогичная , частным случаем которой является задача из первого поста. Таким образом задача сводиться к уже решенной... =)

Цитата Сообщение от Thinker Посмотреть сообщение
олько простая, что ее можно методом итераций сделать даже без использования каких либо массивов, это как ряд Фибоначчи вычислить. Изначально о рекурсии речь шла. Добавлю больше. Это хорошо, что вы об итерации заговорили, так как в рекурсивном методе много повторяющихся вычислений будет, то есть рекурсия не будет линейной, это не очень хорошо, даже очень плохо.
Это не просто очень плохо. Эта задача нерешаема рекурсией в принципе. Для большого n(от 50) не только будет крайне долго считаться, но и программа рано или поздно закрашится из-за stack overflow.
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.09.2011, 14:41 12
diagon, никто не спорит, что с массивом нагляднее и с рекурсией плохо (стек и правда быстро переполнится, так как повторных вычислений много). Но ваш алгоритм зависит от массива, а так можно лестницу сколь угодно длинной рассматривать и длинную арифметику ввести, но это уже другой разговор.
0
24.09.2011, 14:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2011, 14:41

Криволинейная лестница
Помогите, пожалуйста, понять, как можно переделать вот эту винтовую лестницу на...

Олимпиадная задача. Лестница из кубиков.
1) Мальчик Петя строит из кубиков лестницу. Лестница представляет собой...

GlMaterial c GL_SPECULAR проявляет артефакты (лестница)
OpenGL 1.2 самый обычный, без шейдеров и всяких там расширений. Нарисовал эскиз...


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

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

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