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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.75
Юлек
4 / 3 / 0
Регистрация: 26.10.2009
Сообщений: 43
#1

Найти 1+2+3+...+n рекурсивно и итеративно - C++

30.08.2010, 22:29. Просмотров 3064. Ответов 54
Метки нет (Все метки)

Уважаемые программисты!!! помогите разобраться, дали задачу. Найти 1+2+3+...+n.
Первый способ, решить рекурсивно, а второй не рекурсивно. Чем текст программ будет различаться???
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.08.2010, 22:29     Найти 1+2+3+...+n рекурсивно и итеративно
Посмотрите здесь:

Вычислить выражение рекурсивно и итеративно - C++
Помогите записать пример. Решить задачу на фото двумя способами - с применением рекурсии и без неё. ...

Вычислить произведение рекурсивно/итеративно, оценить время выполнения - C++
Нужно разработать программу с использованием рекурсивной функции и без использования рекурсивной функции. Оценит время выполнения. x=...

Найти рекурсивно сумму ряда - C++
e^(-x^2) = сумма, где k от 0 до бесконечности (-1)^k * (x^2*k)/k! x от 1 до 15 Пользуйтесь редактором формул внизу страницы ...

Найти минимальный элемент массива рекурсивно - C++
Всем привет!!! Нужно найти минимальный элемент массива при помощи рекурсии. Просидел вчера весь день и никак не могу воткнуть как...

Найти рекурсивно значение функции Аккермана A(m, n) - C++
Я новичек так что сильно не бейте :) Нужно рекурсивно найти функцию Аккермана. double Akerrman(int m,int n) { if (m = 0) return...

Рекурсивно найти число входящих элементов Е в дерево Т - C++
Почему-то не работает, помогите! :C struct gruz_p // Описание записи о грузополучателе { char nomer, fio, dr, pol, ...

Рекурсивно найти сумму нечетных элементов до заданного n - C++
Добрый вечер! Необходимо рекурсивно найти сумму нечетных элементов до заданного n, даже не знаю с чего начать!...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Эксперт С++
9459 / 5472 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
31.08.2010, 01:04     Найти 1+2+3+...+n рекурсивно и итеративно #41
Lavroff, а зачем? в конструкторе вся основная работа делается. а добавить в класс
C++
1
unsigned int operator () () const { return nResult; }
получится самый, что нинаесть функтор, пригодный для более широкого применения, чем просто вывод суммы на экран...

кстати, если в примере из 6 поста строчку
C++
1
const int sum = Sum<5>::value;
поменять на
C++
1
const int sum = Sum<0>::value;
оно и не скомпилируется, про отрицательные числа и говорить не приходится, да и как это чудо использовать, если значение должно не константой задаваться? При моём подходе во-первых не сложно проверку входных данных устроить, во-вторых использовать просто...
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
31.08.2010, 01:11     Найти 1+2+3+...+n рекурсивно и итеративно #42
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Извините без обид, но люто-бешено напомнило.

Как пишут Hello, world

А на тему класса и функторов, все же тут реальный перебор для такой программы. Действительно красиво, да. Но ведь в таком случае и писать Hello, world через класс тоже нормально, если учитывать что потом программа может делать нечто большее.
Кстати, а в конструкторе нормально выполнять все нужные операции или все же лучше в конструкторе проводить только инициализацию?
NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,918
31.08.2010, 01:21     Найти 1+2+3+...+n рекурсивно и итеративно #43
Цитата Сообщение от easybudda Посмотреть сообщение
получится самый, что нинаесть функтор, пригодный для более широкого применения, чем просто вывод суммы на экран...
Например?

Цитата Сообщение от easybudda Посмотреть сообщение
кстати, если в примере из 6 поста строчку
C++
1
const int sum = Sum<5>::value;
поменять на
C++
1
const int sum = Sum<0>::value;
оно и не скомпилируется, про отрицательные числа и говорить не приходится
Ну логично же. Оно не скомпилируется и выдаст ошибку компиляции. Очень логично. Программа выдаёт ошибки во время работы, метапрограмма - во время компиляции.

Цитата Сообщение от easybudda Посмотреть сообщение
да и как это чудо использовать, если значение должно не константой задаваться? При моём подходе во-первых не сложно проверку входных данных устроить, во-вторых использовать просто...
А здесь всё ещё более логично. "Чудо" это вычисляется во время компиляции. Очевидно, что в готовой программе вместо "чуда" мы имеем константу. Отсюда несложно сделать вывод, что вычислить можно сумму только из тех значений, которые на момент компиляции известны. Я же нигде не писал, что оно будет работать в рантайме, ведь правда? И в ТЗ ничего об этом сказано небыло.

А по поводу того, что ты подставил ноль вместо пяти: нужна сумма первых нуля элементов? Она равна нулю!

Цитата Сообщение от easybudda Посмотреть сообщение
При моём подходе во-первых не сложно проверку входных данных устроить, во-вторых использовать просто...
Твой подход не нужен, потому что вместо него гораздо удобнее фунции, описанные другими товарищами тут в теме до тебя.

Добавлено через 8 минут
Цитата Сообщение от Lavroff Посмотреть сообщение
Кстати, а в конструкторе нормально выполнять все нужные операции или все же лучше в конструкторе проводить только инициализацию?
Я думаю, правильно так:
  1. Нечто внешнее по отношению к данному коду инициализирует функтор (если нужно какими-то данными).
  2. Данный код получает функтор, вызывая его передаёт ему какие-то свои параметры и функтор на основе их и того, что ему было заложено в предыдущем шаге, делает вычисления / что-то полезное.
easybudda
Эксперт С++
9459 / 5472 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
31.08.2010, 01:37     Найти 1+2+3+...+n рекурсивно и итеративно #44
Цитата Сообщение от NightmareZ Посмотреть сообщение
Я же нигде не писал, что оно будет работать в рантайме, ведь правда?
Ну а смысл тогда такой лес городить? Можно гораздо проще и со временем выполнения проблем не будет.
C
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
 
#define SUM(a) ({ int d = a; int s = 0; while ( d ) s += d--; (s); })
 
int main(void){
    printf("SUM(5) = %d\n", SUM(5));
    int i = 5;
    printf("SUM(%d) = %d\n", i, SUM(i));
    
    return 0;
}
Цитата Сообщение от NightmareZ Посмотреть сообщение
Твой подход не нужен
Повторяйте себе это почаще.

Не по теме:

И кстати, ничего, что я с Вами на Вы? Ну это так, элементарная вежливость...

ISergey
Maniac
Эксперт С++
1373 / 884 / 52
Регистрация: 02.01.2009
Сообщений: 2,653
Записей в блоге: 1
31.08.2010, 01:43     Найти 1+2+3+...+n рекурсивно и итеративно #45
Цитата Сообщение от easybudda Посмотреть сообщение
поменять на
C++
1
const int sum = Sum<0>::value;
оно и не скомпилируется
Нашли проблему.. лечится быстро..

C++
1
2
3
4
template<>
struct Sum<0>{
        enum { value = 0 };
};
Как на меня то метапрограмы доволи интересная штука..
NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,918
31.08.2010, 01:46     Найти 1+2+3+...+n рекурсивно и итеративно #46
Цитата Сообщение от easybudda Посмотреть сообщение
Ну а смысл тогда такой лес городить?
Потому что это самый быстрый по производительности код на C++, позволяющий решить поставленную задачу (посчитать сумму N элементов).

Подставить готовое решение в виде константы - значит использовать сторонние инструменты для вычислений, т.е. задача уже решена не на C++ будет.

Вычислять в рантайме - займёт в любом случае больше времени.

Цитата Сообщение от easybudda Посмотреть сообщение
Можно гораздо проще и со временем выполнения проблем не будет.
C
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
 
#define SUM(a) ({ int d = a; int s = 0; while ( d ) s += d--; (s); })
 
int main(void){
    printf("SUM(5) = %d\n", SUM(5));
    int i = 5;
    printf("SUM(%d) = %d\n", i, SUM(i));
    
    return 0;
}
Сложность моего алгоритма в рантайме будет O(1), а твоего O(N), иными словами, у меня будет константа, а у тебя будет N-1 сложений.

Цитата Сообщение от easybudda Посмотреть сообщение

Не по теме:

И кстати, ничего, что я с Вами на Вы? Ну это так, элементарная вежливость...

Вообще, чесно говоря, мне это не нравится. Называй меня пожалуйста на "ты". В интернетах так принято. От обращения на "вы" веет недоброжелательностью.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
31.08.2010, 01:48     Найти 1+2+3+...+n рекурсивно и итеративно #47
ISergey, Действительно интересная вещь. Только вот хоть убей не пойму как этим пользоваться. Обычными шаблонами - да, но настолько закрученными через enum. Эх.
easybudda
Эксперт С++
9459 / 5472 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
31.08.2010, 01:57     Найти 1+2+3+...+n рекурсивно и итеративно #48
Цитата Сообщение от NightmareZ Посмотреть сообщение
Потому что это самый быстрый по производительности код
По-моему при таком подходе это самый ненужный код. Если число константное, так его проще посчитать а) на пальцах; б) на калькуляторе; в) одной из предложенных программ и сразу в программе константой объявить, при этом не насилуя ни мозг, ни компилятор...
NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,918
31.08.2010, 01:59     Найти 1+2+3+...+n рекурсивно и итеративно #49
Цитата Сообщение от Lavroff Посмотреть сообщение
ISergey, Действительно интересная вещь. Только вот хоть убей не пойму как этим пользоваться. Обычными шаблонами - да, но настолько закрученными через enum. Эх.
enum нужен только для того, чтобы можно было задать значение полю (в данном случае value).

А дальше... Есть вот такой код:

C++
1
2
3
4
5
6
7
8
9
10
11
template<int N>
struct Sum
{
        enum { value = N + Sum<N-1>::value };
};
 
template<>
struct Sum<0>
{
        enum { value = 0 };
};
...вызываешь ты его:
C++
1
const int sum = Sum<2>::value;
Компилятор начинает подставлять 2 вместо N:
C++
1
2
3
4
5
template<2>
struct Sum
{
        enum { value = 2 + Sum<2-1>::value };
};
тут ему всё известно, кроме Sub<2-1>. Он подставляет дальше уже 1 вместо N:
C++
1
2
3
4
5
template<1>
struct Sum
{
        enum { value = 1 + Sum<1-1>::value };
};
тут ему опять таки всё известно, но кроме Sub<1-1>.
Sub<1-1> это Sub<0>, а в нём value равно нулю:
C++
1
2
3
4
5
template<>
struct Sum<0>
{
        enum { value = 0 };
};
Компилятор берёт этот value и рекурсия отсюда идёт назад до тех пор, пока не соберётся исходный шаблон.
ISergey
Maniac
Эксперт С++
1373 / 884 / 52
Регистрация: 02.01.2009
Сообщений: 2,653
Записей в блоге: 1
31.08.2010, 02:02     Найти 1+2+3+...+n рекурсивно и итеративно #50
Lavroff, найди вот эту книгу http://www.williamspublishing.com/Bo...59-0513-3.html
почитай.. немного суть проясниться..
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,446
31.08.2010, 05:53     Найти 1+2+3+...+n рекурсивно и итеративно #51
Хвостовая рекурсия:
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
#include <iostream>
#include <cstdlib>
 
unsigned int sum_iter(unsigned int result, unsigned int counter)
{
    if(!counter)
        return result;
    else
        return sum_iter(result + counter, --counter);
}
 
unsigned int sum(unsigned int n)
{
    return sum_iter(0, n);
}
 
int main()
{
    unsigned int n;
    std::cout << "Input n: ";
    std::cin >> n;
    std::cout << "Sum from 0 to " << n << " = " << sum(n) << std::endl;
    return EXIT_SUCCESS;
}
easybudda
Эксперт С++
9459 / 5472 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
01.09.2010, 17:12     Найти 1+2+3+...+n рекурсивно и итеративно #52
Nameless One, а две функции для того, чтобы в вызывающую только одно значение передавать?

Цитата Сообщение от NightmareZ Посмотреть сообщение
Например?
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
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
 
class Sum {
        unsigned int nResult;
public:
        Sum() : nResult(0) {}
        Sum(unsigned int start){
                for ( nResult = 0; start; nResult += start-- )
                        ;
        }
        bool operator () (int test){
            return test > nResult;
        }
 
        friend std::ostream & operator << (std::ostream & ost, const Sum & sum){
                ost << sum.nResult;
                return ost;
        }
};
 
int main(){
        const size_t size = 5;
        int arr[size] = { 8, 12, 5, 14, 21 };
        std::vector<int> vec(arr, arr + size);
        int num = 5;
        Sum sum(num);
        std::vector<int>::iterator fnd;
 
        std::cout << "Array:\n";
        std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
        std::cout << "\nGiven number:\n" << num << std::endl;
        std::cout << "Sum of numbers from 1 to " << num << " = " << sum << std::endl;
        if ( ( fnd = std::find_if(vec.begin(), vec.end(), sum) ) == vec.end() )
            std::cout << "All elements in array less than it." << std::endl;
        else
            std::cout << "First element in array greater it is " << *fnd << std::endl;
 
        return 0;
}
Цитата Сообщение от NightmareZ Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
 
template<int N>
struct Sum
{
    enum { value = N + Sum<N-1>::value };
};
 
template<>
struct Sum<1>
{
    enum { value = 1 };
};
 
int main()
{
    const int sum = Sum<5>::value;
    std::cout << sum;
}
Долго пытался этому практическое применение придумать. Кроме объявления в программе 100500 тысяч констант, представляющих суммы от 1 до исходных 100500 тысяч чисел так и не придумал. Да и в том случае проще заголовочный файл создать например вот таким макаром:
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
#include <stdio.h>
#include <stdlib.h>
 
#define SUM(a) ({ int d = a; int s = 0; while ( d ) s += d--; (s); })
 
#define IN_FILE "constants.txt"
#define OUT_FILE "constants.h"
 
int main(void){
    int val;
    FILE * fin, * fout;
 
    if ( ( fin = fopen(IN_FILE, "r") ) == NULL ){
        perror("fopen");
        exit(1);
    }
    if ( ( fout = fopen(OUT_FILE, "w") ) == NULL ){
        perror("fopen");
        exit(1);
    }
 
    fprintf(fout, "#ifndef _CONSTANTS_H_\n#define _CONSTANTS_H_ 1\n");
    while ( fscanf(fin, "%d", &val) == 1 )
        fprintf(fout, "#define SUM%d %d\n", val, SUM(val));
 
    fprintf(fout, "#endif\n");
 
    fclose(fin);
    fclose(fout);
 
    exit(0);
}
а то мало ли - ещё раз с другими числами понадобится - и чё, блин, делать? Лезть в исходники, править циферки и заново компилировать?
Короче, думаю, что в данном случае всё это метапрограммирование - голый выпендрёж и в принципе нафиг не нужно. Поправьте, если чего-то не понимаю...
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,446
01.09.2010, 17:19     Найти 1+2+3+...+n рекурсивно и итеративно #53
Цитата Сообщение от easybudda Посмотреть сообщение
Nameless One, а две функции для того, чтобы в вызывающую только одно значение передавать?
Тут, я думаю, можно заменить функцию sum_iter на лямбду, либо сделать для функции sum дополнительный параметр. Две функции нужны для того, чтобы при передаче управления рекурсивному вызову самой себя никакая из локальных переменных вызывающей функции не была нужно для формирования результата. Т.е. чтобы вместо простой рекурсии можно было получить хвостовую рекурсию, которая некоторыми компиляторами (вроде msvs и gcc) может быть заменена на простой цикл. Интересная фича из функционального программирования
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
01.09.2010, 18:00     Найти 1+2+3+...+n рекурсивно и итеративно #54
easybudda, Метапрограммирование не для такого нужно... Просмотрел 17 главу в книге, что скинул ISergey. Интересно. Советую просмотреть. Еще не очень развитая фича, но все же.
Зачем нужно метопрограммирование? Как и большинство других технологий программирования, оно применяется, чтобы достичь больших функциональных возможностей ценой меньших затрат, измеряемых обемом кода, усилиями на сопровождение и т.п. Характерной особенностью является то,что определенная часть необходимых пользователю вычислений выполняется на этапе трансляции программы. Его применение часто объясняется повышением производительности (вычисление, которое происходит во время трансляции, легче оптимизировть) или упрощением интерфейса (как правило, метапрограмма короче, чем программа, которая генерируется во время ее работы), а зачастую обеими причинами
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.09.2010, 18:53     Найти 1+2+3+...+n рекурсивно и итеративно
Еще ссылки по теме:

Рекурсивно найти n-ую производную для заданого x. Результат похож на шестнадцатеричный код - C++
Задание:рекурсивно найти n-ую производную f(x)={e}^{(a{x}^{2}+bx+c)} для заданого x,построив для {f}^{(n)}(x) рекурентное соотношение. ...

Рекурсивно обчислити добуток n ≥ 2 співмножників (n парне): у = (2/1)*(2/3)*(4/3)*(4/5)*(6/5)*(6/7).Рекурсивно обчислити добуток n ≥ 2 співмножників - C++
Рекурсивно обчислити добуток n ≥ 2 співмножників (n парне): у = (2/1)*(2/3)*(4/3)*(4/5)*(6/5)*(6/7)...

Вычислить y=x^N рекурсивно - C++
Вычислить y=x^N по следующему алгоритму: y=(x^(N/2))^2 , если N четное; y=x*x^(N-1) , если N нечетное. C ПОМОЩЬЮ РЕКУРСИИ. В чем ошибка? ...

Вычислить сумму рекурсивно - C++

Числа Фибоначчи рекурсивно - C++
Написать рекурсивную функцию, высчитывает N-й элемент последовательности чисел Фибоначчи FK, которая описывается следующими формулами: F1 =...


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

Или воспользуйтесь поиском по форуму:
easybudda
01.09.2010, 18:53     Найти 1+2+3+...+n рекурсивно и итеративно
  #55

Не по теме:

Цитата Сообщение от Lavroff Посмотреть сообщение
Просмотрел 17 главу в книге, что скинул ISergey. Интересно. Советую просмотреть.
Прочитал и, честно говоря, не впечатлился... Во-первых я себе это примерно так и представлял, а во-вторых может просто пока задачи не попадались, в которых без таких вот выкрутасов никуда... Пока же мне это метапрограммирование определение слова "Финдипёрст" из уголовного жаргона напоминает:
Вещь по сути своей бесполезная, но блестящая и напоминающая о воле.

Yandex
Объявления
01.09.2010, 18:53     Найти 1+2+3+...+n рекурсивно и итеративно
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru