Матч 389, Приближенное вычисление (ApproximateDivision)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Деление является дорогостоящей операцией, если только делитель не равен 2. Представим обращение натурального числа b в виде суммы:

где t равно наименьшей степени 2, большей или равной b. Вычислить значение a / b, умножив обращенное значение 1 / b на а. Значение 1 / b следует вычислить по указанной формуле, взяв ровно terms слагаемых.

Класс: ApproximateDivision

Метод: double quotient(int a, int b, int terms)

Ограничения: 1 £ b £ 10000, 0 £ a £ b, 1 £ terms £ 20.

Вход. Целые числа a, b и res.

Выход. Значение a / b, равное (1 / b) * a.

Пример входа

a	b	terms
2	5	2
7	8	5
1	3	10
50	50	1

Пример выхода

0.34375

0.875

0.33333301544189453

0.78125

РЕШЕНИЕ

простые вычисления

Вычислим значение t, равное наименьшей степени 2, большей или равной b. Поскольку b = t – c, то c = b – t. Далее производим суммирование первых terms слагаемых.

ПРОГРАММА

#include <stdio.h>

class ApproximateDivision

{

public:

double quotient(int a, int b, int terms)

{

int c, t = 1;

double res, current;

while(t < b) t *= 2;

c = t - b; current = res = 1.0 / t; terms--;

while(terms--)

{

current *= 1.0 * c / t;

res += current;

}

return res * a;

}

};