Kart Evləri#5716

Kart Evləri (Həll təhlili)

$f (h)$ — card-evlərin hündürlüyünü qurmaq üçün lazım olan kartların sayı. Məsələn, $f (1) = 2, f (2) = 7, f (3) = 15$ f(1) = 2, f(2) = 7, f(3) = 15.

Hündürlüyü $h$ olan ev yaratmaq üçün əsasda $h - 1$ h - 1 örtüklü $h$ sayda $1$ hündürlükdə ev qurmaq lazımdır. Bunlara $2 h$ kart lazımdır, və üstəgəl $h - 1$ h - 1 örtük. Daha sonra bu əsasa $h - 1$ h - 1 hündürlükdə bir ev qurulur, bunun üçün $f (h - 1)$ f(h - 1) kart lazımdır.

Beləliklə,

f (h) = 2 h + h - 1 + f (h - 1)

f(h) = 2h + h - 1 + f(h - 1)

və ya

f (h) = 3 h - 1 + f (h - 1)

f(h) = 3h - 1 + f(h - 1)

Açıq formulu çıxaraq. Rekursiyanı ard-arda açaraq alırıq:

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

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

Nümunə

Hündürlüyü $1$ olan ev üçün $2$ kart kifayətdir.

Hündürlüyü $2$ olan ev üçün $7$ kart lazımdır.

Hündürlüyü $3$ olan ev $15$ kartdan tikilə bilər.

Alqoritmin həyata keçirilməsi

Ev hündürlüyü olan $n$ oxunur.

scanf("%lld", &n);

Ev kart sayını hesablayır və çap edirik.

res = n * (3 * n + 1) / 2;
printf("%lld\n", res);