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

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

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

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

23.09.2011, 20:02. Просмотров 3309. Ответов 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-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.09.2011, 20:02     лестница
Посмотрите здесь:

Платная лестница - C++
Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать...

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

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

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

Лестница - Turbo Pascal
Человек поднимается по лестнице один марш которых содержит N ступенек. За один шаг человек может подняться на 1 или 2, или на 3 ... или на...

лестница у воды
Рядом с берегом стоит корабль со спущенной на воду стальной лестницей. У лестницы 10 ступенек. Расстояние между ступеньками 30 см. Самая...

Олимпиадная задача. Лестница из кубиков. - Pascal
1) Мальчик Петя строит из кубиков лестницу. Лестница представляет собой несколько стоящихся рядом башенок из кубиков, каждая из которых...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
4225 / 2199 / 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
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
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++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.09.2011, 20:22     лестница #4
Байт, при n=0 не совсем верно возвращать 0, так как это означает, что при проектирования маршрута мячика мы уложились вплоть до последней ступеньки. При n<0 верно, возвращаем 0.

Добавлено через 56 секунд
Цитата Сообщение от Байт Посмотреть сообщение
Thinker, У тебя элегантнее и, кажется, точнее.
Спасибо
KuKu
1557 / 1035 / 77
Регистрация: 17.04.2009
Сообщений: 2,980
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
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
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
1928 / 1194 / 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++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.09.2011, 14:19     лестница #10
Цитата Сообщение от diagon Посмотреть сообщение
Однако делать задачу на динамику через рекурсию - извращение.
diagon, эта задача настолько простая, что ее можно методом итераций сделать даже без использования каких либо массивов, это как ряд Фибоначчи вычислить. Изначально о рекурсии речь шла. Добавлю больше. Это хорошо, что вы об итерации заговорили, так как в рекурсивном методе много повторяющихся вычислений будет, то есть рекурсия не будет линейной, это не очень хорошо, даже очень плохо.
Поэтому чтобы ваш алгоритм совсем красивый был, уберите массив. Тогда да, будет оптимальный вариант.
diagon
Higher
1928 / 1194 / 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     лестница
Еще ссылки по теме:

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

Вывести на экран таблицу "Лестница нулей" - Pascal ABC
Написать программу, выдающую на экран таблицу «Лестница нулей» 0123456789 0012345678 0001234567 0000123456 0000012345 ...

Решение задачи "Лестница Фараона" - C#
Есть всем известная задача &quot;Лестница Фараона&quot;, стало интересно ее реализовать, но не тут-то было, я столкнулся с одной проблемой. Основное...

Visual Basic . "Лестница!" - Visual Basic
Ребята.Нужна ваша помощь в решении задачи. Есть лестница,состоящая из N ступенек. Нужно подняться с первой на последнюю ступеньку. Но...


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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
4225 / 2199 / 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