Tək bölənlər#1520

Tək bölənlər (Həll təhlili)

Əgər $n$ ədədi təkdirsə, onda $f (n) = n$ f(n) = n.

Əgər $n$ ədədi cütdürsə, onda $f (n) = f (n /2)$ f(n) = f(n / 2).

Güman edək ki,

g (n) = f (1) + f (2) + ... + f (n)

g(n) = f(1) + f(2) + ... + f(n)

Təbii ədədlər çoxluğunu $1$ -dən $n$ -ə qədər iki altçoxluğa bölək:

ODD — tək ədədlər çoxluğu,
EVEN — cüt ədədlər çoxluğu.

$1$ -dən $n$ -ə qədər olan təbii ədədlər içərisində dəqiq olaraq:

$k = ⌊ (n + 1) /2 ⌋$ k = \left\lfloor (n + 1) / 2 \right\rfloor tək ədədlər,
$l = ⌊ n /2 ⌋$ l = \left\lfloor n / 2 \right\rfloor cüt ədədlər vardır.

O zaman:

f (1) + f (3) + f (5) + ... + f (2 k - 1) = 1 + 3 + 5 + \dots + (2 k - 1) = \frac{1 + 2 k - 1}{2} \cdot k = k^{2}

f(1) + f(3) + f(5) + ... + f(2k - 1) = \\ 1 + 3 + 5 + … + (2k - 1) = \\ {1 +2k - 1\over 2} \cdot k = k^2

Eyni zamanda:

f (2) + f (4) + f (6) + ... + f (2 l) = f (1) + f (2) + f (3) + ... + f (l) = g (l) = g (⌊ n /2 ⌋)

f(2) + f(4) + f(6) + ... + f(2l) = \\ f(1) + f(2) + f(3) + ... + f(l) = \\ g(l) = g(\left\lfloor n / 2 \right\rfloor)

Rekursiyanın bitməsini təmin edək ki, $g (0) = 0$ g(0) = 0. Beləliklə,

g (n) = {k^{2} + g (⌊ n /2 ⌋), k = (⌊ n + 1) /2 ⌋ 0, n = 0

g(n) = \begin{cases} k^2 + g(\left\lfloor n / 2 \right\rfloor), k = (\left\lfloor n + 1) / 2 \right\rfloor \\ 0, n = 0 \end{cases}

Nümunə

İlk testi nəzərdən keçirək, harada $n = 7$ n = 7.

$1$ -dən $7$ -ə qədər olan təbii ədədlər içərisində dəqiq olaraq:

$k = ⌊ (7 + 1) /2 ⌋ = 4$ k = \left\lfloor (7 + 1) / 2 \right\rfloor = 4 tək ədədlər,
$l = ⌊ 7/2 ⌋ = 3$ l = \left\lfloor 7 / 2 \right\rfloor = 3 cüt ədədlər vardır.

g (7) = ⌊ \frac{7 + 1}{2} ⌋^{2} + g (⌊ \frac{7}{2} ⌋) = 16 + g (3) = 16 + ⌊ \frac{3 + 1}{2} ⌋^{2} + g (⌊ \frac{3}{2} ⌋) = 16 + 4 + g (1) = 16 + 4 + 1 = 21

g(7) = \left\lfloor 7 + 1 \over 2 \right\rfloor^2 + g\left(\left\lfloor 7 \over 2 \right\rfloor\right) = 16 + g(3) = \\ 16 + \left\lfloor 3 + 1 \over 2 \right\rfloor^2 + g\left(\left\lfloor 3 \over 2 \right\rfloor\right) = 16 + 4 + g(1) = 16 + 4 + 1 = 21

Alqoritmin realizasiyası

g funksiyasını reallaşdırırıq.

long long g(long long n)
{
  long long k = (n + 1) / 2;
  if (n == 0) return 0;
  return k * k + g(n / 2);
}

Proqramın əsas hissəsi. Hər bir test üçün giriş dəyəri $n$ -ı oxuyur və $g (n)$ -ı çıxarır.

while(scanf("%lld",&n) == 1)
  printf("%lld\n",g(n));

Java realizasiyası

import java.util.*;

public class Main
{
  static long g(long n)
  {
    long k = (n + 1) / 2;
    if (n == 0) return 0;
    return k * k + g(n / 2);
  }
	
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    while(con.hasNext())
    {
      long n = con.nextLong();
      System.out.println(g(n));
    }
  }
}

Java

Python realizasiyası

g funksiyasını reallaşdırırıq.

def g(n):
  if n == 0:
    return 0
  k = (n + 1) // 2
  return k * k + g(n // 2)

Proqramın əsas hissəsi. Hər bir test üçün giriş dəyəri $n$ -ı oxuyur və $g (n)$ -ı çıxarır.

for line in sys.stdin:
  n = int(line)
  print(g(n))