Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 20.09.2002, 14:07   #1
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Smile Попробуйте решить интересную задачу...

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

Жду решений .
Reply With Quote
Old 20.09.2002, 15:18   #2
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Question

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

не понял - oна автоматом стирается ? Т.е. максимум, что я могу сделать с данными буфера[978*2] - всего 1 раз закинуть его кусочек в буфер[197] ?
Reply With Quote
Old 20.09.2002, 21:22   #3
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

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

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

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

* Содержимое устройства после прочтения стирается. Я ставлю такое ограничение, чтобы не пытались там делать внешнюю сортировку слиянием.
Reply With Quote
Old 20.09.2002, 21:47   #4
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

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

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]
все элементы буффера различны.
Reply With Quote
Old 21.09.2002, 09:49   #5
Дошкольник
 
Dark Abyss of Yerevan's Avatar
 
Join Date: 01 2002
Location: hell
Posts: 124
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

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

Вот первое что пришло мне в голову. Тока имей ввиду что
голова щас находится не в самой подходящей кондиции, особенно
учитивая что уже почти утро а я никак заснуть не могу
Если идея понравится могу и прогу написать, только ликвид
по комбинаторным алгоритмам сдам
Reply With Quote
Old 22.09.2002, 19:39   #6
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

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

Всем удачи!
Reply With Quote
Old 23.09.2002, 05:30   #7
Дошкольник
 
Dark Abyss of Yerevan's Avatar
 
Join Date: 01 2002
Location: hell
Posts: 124
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

[ deleted by author ]
Reply With Quote
Old 23.09.2002, 12:16   #8
Академик
 
W_z_rd's Avatar
 
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 45
Posts: 4,854
Downloads: 1
Uploads: 0
Reputation: 225 | 3
Post

Eto ne iz knigi "Zhemchuzhini programmirovaniya ?"
Reply With Quote
Old 23.09.2002, 12:20   #9
Академик
 
W_z_rd's Avatar
 
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 45
Posts: 4,854
Downloads: 1
Uploads: 0
Reputation: 225 | 3
Post

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
Reply With Quote
Old 23.09.2002, 19:02   #10
Дошкольник
 
Dark Abyss of Yerevan's Avatar
 
Join Date: 01 2002
Location: hell
Posts: 124
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

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

Quote:
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
Reply With Quote
Old 23.09.2002, 21:40   #11
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

Встретил я другим способом.
Но книгу "Zhemchuzhini programmirovaniya ?"
я когда-то читал - меня тогда интересовала игра жизнь - общий вариант брал оттуда. (если мы конечно об одной и той же книге говорим).
Reply With Quote
Old 24.09.2002, 00:50   #12
Академик
 
W_z_rd's Avatar
 
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 45
Posts: 4,854
Downloads: 1
Uploads: 0
Reputation: 225 | 3
Post

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.
__________________
Женщин не надо понимать, их надо любить!
Reply With Quote
Old 24.09.2002, 01:13   #13
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

Да, да, да! Ты прав.
А числа я придумал во время формулировки задачи.
То есть подогнать числа - 1500 / 8 + x, где x число для запутывания решателей... )
Но эту книгу я не читал - хотя может и встречал.
Reply With Quote
Old 24.09.2002, 04:18   #14
Академик
 
W_z_rd's Avatar
 
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 45
Posts: 4,854
Downloads: 1
Uploads: 0
Reputation: 225 | 3
Post

Nu, xorosho, s knizhkami razobralis`, ti zadachku davay-ka reshi
Reply With Quote
Old 24.09.2002, 09:51   #15
Дошкольник
 
Dark Abyss of Yerevan's Avatar
 
Join Date: 01 2002
Location: hell
Posts: 124
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

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

Code:
  #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);




}
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 22:40.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.