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

@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 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@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