Sonsuz ardıcıllıq#1211

Sonsuz ardıcıllıq (Həll təhlili)

Bütün $A_{i} (i = 0, 1, ..., n)$ A_i~(i = 0, 1, ..., n) qiymətlərini bir massivlə hesablamaq mümkün deyil, çünki $n \leq 1 0^{12}$ n \le 10^{12} məhdudiyyəti var. Nəticələri yadda saxlamaq üçün map adlanan verilənlər strukturundan istifadə edəcəyik: $A_{i}$ A_i dəyərini $m [i]$ olaraq saxlayacağıq. $A_{n}$ A_n dəyərini hesablamaq üçün ara nəticələri yadda saxlayaraq edəcəyik.

Alqoritmin reallaşdırılması

$A_{i}$ A_i dəyərlərini saxlamag üçün, m dəyişəni elan edəcəyik.

map<long long,long long> m;

calc funksiyası $m [n]$ dəyərini qaytarır.

long long calc(long long n, int p, int q)
{
  if (n == 0) return 1;
  if (m.count(n) > 0) return m[n];
  return m[n] = calc(n/p,p,q) + calc(n/q,p,q);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%lld %lld %lld",&n,&p,&q);

Cavabı hesablayır və çıxarırıq.

res = calc(n,p,q);
printf("%lld\n",res);

Java reallaşdırılması

import java.util.*;

public class Main
{
  static Map<Long, Long> m = new HashMap<Long, Long>();
  
  public static long calc(long n, long p, long q)
  {
    if (m.containsKey(n)) return m.get(n);
    if (n == 0) return 1;
    long res = calc(n/p,p,q) + calc(n/q,p,q);
    m.put(n,res);
    return res;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long n = con.nextLong(), 
         p = con.nextLong(), 
         q = con.nextLong();
    System.out.println(calc(n,p,q));
  }
}

Java