указатели с++, дорешать)

@Guzal · Регистрация: 11.11.2010

Студворк — интернет-сервис помощи студентам

Пожалуйста, помогите дорешать задачку:

SuperSum функция, найденная из:
• SuperSum(0 , n) = n, для положительных n.
• SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + SuperSum(k-1 , n), для положительных k, n.
Для данных k , n вернуть значение функции SuperSum(k , n)

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
например:
вводятся числа 2 и 3:
(2, 3) = (2, 2) + (1, 2) + (1, 3)
 k   n      0, 1      0, 1       0, 1        
                         0, 2       0, 2
                                      0, 3
             1            3            6     = 9 -ответ    
пример2:
(3, 4) = (2, 1) + (2, 2) + (2, 3) + (2, 4)
             1, 1      1, 1       1, 1      1, 1
                         1, 2       1, 2      1, 2
                                       1, 3     1, 3
                                                  1, 4
               2         5               9       14     = 30

Как добавить в функцию это условие SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + SuperSum(k-1 , n)?

я начала..

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
    
    int superSum (int k, int *n) {
    int sum = 0;
    if (k==0) return *n;
        else if (k==1) {
        for (int i=k; i<*n+1; i++)
        sum+=i;
         return sum;
                 }
                            }
    int main() {
       int k, n;
       cin >>k>>n;
      cout << superSum (k, &n);
       
    return 0;
    }

__________________

silent_1991 · 11.11.2010, 21:11

Здесь рекурсия нужна. А вообще, считать вы не умеете. 1 + 3 + 6 = 10, а не 9. Далее, (3, 4) = 1 + 4 + 10 + 20 = 35. Ну а программа вот

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
#include <iostream>
 
int SuperSum(int, int);
 
int main()
{
    int k, n;
 
    std::cout << "Enter k: ";
    std::cin >> k;
    std::cout << "Enter n: ";
    std::cin >> n;
 
    std::cout << "SuperSum(" << k << ", " << n << ") = " << SuperSum(k, n) << std::endl;
 
    std::cin.get();
    return 0;
}
 
int SuperSum(int k, int n)
{
    if (k == 0 || n == 1)
        return n;
 
    int sum = 0;
 
    for (int i = 1; i <= n; i++)
        sum += SuperSum(k - 1, i);
 
    return sum;
}

@Guzal · 11.11.2010, 21:51 **[ТС]**

да, там 10)извините ошиблась.Спасибо!
значит я не до конца понимаю задание, если во втором примере я считаю так(
могли бы вы объяснить как это работает?

silent_1991 · 11.11.2010, 22:15

Ну давайте посчитаем вручную второй пример:

Каждый следующий отступ - шаг вглубь, если невозможно непосредственно вычислить выражение на этом шаге.

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(3, 4) = (2, 1) + (2, 2) + (2, 3) + (2, 4) = 1 + 4 + 10 + 20 = 35, т.к.
    (2, 1) = (1, 1) = 1
    (2, 2) = (1, 1) + (1, 2) = 1 + 3 = 4, т.к.
        (1, 1) = (0, 1) = 1
        (1, 2) = (0, 1) + (0, 2) = 1 + 2 = 3
    (2, 3) = (1, 1) + (1, 2) + (1, 3) = 1 + 3 + 6 = 10, т.к.
        (1, 1) = (0, 1) = 1
        (1, 2) = (0, 1) + (0, 2) = 1 + 2 = 3
        (1, 3) = (0, 1) + (0, 2) + (0, 3) = 1 + 2 + 3 = 6
    (2, 4) = (1, 1) + (1, 2) + (1, 3) + (1, 4) = 1 + 3 + 6 + 10 = 20, т.к.
        (1, 1) = (0, 1) = 1
        (1, 2) = (0, 1) + (0, 2) = 1 + 2 = 3
        (1, 3) = (0, 1) + (0, 2) + (0, 3) = 1 + 2 + 3 = 6
        (1, 4) = (0, 1) + (0, 2) + (0, 3) + (0, 4) = 1 + 2 + 3 + 4 = 10

Вот так же примерно работает и рекурсия: если входные параметры удовлетворяют некоторому условию - базису рекурсии, то сразу вычисляется и возвращается результат. Если базис не достигнут, т.е. непосредственно, напрямую, вычислить выражение не удаётся - то функция вызывает саму себя, но с новыми параметрами. Главное условие - новые параметры всегда должны быть ближе к базису, чем предыдущие, иначе рекурсия не сможет развернуться, т.е. в данном случае функция вызовет саму себя с параметром k - 1, что на 1 ближе к базису, чем предыдущий параметр k. Далее, внутри вновь вызванной функции будет новый параметр k, который на 1 меньше, чем начальный. И эта новая функция вызовет сама себя с уже новым параметром k - 1, а это уже на 2 меньше, чем самый начальный. Таким образом мы обязательно когда-нибудь достигнем условия k == 0 и ветвь рекурсии начнёт разворачиваться (т.е. функция перестанет вызывать сама и будет выдавать уже вполне конкретные числовые ответы). Вообще рекурсия, не очень тривиальная тема, и, возможно, вы ничего не поняли, но тут уж ничего не поделаешь, фиговый из меня учитель)))

@Guzal · 11.11.2010, 22:38 **[ТС]**

Спасибо огромное, с этой задачей разобралась)
но насчет рекурсии..э..не совсем, но общее представление есть.
спасибо)

silent_1991 · 11.11.2010, 23:01

Ну для примера вот вам простейшая рекурсия - вычисление факториала (n-факториал, обозначается n! = n * (n - 1) * (n - 2) * ... * 2 * 1 - произведение целых чисел от 1 до n. При этом принято, что 0! = 1! = 1):

C
1
2
3
4
5
6
7
int fact(int n)
{
    if (n == 0 || n == 1)
        return 1;
 
    return n * fact(n - 1);
}

Функция работает так. Например, передаём 0 или 1. Она проверяет базис, видит, что он выполняется, и возвращает 1.
Если передаём, например 4. Тогда. Функция проверяет базис. Он не выполняется. И функция как-бы возвращает n * fact(n - 1). Т.е. чтобы вернуть результат, ей сначала надо вызвать саму себя. Будет вызов 4 * fact(3).
Теперь у нас вызвана новая функция fact с параметром 3. Она вообще не знает, что её вызвала другая функция, и что до этого был какой-то параметр 4, она просто должна выполнить некоторые действия со своим параметром - тройкой. А действия аналогичные. Проверяем базис. Не выполняется - возвращаем 3 * fact(2), т.е. снова происходит рекурсивный вызов функции fact. Она делает то же самое, сверяет базис, и, так как он не выполняется, вызывает себя рекурсивно с параметром 1. И тут-то начинается самое интересное. Базис выполняется. Функция больше не вызывает себя рекурсивно - она возвращает 1. А куда возвращает? А туда, откуда её вызвали, т.е. в предыдущий вызов функции, тот, где параметром была двойка. А там, как мы помни, стояло следующее: return 2 * fact(1);. Т.к. fact(1) уже вычислен и равен 1, получается, что там, по сути, стоит return 2 * 1;. Т.е. функция, у которой параметр был 2, вернёт 2. А куда? А, опять же, туда, откуда её вызвали, т.е. в ещё одну функцию fact, у которой параметр был 3. Там, как мы помним, было return 3 * fact(2);, но fact(2) уже вычислен - он равен 2. Тогда функция fact(3) вернёт 3 * 2, т.е. 6. Вернёт, как нетрудно догадаться, в функцию fact(4), из которой была вызвана. Там было return 4 * fact(3);, т.е. return 4 * 6;. Получается, что fact(4) вернёт 24. А куда? А туда, откуда её вызвали... Но мы же её вызвали из функции main. Вот это да! Вот так шутя мы вычислили факториал 4. Будь на месте 4 другое число - просто глубина рекурсии была бы больше, но суть бы осталась. Вся прелесть рекурсии в том, что функции пофиг, кто её вызывает, функция main, другая функция программы или же та же самая функция. Ей об этом знать не надо, ей надо просто выполнить арифметические операции и вернуть ответ. И на каждом из уровней рекурсии ей, можно сказать, даже всё равно, что она вызывает сама себя. С её точки зрения это выглядит как вызов любой другой функции, необходимой для получения результата. Она просто дождётся, когда эта вызванная функция выполнится и вернёт результат.

@Guzal · 12.11.2010, 22:01 **[ТС]**

спасибо большое за объяснение) дошло))

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

@Guzal 0 / 0 / 0 Регистрация: 11.11.2010 Сообщений: 6
	11.11.2010, 21:51 [ТС]
	да, там 10)извините ошиблась.Спасибо! значит я не до конца понимаю задание, если во втором примере я считаю так( могли бы вы объяснить как это работает? 0

@Guzal 0 / 0 / 0 Регистрация: 11.11.2010 Сообщений: 6
	11.11.2010, 22:38 [ТС]
	Спасибо огромное, с этой задачей разобралась) но насчет рекурсии..э..не совсем, но общее представление есть. спасибо) 0

@Guzal 0 / 0 / 0 Регистрация: 11.11.2010 Сообщений: 6
	12.11.2010, 22:01 [ТС]
	спасибо большое за объяснение) дошло)) 0