Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 03.06.2021
Сообщений: 9

Почему здесь лучше использовать рекуррентную последовательность, а не массив?

09.06.2022, 09:10. Показов 651. Ответов 15

Студворк — интернет-сервис помощи студентам
Всем привет, дана задача в которой нужно найти сумму при помощи рекуррентной последовательности. Запрещено пользоваться массивом


Почему в этом задании можно не пользоваться массивом? Чем было бы плохо использование массива в данном случае?


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
 
double Sum(int n, double r1, double r2, double r3)
{
    double r4 = (1.2 * sin(r3 + r2) + 0.8 * r1) / (1 - cos(r3)) - int(0.55 * r2);
    if (n == 0)
        return 0;
    else if (n == 1)
        return r1;
    else if (n == 2)
        return r1 + r2;
    else if (n == 3)
        return r1 + r2 + r3;
    else
        return r1 + Sum(n - 1, r2, r3, r4);
}
 
int main()
{
    cout << "Sum = " << Sum(1000, 1.23, 0.65, -0.25) << endl;
    return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
09.06.2022, 09:10
Ответы с готовыми решениями:

Как лучше залить текстуру в массив? Какой формат текстуры лучше использовать?
Как лучше залить текстуру в массив? Какой формат текстуры лучше использовать?

Что лучше использовать и почему???
Добрый день всем! Занимаюсь парсингом html-странички, точнее нахожу все ссылки &quot;&lt;a href&gt;&quot;. Есть 2 варианта- при помощи...

Какой сборщик лучше использовать и почему ?
Доброго времени суток. Интересует такой вопрос. Есть сборщики для javascrip: WebPack, gulp, docker, angularCLI. Вопрос в следующем:...

15
736 / 702 / 110
Регистрация: 29.05.2015
Сообщений: 4,293
09.06.2022, 09:49
Ничем. Массив даже лучше, т.к. экономит ресурсы (память) компьютера. Только голову иногда приходится поломать, как заменить рекурсию массивом.
1
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
09.06.2022, 10:05
пройти 4 круга адаветвления что бы пройти к след шагу рекурсии, это мощно ...
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
09.06.2022, 11:32
Добавьте в функцию еще один аргумент, чтобы return r1 + Sum(n - 1, r2, r3, r4) можно было заменить на return Sum(n - 1, r2, r3, r4,r1) (при первом вызове дополнительный аргумент=0). После этого вы получите хвостовую рекурсию. Хвостовая рекурсия в свою очередь заменяется циклом. Либо ручками, либо силами компилятора. Итого, массив не нужен.
0
0 / 0 / 0
Регистрация: 03.06.2021
Сообщений: 9
09.06.2022, 11:47  [ТС]
Да, но дело в том, что я не понимаю как можно было массив использовать и чем он плох, потому что в источниках информации пишут что рекурсия много памяти занимает, отдельные функции создает, а якобы массив занимает меньше памяти
Не понимаю почему в этой задаче не эффективно использовать массив....
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
09.06.2022, 16:47
Рекурсия создает стек-фреймы. Грубо говоря, у нее под капотом тот же самый массив, только она в него пихает все свои переменные разом (r1, r2, r3...) и немного технической информации сверху. Так что да, решение на массивах может быть рациональнее в плане расхода ресурсов. Стоит ли овчинка выделки это уже другой вопрос, надо смотреть сколько ресурсов уходит на, собственно, функцию и сколько на техническую информацию. Экономить 1% ресурсов в ущерб читаемости кода - так себе затея. Плюс, размер своего массива вы знаете, а вот сколько памяти выделено под стек - нет. Поэтому, когда место в стеке кончается, оно кончается внезапно и программа обычно просто грохается. Но если у вас не идет речи о тысячах вложенных вызовов или создания крупных массивов внутри функции, вас эта проблема скорее всего не коснется.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
13200 / 6835 / 1822
Регистрация: 18.10.2014
Сообщений: 17,293
09.06.2022, 18:42
Цитата Сообщение от katekfkspfr Посмотреть сообщение
Почему в этом задании можно не пользоваться массивом? Чем было бы плохо использование массива в данном случае?
Что значит "можно" или "плохо"? Это просто такое студенческое задание. Никакого отношения ни к "можно" или "плохо" постановка задания не имеет.

Для вычисления суммы такой последовательности не нужно ни массива (если не считать массивом набор переменных r), ни рекурсии. Она прекрасно вычисляется обычным циклом.
1
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
16.08.2022, 10:18
Рекурсия может быть полезна для compiletime eval)
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
37
38
39
40
41
42
43
44
45
46
47
 #include <iostream>
  #include <cmath>
 
 constexpr
 double
Sum(int n, double r1, double r2, double r3)
{
    return
    0 == n ?  0 :
        1 == n ? r1 :
            2 == n ? r1 + r2 :
                3 == n ? r1 + r2 + r3 :
    r1+Sum(
           n-1,
           r2,
           r3,
 
           (1.2 * sin(r3 + r2) + 0.8 * r1) / (1 - cos(r3)) - int(0.55 * r2)
             );
}
 
constexpr double
 s0=Sum(0, 1, 2, 3)
,s1=Sum(1, 1, 2, 3)
,s2=Sum(2, 1, 2, 3)
,s3=Sum(3, 1, 2, 3)
,s4=Sum(4, 1, 2, 3)
;
 
int main()
{
    std::cout<<"compiltime results are:\n"<<
           s0<<'\n'<<
            s1<<'\n'<<
             s2<<'\n'<<
              s3<<'\n'<<
               s4<<"\n\n"
               ;
 
    double r1 =1, r2=2, r3=3, result[5]={0} ;
    for(int n=0 ; n<5 ; ++n)
    result[n]=Sum(n, r1, r2, r3);
 
    for(int n=0 ; n<5 ; ++n)
        std::cout<<result[n]<<'\n';
return 0;
}
0
Неэпический
 Аватар для Croessmah
18149 / 10731 / 2067
Регистрация: 27.09.2012
Сообщений: 27,035
Записей в блоге: 1
16.08.2022, 10:24
Цитата Сообщение от IGPIGP Посмотреть сообщение
constexpr
sin и cos тоже constexpr?
1
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
16.08.2022, 10:28
Цитата Сообщение от Croessmah Посмотреть сообщение
sin и cos тоже constexpr?
Не подумал) В принципе это от компилятора может зависеть. Не думаю, что в библиотеке cmath есть нетривиальные типы для тригонометрии. Если там есть определения constexpr то должно работать, по идее)
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
16.08.2022, 10:28
Цитата Сообщение от IGPIGP Посмотреть сообщение
Рекурсия может быть полезна для compiletime eval)
Давно не актуально - с четырнадцатого стандарта можно ставить в constexpr функцию циклы и не извращаться.
1
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
16.08.2022, 10:32

Не по теме:

Renji, а у нас на роботе до сих пор 11. И фирма известная. По слухам ближайшие лет 5 ни чего не изменится


Renji, есть ряд прёмов в метапрограммировании где без рекурсии ни как. Это может полезно знать даже новичку)
0
Неэпический
 Аватар для Croessmah
18149 / 10731 / 2067
Регистрация: 27.09.2012
Сообщений: 27,035
Записей в блоге: 1
16.08.2022, 10:36
Цитата Сообщение от IGPIGP Посмотреть сообщение
Не подумал) В принципе это от компилятора может зависеть. Не думаю, что в библиотеке cmath есть нетривиальные типы для тригонометрии. Если там есть определения constexpr то должно работать, по идее)
Они не constexpr. Я так понимаю, вы собирали с помощью gcc.
gcc заменяет вызов этих функции на __builtin_*. Вы можете добавить ключ -fno-builtin и он перестанет это делать.

Добавлено через 53 секунды
https://godbolt.org/z/E8rhKx4hr
1
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
16.08.2022, 10:52
Цитата Сообщение от Croessmah Посмотреть сообщение
Я так понимаю, вы собирали с помощью gcc.
так и есть. То что
Цитата Сообщение от Croessmah Посмотреть сообщение
gcc заменяет вызов этих функции на __builtin_*
довольно мудро. Глупо писать нужные константы вручную. Или вычислять синусы pi/4 или других, менее удобных аргументов в рантайме. Однако, спасибо. Выходит, что в настоящее время этот код непереносим. Ну что же. Это тоже полезно знать)
0
631 / 526 / 104
Регистрация: 05.08.2022
Сообщений: 2,810
16.08.2022, 12:26
Цитата Сообщение от katekfkspfr Посмотреть сообщение
Почему в этом задании можно не пользоваться массивом? Чем было бы плохо использование массива в данном случае?
Это же учебная задача?
Учат применять определённые методы.

Добавлено через 2 минуты
Цитата Сообщение от katekfkspfr Посмотреть сообщение
Да, но дело в том, что я не понимаю как можно было массив использовать
Видимо имеется ввиду

double arr[1000];
заполняем элементы arr[] случайными значениями
суммируем элементы массива
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,536
Записей в блоге: 1
16.08.2022, 14:58
Народ, не забывайте также, что вычисление рядов по принципу https://www.cyberforum.ru/cgi-bin/latex.cgi?{a}_{i+1} = {a}_{i} * \delta (т.е. через предыдущий член)
Тоже называется рекуррентным вычислением ряда. И в школах часто дают задания "вычислить рекуррентно", имея в виду именно это вычисление, а не применение рекурсивных функций в программировании.
Вы тут затеяли похоже большую дискуссию о нужде в рекурсии. Да и сам автор начал топик с рекурсивной функции. Но я на этом форуме сотню раз уже видел посты "сделайте мне рекурсию", когда имелся в виду цикл с рекуррентным соотношением.

P.s. немного вник в задание автора, да, конкретно к его заданию моё замечание не относится. Но всё же.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
16.08.2022, 14:58
Помогаю со студенческими работами здесь

Что лучше использовать QMake или CMake и почему?
Пользуюсь Qt 5.7 MSVC , Qt Creator. Что лучше использовать QMake или CMake и почему?

Многопоточность: когда и почему лучше использовать thread или async?
Подскажите, пожалуйста, когда и почему лучше использовать thread или async?

Какой из видов линейных списков лучше использовать, если нужно введенную последовательность вывести наоборот?
Какой из видов линейных списков лучше использовать, если нужно введенную последовательность вывести наоборот? Пока только обучаюсь С++,...

Как лучше закодировать app.config connectionStrings? Или лучше не здесь хранить подключение к бд?
Я знаю, что app.config можно кодировать через консоль или же с помощью...

Какую графику лучше использовать при создании изображений для сайтов и почему?
Какую графику лучше использовать при создании изображений для сайтов и почему?


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Новые блоги и статьи
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД
Maks 14.04.2026
Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code
Loafer 13.04.2026
{ "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы
Maks 13.04.2026
Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .
Архитектура слоя интернета для сервера-слоя.
Hrethgir 11.04.2026
В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа
Maks 10.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .
Очистка реквизитов документа при копировании
Maks 09.04.2026
Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru