Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Задачи на эффективность

Автор: -Hex- 12.01.2007 1:48

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

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

2. дается квадратная матрица размерности N. Требуется повернуть ее на 90 градусов используя минимум памяти.

Автор: volvo 12.01.2007 1:59

#2: http://forum.pascal.net.ru/index.php?s=&showtopic=3371&view=findpost&p=61325

Автор: Michael_Rybak 12.01.2007 2:04

Цитата
требуется сделать это с эфективностью порядка логорифм 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). Нумерация строк и столбцов - с единицы.

Автор: Гость 12.01.2007 2:16

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

2Michael_Rybak
не понял это - a[2^p] = 1
что такое р, что такое а?

Автор: Michael_Rybak 12.01.2007 2:48

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

Автор: -Hex- 15.01.2007 7:09

Цитата(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), и дальше что то с ним сделать?? но индекс последней еденици это не "сначала", это и есть требование задачи... как я его нахожу, в этом и вопрос...
обьясни плиз поподробней.

Автор: Michael_Rybak 15.01.2007 7:53

Цитата
ты пишеш что сначала надо найти индекс последней единицы(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;

Автор: Michael_Rybak 15.01.2007 8:22

Косячек небольшой: после step := 1 shl p; надо вставить строку "p := 1 shl p"

Автор: -Hex- 17.01.2007 0:19

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

Автор: volvo 17.01.2007 0:22

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