1

Тема: Знайти значення функції

Знайти значення функції:
f(x,y)=
          0, x<=0 or y<=0;
          f(x-1,y-2)+f(x-2,y-1)+2, x<=y;
          f(x-2,y-2)+1, x>y.

Вхідні дані:
Два цілих числа x, y (0 ≤ x, y ≤ 50).

Вихідні дані
Вивести значення функції f(x,y).

Вхідні дані #1
2 3
Вихідні дані #1
4

Вхідні дані #2
34 12
Вихідні дані #2
6

Мій варіант рішення:

#include <iostream>
using namespace std;
long long f(long long x, long long y)
{
    if ((x<=0) || (y<=0)) return 0;
    else if (x<=y) return f(x-1,y-2)+f(x-2,y-1)+2;
    else if (x>y) return f(x-2,y-2)+1;
}
int main()
{
    long long x,y;
    cin>>x>>y;
    cout<<f(x,y)<<endl;
    return 0;
}

Проблема полягає в тому, що якщо зазначену функцію реалізувати безпосередньо, то навіть для невеликих значень х,y програма буде працювати довго через присутню рекурсію.
Тому програма проходить не всі тести. Як можна удосконалити рекурсивну функцію?

Подякували: Arete, koala2

2

Re: Знайти значення функції

Задачу треба розв'язати лише для 0 ≤ x, y ≤ 50. Найпростіше - створити двовимірний масив 50 на 50 і заповнити його з менших значень до більших, а потім брати звідти дані.
Втім, можу ще звернути увагу, що для випадку x>y наступний крок рекурсії буде братися за тою ж формулою - тобто
f(10,7) = f(8,5)+1 = f(6,3)+2 = f(4,1)+3 = f(2,-1)+4 = 4. Нескладно побачити, що нерекурсивна формула тут буде f(x,y)=(min(x,y)+1)/2 (ділення цілочисельне).
Ну і накидана за хвилинку програма на Python каже, що

>>> f(50,50)
1169627967

Що цілком вміщається в int.

Подякували: leofun01, aassii2

3

Re: Знайти значення функції

Окремо: вітаю на форумі і дякую за добре поставлене питання, на відміну від другої вашої теми.

4 Востаннє редагувалося aassii (09.01.2019 22:59:52)

Re: Знайти значення функції

вітаю на форумі і дякую за добре поставлене питання


Дякую.


Втім, можу ще звернути увагу, що для випадку x>y наступний крок рекурсії буде братися за тою ж формулою - тобто
f(10,7) = f(8,5)+1 = f(6,3)+2 = f(4,1)+3 = f(2,-1)+4 = 4. Нескладно побачити, що нерекурсивна формула тут буде f(x,y)=(min(x,y)+1)/2 (ділення цілочисельне).

Тобто програму можна записати так?

#include <iostream>
using namespace std;
long long f(long long x, long long y)
{
    if ((x<=0) || (y<=0)) return 0;
    else if (x<=y) return f(x-1,y-2)+f(x-2,y-1)+2;
    else if (x>y) return (min(x,y)+1)/2;
        //f(x-2,y-2)+1;
}
int main()
{
    long long x,y;
    cin>>x>>y;
    cout<<f(x,y)<<endl;
    return 0;
}

Хоча мені здається, що програма по часу не проходить деякі тести через:  f(x-1,y-2)+f(x-2,y-1)+2, x<=y;?

5

Re: Знайти значення функції

Найпростіше - створити двовимірний масив 50 на 50 і заповнити його з менших значень до більших, а потім брати звідти дані.

А як тоді вираховувати ці значення?

6

Re: Знайти значення функції

З попередньо обчислених в цьому ж масиві.

7

Re: Знайти значення функції

#include <iostream>
using namespace std;

int vals[50][50];//значення індексів будуть на 1 менше, тобто f(1,1) == vals[0][0]

int f(int x, int y)
{
    return (x<=0 || y<=0) ? 0 : vals[x-1][y-1];
}

int main()
{
    for(int x=1;x<=50;++x)
        for(int y=1;y<=50;++y)
            vals[x-1][y-1] = (x<=y) ? f(x-1,y-2)+f(x-2,y-1)+2 : f(x-2,y-2)+1;
    long long x,y;
    cin>>x>>y;
    cout<<f(x,y)<<endl;
    return 0;
}
за що я люблю Python
from functools import lru_cache

@lru_cache(maxsize=2500)
def f(x,y):
    return 0 if x<=0 or y<=0 else \
        f(x-1,y-2)+f(x-2,y-1)+2 if x<=y else \
        f(x-2,y-2)+1

А по-хорошому тут слід було б вивести нерекурсивну формулу для другої половини, там щось схоже на трикутник Паскаля ніби вимальовується. Але ліньки.

Подякували: aassii1

8

Re: Знайти значення функції

koala, дякую))

9

Re: Знайти значення функції

Хоча в Python набагато менший і красивіший код, але, якщо я не помиляюсь, програми на Python працюють трішки повільніше ніж на С++ і тому на олімпіадах ліміт часу на програми в Python трішки збільшують.

10

Re: Знайти значення функції

aassii написав:

Хоча в Python набагато менший і красивіший код, але, якщо я не помиляюсь, програми на Python працюють трішки повільніше ніж на С++ і тому на олімпіадах ліміт часу на програми в Python трішки збільшують.

Є така проблема. Але неоптимальний код збільшує час значно сильніше за накладні витрати Python. Так що для навчання й олімпіад Python - те, що треба, а от для високонавантажених систем краще брати C/C++ і лізти в асемблерний код у критичних місцях.

Подякували: leofun011