вычислить функцию

Условие задачи
Вычислите функцию:
$$f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}$$
Входные данные
Одно натуральное число $n$ $(1 \leq n \leq 10^{12})$
Выходные данные
Значение $f(n)$ , взятое по модулю $2^{32}$.
Тесты

Входные данные	Выходные данные
10	7
123	229966
1	1
100	136345
51	5092

Код программы

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.HashMap;
import java.lang.Math;

class Main
{

    private static long mod = 1L << 32;
    public static Map<Long, Long> mp = new HashMap<Long, Long>();

    public static long f(long n) {
        if (n <= 2) {
            return 1;
        }
        if (mp.containsKey(n)) {
            return mp.get(n);
        }
        if (n % 2 == 1) {
            long d = (f(6 * n / 7) % mod + f(2 * n / 3) % mod) % mod;
            mp.put(n, d);
            return mp.get(n);
        }
        long o = (f(n - 1) % mod + f(n - 3) % mod) % mod;
        mp.put(n, o);
        return mp.get(n);
    }


    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = bufferedReader.readLine().split(" ");
        long n;
        n = Long.parseLong(params1[0]);
        System.out.print(f(n));
    }
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Map;

import java.util.HashMap;

import java.lang.Math;

class Main

{

private static long mod = 1L << 32;

public static Map<Long, Long> mp = new HashMap<Long, Long>();

public static long f(long n) {

if (n <= 2) {

return 1;

}

if (mp.containsKey(n)) {

return mp.get(n);

}

if (n % 2 == 1) {

long d = (f(6 * n / 7) % mod + f(2 * n / 3) % mod) % mod;

mp.put(n, d);

return mp.get(n);

}

long o = (f(n - 1) % mod + f(n - 3) % mod) % mod;

mp.put(n, o);

return mp.get(n);

}

public static void main (String[] args) throws java.lang.Exception

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

long n;

n = Long.parseLong(params1[0]);

System.out.print(f(n));

}

Решение задачи
Решение данной задачи стоит начать с написания рекурсивной функции для вычисления функций по условию задачи. Так как рекурсия будет довольно таки сложной и много раз повторяются одни и те же результаты при вызове функции, следовательно, программа будет долгое время обрабатывать нашу задачу. То есть, к примеру, на 5 и 20 итерации, возвращаемые значения функции могут совпасть, что без оптимизации будет просчитываться еще раз, а с оптимизацией функция уже знает, чему равно значение с данными аргументами.Далее, по условию, мы пишем наконец нашу функцию:

Если число, которое ввел пользователь, меньше либо равно двум, то наша функция возвращает значение один.
Если есть значение с таким же ключом, то оно возвращает значение.
Если число, которое ввел пользователь, дает остаток от деления один, то наша функция возвращает значение $f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor)$.
Во всех остальных случаях наша функция возвращает значение $f(n-1)+f(n-3)$.

Ссылки
Задача на сайте e-olymp
Код решения в Ideone

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: вычислить функцию

e-olymp 1868. Функция

10

7

123

229966

1

1

100

136345

51

5092