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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.94
xADMIRALx
67 / 61 / 1
Регистрация: 09.06.2012
Сообщений: 291
#1

Рекурсия не могу понять - C++

29.06.2012, 14:10. Просмотров 3996. Ответов 26
Метки нет (Все метки)

Здравствуйте программисты,помнится давно давно изучал с++,и тут по новой начал читать книгу и дело дошло до факториала,есть способ через циклы и через рекурсию.Так вот : метод возвращает всё как положено,но вот только я не могу понять как?Как она это делает?так как в конце у нас return 1 почему когда я вывожу в cout у меня 2 6 24 120.Разъесните пожалуйста что как и где происходит,а то блин я чуть монитор уже не выкинул в окно...
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
27
28
29
30
31
32
#include <iostream>
#include <locale>
#include <stdlib>
 
 
using namespace std;
 
int factr(int n);
int main()
{
    setlocale(LC_ALL,".1251");
 
    cout << "Факториал числа 5 : " << factr(5)<< endl;
 
 
 
 
 
 
 
    system("PAUSE");
    return 0;
}
int factr(int n)//5
{
    int answer = 0;
 
    if (n == 1) return 1;
    cout << (answer = factr(n - 1) * n) << endl;
    return answer;
 
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2012, 14:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия не могу понять (C++):

Стек на основе массива структур - эт как понять читаю литературу и не могу понять! - C++
Стек статически (на основе массива структур). Пример структура &quot;Товар&quot; которая включает в себя: № по каталогу(ключ), Название, цена, срок...

Не могу сделать полиморфизм. Не могу до конца понять пример по этому поводу - C++
Есть такая задача: Класс Animal должен быть абстрактным, имеет имя и вес. Класс Reptile имеет habitate, который держит в себе среду...

не могу понять - C++
как сделать так чтобы B двигался по массиву? #include&lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int main() { int...

не могу понять - C++
есть такой код void addElement(const T&amp; elem){ *(_pointer) = elem; // int t1 = _pointer &lt; &amp;_deque_data; // int t2 =...

Не могу понять ошибку - C++
#include&lt;iostream.h&gt; #include&lt;math.h&gt; #include&lt;conio.h&gt; #include&lt;stdio.h&gt; int main() { double x=3.741, y=-0.825,z=0.160, A,...

Не могу понять, почему? - C++
Доброго времени суток=) Такая печаль. Создается класс Окружность с полями радиус, площадь и длина окружности. Нужно создать функции...

26
Catstail
Модератор
22735 / 11104 / 1797
Регистрация: 12.02.2012
Сообщений: 18,300
01.07.2012, 09:12 #16
Посмотри презентацию, которую я использовал на своих лекциях. Может, легче станет:
0
Вложения
Тип файла: zip lec-05.zip (239.3 Кб, 17 просмотров)
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.07.2012, 09:36 #17
Цитата Сообщение от SeryZone Посмотреть сообщение
Я отправил задачу на тестирование. Сайт - e-olimp.com. Там эта функция показала лучшие результаты! Хотя заранее я отправлял другие коды вычисления факториала.
И что? А сам то пробовал тестировать? На том кривосайте видимо вообще не было годных факториалов. А лучший вот:
C++
1
2
3
4
5
6
7
8
9
unsigned __int64 factorial(uint8_t n)
{
 unsigned __int64 Result=1;
 for (; n>0; --n)
 {
  Result*=n;
 }
 return Result;
}
. Кстати, декремент лучше вычитания. А лучший декремент - префиксный. Вот это действительно быстрейший факториал. А твой - эталон тормознутости. И при тестах факториала разрешение часов, или таймера не достаточно, надо сравнивать только по счётчику тактов, так как аргумент всегда мал и даже рекурсивная функция гарантировано уложится во временное разрешение остальных измерялок. А если увеличивать аргумент, то наткнёшься на переполнение типа и ни каких гвоздёв.
0
Catstail
Модератор
22735 / 11104 / 1797
Регистрация: 12.02.2012
Сообщений: 18,300
01.07.2012, 09:49 #18
Цитата Сообщение от taras atavin Посмотреть сообщение
так как аргумент всегда мал
Чем "ловить блох", попробуйте, например, вычислить 200! Могу заранее подсказать ответ:

788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830 257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242 407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000 000000000000000

А чтобы замерить производительность короткого кода, погрузите его в цикл и выполните 10000 раз (или более). Так можно и два алгоритма сравнить (только цикл должен быть организован одинаково)...
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.07.2012, 09:58 #19
Цитата Сообщение от Catstail Посмотреть сообщение
Чем "ловить блох", попробуйте, например, вычислить 200!
Про переполнение пропустил? А функции с поддержкой длинной арифметики медленны по определению, даже когда эти тормоза оправданы.
0
Catstail
Модератор
22735 / 11104 / 1797
Регистрация: 12.02.2012
Сообщений: 18,300
01.07.2012, 10:13 #20
Не пропустил, просто пошутил...

Для чего могут понадобиться факториалы чисел в диапазоне до 15-20? Биномиальные коэфф-ты, спецфункции и т.д. Но в нормальных программах массив факториалов вычисляют один раз, а потом нужный факториал просто берут из соотв. ячейки (обращаясь по индексу), что всяко быстрее, чем вычислять его заново...

"Театр начинается с вешалки... но будущее все равно за кинематографом" В. Пелевин.
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.07.2012, 10:25 #21
Я разве где то утверждал актуальность гонки на факториале? Но и один раз можно сделать быстрее, или медленнее. Время загрузки и инициализации - тоже фактор "быстрости".
0
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
01.07.2012, 18:12 #22
Слабаки! Я вычислял при помощи кода 20000! Код мощный и быстрый.
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.07.2012, 18:16 #23
В сравнении с чем? Если сравнивать оптимизированным вариантом только для стандартных типов, то он у тебя факториал десяти будет считать дольше, чем в моём варианте считается факториал восемнадцати.
0
Catstail
Модератор
22735 / 11104 / 1797
Регистрация: 12.02.2012
Сообщений: 18,300
01.07.2012, 21:39 #24
SeryZone: покажи код!
0
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
01.07.2012, 22:40 #25
Вот, смотри! Увеличишь количество элементов массива, будет считать и выше 20000!
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
27
28
29
30
31
32
33
34
35
36
#include<stdio.h>
 
int main()
 {
  int a[2000]={0}, i, j, n, fl=0, max=0;
  scanf("%d", &n);
  a[0]=1;
  for(i=2; i<=n; i++)
  {
      for(j=0; j<=max; j++)
          a[j]*=i;
      for(j=0; j<max; j++)
          if(a[j]>99999)
          {
              a[j+1]+=a[j]/100000;
              a[j]%=100000;
          }
      if(a[max]>99999)
      {
              a[max+1]+=a[max]/100000;
              a[max++]%=100000;
      }
  }
  for(i=1999; i>=0; i--)
  {
      if(fl==1)
          printf("%05d", a[i]);
      if(a[i]>0 && fl==0)
      {
          printf("%d", a[i]);
          fl=1;
      }
  }
  printf("\n");
return 0;
 }
Можешь и сам код усовершенствовать!
1
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
02.07.2012, 15:39 #26
SeryZone, всякая оптимизация бывает только в рамках цели и при определённом комплексе ограничений. Быстрейшая функция работает в короткой арифметике, в длинной всё закономерно медленнее. Не обязательно хуже, если нужна такая длина, то короткотипные функции вообще выпадают по ограничениям. Но медленно. Потому что или жертвуем скоростью ради размера данных, или наоборот.
0
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
05.07.2012, 23:30 #27
Ну, этот код явно не для коротких чисел!
0
05.07.2012, 23:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.07.2012, 23:30
Привет! Вот еще темы с ответами:

Цикл do while не могу понять, - C++
программу которая принимает число N и выводит на экран N звездочек, использовать цикл do while

Указатели не могу понять - C++
Все вопросы указал в комментариях к коду. Не могу понять почему так #include &lt;iostream&gt; using namespace std; int main() { int...

не могу понять ошибку - C++
Народ, здарова, сижу над классами, конкретно наследование классов! Компилятор выдает ошибку: Unit1.cpp(143): E2285 Could not find a...

не могу понять ошыбки - C++
привет всем. помогите вычислить ошыбку, вроде маленькая но я все же хочу узнать какая проблема в этой проге. #include &quot;StdAfx.h&quot;...


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

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

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