(1 курс ФИИТ) CS101. Основы программирования — практика

Архив 2015/16
#166

Да.

#167

Приведу пару примеров элегантных решений задач из вчерашней лабораторной.

1. Удаление максимума из несортированного списка List<integer>

Лобовая реализация выглядела так:

result := data.Max();
data.remove(result);

Недостаток этого решения в том, что он два раза проходится по «списку». Тип List предоставляет эффективный доступ по индексу и если бы мы написали обычный цикл for с поиском индекса максимального элемента, то удаление выполнялось бы с помощью RemoveAt(i), что потенциально быстрее, чем Remove, который выполняет линейный поиск.

Возникает вопрос: нельзя использовать удаление по индексу RemoveAt(i) вместо менее эффективного Remove, но при этом не искать максимум вручную? Положительный ответ на этот вопрос даёт следующий код.

var p := Range(0, data.Count - 1).ZipTuple(data).MaxBy(p -> p.Item2);
Result := p[1];
data.RemoveAt(p[0]);

В первой строке мы генерируем индексы для каждого элемента списка (Range) и прикрепляем к каждому элементу списка его индекс (ZipTuple). В результате получается последовательность пар (i, x): элемент x и его индекс. В этой последовательности находится пара с максимальным x с помощью MaxBy. Полученная p это максимум и его индекс.

2. Проверка отсортированности списка

В проверке реализации очереди с приоритетом предлагалось перемещать все элементы из очереди в список и проверить его отсортированность. В качестве списка можно опять использовать List<integer>. Сделать это можно с помощью такой функции:

function IsSorted(list1: List<integer>): boolean;
begin
  var list2 := new List<integer>(list1);
  result := list2.OrderBy(x -> 1 / x).SequenceEqual(list1);
end;

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

  • более эффективно,
  • напоминает алгоритм, который многие программировали циклом
  • не содержит явных циклов.

Приведу его позже, если эти вызовут интерес.

#168

Второе задание ДЗ.

Дано бинарное дерево. Дополнить его до полного значениями default(T), не увеличивая количество уровней.

На всякий случай переспрошу. Тут имеется ввиду full binary tree, в котором каждый узел имеет 0 или 2 потомка, или complete binary tree, в котором все узлы имеют 2 потомка (кроме листьев), а все листья находятся на одном уровне?

#169

Первое.

#170

в 6 ДЗ по рекурсии в B части 2 задание: должен ли учитываться регистр слова? там получается 2 подпрограммы: вспомогательная рекурсивная и основная. Можно же в основной для обработки текста(разбиение на слова) использовать циклы?

#171

Не должен. Можно.

Пожалуйста: когда задаёте вопрос про конкретную задачу, приводите здесь её текст целиком.

#172

Опубликовано первое ДЗ третьего модуля — самое короткое в мире.

#173

Настолько короткое, что его вообще нет? :smile:

#174

Виноват: торопился перейти к подготовке празднования 9 мая…

#175

Что загружать в ДЗ, если я его выполнил на лабораторной?

#176

Ничего.

#177

На станице курса опубликовано последнее бонусное задание со сроком выполнения в две недели.

#178

Опубликовано ДЗ.

Просьба к следующему занятию разобрать материал последней лекции «Наследование».

#179

Открыт заключительный тест по второму модулю, неделя на выполнение. Не спрашивайте, почему так поздно: надо было напомнить…

#180

Точно открыт? А то год немного не тот=)

#181

Спасибо, исправил.

#182

Всем привет! Хочу сделать комментарий по поводу вчерашнего задания на наследование с калькуляторами.

Дробные числа. Я пришёл к выводу, что подход описанный в задании плохой. Он не работал при повторном нажатии плюс: вычисление 1 + 2.3 + 4 давало неверный результат. Многие этого не заметили. Хотя это не смертельно и задача была всё-таки в первую очередь посмотреть на наследование, но всё же имейте ввиду:

если вы не нашли указанной ошибки, это повод задуматься о том, насколько тщательно вы тестируете свои программы.

На данный момент я получил решение, которое проходит следующие тесты.

  // инициализация
  var calc := new AddRatioCalculator;  Assert(calc.ToString = '0', 'test-1');
  
  // набор числа
  calc.Digit(3);    Assert(calc.ToString = '3',   'test-2-1');
  calc.Dot;         Assert(calc.ToString = '3,',  'test-2-2');
  calc.Digit(1);    Assert(calc.ToString = '3,1', 'test-2-3');

  calc.CE;

  // три слагаемых: целое + дробное + целое
  calc.Digit(1);  Assert(calc.ToString = '1');    // 1
  calc.Plus;      Assert(calc.ToString = '1');    // +
  calc.Digit(2);  Assert(calc.ToString = '2');    // 2
  calc.Dot;       Assert(calc.ToString = '2,');   // .
  calc.Digit(3);  Assert(calc.ToString = '2,3');  // 3
  calc.Plus;      Assert(calc.ToString = '3,3');  // +
  calc.Digit(4);  Assert(calc.ToString = '4');    // 4
  calc.Result;    Assert(calc.ToString = '7,3');  // =

  // не очищая результат прибавим ещё дробное
  calc.Plus;      Assert(calc.ToString = '7,3');    // +
  calc.Digit(2);  Assert(calc.ToString = '2');      // 2
  calc.Digit(1);  Assert(calc.ToString = '21');     // 1
  calc.Dot;       Assert(calc.ToString = '21,');    // .
  calc.Digit(5);  Assert(calc.ToString = '21,5');   // 3
  calc.Digit(5);  Assert(calc.ToString = '21,55');  // 3
  calc.Result;    Assert(calc.ToString = '28,85');  // =

Принципиальная ошибка была считать кнопку с точкой командной кнопкой. Я убрал Dot из перечисления Command и добавил DotB в перечисление Button.

В классе-наследнике я завёл вдобавок к указанному в задании полю-счётчику цифр после точки, ещё одно логическое поле fDotPressed и метод для их очистки:

    procedure ClearDot();
    begin
      fdigitsAfterDot := 0;
      fDotPressed := false;
    end;

Этот метод приходится вызывать в действиях CE, Plus, Result, потом их следует переопределять с вызовом унаследованных методов перед очисткой (ClearDot).

Флаг fDotPressed взводится в методе Dot (ранее назывался DotDec, я сократил). Там же приходится добавить одну проверку: когда точку жмут после =

      if (fLastButton = ComB) and (fLastCommand = Res) then
        CE();

аналогичная проверка есть в Digit предка (внутри case).

Константу DotB можно было вообще не добавлять, я её добавил и делаю fLastButton := DotB чтобы проверить это переопределённом в потомке Tostring, чтобы дописывать символ запятой (см. например test-2-2 в примере тестов).

Наконец, Digit в потомке такой же, как говорился, только условный оператор проверяет флаг fDotPressed, а не fLastCommand.

#183

в домашнем задании есть такой пункт: (из 3 лабораторной) Дополнительная задача. Проект «Статистика текста» В одной из прошлых лабораторных вы реализовывали БДП для подсчёта вхождений слов в тексте. Реализуйте класс TextStatistics для углублённой работы со статистикой текста (на основе БДП).

Объект класса должен инициализироваться текстом и предоставлять следующие возможности: …

Вопрос: я должен наследовать свой класс от того, что мы делали ранее или писать новый?

#184

Наследовать не надо. Можно использовать включение.

#185

Объект класса должен инициализироваться текстом и предоставлять следующие возможности:

Количество слов в тексте — свойство на чтение Count.

Проверка наличия заданного слова в тексте (метод Contains).

Индексное свойство, которое по данному слову возвращает число вхождений слова в текст. Если такое слово не встречается в тексте, должно возвращаться значение 0.

Поиск любого слова с минимальным числом вхождений в текст, не меньшим заданного значения. Если такого слова нет, вернуть nil. Реализация должна быть нерекурсивной — используйте очередь!

Пример. В тексте есть слова с числом вхождений 5, 10, 8, 2, 4, 6. Нужно найти слово с минимальным числом вхождений, не меньшим значения 3. Результат — слово с числом вхождений 4.

Поиск любого слова с максимальным числом вхождений в текст, не превышающим заданное значение (реализация любая, какая вам больше нравится).

Получение списка (односвязного или двусвязного) с информацией о словах, начинающихся на заданную непустую подстроку.

Печать статистики по словам в алфавитном порядке.

Насчет задания со списком: слова должна находиться в каком-то лексикографическом порядке?