Español
English
Português
中文 (中国)
العربية
हिन्दी
Français
Deutsch
Ελληνικά
Italiano
日本語
한국어
LatineКраткое содержание
Этот урок открывает шестой раздел курса, посвящённый составным данным. Он объясняет, для чего нужен раздел: научить представлять коллекции данных (последовательности фиксированного и переменного размера, таблицы и записи) и обрабатывать их базовыми алгоритмами, написанными вручную и взятыми из библиотеки, оценивая их сложность; представляет шесть его уроков и нить, которая их связывает; напоминает, что раздел считает известным, прежде всего циклы с инвариантом и передачу по константной ссылке; формулирует задачу, которую решает раздел, задачу программы, которая должна хранить данные в заранее неизвестном количестве и которая, будучи написанной с отдельными переменными, молча пропускает лишние; заранее вводит сложность как вторую меру алгоритма наряду с его корректностью; и показывает, куда ведёт раздел, в следующих разделах и в курсе «Программирование на C++ II».
Цели обучения
- Описывать последовательность содержания раздела и объяснять, что каждый урок даёт следующему.
- Вспомнить циклы, их инварианты и передачу параметров (по значению, по ссылке и по константной ссылке) и при необходимости повторить их.
- Заранее понять на примере сложность алгоритма как вторую меру его качества наряду с его корректностью.
- Понимать, что ожидается уметь по окончании раздела, и отличать это от того, что будет изучено в следующих разделах.
Входная проверка
Прежде чем проходить раздел, полезно определить исходный уровень. Эта проверка является самопроверкой: она не оценивается, и её единственная цель состоит в том, чтобы направить занятия. Первые четыре вопроса касаются того, что раздел считает известным: инварианта цикла, который ищет максимум, способа передачи большого параметра, числа итераций двух вложенных циклов и беззнаковой арифметики. Следующие шесть в порядке уроков касаются центральных идей раздела: допустимых индексов последовательности, создания вектора, числа делений размера пополам, поиска в упорядоченных данных, двойного индекса таблицы и опасности хранить в отдельных коллекциях данные одной и той же сущности. Никто не обязан пока отвечать на них верно, а в некоторых из них «пока не знаю» является честным ответом: каждый ответ, верный или нет, объясняет суть дела и называет урок, где она разбирается. Те же умения измеряются снова в конце, в уроке итогов.
Перед началом раздела оцени свою отправную точку. Это короткая самопроверка: она не оценивается, а результат хранится только в твоём браузере.
Вопрос 1Из предыдущих разделовФрагмент
int largest{0}; int t{}; while (std::cin >> t) { if (t > largest) { largest = t; } }должен оставить вlargestнаибольшую из прочитанных температур. На каких входных данных он ошибается?Первая итерация сравнивает значение с 0 и сохраняет его, если оно положительно: при одном положительном значении результат верен. Прежде чем отвечать, стоит выполнить трассировку.При>значение, равное максимуму, его не заменяет, но максимум остаётся тем же числом: повторение не меняет результата.Выдаёт то, что инициализация не была сверена с инвариантом: правильный цикл требует, чтобы инвариант выполнялся до первой итерации.Желаемый инвариант, «largestесть максимум прочитанного до сих пор», не выполняется в начале, потому что до чтения максимума нет, а начальный 0 больше любого отрицательного значения. Это исправляется инициализацией первым значением после того, как удалось убедиться, что оно существует. Урок Векторы делает то же самое на сохранённой последовательности, а библиотека выражает это черезstd::ranges::max, предусловие которой состоит в том, что последовательность не пуста.Повторить: Проектирование правильных циклов
Вопрос 2Из предыдущих разделовФункция подсчитывает, сколько гласных в тексте из миллиона символов, хранящемся в
std::string, и не изменяет его. Как лучше объявить её параметр?Передача по значению копирует миллион символов при каждом вызове: это правильно, но означает плату, которая ничего не даёт.Не копирует, но без необходимости позволяет изменять текст и не принимает ни литерал, ни временный объект: смешивает «не копировать» с «разрешить изменять».Способ передачи входит в интерфейс: передача по значению обещает функции собственную копию, и программа должна её сделать.Константная ссылка читает текст, не копируя его и не имея права его изменять, и к тому же принимает временный объект. В разделе 6 этот выбор становится правилом: функция, которая читает вектор из миллиона значений, получает его какconst std::vector<int>&, а ненужная копия становится самой частой ошибкой, связанной со стоимостью.Повторить: Параметры и область видимости
Вопрос 3Из предыдущих разделовСколько раз выполняется
++countвfor (int i{0}; i < 6; ++i) { for (int j{0}; j < i; ++j) { ++count; } }?Правильный ответ:
Внутренний цикл делает 0 итераций при , одну при и так далее до 5 при : всего , что равно . Урок Сложность алгоритма обобщает этот подсчёт: два цикла, перебирающие все пары из значений, делают итераций, и это число решает, годится ли алгоритм для миллиона значений.Повторить: Циклы
Вопрос 4Из предыдущих разделовЧто выводит
std::println("{}", 0u - 1);в системе, гдеunsigned intимеет 32 бита?Считает, что беззнаковый тип допускает отрицательные значения.Считает, что вычитание останавливается на наименьшем значении типа; беззнаковая арифметика переходит через край, а не насыщается.Смешивает возможное предупреждение с ошибкой: выражение допустимо, и его значение определено.Беззнаковая арифметика является модульной: вычитание 1 из 0 переходит через край к наибольшему значению типа, . Раздел 6 измеряет размеры типомstd::size_t, который тоже беззнаковый, так чтоv.size() - 1для пустого вектора даёт не , а огромное число; урок Массивы предупреждает об этом вычитании, а урок Векторы показывает цикл, который из-за него выходит за границы.Повторить: Целые числа и их представление
Вопрос 5В последовательности из элементов, занумерованных как в C++, какие индексы обозначают элемент?
Нумерует с единицы, как в обычной речи; в C++a[n]уже находится вне последовательности.Это самая частая ошибка на единицу: насчитывает индексов для элементов.Это честный ответ: урок 6.1 объясняет это и называет причину, по которой счёт идёт от нуля.Индекс в C++ отсчитывается от нуля, потому что он есть смещение от первого элемента: первый элемент естьa[0], а последнийa[n - 1]. Обращение через[]по индексу вне этого промежутка является неопределённым поведением, и урок Массивы учит доказывать с помощью инварианта цикла, что каждое обращение допустимо.Повторить: Массивы
Вопрос 6Что содержит
vпослеstd::vector<int> v(3, 7);?Читает круглые скобки так, будто это фигурные.Меняет местами роли двух чисел.Это честный ответ: урок 6.2 представляет вектор и способы его создания.С круглыми скобками первое число есть количество, а второе есть значение каждого элемента; с фигурными скобкамиstd::vector<int> v{3, 7};есть список элементов, 3 и 7. Вектор является первым типом курса, у которого фигурные и круглые скобки означают разное, и урок Векторы показывает это на программе.Повторить: Векторы
Вопрос 7Сколько итераций делает
for (int m{1024}; m > 1; m /= 2) { ... }?Правильный ответ:
Значенияmв начале каждой итерации равны 1024, 512, 256, 128, 64, 32, 16, 8, 4 и 2: десять итераций, потому что , а десять есть . Алгоритм, который на каждом шаге уменьшает свою задачу вдвое, делает порядка шагов, и урок Сложность алгоритма называет его логарифмическим: для миллиарда значений ему хватает около тридцати.Повторить: Сложность алгоритма
Вопрос 8В телефонном справочнике миллион имён в алфавитном порядке. Чтобы найти одно из них, справочник открывают посередине, отбрасывают половину, где имени быть не может, и повторяют то же с другой половиной. Сколько раз, самое большее, придётся его открыть?
Это подсчёт для поиска, который просматривает имена по одному: если не пользоваться порядком, в среднем проходится половина справочника.Это квадратный корень из миллиона: смешивает деление части пополам с делением её на блоки.Использует десятичный логарифм: каждое открытие отбрасывает половину, а не девять десятых.Каждое открытие вдвое сужает часть, где может находиться имя, а больше миллиона: после двадцати делений пополам остаётся одно имя. Это двоичный поиск из урока Поиск и сортировка, который работает только на упорядоченных данных и обосновывается инвариантом.Повторить: Поиск и сортировка
Вопрос 9При
std::vector<std::vector<int>> t{{1, 2, 3}, {4, 5, 6}};чему равныt[1][0]иt.size()?Читает первый индекс как столбец и считает столбцы вместо строк.Полагает, чтоsize()считает все клетки таблицы.Это честный ответ: урок 6.5 представляет таблицы как векторы векторов.Вопрос 10Программа хранит имена группы в одном векторе, а их оценки в другом, так что оценка
grades[i]принадлежитnames[i]. Что произойдёт, если отсортировать только вектор оценок?Для компилятора два вектора независимы: связь существует только в голове того, кто написал программу.Алгоритм получает один вектор и ничего не знает о существовании другого.Каждое обращение допустимо, и каждый результат определён: дефект логический, и поэтому его не обнаруживает ни один из двух санитайзеров курса (санитайзер ошибок памяти, AddressSanitizer, и санитайзер неопределённого поведения, UndefinedBehaviorSanitizer).
Загрузка содержимого…