Уже не один день мучаю свой мозг.. Ну не могу я предумать такую процедуру... Помогите, а?
Дан файл f = file of integer. Удалить из файла все повторяющееся элементы, БЕЗ создания дополнительного файла, матриц и т.п. Вот такая разминка для мозгов.
Заранее огромное спасибо!
volvo
11.05.2006 2:29
Цитата(mapblwka @ 10.05.2006 22:16)
Уже не один день мучаю свой мозг.
Значит, должны быть наброски, какие-то попытки, идеи в конце-концов... Вот и покажи, КАК пыталась это сделать.
mapblwka
11.05.2006 10:17
volvo, вся проблема в удаление элементов из файла, остальное я уже придумала в 5 вариантах, но функция удаления... я даже идийного алгоритма построить не могу.
Бродяжник
11.05.2006 14:24
Смущает вот что: ну хорошо, мы удалили повторяющиеся элементы, то есть было в файле 122333456, стало 123456. Значит ли это, что длина файла должна была уменьшиться? И если да, то как ее корректировать? Если дополнительные файлы запрещены, это значит, что все изменения надо производить на месте. Надо ли при этом менять длину файла? Удалить-то не проблема...
Malice
11.05.2006 14:47
Цитата(Бродяжник @ 11.05.2006 11:24)
Значит ли это, что длина файла должна была уменьшиться? И если да, то как ее корректировать? Если дополнительные файлы запрещены, это значит, что все изменения надо производить на месте.
Для этого есть процедура Truncate(f)
Бродяжник
11.05.2006 15:46
mapbwlka Нужно открыть файл для чтения/записи. Потом прочесть первое число и запомнить его. Потом надо читать все последующие и сравнивать их с первым. Пока они разные, все нормально. Как только мы наткнулись на совпадение, начинаем развлекаться. Запоминаем позицию совпавшего числа. Читаем следующее за ним. Если оно отличается, перезаписываем его в запомненную позицию. Начиная с этого момента, у нас возникает две позиции в файле - очередная позиция чтения и очередная позиция записи. По мере выявления совпадений эти две позиции будут все больше расходиться. Когда мы дочитаем до конца файла, нужно урезать длину файла с учетом найденных повторений. Теперь мы смещаемся ко второму числу, читаем его и повторяем ту же процедуру. И так до упора. Весело будет...
volvo
11.05.2006 15:50
mapbwlka, появилась у меня одна интересная идея... Только для того, чтобы браться за ее реализацию, я должен знать - ограничен ли размер файла, и есть ли какие-то временнЫе рамки (критична ли скорость выполнения программы)?
Malice
11.05.2006 16:58
Цитата(volvo @ 11.05.2006 11:50)
mapbwlka, появилась у меня одна интересная идея... Только для того, чтобы браться за ее реализацию, я должен знать - ограничен ли размер файла, и есть ли какие-то временнЫе рамки (критична ли скорость выполнения программы)?
Увеличить его придется максимум на 8Kb, я думаю это не критично. А по времени-если решать в лоб, без увеличения размера и использования другий файлов/массивов, полюбому дольше будет, причем гораздо..
volvo
11.05.2006 17:16
Malice, я кому задал вопрос? Тебе? Будь добр НЕ отвечать на те вопросы, которые заданы НЕ ТЕБЕ (вместо спрашиваемого), ОК? Ты что, знаешь, какой алгоритм я хочу предложить? Нет.
А догадываться будешь на форуме телепатов. Я понятно излагаю?
hardcase
11.05.2006 23:00
А вариант с открытым хэшированием не пройдёт? Мы ползём по файлу, если следующего элемента нету в хэш-таблице, то добавляем его и дописываем в результирующий файл. Если элемент оказался в хэше, то переходим к следующему. В конце работы программа просто заменяет входной файл результирующим.
--добавил чуток позднее
ой! описание задачи недочитал! пардон. Тогда чего-то я не понимаю, как хранить промежуточную инфу? Если в файле - то это очень долго. Ну, например ты умудрилась всётаки грохнуть элементы - на их месте можно нули писать. Тогда потом можно просто уплотнить файл: переписать элементы с конца файла в "дырки" в середине файла.
volvo
11.05.2006 23:14
Вариант с рекурсией ОПЯТЬ не рассматривается? В стеке храниться все элементы и будут. Я для чего про размер файла спрашивал?
Вот, например, так:
type int_f = file of integer;
procedure create(var f: int_f); const n = 24; a: array[1 .. n] of integer = ( 1, 1, 3, 8, 5, 3, 8, 2, 4, 5, 6, 10, 11, 14, 13, 18, 15, 16, 18, 12, 14, 15, 16, 20); var i: integer; begin rewrite(f); for i := 1 to n do write(f, a[i]); close(f); end;
procedure print(var f: int_f); var X: integer; begin reset(f); while not eof(f) do begin read(f, X); write(X:4); end; writeln; end;
var f_pos: longint;
procedure compress(var f: int_f); var X, V: integer; found: boolean; begin if f_pos < 0 then begin rewrite(f); exit end
else begin seek(f, f_pos); read(f, X); dec(f_pos); compress(f); end;
reset(f); found := false; while not eof(f) and not found do begin read(f, V); found := (X = V); end; seek(f, filesize(f)); if not found then write(f, X); end;
Рекурсия - хорошая идея. только долго всё это будет: для каждого элемента бегать по файлу...
volvo
11.05.2006 23:33
И это я пытался у автора выяснить
Цитата(Self)
(критична ли скорость выполнения программы)?
Ответа почему-то не последовало ... Будем надеяться, что пока ...
mapblwka
11.05.2006 23:40
ой! ребята! Вы такие умные тут! Все намного оказалось проще... Дошла до инута спросила "умных": "че делать???", ответ был до боли простой! truncate(var F) и все дела.
Переписывать письменный вариант решенной задачки честно лень, устала очень, позже выложу. Но вся фишка в том что: берем элемент файла, проверяем его на повторяемость, если повторяется, то каждый повторный элемент методом сдвига перегоняем в конец файла и truncate. Complete! почувствовала себя умной.
Так вот в следующий раз СНАЧАЛА спроси у них "Че делать", а потом иди на форум. Понятно? Блин, мало того, что помоги человеку, так он еще и фыркает в ответ...
Vincent_Moro
26.05.2020 17:49
Цитата(hardcase @ 11.05.2006 23:26)
Рекурсия - хорошая идея. только долго всё это будет: для каждого элемента бегать по файлу...
Рекурсия жрет дохрена ресурсов компухтера, лучше будет если мы все элементы файла вобьем в множество. С учетом, конечно, если порядок элементов в файле нам не важен. Такие сложные конструкции придумываете, что в космос запускай
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.