Рекуррентость о двух переменных

[wolf.ram]

$f(0,b) = 0;$
$f(a,b) = (b \operatorname{div} a) + f(b \mod a, a).$

a, b целые неотрицательные числа. div означает целочисленное деление. Интересно, можно ли привести данную рекуррентность к замкнутому виду?

[Xaositect]

Смотря что считать замкнутым видом. $f$ можно выразить через НОД.

[ИСН]

Короче, спуститься по алгоритму Евклида, суммируя все частные. Посмотрел графики. Мда... Ну, значит, судьба такая. Вряд ли это через что-нибудь как-нибудь.

[wolf.ram]

На НОД мне уже намекали в друго месте. Но НОД тоже не замкнут.

График хорош, да. По диагонали красиво: впадина и по краям два хребта.

Вообще формула получена для такой задачи: дан прямоугольник с целочисленными длинами сторон. На сколько квадратов его можно разделить, отрезая каждый раз квадрат наибольшего размера. Квадраты, разумеется, тоже целочисленнодлинные.

Вообще рекуррентность очень быстро сходится, замкнутая форма нужна из спортивного интереса.

[Xaositect]

Я все-таки напишу через НОД.
Если мы применяем второе правило к выражению $f(a,b) + c$: $f(a,b) + c = f(b \mathop{\mathrm{mod}} a, a) + b \mathop{\mathrm{div}} a + c = f(a',b')+c'$, то сумма $a+b+c = a'+b'+c'$
С помощью применения второго правила $f(a,b)$ преобразуется к $f(0,d)+c =c$, где $d$ - это НОД. $a+b = d+c$, $c = a + b - d$

[ИСН]

У Вас что, $b\mod a+b\mathop\mathrm{div} a = b$?

[wolf.ram]

А это разве не так?

[ИСН]

Так, если второе слагаемое умножить на a.

[wolf.ram]

По Тора пился.

[Xaositect]

wolf.ram в сообщении #541580 писал(а):

Так, если второе слагаемое умножить на a.

Ох, действительно, что это я.