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

[Agregat]

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

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

[greka]

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

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

[Agregat]

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

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

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

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

[Agregat]

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

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]
все элементы буффера различны.

[Dark Abyss of Yerevan]

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

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

[Agregat]

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

Всем удачи!

[Dark Abyss of Yerevan]

[ deleted by author ]

[W_z_rd]

Eto ne iz knigi "Zhemchuzhini programmirovaniya ?" :)

[W_z_rd]

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

[Dark Abyss of Yerevan]

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'?

Originally posted by W_z_rd:
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: 153440

[Agregat]

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

[W_z_rd]

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.

[Agregat]

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

[W_z_rd]

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

[Dark Abyss of Yerevan]

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

#include <stdio.h>


void main(){
int i,i1,i2,i3,t;
long total;

total=0;
for (i=0;i<=27;i++){

t=0;

/* найти количество разбиений числа i */
for (i1=0;(i1<=i)&&(i1<=9);i1++)
for (i2=0;(i-i1<=18)&&(i1+i2<=i)&&(i2<=9);i2++)
if (i-i1-i2<=9)t++;

total+=t*t;
// printf(&quot;i=%d, t=%d&quot;,i,t);

};

printf(&quot;\ntotal=%d&quot;,total);




}

[W_z_rd]

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

#include <stdio.h>


void main(){
int i,i1,i2,i3,t;
long total;

total=0;
for (i=0;i<=27;i++){

t=0;

/* найти количество разбиений числа i */
for (i1=0;(i1<=i)&&(i1<=9);i1++)
for (i2=0;(i-i1<=18)&&(i1+i2<=i)&&(i2<=9);i2++)
if (i-i1-i2<=9)t++;

total+=t*t;
// printf(&quot;i=%d, t=%d&quot;,i,t);

};

printf(&quot;\ntotal=%d&quot;,total);




}Ochen` nedurno, ideya pravil`naya, realizaciyu mozhno poluchshe sdelat`. Esli primenit` massiv, to mozhno povisit` evvektivnost` ~1.5 raza i izbavit`sya ot operatora sravneniya voobshe. V obshem, molodec.

[Rainman]

Abiss - i lucum@ sxal che, bajc kareli !
najev ajspes: Vercnenq massiv 3 erkarutjamb(vor@ algoritmi
ashxatanqi skzbum amboxjovin zro !)
ev 9 erkarutjamb Numbercount massiv = 0:Im algoritmum ogtagorcvelu !
nujn algoritm@ inch vor abiss - algoritmum,
bajc == - @ yndhanrapes chi ogtagorcvelu:Massivi verjin elementin kavelacnenq 1,
kpahenq @nt acik popoxakan ` count vor@ nujnpes kavelacnenq 1 - ov,
Numbercount[count - 1]++:Erb vor verjin element@ kdarna 9 ev nran kavelacnenq
1 apa inchpes sovorakan gumarman
depqum` naxaverjin element@ kavelana
1 - ov, isk verjin kzrojacnenq, ajd
@ntacqum count - @` count - 9 + 1,
ev Numbercount[count - 1]++: Verjum parzapes`

int total = 0;
For(int i = 0; i < 9; i++)
total += (Numbercount[i])^ 2;

total - @ mer patasxann !:&quot;

[Dark Abyss of Yerevan]

Ну что же, решите и вы задачку :D
Дано множество 1,2,..,3n натуральных чисел и какие нибудь 3 непересекающиеся подмножества этого множества по n чисел в каждом. Требуется со всей математической строгостью доказать, что можно
выбрать по одному числу из каждого множества так, чтобы одно число из выбранных равнялась сумме двух других.

P.S.
Я и сам не знаю решения. Задачка эта из учебника 'Тоноян. Комбинаторные Алгоритмы', No4.