Здравствуйте, Pushkin, Вы писали:


P>

P>N+(N+K-3)/(K-1)
P>

P>Или, если кому милее, так

P>

P>(N*K+K-3)/(K-1)
P>

А как это выводится?
В частности откуда -3?

Здравствуйте, UgN, Вы писали:

UgN>( N / K + N + ( 2 — ( N % K + N — 1 ) / N ) );

Давай подставим какой-нибудь простейший случай, чтобы выяснить все недоразумения

N=5 K=2

Очевидно дерево такое (о-листья, х-развилки)

        х
      /   \
    х      х
   / \    / \
  х   о  о   о
 / \   
о   о

Всего узлов 9 (всяких — именно это и спрашивалось)

Теперь считаем по-твоему

5/2 + 5 — ( 5%2 + 5 — 1 ) / 5 = 2 + 5 — ( 1 + 5 — 1 ) / 5 = 8

Считаем как учил MichaelP

5 + (5+2-3)/(2-1) = 5 + 4 = 9

Здравствуйте, UgN, Вы писали:

UgN>Здравствуйте, Pushkin, Вы писали:

UgN>
P>>

P>>N+(N+K-3)/(K-1)
P>>

P>>Или, если кому милее, так

P>>

P>>(N*K+K-3)/(K-1)
P>>

UgN>А как это выводится?
UgN>В частности откуда -3?

1) ceil (X/Y) для целых X и Y переписывается всегда как (X+Y-1)/Y (это думаю все знают, но можно проверит на примерах)

2) в целых числах прекрасно работает обычное справило сложения дробей X/Y+Z = (X+Z*Y)/Y

Поэтому взяв исходную формулу имеем

N + ceil(1.0*(N-1)/(K-1)) =
N + ((N-1)+(K-1)-1)/(K-1) =
N + (N+K-3)/(K-1) =
(N*(K-1)+N+K-3)/(K-1) = (N*K+K-3)/(K-1)

Прости за такое количество математики

Что касается вывода основной формулы, то вот моё изложение, може оно будет понятней:
Каждое разветвление заменяет K узлов на 1, т.е. убивает K-1 узлов
Было N узлов, остался один верхний — надо убить N-1.
Причём гарантированно, поэтому круглим вверх.
Итого (N-1)/(K-1) с округлением вверх.

Здравствуйте, Pushkin, Вы писали:

P>Давай подставим какой-нибудь простейший случай, чтобы выяснить все недоразумения

А какие недоразумения?

Я уже отметил свое согласие с MichaelP и Pushkin (кто это такой, не знаешь?)

P>N=5 K=2

P>Очевидно дерево такое (о-листья, х-развилки)

P>

P>        х
P>      /   \
P>    x      х
P>   / \    / \
P>  х   о  о   о
P> / \   
P>о   о
P>

P>Всего узлов 9 (всяких — именно это и спрашивалось)

Согласен.

Глюканул где-то.