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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.96
tennisru
13 / 13 / 1
Регистрация: 10.09.2011
Сообщений: 179
#1

лестница - C++

23.09.2011, 20:02. Просмотров 3208. Ответов 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-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 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;
}
Байт
Эксперт C
15551 / 9893 / 1487
Регистрация: 24.12.2010
Сообщений: 18,507
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, У тебя элегантнее и, кажется, точнее.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.09.2011, 20:22     лестница #4
Байт, при n=0 не совсем верно возвращать 0, так как это означает, что при проектирования маршрута мячика мы уложились вплоть до последней ступеньки. При n<0 верно, возвращаем 0.

Добавлено через 56 секунд
Цитата Сообщение от Байт Посмотреть сообщение
Thinker, У тебя элегантнее и, кажется, точнее.
Спасибо
KuKu
1554 / 1032 / 75
Регистрация: 17.04.2009
Сообщений: 2,971
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 - это место назначения)
Байт
Эксперт C
15551 / 9893 / 1487
Регистрация: 24.12.2010
Сообщений: 18,507
23.09.2011, 20:33     лестница #6
KuKu, Если n==3, то путей уже 4
east
5 / 5 / 0
Регистрация: 23.09.2011
Сообщений: 10
23.09.2011, 20:36     лестница #7
C
1
int sk(unsigned int n)
- так лучше, KuKu
tennisru
13 / 13 / 1
Регистрация: 10.09.2011
Сообщений: 179
23.09.2011, 21:29  [ТС]     лестница #8
Thinker интересный алгоритм щас посомтрю может проверить а мой правильный?
diagon
Higher
1924 / 1190 / 49
Регистрация: 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];
}
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.09.2011, 14:19     лестница #10
Цитата Сообщение от diagon Посмотреть сообщение
Однако делать задачу на динамику через рекурсию - извращение.
diagon, эта задача настолько простая, что ее можно методом итераций сделать даже без использования каких либо массивов, это как ряд Фибоначчи вычислить. Изначально о рекурсии речь шла. Добавлю больше. Это хорошо, что вы об итерации заговорили, так как в рекурсивном методе много повторяющихся вычислений будет, то есть рекурсия не будет линейной, это не очень хорошо, даже очень плохо.
Поэтому чтобы ваш алгоритм совсем красивый был, уберите массив. Тогда да, будет оптимальный вариант.
diagon
Higher
1924 / 1190 / 49
Регистрация: 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.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2011, 14:41     лестница
Еще ссылки по теме:

Turbo Pascal Лестница
Определить сколькими различными способами можно подняться на заданную ступеньку (Лестница в Небо) C++
OpenGL GlMaterial c GL_SPECULAR проявляет артефакты (лестница)

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.09.2011, 14:41     лестница #12
diagon, никто не спорит, что с массивом нагляднее и с рекурсией плохо (стек и правда быстро переполнится, так как повторных вычислений много). Но ваш алгоритм зависит от массива, а так можно лестницу сколь угодно длинной рассматривать и длинную арифметику ввести, но это уже другой разговор.
Yandex
Объявления
24.09.2011, 14:41     лестница
Ответ Создать тему
Опции темы

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