Объединения двух упорядоченных числовых файлов в один упорядоченный

      Комментарии к записи Объединения двух упорядоченных числовых файлов в один упорядоченный отключены

Главная Форумы Программирование Помощь с решением задач на Prolog Задачи на строки и файлы Объединения двух упорядоченных числовых файлов в один упорядоченный

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 11 мес. назад.

  • Автор
    Сообщения
  • #1889

    questioner
    Участник

    Решить задачу нужно на Visual 5.2/Turbo Prolog.
    У меня получилось считать элементы файла в список:

    domains
      n=integer*
     
    predicates
      readtolist(n).
     
    clauses
      readtolist([]):-eof(f1),!.
      readtolist(N):-
        not(eof(f1)),
        readint(X),
        readtolist(N1),
        N=[X|N1].
     
    goal
      write(«Vvedite imq faila: «), readln(X),
      openread(f1,X),
      readdevice(f1), readtolist(L),
      closefile(f1),
      write(L), nl,
      write(«Ok»).

    Как считать элементы со второго файла? Как соеденить списки так, чтобы не нарушить упорядоченность?
    Можно ли соеденить списки, а затем отсортировать результат?

  • #1890

    Элементы второго файла считываются точно также, как и первого. Что не получается?
    Соединить и отсортировать можно, это можно сделать встроенными функциями append и sort, однако это совсем не оптимально. Сложность алгоритма соединения списков – O(N), сложность алгоритма сортировки – O(N*log(N)). Ваш алгоритм выполнит обе операции, однако слияние упорядоченных списков выполняется за O(N), посмотрите правило rangConcat(List1, List2, List1AndList2).

Для ответа в этой теме необходимо авторизоваться.