Работа с рядками

Модератор: Модераторы

Работа с рядками

Сообщение Xiean » 02.04.2021 19:21:20

Дана последовательность слов; между соседними словами запятая, за последним
словом - точка. Напечатать все слова, встречающиеся в последовательности
по одному разу.
Xiean
незнакомец
 
Сообщения: 3
Зарегистрирован: 01.04.2021 19:45:37

Re: Работа с рядками

Сообщение debi12345 » 03.04.2021 12:43:26

Дана последовательность слов; между соседними словами запятая, за последним
словом - точка. Напечатать все слова, встречающиеся в последовательности
по одному разу.
Построить из этих слов хэш-таблицу с индексами, равными sha256 от каждого слова. Тогда в этой таблице автоматом останется по одному экземпляру каждого слова.

Добавлено спустя 1 минуту 21 секунду:
Или загрузить эти слова в БД (SQLITE3 и т.п.) и сделать DISTINCT SQL-запрос
Аватара пользователя
debi12345
долгожитель
 
Сообщения: 5752
Зарегистрирован: 10.05.2006 23:41:15
Откуда: Ташкент (Узбекистан)

Re: Работа с рядками

Сообщение Снег Север » 03.04.2021 14:14:18

debi12345 писал(а):Построить из этих слов хэш-таблицу

издеваетесь? :shock:
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 2993
Зарегистрирован: 27.11.2007 16:14:47

Re: Работа с рядками

Сообщение debi12345 » 03.04.2021 15:15:42

издеваетесь?

Ну "красно-черное дерево" как альтернативу, но под него придется писать функцию-компаратор - что сложнее.
Сейчас вручную тасовать список - все равно что считать числа в уме, имея под рукой калькулятор
Аватара пользователя
debi12345
долгожитель
 
Сообщения: 5752
Зарегистрирован: 10.05.2006 23:41:15
Откуда: Ташкент (Узбекистан)

Re: Работа с рядками

Сообщение Mirror » 03.04.2021 15:21:22

Умилился родному украинизму в заголовке (не «строки», а «рядки») и решил сделать за кого-то ДЗ.

Не использовал стандартную библиотеку (типа TStringList), современный режим {$mode ObjFPC}, свои типы, классы и записи, т.к. не знаю, проходили ли вы их. Не пытался делать эффективно или универсально (на большом количестве строк программа быстро станет тормозить).

Код: Выделить всё
{ Дана послідовність слів; поміж сусідніми словами кома, за останнім словом -
  крапка.  Надрукувати всі слова, які зустрічаються в послідовності по одному
  разі. }
program StringHandling;

var
  CurrentPart: String;
  FinishedReading: Boolean = False;

  Words: array [1..100] of String;
  WordCounts: array [1..100] of Integer;
  WordsLength: Integer = 0;

{ Якщо слово вже було додано в масив слів, повертає його номер індекс.
  Якщо слова в послідовності немає, повертає 0. }
function GetWordIndex(S: String): Integer;
var
  I: Integer;
begin
  GetWordIndex := 0;

  for I := 1 to WordsLength do
    if Words[I] = S then begin
      GetWordIndex := I;
      Exit
    end
end;

{ Забирає пробіли з початку або кінця рядка }
function Trim(S: String): String;
var
  StartIndex: Integer = 1;
  Count: Integer;
begin
  while (StartIndex <= Length(S)) and (S[StartIndex] = ' ') do
    Inc(StartIndex);

  Count := Length(S) - StartIndex;
  while (Count > 0) and (S[StartIndex + Count] = ' ') do
    Dec(Count);

  Trim := Copy(S, StartIndex, Count + 1)
end;

{ Додає слово в масив слів або збільшує його кількість. Якщо місця в
  списку немає, закінчує процес читання та додавання, виводячи помилку
  та встановлюючи FinishedReading := True }
procedure AddWord(Word: String);
var
  TrimmedWord: String;
  Index: Integer;
begin
  TrimmedWord := Trim(Word);
  Index := GetWordIndex(TrimmedWord);

  if Index = 0 then begin
    if WordsLength >= 100 then begin
      WriteLn(StdErr, 'Ліміт слів перевищено.');
      FinishedReading := True;
      Exit
    end;

    Inc(WordsLength);
    Words[WordsLength] := TrimmedWord;
    WordCounts[WordsLength] := 1
  end else
    Inc(WordCounts[Index])
end;

{ Читає частину слів. Частина має закінчуватися на кому або крапку, інакше
  останнє слово буде викнуте. }
procedure ProcessPart(Part: String);
var
  CurrentWord: String = '';
  I: Integer;
begin
  for I := 1 to Length(Part) do begin
    if Part[I] = '.' then begin
      AddWord(CurrentWord);
      FinishedReading := True;
      Break
    end else if Part[I] = ',' then begin
      AddWord(CurrentWord);
      CurrentWord := ''
    end else
      CurrentWord := CurrentWord + Part[I];

    { AddWord може закінчити читання, якщо місця в масиві слів
      не залишилося, отож перевіримо цей випадок }
    if FinishedReading then
      Break;
  end;
end;

{ Друкує список слів, які зустрілися один раз }
procedure WriteUniqueWords();
var
  I: Integer;
begin
  for I := 1 to WordsLength do
    if WordCounts[I] = 1 then
       WriteLn(Words[I])
end;

begin
  while not FinishedReading do begin
    ReadLn(CurrentPart);
    ProcessPart(CurrentPart);
  end;

  WriteUniqueWords
end.


P.S. Решения, которые написал debi12345, абсолютно правильные. Во многих реальных программах нужны именно они. Но при этом ваш_а преподаватель_ница вряд ли ожидает таких решений.
P.P.S. Не заметил, что тема в разделе «Помощь за вознаграждение», сделал бесплатно :D
P.P.P.S. Кстати, мы с debi12345 по-разному поняли задание:

«Напечатать все слова, встречающиеся в последовательности по одному разу.»
Я понял «напечатать [все слова, встречающиеся в последовательности по одному разу]». Т.е. если слово встречается один раз — печатаем, если больше — не печатаем.
debi12345 понял «напечатать [все слова, встречающиеся в последовательности] [по одному разу]», т.е. в его решениях слова, встречающиеся несколько раз, всё равно будут напечатаны (но только один раз).

Мой код делает именно первое — печатает только те, которые встречаются один раз. По-моему это правильная трактовка (с учётом того, как расставлены запятые в задании).

Но если вдруг нужно печатать все по одному разу, то код надо поменять.
Mirror
новенький
 
Сообщения: 49
Зарегистрирован: 22.05.2005 12:02:48
Откуда: Порту

Re: Работа с рядками

Сообщение debi12345 » 03.04.2021 18:47:23

По-любому правильное (масштабируемое на большой набор данных) решение - "красно-черное дерево" (далее см. число элементов в каждом "узле", чтобы отсечь по числу повторов). В хэш-таблицах (и SQL-е) тоже оно ("дерево") используется - как внутренняя реализация хэш-индексов. Возможно если топик-стартер шиканет таким (промышленным, из реального мира) решением, то препод(ша) врядли за это жестко покарает :mrgreen:
Аватара пользователя
debi12345
долгожитель
 
Сообщения: 5752
Зарегистрирован: 10.05.2006 23:41:15
Откуда: Ташкент (Узбекистан)


Вернуться в Помощь за вознаграждение

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3

Рейтинг@Mail.ru
cron