Распечатать полином, используя минимальное количество вызовов

Question

Я продолжаю получать эти трудные вопросы интервью.Это действительно сбивает меня с толку.

Вам дана функция poly, которая принимает и возвращает int.На самом деле это полином с неотрицательными целыми коэффициентами, но вы не знаете, что это за коэффициенты.

Вы должны написать функцию, которая определяет коэффициенты, используя как можно меньше вызовов poly.

Моя идея состоит в том, чтобы использовать рекурсию, зная, что я могу получить последний коэффициент на poly(0).Поэтому я хочу заменить poly на (poly - poly(0))/x, но я не знаю, как это сделать в коде, так как я могу вызвать только poly.У кого-нибудь есть идеи, как это сделать?

Answer 1

Вот хитрый трюк.

int N = poly(1)

Теперь мы знаем, что каждый коэффициент в полиноме не больше N.

int B = poly(N+1)

Теперь разверните B в базе N+1, и у вас есть коэффициенты.

---

Попытка объяснения: алгебраически, многочлен будет

poly = p_0 + p_1 * x + p_2 * x^2 + ... + p_k * x^k

Если у вас естьчисло b и разверните его в базе n, тогда вы получите

b = b_0 + b_1 * n + b_2 * n^2 + ...

, где каждый b_i уникально определен и b_i < n.