1

введите сюда описание изображения

#include <iostream>
using namespace std;

int row(int n, int x);

int main()
{
    int n,x;
    cout << "Input number: ";
    cin >> n;
    cout << "Input x: ";
    cin >> x;
    if (n == 0) {cout << 1;return 0;}
    while (n < 0)
    {
        cout <<  "Error! Type n > 0!";
        cin >> n;   
    }
    cout << row(n, x);
    return 0;
}

int row(int n, int x)
{
    int s;
    if (n==0) return 1;
    if (n==1) return x;
    if (n==n) { 
        s = ((2*n-1)*x*row(n-1,x)-row(n-2,x));
        }

    return s;
}

Вот мой код. Скажите пожалуйста, что с ним не так? P.S. Он что-то выводит, но я не понимаю, выводит то, что требуется, или же нет

0

1 ответ 1

3

Ну, ваш код быстро зашьется из-за экспоненциального роста ветвей рекурсии... Можно, конечно, воспользоваться мемоизацией... Но можно просто работать итеративно:

double P(unsigned int n, double x)
{
    if (n == 0) return 1;
    if (n == 1) return x;
    double p0 = 1, p1 = x;
    for(unsigned int i = 2; i <= n; ++i)
    {
        double p = (2*i-1)*x*p1-p0;
        p0 = p1;
        p1 = p;
    }
    return p1;
}

P.S. Не компилировал, набросал на коленке. Но вроде бы на глаз без ошибок...

Рекурсивно:

double R(unsigned int n, double x)
{
    if (n == 0) return 1;
    if (n == 1) return x;
    return (2*n-1)*x*R(n-1,x)-R(n-2,x);
}

См. результаты: https://ideone.com/KcrNqo

Но такая рекурсия быстро станет крайне медленной - нужна мемоизация (сохранять один раз посчитанные значения в таблице и далее брать их оттуда).

4
  • Спасибо большое за ответ, но я забыл добавить, что нужно решить эту задачу именно с помощью рекурсии, поэтому я её и использую
    – Ive Karp
    6 ноя 2019 в 18:15
  • Блин, ну кто же так поступает?! Пишете неточное ТЗ, получаете в ответ ХЗ... См. дополненный ответ.
    – Harry
    6 ноя 2019 в 18:51
  • Чуть поофтоплю, не могу сдержаться :) Когда рекурсия быстро умирает из-за экспоненциального роста числа ветвей - это повод задуматься о ДП, и оно тут кажется очень даже к месту (вообще по моему опыту почти всегда если приходится делать кэширование - мемоизацию, то обычно алгоритм переписывается на ДП)...
    – zcorvid
    18 ноя 2019 в 8:10
  • @zcorvid Вообще-то мемоизация - и есть частный случай ДП...
    – Harry
    18 ноя 2019 в 8:36

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.