Задачи на эффективность |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Задачи на эффективность |
-Hex- |
Сообщение
#1
|
Гость |
подскажите решение:
1. дается упорядоченный массив типа 111..11100000...000. нужно опсчитать количество единиц в нем. нет проблем сделать это с эфективностью порядка логорифм М по основанию 2 (где М-длинна всего массива). требуется сделать это с эфективностью порядка логорифм N по основанию 2 (где N-количество единиц в массиве). для простоты длинну массива можно ограничить <20. 2. дается квадратная матрица размерности N. Требуется повернуть ее на 90 градусов используя минимум памяти. |
volvo |
Сообщение
#2
|
Гость |
|
Michael_Rybak |
Сообщение
#3
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата требуется сделать это с эфективностью порядка логорифм N по основанию 2 (где N-количество единиц в массиве). Сначала находишь наибольшее p такое, что a[2^p] = 1. Теперь пытаешься идти дальше с шагом 2^(p-1), уменьшая шаг в 2 раза каждый раз, когда упираешься в нолик. Цитата 2. дается квадратная матрица размерности N. Требуется повернуть ее на 90 градусов используя минимум памяти. Дополнительная память - O(1). Крутятся по отдельности,прямо на месте, четверки (x, y)->(n-y+1, x)->(n-x+1, n-y+1)->(y, n-x+1). Нумерация строк и столбцов - с единицы. |
Гость |
Сообщение
#4
|
Гость |
2volvo, Michael_Rybak
спасибо) 2Michael_Rybak не понял это - a[2^p] = 1 что такое р, что такое а? |
Michael_Rybak |
Сообщение
#5
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
a - это заданный массив, p - это число, которое надо найти циклом for. А 2^p - это 2 в степени p.
|
-Hex- |
Сообщение
#6
|
Гость |
a - это заданный массив, p - это число, которое надо найти циклом for. А 2^p - это 2 в степени p. чет не догоняю... Цитата Сначала находишь наибольшее p такое, что a[2^p] = 1. Теперь пытаешься идти дальше с шагом 2^(p-1), уменьшая шаг в 2 раза каждый раз, когда упираешься в нолик. вообще не врубаюсь.. ты пишеш что сначала надо найти индекс последней единицы(a[2^p] = 1, p max), и дальше что то с ним сделать?? но индекс последней еденици это не "сначала", это и есть требование задачи... как я его нахожу, в этом и вопрос... обьясни плиз поподробней. |
Michael_Rybak |
Сообщение
#7
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата ты пишеш что сначала надо найти индекс последней единицы(a[2^p] = 1, p max) Не последней единицы, а *наибольшей степени двойки* такой, что в этом месте стоит единица. Цитата обьясни плиз поподробней. Проще всего объяснить кодом: p := 0; |
Michael_Rybak |
Сообщение
#8
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Косячек небольшой: после step := 1 shl p; надо вставить строку "p := 1 shl p"
|
-Hex- |
Сообщение
#9
|
Гость |
О! пасиб)
что то уже прояснилось, только вот оператор shl мы еще не проходили, можеш переписать код без него? |
volvo |
Сообщение
#10
|
Гость |
Ну возьми, и перепиши... Shl - это возведение 2-ки в соответствующую степень... Замени его простым циклом, в котором происходит умножение на 2...
|
Текстовая версия | 23.12.2024 21:12 |