Почти "классические" задачи

From

Victor Petrenko (2:5061/52)

To

All

Date

2002-05-08T15:52:52Z

Area

RU.ALGORITHMS

Привет All!

===  ===
1. Возведение в целую степень
Составить алгоритм, который определяет наименьшее количество умножений, за
которое можно возвести число A в целую степень n. Разрешается производить только
умножения и присваивания. Составить таблицу троек (i, наименьшее количество
умножений при возведении A в степень i, вариант умножения), i=1..n, для как
можно больших n.

2. Интервальный поиск с подсчетом
Имеется база данных служащих некоторой компании. Предполагается, что количество служащих равно n, где n велико, и база данных фиксирована (не меняется с
течением времени). Требуется разработать эффективный алгоритм для реализации
запросов вида "определить количество служащих, жалование которых находится в
диапазоне [a,b] (вне диапазона [a,b]) и рейтинг - в диапазоне [c,d] (вне
диапазона [c,d])", где жалование, рейтинг, а также числа a,b,c,d - вещественные.

3. Обход конем шахматной доски
Обойти шахматным конем доску n x n, начав с клетки (x1,y1) и закончив в клетке
(x2,y2) и побывав в каждой клетке ровно 1 раз. Программа должна выдавать для
данной клетки (x1,y1) по каждой клетке (x2,y2), не совпадающей с (x1,y1), время расчета в секундах с точностью до десятых, путь или информацию о невозможности
пути. Условия отсечения должны быть сформулированы словесно (в тексте программы в виде комментариев).

От составителей.
Все задачи являются, в каком-то смысле, классическими. Однако, доведение до
уровня программы даже известных алгоритмов часто приводит к необходимости
решения совершенно неожиданных проблем. В задаче 3, например, классический
алгоритм перебора с возвратом работает катастрофически долго даже при n=8. При
переборе необходимо выбрать хорошие условия отсечения.
===  ===

Большая просьба откликнуться на это письмо и ответить на следующие вопросы:

1. Какую литературу бы вы порекомендовали в связи с этими задачами?

2. Предполагая сабж, есть подозрения, что эти задачи в литературе уже проработаны и есть какие-то мысли по этому поводу. Что посоветуете почитать и где это может быть?

3. Всячески приветствуются мысли по решению этих задач. Любые размышления и предположения по поводу алгоритмов для их решения.

       Teams: [DreamWeb] [Eloy]

С уважением, Victor Petrenko.

--- //KMS //AsmOS (http://asmdev.narod.ru/)
 * Origin: От стpаданья одно сpедство-не влюбляйся с малолетства (2:5061/52)