September 18th, 2014

Def kz

Хватит политоты

Вот вам простая задачка из разряда математики.

Есть целое неотрицательное число X, нужно найти два таких целых числа A, B (A < X, B < X, Amax * Bmax > X), чтобы A * B был максимально приближен к X. Естественно, это должно быть сделано без перебора, таблиц и за приемлимый промежуток времени.

В большинстве своем задача решается просто - A = Amax, B = X / A. Решение простое, быстрое, но гарантирует примерный результат. Вопрос простой, можно ли его улучшить в приемлимый промежуток времени?

Практически в железе подобная задача используется для рассчета предделителя. Например, нужно сделать генерацию сигнала частотой 40КГц. Примерный результат даст нам, скажем, 40020 Гц. Где-то это приемлимо, а где-то не очень...