Мне неприятно это говорить, но это тривиально простой вопрос для курса по структурам данных.Я не хочу быть грубым или злым, или что-то в этом роде, но это примерно так просто, как получают эти вопросы.
Но вы просили предложения, а не решения.Это хорошая вещь.: -)
Я бы начал с того, чтобы убедиться, что вы знаете определение коэффициента ветвления.Затем я бы выбрал пару простых значений для k, n вроде (1,1) (2,2) (3,2) и посмотрю, каков результат.Я обещаю вам, что появится шаблон!
Редактировать:
Итак, вы понимаете фактор ветвления.Давайте посмотрим на минимум.
Если у вас есть глубина k, вы знаете, что вы можете перемещаться по k различным узлам, верно?Поэтому, если ни один из этих узлов не имеет других дочерних узлов, а конечный узел не имеет дочерних узлов, что вы можете сказать об этих узлах?
Хорошо, это было легко.Максимум немного сложнее, но все же довольно просто.Самый простой способ взглянуть на это - меньше думать, как дерево.Деревья имеют верхушку и спускаются.Вместо этого думайте об этом как о серии концентрических кругов, каждый из которых представляет уровень глубины.
Давайте начнем с (глубины = 1).Вы знаете, что у вас будет только один узел, верно?Я имею в виду, что у него не может быть детей, потому что вы ограничены 1 глубиной!Теперь давайте посмотрим на глубину 2. Начальный узел может иметь n (при условии, что n является фактором ветвления) дочерних узлов.Так что это будет n + 1.
Теперь, если мы добавим еще один к этому, мы получим n узлов на «внешнем кольце», каждый из которых может иметь n дочерних элементов.Таким образом, вы получите n * n + n + 1.
На каждом последующем кольце вы получите (узлы, добавленные в последний раз) * (коэффициент ветвления) + все существующие узлы.Теперь вы можете придумать способ выразить это как формулу?