Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет qwerty ([info]qwerty)
@ 2010-01-24 17:11:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Задачка

Есть одномерный массив целых. В начале его расположен массив A длиной a, в конце B длиной b, а посредине не интересующий нас мусор длиной c. Требуется красивым образом переместить B в начало, за ним расположить A, причем сделав при этом не более a+b чтений и записей в массив. Судьба мусора не интересует. Файлы, посторонняя память и рекурсия категорически отсутствуют.


(Читать комментарии) - (Добавить комментарий)


[info]crazyhome.livejournal.com
2010-01-25 14:58 (ссылка)
x[b+1]=x[1]; x[1]=x[a+c+1];
x[b+2]=x[2]; x[2]=x[a+c+2];
...

(Ответить) (Ветвь дискуссии)


[info]qwerty
2010-01-25 15:10 (ссылка)
Все бы ничего, но ведь вы пишите в тот же массив, из которого читаете. И в том месте, куда вы пишите, не обязательно лежит мусор. А зависит это от соотношений между a, b и c.

И, разумеется, если бы эта задачка решалась таким простым образом, в ней не было бы ничего интересного.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]crazyhome.livejournal.com
2010-01-25 16:59 (ссылка)
Хотел кратко, но, видимо, надо пояснить.
У меня идут пары присваивания. В какой-то момент пары прекращаются и остается только одно из двух (какое из двух - в зависимости от того, что больше - а или b). Первое из пары - это перемещение массива А на свое место и освобождение места под В; второе из пары - это перемещение массива B на свое место (там, где был только что элемент из А).
В том месте, куда я пишу, лежит или мусор (первое присваивание из пары), или "уже мусор" (второе присваивание из пары; это элемент массива А или B, который уже перемещен на свое место в первом присваивании из пары, и свое старое место освободил для другого элемента массива).
В общем, суть в том, что массивы перемещаются не "по очереди" (сначала весь один массив, а потом весь другой), а "параллельно" (одни элемент из А, один элемент их B, одни элемент из А, один элемент их B и т.д.).

(Ответить) (Уровень выше)


[info]crazyhome.livejournal.com
2010-01-25 17:02 (ссылка)
Посмотрел коммент ниже и понял, что мой способ работает только при c>0. А при с=0, по-моему, вообще нельзя, если посторонняя память не используется.

(Ответить) (Уровень выше)


[info]crazyhome.livejournal.com
2010-01-25 17:47 (ссылка)
А, понял... Немного недодумал ;) ppkk - додумал ;)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ppkk
2010-01-25 20:27 (ссылка)
Но я неправильно написал: поторопился, не проверил. В моём понимании условий либо этот алгоритм работал, либо невозможно (причём я подразумевал наличие нескольких целочисленных переменных).

http://lj.rossia.org/users/qwerty/132388.html?thread=503332#t503332 — для этого не работает.

Похоже, что какие-то недомолвки имеются, какие-то вольности с арифметическими действиями или посторонней памятью. Пока я деталей не пойму, как идёт учёт действий при a=1, c=0 и b=1, исправлять ошибку свою не берусь.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2010-01-26 00:04 (ссылка)
Ну, давайте считать, что у нас имеется абстрактный вычислитель load-store архитектуры с 8 или 16 регистрами общего назначения, некоторым набором 2-адресных инструкций, оперативной памятью ровно в размер упомянутого массива и памятью и достаточным количеством памяти для хранения инструкций программы, с которой больше ничего делать нельзя. К вычислителю Дед Мороз приложил простой компилятор с Ц-подобного языка, который все локальные переменные отводит в регистрах, а если не может этого сделать, то ломается.

(Ответить) (Уровень выше)


(Читать комментарии) -