Задачи на эффективность Опции

[-Hex-]

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

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

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

[volvo]

#2: Модификация двумерных массивов

[Michael_Rybak]

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

[Гость]

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

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

[Michael_Rybak]

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

[-Hex-]

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

чет не догоняю...

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

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

[Michael_Rybak]

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

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

[-Hex-]

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

[volvo]

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