Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

Вычисление цепной дроби (рекурсивно и итеративно) - C++
Как это вообще сделать ??? Нужно с помощь. рекурсии и без неё С++.

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

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

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

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

54
NightmareZ
1398 / 610 / 38
Регистрация: 31.03.2009
Сообщений: 1,978
31.08.2010, 01:46 #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 Посмотреть сообщение

Не по теме:

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

Вообще, чесно говоря, мне это не нравится. Называй меня пожалуйста на "ты". В интернетах так принято. От обращения на "вы" веет недоброжелательностью.
0
ForEveR
В астрале
Эксперт С++
7994 / 4753 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
31.08.2010, 01:48 #47
ISergey, Действительно интересная вещь. Только вот хоть убей не пойму как этим пользоваться. Обычными шаблонами - да, но настолько закрученными через enum. Эх.
1
easybudda
Модератор
Эксперт CЭксперт С++
10020 / 5943 / 1004
Регистрация: 25.07.2009
Сообщений: 11,230
31.08.2010, 01:57 #48
Цитата Сообщение от NightmareZ Посмотреть сообщение
Потому что это самый быстрый по производительности код
По-моему при таком подходе это самый ненужный код. Если число константное, так его проще посчитать а) на пальцах; б) на калькуляторе; в) одной из предложенных программ и сразу в программе константой объявить, при этом не насилуя ни мозг, ни компилятор...
0
NightmareZ
1398 / 610 / 38
Регистрация: 31.03.2009
Сообщений: 1,978
31.08.2010, 01:59 #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 и рекурсия отсюда идёт назад до тех пор, пока не соберётся исходный шаблон.
1
ISergey
Maniac
Эксперт С++
1407 / 918 / 57
Регистрация: 02.01.2009
Сообщений: 2,743
Записей в блоге: 1
31.08.2010, 02:02 #50
Lavroff, найди вот эту книгу http://www.williamspublishing.com/Books/5-8459-0513-3.html
почитай.. немного суть проясниться..
1
Nameless One
Эксперт С++
5783 / 3432 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
31.08.2010, 05:53 #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;
}
1
easybudda
Модератор
Эксперт CЭксперт С++
10020 / 5943 / 1004
Регистрация: 25.07.2009
Сообщений: 11,230
01.09.2010, 17:12 #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);
}
а то мало ли - ещё раз с другими числами понадобится - и чё, блин, делать? Лезть в исходники, править циферки и заново компилировать?
Короче, думаю, что в данном случае всё это метапрограммирование - голый выпендрёж и в принципе нафиг не нужно. Поправьте, если чего-то не понимаю...
0
Nameless One
Эксперт С++
5783 / 3432 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
01.09.2010, 17:19 #53
Цитата Сообщение от easybudda Посмотреть сообщение
Nameless One, а две функции для того, чтобы в вызывающую только одно значение передавать?
Тут, я думаю, можно заменить функцию sum_iter на лямбду, либо сделать для функции sum дополнительный параметр. Две функции нужны для того, чтобы при передаче управления рекурсивному вызову самой себя никакая из локальных переменных вызывающей функции не была нужно для формирования результата. Т.е. чтобы вместо простой рекурсии можно было получить хвостовую рекурсию, которая некоторыми компиляторами (вроде msvs и gcc) может быть заменена на простой цикл. Интересная фича из функционального программирования
1
ForEveR
В астрале
Эксперт С++
7994 / 4753 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
01.09.2010, 18:00 #54
easybudda, Метапрограммирование не для такого нужно... Просмотрел 17 главу в книге, что скинул ISergey. Интересно. Советую просмотреть. Еще не очень развитая фича, но все же.
Зачем нужно метопрограммирование? Как и большинство других технологий программирования, оно применяется, чтобы достичь больших функциональных возможностей ценой меньших затрат, измеряемых обемом кода, усилиями на сопровождение и т.п. Характерной особенностью является то,что определенная часть необходимых пользователю вычислений выполняется на этапе трансляции программы. Его применение часто объясняется повышением производительности (вычисление, которое происходит во время трансляции, легче оптимизировть) или упрощением интерфейса (как правило, метапрограмма короче, чем программа, которая генерируется во время ее работы), а зачастую обеими причинами
0
easybudda
01.09.2010, 18:53     Найти 1+2+3+...+n рекурсивно и итеративно
  #55

Не по теме:

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

0
01.09.2010, 18:53
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.09.2010, 18:53
Привет! Вот еще темы с ответами:

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

Рекурсивно найти сумму нечетных элементов до заданного n - C++
Добрый вечер! Необходимо рекурсивно найти сумму нечетных элементов до заданного 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)...


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

Или воспользуйтесь поиском по форуму:
55
Ответ Создать тему
Опции темы

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