IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Задачи на эффективность
сообщение
Сообщение #1


Гость






подскажите решение:
1. дается упорядоченный массив типа 111..11100000...000. нужно опсчитать количество единиц в нем.

нет проблем сделать это с эфективностью порядка логорифм М по основанию 2 (где М-длинна всего массива).
требуется сделать это с эфективностью порядка логорифм N по основанию 2 (где N-количество единиц в массиве).
для простоты длинну массива можно ограничить <20.

2. дается квадратная матрица размерности N. Требуется повернуть ее на 90 градусов используя минимум памяти.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






#2: Модификация двумерных массивов
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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). Нумерация строк и столбцов - с единицы.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






2volvo, Michael_Rybak
спасибо)

2Michael_Rybak
не понял это - a[2^p] = 1
что такое р, что такое а?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


a - это заданный массив, p - это число, которое надо найти циклом for. А 2^p - это 2 в степени p.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Цитата(Michael_Rybak @ 11.01.2007 22:48) *

a - это заданный массив, p - это число, которое надо найти циклом for. А 2^p - это 2 в степени p.


чет не догоняю...
Цитата
Сначала находишь наибольшее p такое, что a[2^p] = 1. Теперь пытаешься идти дальше с шагом 2^(p-1), уменьшая шаг в 2 раза каждый раз, когда упираешься в нолик.


вообще не врубаюсь.. ты пишеш что сначала надо найти индекс последней единицы(a[2^p] = 1, p max), и дальше что то с ним сделать?? но индекс последней еденици это не "сначала", это и есть требование задачи... как я его нахожу, в этом и вопрос...
обьясни плиз поподробней.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
ты пишеш что сначала надо найти индекс последней единицы(a[2^p] = 1, p max)


Не последней единицы, а *наибольшей степени двойки* такой, что в этом месте стоит единица.

Цитата
обьясни плиз поподробней.


Проще всего объяснить кодом:

p := 0;
while a[1 shl (p + 1)] = 1 do
p := p + 1;

step := 1 shl p;
while step > 0 do begin
if a[p + step] = 1 then
p := p + step;
step := step div 2;
end;
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Косячек небольшой: после step := 1 shl p; надо вставить строку "p := 1 shl p"
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






О! пасиб)
что то уже прояснилось, только вот оператор shl мы еще не проходили, можеш переписать код без него?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Ну возьми, и перепиши... Shl - это возведение 2-ки в соответствующую степень... Замени его простым циклом, в котором происходит умножение на 2...
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.12.2024 21:12
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name