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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 107, средняя оценка - 4.70
barlog
2 / 2 / 0
Регистрация: 03.11.2009
Сообщений: 227
#1

Рекурсия: вычисление суммы ряда - C++

13.05.2011, 18:58. Просмотров 14076. Ответов 1
Метки нет (Все метки)

Тема: Рекурсивные функции. используя механизм рекурсии;
Вычислить для заданного натурального n:

http://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{i=1}^{n} \frac{{\left(-1 \right)}^i\, \cdot\, i^2 \,\cdot \,\left(i+1 \right)}{i!}

ПОМОГИТЕ ЛЮДИ ДОБРЫЕ!!!!Я вообше в этой рекурсии не рублю!!!Совсем не понимаю как это делать((Помогите пожалуйста!!
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2011, 18:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия: вычисление суммы ряда (C++):

Рекурсия: вычисление суммы ряда 1/n! - C++
Здравствуйте) Есть задача, чтобы сделать её с рекурсией и без. Вычислить значение суммы S = 1/1! + 1/2! + ... + 1/k! Без рекурсии я...

Рекурсия для вычисления суммы ряда - C++
Используя рекурсивный вызов функции вычислить с заданной точностью сумму ряда: 2/3+4/9+6/27+8/81+... (GUI)

Рекурсия (вычисление суммы, вывод элементов одномерного массива в обратном порядке) - C++
Я хочу реализовать рекурсивные функции:1)вычисления суммы k первых членов арифметической прогрессии. 2)вывода в консоль элементов...

Рекурсия: вычисление суммы и количества цифр числа, максимальной и минимальной его цифры - C++
Помогите, пожалуйста, разобраться и написать программу на С++. Условие такое: Для числа, введеного с клавиатуры, определить рекурсивные...

Вычисление суммы n ряда - C++
Помогите сделать с этими операторами задачи, знаю только как с for. 1. Составить программу вычисления суммы 15 членов ряда S =...

Вычисление суммы ряда - C++
Для заданных значений ε>0 и x вычислить сумму ряда с точностью ε. Суммирование ряда завершить, если модуль очередного члена ряда не...

1
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
13.05.2011, 19:06 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот тебе ликбез.

Рекурсивные функции
Язык C++ предоставляет возможность написания рекурсивных функций, однако целесообразность применения рекурсии оставляется на усмотрение программиста. Как правило, рекурсивные алгоритмы применяются там, где имеется явное рекурсивное определение обрабатываемых данных. Не будем отступать от традиции и рассмотрим функцию факториала n!. Как правило, в программировании её определяют как произведение первых n целых чисел:
n! = 1 * 2 * 3 * ... * n
Такое произведение можно легко вычислить с помощью итеративных конструкций, например, оператора цикла for (листинг 7.14).
C++
1
2
3
4
5
Листинг 7.14. Итеративная функция вычисления факториала
long Fact(int k)
{ long f; int i;  for(f = 1, i = 1; i<k; i++) f*= i;
  return f;
}
Однако существует также другое (математическое) определение факториала, в котором используется рекуррентная формула и которое имеет такой вид:
0! = 1
n > 0 n! = n*(n-1)!
Если для факториала первое (итеративное) определение может показаться проще, то для чисел Фибоначчи рекурсивное определение
F(1) = 1,
F(2) = 1,
 n > 2 F(n) = F(n-1) + F(n-2)
выглядит для вычислений гораздо лучше, чем прямая формула.
Понятно, что организовать вычисления по рекуррентным формулам можно и без использования рекурсии. Однако, как видно на примерах, представленных в [Шалыто-Программист], преобразование естественной рекурсивной формы в итеративную – довольно сложная задача. Использование рекурсии позволяет легко (почти автоматически) запрограммировать вычисления по рекуррентным формулам. Например, рекурсивная функция для вычисления факториала n! имеет следующий вид (листинг 7.15).
C++
1
2
3
4
5
Листинг 7.15. Рекурсивная функция вычисления факториала
long Fact(int k)
{ if (k==0) return 1;
  return (k*Fact(k-1));     // рекурсивный вызов !
}
Аналогично, по указанному определению легко написать функцию вычисления чисел Фибоначчи (листинг 7.16).
C++
1
2
3
4
5
Листинг 7.16. Рекурсивная функция вычисления чисел Фибоначчи
long Fibo(int k)
{ if ((k==2)||(k==1)) return 1;
  return (Fibo(k-1)+Fibo(k-2)); // рекурсивный вызов !
}
Рекурсивной функцией называется функция, вызывающая саму себя в своем теле. Необходимо ещё раз подчеркнуть, что «самовызов» будет рекурсивным только в том случае, если находится в теле функции. Как мы видели ранее, «самовызов» в списке параметров не является рекурсивным.
Обычно различают прямую и косвенную рекурсию. Если в теле функции явно используется вызов той же самой функции, то имеет место прямая рекурсия (self-calling), как в приведенных примерах. Если две или более функций взаимно вызывают друг друга, то имеет место косвенная рекурсия. Обычно косвенная рекурсия возникает при реализации программ синтаксического анализа методом рекурсивного спуска.
Прекрасным примером рекурсивной функции является быстрая сортировка Хоора. Сама схема алгоритма является рекурсивной, поэтому написать итеративную программу достаточно сложно, что можно увидеть в книге Н.Вирта [9] и в [30]. Схема функции выглядит так:
C++
1
2
3
4
5
6
void QuickSort(A, 1, n)
{  //--Выбрать разделяющий элемент с номером  1<k<n
   //--Разделить массив А относительно k-го элемента
   QuickSort(A, 1, k-1);    //-рекурсивный вызов с левой частью
   QuickSort(A, k+1, n);   //-рекурсивный вызов с правой частью
}
Есть большое количество традиционных «игрушечных» задач (ханойские башни, расстановка ферзей и т.п.), которые анализируются в литературе [9,34] для демонстрации рекурсии. Мы не будем на них останавливаться — гораздо интереснее рассмотреть типично итеративные алгоритмы, которые можно представить рекурсивным образом. В принципе, любой цикл можно заменить эквивалентной рекурсивной программой. В качестве примера рассмотрим рекурсивную реализацию (листинг 7.17) функции вычисления длины строки (см. листинг 3.11).
C++
1
2
3
4
5
Листинг 7.17. Рекурсивная функция вычисления длины строки
unsigned int Length (char *s)
{ if (*s==0) return 0;      // можно просто !(*s)
  else return 1+Len(s+1);
}
Вызов такой функции абсолютно ни в чём не отличается от вызова аналогичной итеративной, например:
C++
1
cout<<Len(1234567890);
на экран совершенно правильно выводится 10. Работа рекурсивных функций обычно имеет несколько «мистический» оттенок, поэтому не будем пока в деталях разбирать работу этой функции, но обратим внимание на несколько важных моментов:
1. Цикла в функции нет – вместо него у нас имеется рекурсивный вызов. Таким образом, явное повторение заменяется неявным – рекурсивным.
2. Параметр, который является указателем, в рекурсивном вызове увеличивается, перемещаясь к следующему символу.
3. Чтобы такое увеличение не происходило до бесконечности, имеется в наличии условие окончания рекурсии — в операторе if проверяется достижение конца строки.
Эту же функцию можно написать несколько иначе:
C++
1
2
3
4
unsigned int Length (char *s)
{ if (*s) return 1+Len(s+1);
  else return 0;
}
И здесь мы наблюдаем те же три перечисленных выше особенности:
1. Вместо цикла имеется рекурсивный вызов;
2. Параметр в рекурсивном вызове изменяется;
3. Условие окончания заменено условием продолжения.
Прежде, чем делать выводы, рассмотрим еще один пример – последовательную обработку файла. Пусть открытие и закрытие файла выполняются в главной программе, а обработка – в отдельной функции, которая последовательно читает записи файла и обрабатывает их. Традиционно такая обработка выполняется в цикле следующего вида:
C++
1
2
3
4
while (не конец файла)
{   //-- читать запись
    //--обработать запись
}
Попробуем написать рекурсивную процедуру без использования цикла. Пусть потоковая переменная имеет имя f. Файл представляет собой файл строк – исходный текст самой этой программы, который находится в том же каталоге, что и исполняемая программа (листинг 7.18).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Листинг 7.18. Рекурсивная функция обработки текстового файла
void ReadFile(ifstream &f)
{  char s[100];         //--буфер для строки    
    getline(f,s);           //--читаем строку   
    cout<<s;                //--обработка строки
    if (!f.eof())           //-пока не конец файла 
        ReadFile(f);        //--рекурсивный вызов
}
int main(void)
{   ifstream f("recurs.cpp");
    ReadFile(f);
    f.close();
    return 0;
}
Как мы видим, функция ReadFile несколько отличается от приведенных выше функций – отсутствует явное изменение параметра. Параметр-то все равно изменяется, но неявно — как состояние потока f при чтении. Как и в предыдущих случаях, цикл заменен рекурсивным вызовом, и присутствует условие продолжения.

Формы рекурсивных функций
В общем случае любая рекурсивная функция Rec включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова Rec. Как мы видели на примерах, рекурсивный вызов обязательно сопровождался некоторым условием: либо условием окончания, либо условием продолжения. Это понятно, поскольку безусловные рекурсивные вызовы приводят к бесконечным процессам – они сродни бесконечному циклу. Вспомните детский стишок «У попа была собака…» — это как раз случай бесконечной рекурсии. Если реализовать вывод этого стишка как рекурсивную функцию, то она может выглядеть так.
C++
1
2
3
4
5
6
void PriestAndDog(void)                           
{   сout<<“У попа была собака, он ее любил.”;   
    сout<<“Она съела кусок мяса, он ее убил,”;  
    сout<<“вырыл яму, закопал и на камне написал:;       
  PriestAndDog();                                   
}
Теоретически работа этой функции никогда не завершится. На практике программа закончится аварийно по причине переполнения стека (кто хочет – может проверить). Следовательно, главное требование к рекурсивным функциям заключается в том, что вызов рекурсивной функции должен выполняться по условию. Это условие прописывается в операторе if и может быть либо условием продолжения, либо условием окончания. В первом случае в if пишется рекурсивный вызов, во втором — оператор возврата.

Примечание
Это не гарантирует завершение рекурсивной функции – можно совершить другие ошибки. Например, если в определении функции вычисления факториала рекурсивный вызов записан в форме Fact(k--), то при выполнении возникает ошибка переполнения стека при любом способе передачи параметра. В этом случае при рекурсивном вызове берется значение k до уменьшения. В результате происходит вызов с одним и тем же значением параметра, условие никогда не удовлетворяется и рекурсия превращается в бесконечную.

Структура рекурсивной функции может принимать три разных формы (используем условие продолжения):
- форма с выполнением действий до рекурсивного вызова (на рекурсивном спуске):
C++
1
void Rec(void) { S; if (условие) Rec(); }
- форма с выполнением действий после рекурсивного вызова (на рекурсивном возврате — подъеме):
C++
1
void Rec(void) { if (условие) Rec(); S; }
- форма с выполнением действий как до (на рекурсивном спуске), так и после рекурсивного вызова (на рекурсивном возврате):
C++
1
void Rec(void) { S1; if (условие) Rec(); S2; }
В образцах указан заголовок
C++
1
void Rec(void)
поскольку в данном случае нам важно было продемонстрировать именно формы рекурсивных функций, не отвлекаясь на другие детали. Названия «рекурсивный спуск» и «рекурсивный подъем» связаны с понятием глубины рекурсии (см. далее) – функция спускается на глубину рекурсии и поднимается «оттуда».
Функция вычисления факториала написана в первой форме. Нам удалось написать вторую форму функции, вычисляющей длину строки. Аналогично, поменяв условие, можно преобразовать и функцию вычисления факториала (листинг 7.19).
C++
1
2
3
4
5
Листинг 7.19. Вторая форма рекурсивной функции вычисления факториала
long Fact(int k)
{ if (k>0) return (k*Fact(k-1));        // рекурсивный вызов !
  else     return 1;    
}
Однако переделать функцию чтения файла нам так просто не удастся. Попытка в «лоб» не приносит успеха:
C++
1
2
3
4
5
6
7
void ReadFile(ifstream &f)
{  char s[100];         //--буфер для строки    
    if (!f.eof())           //-пока не конец файла 
        ReadFile(f);        //--рекурсивный вызов 
    getline(f,s);           //--читаем строку   
    cout<<s;                //--обработка строки
}
Функция становится бесконечной. Конец файла никогда не достигается, поскольку до рекурсивного вызова не выполняется операция чтения. Это наводит на мысль о возможности преобразования данной функции в третью форму – чтение строки выполнять до проверки условия, а вывод строки – после рекурсивного вызова. Попробуем и посмотрим, что получится.
C++
1
2
3
4
5
6
7
void ReadFile(ifstream &f)
{  char s[100];         //--буфер для строки    
   getline(f,s);            //--читаем строку       
   if (!f.eof())            //-пока не конец файла 
        ReadFile(f);        //--рекурсивный вызов 
   cout<<s;             //--обработка строки
 }
Функция работает, но совсем не так как, ожидалось. Строки файла выводятся на экран в обратном порядке! Таким образом, для некоторой рекурсивной задачи подходит отнюдь не любая форма рекурсивной функции. Можно сказать, что для всякой рекурсивной задачи существует естественная для нее форма рекурсивной функции.
5
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2011, 19:06
Привет! Вот еще темы с ответами:

Вычисление суммы ряда - C++
Вычислить \sum_{i=1}^{\propto }i^2 пока S&lt;50 с помощью цикла while

Вычисление суммы ряда - C++
Привет всем) Задачу и формулы надо переписывать! Редактор формул внизу страницы. Дана такая формула: Всё вроде ничего, но не...

Вычисление суммы ряда в C++ - C++
Помогите пожалуйста балбеске написать программу вычисления суммы ряда \sum_{n=1}^{10} n / (4n^2-1)

Вычисление суммы ряда - C++
1^2+3^2+5^2+...+(2n-1)^2


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

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

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