Попробуйте решить интересную задачу...
 

Итак предположим мы собираем данные в условиях жесткого аппаратного недостатка.
У нас есть буффер содержащий 978 чисел (каждое занимает 2 байта и уникально), все из которых находятся в диапазоне от 0 до 1500.
Так же предположим, что буффер устроен так: после прочтения - данные в нем стираются.
Надо написать алгоритм для устройства, которое прочтет эти данные и отсортирует их. У устройства есть одно ограничение - буффер данных всего - лишь 197 байтов. Программа - будет прошита в пзу и ей озу не надо.
Итак:
1. Нужно прочесть 978 чисел (при том, что это возможно всего лишь однажды. Читаются они, кстати, последовательно, как в файле) в диапазоне [0, 1500].
2. Отсортировать их в памяти размер которой 197 байтов.
3. записать обратно в буффер в нужном порядке, что бы следующее устройство провело статистический анализ (for example).

Жду решений :) .

>Так же предположим, что буффер устроен так: после прочтения - данные в нем стираются.

не понял - oна автоматом стирается ? Т.е. максимум, что я могу сделать с данными буфера[978*2] - всего 1 раз закинуть его кусочек в буфер[197] ?

Поставлю задачу снова:

Итак:
1. Памяти у тебя всего 197 байтов.
2. В устройстве записанно 987 чисел в диапазоне 1 до 1500. Каждое число встречается лишь один раз (это важное условие).
3. Надо отсортировать эти числа.

А вот как это сделать и есть весь вопрос!

* Содержимое устройства после прочтения стирается. Я ставлю такое ограничение, чтобы не пытались там делать внешнюю сортировку слиянием.

Каркас функции такой:

static char ALL_MY_RAM[193];
short k;
short i;
/*все три переменные вместе дают 197 байт*/
extern int BUFSIZE;
extern short read_from_buf(short index);
extern void write_to_buf(short index, short value);

void sort()
{
for (i = 0; i != BUFSIZE; ++i)
{
k = read_from_buf(i);
/*работа с k*/
....
}
/* сама сортировка*/
....
/**/
for (i = 0; i != BUFSIZE; ++i)
{
/*получить k*/
...
write_to_buf(i, k);
}
}

Условия:
BUFSIZE (1; 1499)
все элементы буффера принадлежат отрезку [0; 1500]
все элементы буффера различны.

Можно например так. Используем нашу весьма скромную
память как бит филд. Представь длинное битовое поле
длиной в 1500 бит. К счастью 1500/8=187.5, пусть будет
188 - меньше 197, т.е. даже запаска будет. Нас выручает
именно то обстоятельство что все элементы не превышают
1500 и уникальны. Итак, поочередно читаем все элементы
последовательности, и устанавливаем соответствующий бит
в нашем поле. Например если прочли 10 то устанавливаем
бит No 10 (неважно справа или слева). Далее начинаем
сканировать наше битовое поле с первого по 1500ый бит,
и если очередной бит установлен, до пишем в буфер
соответствующее число. Все.

Вот первое что пришло мне в голову. Тока имей ввиду что
голова щас находится не в самой подходящей кондиции, особенно
учитивая что уже почти утро а я никак заснуть не могу :)
Если идея понравится могу и прогу написать, только ликвид
по комбинаторным алгоритмам сдам :D

Браво!
Это и есть единственно правильное решение.
Ну а числа я пециально так подгонял, что бы решение было найдено.

Всем удачи!

[ deleted by author ]

Eto ne iz knigi "Zhemchuzhini programmirovaniya ?" :)

Reshi-ka luchshe druguyu zadachu: poschitat` kol-vo 'schastlivix biletov' v diapazone 000000-999999, ne ispol`zuya operator sravneniya v yavnom vide (kak chast` operatora cikla, skazhem, mozhno).
Schastlivoe chislo eto kogda summa trex pervix cift ravna summe trex poslednix, naprimer: 153441

Ya ne sovsm ponyal shto znachit 'ne ispol`zuya operator sravneniya v yavnom vide'.
A shto eto za kniga "Zhemchuzhini programmirovaniya ?" Kto avtor, i gde mojno dostat'?

Встретил я другим способом.
Но книгу "Zhemchuzhini programmirovaniya ?"
я когда-то читал - меня тогда интересовала игра жизнь - общий вариант брал оттуда. (если мы конечно об одной и той же книге говорим).

To Dark Abyss of Yerevan:

Ya imel vvidu, chto nelzya ispol`zovat` operatori sravneniya v uslovnix operatorax "if...else...". T.e., ne ispol`zovat` konstrukcii tipa IF a+b+c = d+e+f THEN inc(TicketsNumber);

To Agregat :
Net, kniga o kotoroy ti govorish, eto "Etyudi dlya programmistov", tozhe klassnaya kniga, ya ee kogda-to davno chital.
A 'Zhemchuzhini programmirovaniya' ya v svoe vremya u kogo-to bral, i tam byla kak raz eta zadachka, tol`ko cifri byli raznie.

Да, да, да! Ты прав.
А числа я придумал во время формулировки задачи.
То есть подогнать числа - 1500 / 8 + x, где x число для запутывания решателей... ;) )
Но эту книгу я не читал - хотя может и встречал.

Nu, xorosho, s knizhkami razobralis`, ti zadachku davay-ka reshi :)

Значит так. В цикле крутим числа i от 0 до 27 (9+9+9),
и для каждого i подсчитываем t - число разбиений числа
i ( a+b+c == i/ a,b,c IN [0..9]). Ясно что количество
счастливых билетов с суммой первых (или последних) трех
чисел == i равно t*t (t^2). Там конечно используется оператор
сравнения, но насколько я понял ограничение поставлено для того
чтобы не допустить тупого перебора и сравнения левой части с
правой. Думаю что в данном случае все ок. В крайнем случае
можно изменить процедуру нахождения количества разбиений.