Вход | Регистрация
 
Информационные технологии :: Математика и алгоритмы

Рекурсия. Как подсчитать следующую сумму без цикла?

Рекурсия. Как подсчитать следующую сумму без цикла?
Я
   GANR
 
17.12.20 - 14:28
Как подсчитать следующую сумму без цикла?

a +
a * (a+1) +
a * (a+1) * (a+2) +
a * (a+1) * (a+2) * (a+3) +

...

a * (a+1) * (a+2) * (a+3) * ... * (a+n)

Факториал то легко. А вот такое?
   GANR
 
1 - 17.12.20 - 14:28
даны a, n
   Ненавижу 1С
 
2 - 17.12.20 - 14:30
чем от факториала принципиально отличается?
   GANR
 
3 - 17.12.20 - 14:33
(2) Так тут сумма же ещё вдобавок. В факториале то всё просто f(n) = n * f(n-1), f(1) = 1.
   ДенисЧ
 
4 - 17.12.20 - 14:35
g(a, n) = n * g(a, n-1), f(a, 1) = a.

Так?
   H A D G E H O G s
 
5 - 17.12.20 - 14:35
Ну в цикле и считай
   GANR
 
6 - 17.12.20 - 14:39
(4) сомневаюсь, проверю позже сверив с результатом который даст цикл
(5) так без цикла хочу
   Вафель
 
7 - 17.12.20 - 14:41
а как факториал без цикла посчитать?
   GANR
 
8 - 17.12.20 - 14:41
(7) рекурсией
   Garykom
 
9 - 17.12.20 - 14:42
(0) =n!-a!
   Garykom
 
10 - 17.12.20 - 14:42
(9) или +
   del123
 
11 - 17.12.20 - 14:43
функция Фн(Зн, тек, Макс)
    Если Тек = Макс тогда
        возврат Зн + макс;
    иначе
        возврат (Зн + тек) * Фн(Зн, тек + 1, Макс);
    КонецЕсли;
КонецФункции
   cViper
 
12 - 17.12.20 - 14:43
(0) Гугли Dynamic Programming. Там найдешь ответ на то как это сделать оптимально.
   del123
 
13 - 17.12.20 - 14:43
Рез = Фн(а,0,н);
   Garykom
 
14 - 17.12.20 - 14:44
(10) хотя не, точно -

a+1, a+2,...,a+n
это же смещенный от 1 на a факториал
=(a+n)!-a!
   Ёпрст
 
15 - 17.12.20 - 14:44
(8) ты не поверишь..но рекурсия это тоже цикл
   del123
 
16 - 17.12.20 - 14:45
а, их еще сложить надо
   del123
 
17 - 17.12.20 - 14:52
Рез = ФнС(а,н,н);

Функция ФнС(Зн, ТекС, Макс)
    Если ТекС = 0 тогда
        возврат Зн;
    иначе
        возврат ФнП(Зн, 0, ТекС) + ФнС(Зн, ТекС-1, Макс);
    КонецЕсли;
КонецФункции

функция ФнП(Зн, текП, Макс)
    Если ТекП = Макс тогда
        возврат Зн + макс;
    иначе
        возврат (Зн + текП) * ФнП(Зн, текП + 1, Макс);
    КонецЕсли;
КонецФункции
   МихаилМ
 
18 - 17.12.20 - 14:54
   GANR
 
19 - 17.12.20 - 14:58
(15) верю, неявный цикл. правильнее сказать без использования операторов цикла
   cViper
 
20 - 17.12.20 - 15:04
public int calculate(int a, int n) {
if(a < 0) {
return 1;
}
return (a + n) * calculate(a + (n - 1))
}
   Дегенератор идей
 
21 - 17.12.20 - 15:04
функция ф(а,н)
если н=0
возврат а
иначе
  возврат а*н+ф(а,н-1)
конец
   RomanYS
 
22 - 17.12.20 - 15:29
Что-то все одной функцией пытаются решить и похоже неправильно. По идее если делать две функции, то задача становится элементарной.
   Garykom
 
23 - 17.12.20 - 15:34
(22) дык нужна только функция факториала в формуле "(a+n)!-a!"
   RomanYS
 
24 - 17.12.20 - 15:41
(23) Так явно кривая формула. Вычисли (0.5)!
   Garykom
 
25 - 17.12.20 - 15:44
   RomanYS
 
26 - 17.12.20 - 15:48
(25) Красота! Просто вычисли рекурсией (24)
   RomanYS
 
27 - 17.12.20 - 15:50
(23) да любые значения подставь, хотя бы (1,1)
   del123
 
28 - 17.12.20 - 15:51
в 17 рабочий вариант)
   Ёпрст
 
29 - 17.12.20 - 15:58
(24) факториал определен только на множестве целый неотрицательных числах
   RomanYS
 
30 - 17.12.20 - 16:00
(28) может быть. Только "+1" в последней формуле скорее всего ошибка, вероятно правильнее "-1"
 
 Рекламное место пустует
   RomanYS
 
31 - 17.12.20 - 16:02
(29) я в курсе), а вот (0) вполне определена на всех действительных и даже комплексных чисел.
   Малыш Джон
 
32 - 17.12.20 - 16:20
OMG... Почему минус-то? это ж факториал

A*(A+1)*(A+2)*...*(A+N) = (A+N)!/(A-1)!
   RomanYS
 
33 - 17.12.20 - 16:37
(32) ага, только придётся расширить понятие факториала на все действительные числа
   Classic
 
34 - 17.12.20 - 16:53
Функция СуммаФакториалов(А, N, Факториал = 1)
     Если N = 0 Тогда
         Факториал = A;
         Возврат A;
     Конец;
     ПредФакториал = 1;
     ПредШаг = СуммаФакториалов(A, N - 1, ПредФакториал);
     Факториал = ПредФакториал * (A + N);
     Возврат ПредШаг + Факториал
КонецФункции
   fisher
 
35 - 17.12.20 - 17:25
Функция Ряд(a, N, Знач НомерЭлементаРяда = 0, Знач ПредыдущийЭлементРяда = 1)
    
    НомерЭлементаРяда = НомерЭлементаРяда + 1;
    Если НомерЭлементаРяда > N Тогда
        Возврат 0;
    КонецЕсли;
    
    ТекущийЭлементРяда = ПредыдущийЭлементРяда * (a + НомерЭлементаРяда - 1);
    
    Возврат ТекущийЭлементРяда + Ряд(a, N, НомерЭлементаРяда, ТекущийЭлементРяда);
    
КонецФункции
   cViper
 
36 - 17.12.20 - 17:33
Опечатался в (20)

public int calculate(int a, int n) {
   if(n < 0) {
      return 1;
   }
   return (a + n) * calculate(a + (n - 1))
}
   Йохохо
 
37 - 17.12.20 - 17:38
(33) это школа ты чего
   Йохохо
 
38 - 17.12.20 - 17:38
10й класс
   RomanYS
 
39 - 17.12.20 - 17:41
(38) ответь на (24) и алгоритм его вычисления рекурсиво
   fisher
 
40 - 17.12.20 - 17:43
Так на строчку короче:
Функция Ряд(a, N, Знач НомерЭлементаРяда = 1, Знач ПредыдущийЭлементРяда = 1)
    
    Если НомерЭлементаРяда > N Тогда
        Возврат 0;
    КонецЕсли;
    
    ТекущийЭлементРяда = ПредыдущийЭлементРяда * (a + НомерЭлементаРяда - 1);
    
    Возврат ТекущийЭлементРяда + Ряд(a, N, НомерЭлементаРяда + 1, ТекущийЭлементРяда);
    
КонецФункции
   Classic
 
41 - 17.12.20 - 17:44
(40)

Сообщить(Ряд(1, 0))
   fisher
 
42 - 17.12.20 - 17:46
(41) 0. Ведь при N=1 должно быть а. Не?
   Classic
 
43 - 17.12.20 - 17:47
(42) Нет
   Classic
 
44 - 17.12.20 - 17:47
При N=1 должно быть A + A * (A + 1)
   fisher
 
45 - 17.12.20 - 17:52
(44) Эта чой-та? И как тогда получить первый элемент ряда? Это же формула ряда?
   Доктор Манхэттен
 
46 - 17.12.20 - 17:53
(0) Если факториал тебе легко посчитать, то считай через факториал, вот так: n! / a!
   Classic
 
47 - 17.12.20 - 17:55
(45)
Посмотри последнюю строку в (0)

a * (a+1) * (a+2) * (a+3) * ... * (a+n)


Здесь же очевидно, что при n = 1 будет a*(a+1)
   Classic
 
48 - 17.12.20 - 17:55
Точнее a+a*(a+1)
   Доктор Манхэттен
 
49 - 17.12.20 - 17:55
(46) А, не заметил что там еще сумма этого всего. Тогда не пойдет. Думайте сами
   fisher
 
50 - 17.12.20 - 17:59
(47) Да ради бога.
Тогда так :)
Функция Ряд(a, N, Знач НомерЭлементаРяда = 1, Знач ПредыдущийЭлементРяда = 1)
    
    Если НомерЭлементаРяда > N + 1 Тогда
        Возврат 0;
    КонецЕсли;
    
    ТекущийЭлементРяда = ПредыдущийЭлементРяда * (a + НомерЭлементаРяда - 1);
    
    Возврат ТекущийЭлементРяда + Ряд(a, N, НомерЭлементаРяда + 1, ТекущийЭлементРяда);
    
КонецФункции
   cViper
 
51 - 17.12.20 - 18:06
(0)А зачем тебе вообще считать это без цикла через рекурсию? Оно ведь памяти больше ест так.
   педальный трактор
 
52 - 17.12.20 - 19:03
Для n! есть формула Стирлинга. Для твоего цикла по идее можно сделать аналог этой формулы.
   Конструктор1С
 
53 - 17.12.20 - 19:59
(0) дурной тон использовать рекурсию там, где можно использовать простой цикл
   RomanYS
 
54 - 17.12.20 - 20:00
(53) задачка явно не прикладная
   G-Re
 
55 - 17.12.20 - 20:10
(52) Стирлинг это приближение к n! :))
   ДедМорроз
 
56 - 17.12.20 - 20:58
Сумма(А,Н)=А*(1+Сумма(А+1,Н-1))
Сумма(Х,0)=Х
Как бы рекурсия.
   RomanYS
 
57 - 17.12.20 - 21:08
(56) Красава! Всё-таки есть решение с одной функцией.
   Salimbek
 
58 - 17.12.20 - 23:00
(49) Да без проблем
a!/(a-1)!+(a+1)!/(a-1)!+... = [a!+(a+1)!+(a+2)!+...]/(a-1)!
   GANR
 
59 - 18.12.20 - 14:55
(58) Компьютер дриснет)
   НЕА123
 
60 - 18.12.20 - 15:17
функция добавить(Эн,Нечто="а")
    Если Зн <=0  ТОгда
    возврат Нечто;
Иначе
Эн=Эн-1;
Нечто = Нечто+ "+" +Нечто+ "*(а+"+Формат(Эн) +")";
      возврат добавить(Нечто,Эн);
КонецЕсли;
конецфункции
ЗЫ при вызове второй параметр не указывать
 
 Рекламное место пустует
   GANR
 
61 - 19.12.20 - 00:17
(56) Реально красавец, четко 1 в 1 результат с моим циклом совпадает.
   fisher
 
62 - 20.12.20 - 15:25
(56) У меня при Н=2 фигня какая-то получается.
   DrHiHi
 
63 - 27.12.20 - 15:18
еще можно попробовать асинхронно, но на сколько это практично, то хз
   Конструктор1С
 
64 - 27.12.20 - 19:24
(54) но учит плохому
   RomanYS
 
65 - 27.12.20 - 20:06
Ничего плохого в периодическом напряжении мозга не вижу. Просто не рассматривай (0) как задачу по 1С или промышленному программированию, просто математика.


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.