Версия для печати темы

Автор: mapblwka 11.05.2006 2:16

Уже не один день мучаю свой мозг.. Ну не могу я предумать такую процедуру... Помогите, а?

Дан файл f = file of integer. Удалить из файла все повторяющееся элементы, БЕЗ создания дополнительного файла, матриц и т.п. Вот такая разминка для мозгов.

Заранее огромное спасибо!

Автор: volvo 11.05.2006 2:29

Значит, должны быть наброски, какие-то попытки, идеи в конце-концов... Вот и покажи, КАК пыталась это сделать.

Автор: mapblwka 11.05.2006 10:17

volvo, вся проблема в удаление элементов из файла, остальное я уже придумала в 5 вариантах, но функция удаления... я даже идийного алгоритма построить не могу.

Автор: Бродяжник 11.05.2006 14:24

Смущает вот что: ну хорошо, мы удалили повторяющиеся элементы, то есть было в файле 122333456, стало
123456. Значит ли это, что длина файла должна была уменьшиться? И если да, то как ее корректировать? Если дополнительные файлы запрещены, это значит, что все изменения надо производить на месте. Надо ли при этом менять длину файла? Удалить-то не проблема...

Автор: Malice 11.05.2006 14:47

Для этого есть процедура Truncate(f)

Автор: Бродяжник 11.05.2006 15:46

mapbwlka
Нужно открыть файл для чтения/записи.
Потом прочесть первое число и запомнить его.
Потом надо читать все последующие и сравнивать их с первым. Пока они разные, все нормально. Как только мы наткнулись на совпадение, начинаем развлекаться. Запоминаем позицию совпавшего числа. Читаем следующее за ним. Если оно отличается, перезаписываем его в запомненную позицию. Начиная с этого момента, у нас возникает две позиции в файле - очередная позиция чтения и очередная позиция записи. По мере выявления совпадений эти две позиции будут все больше расходиться. Когда мы дочитаем до конца файла, нужно урезать длину файла с учетом найденных повторений. Теперь мы смещаемся ко второму числу, читаем его и повторяем ту же процедуру. И так до упора. Весело будет...

Автор: volvo 11.05.2006 15:50

mapbwlka, появилась у меня одна интересная идея... Только для того, чтобы браться за ее реализацию, я должен знать - ограничен ли размер файла, и есть ли какие-то временнЫе рамки (критична ли скорость выполнения программы)?

Автор: Malice 11.05.2006 16:58

Увеличить его придется максимум на 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;

var
  f: int_f;

begin
  assign(f, 'f.int');
  create(f);
  print(f);

  reset(f);
  f_pos := pred(filesize(f));
  compress(f);
  close(f);

  print(f);

end.

Автор: hardcase 11.05.2006 23:26

Рекурсия - хорошая идея. только долго всё это будет: для каждого элемента бегать по файлу...

Автор: volvo 11.05.2006 23:33

И это я пытался у автора выяснить

Ответа почему-то не последовало ... Будем надеяться, что пока ...

Автор: mapblwka 11.05.2006 23:40

ой! ребята! Вы такие умные тут! Все намного оказалось проще... Дошла до инута спросила "умных": "че делать???", ответ был до боли простой! truncate(var F) и все дела.

Переписывать письменный вариант решенной задачки честно лень, устала очень, позже выложу. Но вся фишка в том что: берем элемент файла, проверяем его на повторяемость, если повторяется, то каждый повторный элемент методом сдвига перегоняем в конец файла и truncate. Complete! почувствовала себя умной.

Так вот в следующий раз СНАЧАЛА спроси у них "Че делать", а потом иди на форум. Понятно?
Блин, мало того, что помоги человеку, так он еще и фыркает в ответ...

Автор: Vincent_Moro 26.05.2020 17:49

Рекурсия жрет дохрена ресурсов компухтера, лучше будет если мы все элементы файла вобьем в множество. С учетом, конечно, если порядок элементов в файле нам не важен. Такие сложные конструкции придумываете, что в космос запускай