Kök, logaritm, sinus#1207

Kök, logaritm, sinus (Həll təhlili)

$x_{i}$ x_i dəyərini $f (i)$ funksiyası vasitəsilə hesablayacağıq. Bunun üçün təkrarlanma relasiyasını həyata keçirmək lazımdır

f (i) = f (⌊ i - i ⌋) + f (⌊ l n (i)⌋) + f (⌊ i \cdot s i n^{2} (i)⌋)

f(i) = f(\lfloor i - \sqrt{i} \rfloor) + f(\lfloor ln(i) \rfloor) + f(\lfloor i \cdot sin^2(i) \rfloor)

f (0) = 1

f(0) = 1

$f (i)$ dəyərlərini $1 0^{6}$ 10^6 ölçülü xətti massivdə $d p$ yadda saxlamağa görə.

Alqoritmin həyata keçirilməsi

$x_{i}$ x_i dəyərləri $d p$ massivində saxlanılacaq.

#define MAX 1000001
int dp[MAX];

$f (n)$ funksiyası $x_{n}$ x_n dəyərini hesablayır.

int f(int n)
{

Rekursiyanın bitmə şərti.

  if (n == 0) return 1;

Əgər $x_{n}$ x_n dəyəri artıq hesablanmışdırsa ( $d p [n] \neq = - 1$ dp [n] \ne -1 ), geri qaytarırıq.

  if (dp[n] != -1) return dp[n];

Birinci, ikinci və üçüncü termləri rekursiv şəkildə hesablayırıq.

  int a = f((int)(n - sqrt(n)));
  int b = f((int)(log(n)));
  int c = f((int)(n * sin(n) * sin(n)));

$x_{n}$ x_n dəyərini hesablayır, yadda saxlayır və geri qaytarırıq.

  return dp[n] = (a + b + c) % 1000000;
}

Proqramın əsas hissəsi. $x_{i}$ x_i dəyəri hələ hesablanmayıbsa $d p [i] = - 1$ dp[i] = -1 qəbul edək.

memset(dp,-1,sizeof(dp));

Bir neçə testi işləyirik. Hər bir $n$ dəyəri üçün cavabı göstəririk.

while(scanf("%d",&n), n != -1)
  printf("%d\n",f(n));

Alqoritmin həyata keçirilməsi — rekursiv olmayan

$x_{i}$ x_i dəyərləri $x$ massivində saxlanılacaq.

int x[1000001];

$x$ massivinin elementlərini verilmiş təkrarlanma relasiyası ilə doldururuq.

x[0] = 1;
for (i = 1; i <= 1000000; i++)
  x[i] = (x[(int)(i - sqrt(i))] + x[(int)(log(i))] +
          x[(int)(i * sin(i) * sin(i))]) % 1000000;

Bir neçə testi işləyirik. Hər bir $n$ dəyəri üçün cavabı göstəririk.

while (scanf("%d", &n), n != -1)
  printf("%d\n", x[n]);

Java ilə həyata keçirilməsi

import java.util.*;

public class Main
{
  static int dp[] = new int[1000001];

  static int f(int n)
  {
    if (n == 0) return 1;
    if (dp[n] != -1) return dp[n];
    
    int a = f((int)(n - Math.sqrt(n)));
    int b = f((int)(Math.log(n)));
    int c = f((int)(n * Math.sin(n) * Math.sin(n)));
    return dp[n] = (a + b + c) % 1000000;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    Arrays.fill(dp, -1);
    while(true)
    {
      int n = con.nextInt();
      if (n == -1) break;
      System.out.println(f(n));
    }
    con.close();
  }
}

Java

Python ilə həyata keçirilməsi

import math

$x$ massivini inizializasiya edirik.

x = [0] * 1000001
x[0] = 1

$x$ massivinin elementlərini verilmiş təkrarlanma relasiyası ilə doldururuq.

for i in range(1, 1000001):
  x[i] = (x[int(i - math.sqrt(i))] +
          x[int(math.log(i))] +
          x[int(i * math.sin(i)**2)]) % 1000000

Bir neçə testi işləyirik. Hər bir $n$ dəyəri üçün cavabı göstəririk.

while True:
  n = int(input())
  if n == -1:
    break
  print(x[n])