|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Victor Petrenko 2:5061/52 08 May 2002 15:52:52
To : All
Subject : Почти "классические" задачи
--------------------------------------------------------------------------------
=== ===
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
