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

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

Восстановить пароль Регистрация
 
Guzal
0 / 0 / 0
Регистрация: 11.11.2010
Сообщений: 6
11.11.2010, 20:07     указатели с++, дорешать) #1
Пожалуйста, помогите дорешать задачку:

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)

Код
например:
вводятся числа 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)?

я начала..

Код
#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;
	}
__________________
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.11.2010, 20:07     указатели с++, дорешать)
Посмотрите здесь:

указатели C++
указатели C++
Указатели. C++
C++ Задачка на динамический список. Помогите дорешать
Указатели C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.11.2010, 21:11     указатели с++, дорешать) #2
Здесь рекурсия нужна. А вообще, считать вы не умеете. 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
0 / 0 / 0
Регистрация: 11.11.2010
Сообщений: 6
11.11.2010, 21:51  [ТС]     указатели с++, дорешать) #3
да, там 10)извините ошиблась.Спасибо!
значит я не до конца понимаю задание, если во втором примере я считаю так(
могли бы вы объяснить как это работает?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.11.2010, 22:15     указатели с++, дорешать) #4
Ну давайте посчитаем вручную второй пример:

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

Код
(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
0 / 0 / 0
Регистрация: 11.11.2010
Сообщений: 6
11.11.2010, 22:38  [ТС]     указатели с++, дорешать) #5
Спасибо огромное, с этой задачей разобралась)
но насчет рекурсии..э..не совсем, но общее представление есть.
спасибо)
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.11.2010, 23:01     указатели с++, дорешать) #6
Ну для примера вот вам простейшая рекурсия - вычисление факториала (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, другая функция программы или же та же самая функция. Ей об этом знать не надо, ей надо просто выполнить арифметические операции и вернуть ответ. И на каждом из уровней рекурсии ей, можно сказать, даже всё равно, что она вызывает сама себя. С её точки зрения это выглядит как вызов любой другой функции, необходимой для получения результата. Она просто дождётся, когда эта вызванная функция выполнится и вернёт результат.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.11.2010, 22:01     указатели с++, дорешать)
Еще ссылки по теме:

C++ Как дорешать задачу?
C++ как изобразить декартову систему координат ?немогу дорешать задачку
C++ Вычислить функцию f(x), используя ее разложение в степенной ряд (дорешать)

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

Или воспользуйтесь поиском по форуму:
Guzal
0 / 0 / 0
Регистрация: 11.11.2010
Сообщений: 6
12.11.2010, 22:01  [ТС]     указатели с++, дорешать) #7
спасибо большое за объяснение) дошло))
Yandex
Объявления
12.11.2010, 22:01     указатели с++, дорешать)
Ответ Создать тему
Опции темы

Текущее время: 17:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru