Автовыведение типа
Несмотря на то, что ключевое слово auto было введено еще в C++11, многие программисты продолжают его игнорировать. А ведь автовыведение позволяет экономить время и делает код лаконичным.
Увидеть преимущества можно даже на примере стандартных типов STL.
➡️ @cpp_geek
Несмотря на то, что ключевое слово auto было введено еще в C++11, многие программисты продолжают его игнорировать. А ведь автовыведение позволяет экономить время и делает код лаконичным.
Увидеть преимущества можно даже на примере стандартных типов STL.
➡️ @cpp_geek
Сортировка пузырьком
Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.
Формат входных данных:
На первой строке дано целое число n (1 ≤ n ≤ 1000) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива – различные целые числа, не превышающие по модулю 10^9.
Формат выходных данных:
Выведите одно число – количество обменов пузырьковой сортировки.
➡️ @cpp_geek
Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.
Формат входных данных:
На первой строке дано целое число n (1 ≤ n ≤ 1000) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива – различные целые числа, не превышающие по модулю 10^9.
Формат выходных данных:
Выведите одно число – количество обменов пузырьковой сортировки.
➡️ @cpp_geek
This media is not supported in your browser
VIEW IN TELEGRAM
Дерево Фенвика
Довольно простая и быстрая, но совсем не очевидная в плане идеи и понимания структура данных. Позволяет находить сумму на префиксе и изменять отдельные элементы за O(log n). В следующем посте — реализация на C++.
➡️ @cpp_geek
Довольно простая и быстрая, но совсем не очевидная в плане идеи и понимания структура данных. Позволяет находить сумму на префиксе и изменять отдельные элементы за O(log n). В следующем посте — реализация на C++.
➡️ @cpp_geek
Структура представлена в виде массива f, в котором f[i] – сумма всех элементов от F[i] до i. Функция F(x) связана с битовым представлением аргумента. Вкратце можно описать так: F(x) заменяет группу единичных битов, находящихся в конце числа (младших) на нули. Если x заканчивается на нулевой бит, то F(x) = x. В битовых операциях F(x) задаётся так: F(x) = x & (x + 1).
Нам понадобятся три функции: прибавление x к элементу с индексом i, получение суммы дерева от 0до xи получение суммы на [a..b].
➡️ @cpp_geek
Нам понадобятся три функции: прибавление x к элементу с индексом i, получение суммы дерева от 0до xи получение суммы на [a..b].
➡️ @cpp_geek
Быстрая сортировка
Отсортируйте заданный массив с помощью быстрой сортировки.
Формат входных данных:
Первая строка входных данных содержит одно натуральное число nn (1 ≤ n ≤ 10^5) – количество элементов в массиве. В следующей строке находятся элементы массива – n целых чисел, не превосходящих по абсолютной величине 10^9.
Формат выходных данных:
Выведите элементы массива в порядке неубывания.
➡️ @cpp_geek
Отсортируйте заданный массив с помощью быстрой сортировки.
Формат входных данных:
Первая строка входных данных содержит одно натуральное число nn (1 ≤ n ≤ 10^5) – количество элементов в массиве. В следующей строке находятся элементы массива – n целых чисел, не превосходящих по абсолютной величине 10^9.
Формат выходных данных:
Выведите элементы массива в порядке неубывания.
➡️ @cpp_geek
Корень числа
Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a, используя вещественный бинарный поиск.
Формат входных данных:
С клавиатуры через пробел вводится два числа:
1. a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после десятичной точки;
2. n – натуральное, не превосходящее 10.
Формат выходных данных:
Требуется вывести число с точностью не менее 6 знаков после запятой.
➡️ @cpp_geek
Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a, используя вещественный бинарный поиск.
Формат входных данных:
С клавиатуры через пробел вводится два числа:
1. a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после десятичной точки;
2. n – натуральное, не превосходящее 10.
Формат выходных данных:
Требуется вывести число с точностью не менее 6 знаков после запятой.
➡️ @cpp_geek
Жадный алгоритм
Данный алгоритм на каждом шаге делает локально оптимальный выбор, надеясь в итоге получить глобально оптимальное решение.
Пример: Дробный Рюкзак
Задача состоит в том, чтобы выбрать, какие предметы, имеющие вес и стоимость, поместить в рюкзак ограниченной ёмкости W, да так, чтобы максимизировать общую ценность его содержимого. Мы можем определить соотношение стоимости предмета к его весу, т. е. с «жадностью» выбирать предметы, имеющие высокую стоимость, но в то же время маленький вес, а затем сортировать их по этим критериям. В задаче с дробным рюкзаком нам разрешено брать дробные части предмета.
Поскольку сортировка — самая дорогая операция, алгоритм работает за время O(n log n). Принимая в формате (стоимость, вес) три пары предметов — {(60, 10), (100, 20), (120, 30)} — и итоговую вместительность рюкзака W = 50, приведённый выше код выводит следующее:
жадный дробный рюкзак
максимальная ценность: 240.
➡️ @cpp_geek
Данный алгоритм на каждом шаге делает локально оптимальный выбор, надеясь в итоге получить глобально оптимальное решение.
Пример: Дробный Рюкзак
Задача состоит в том, чтобы выбрать, какие предметы, имеющие вес и стоимость, поместить в рюкзак ограниченной ёмкости W, да так, чтобы максимизировать общую ценность его содержимого. Мы можем определить соотношение стоимости предмета к его весу, т. е. с «жадностью» выбирать предметы, имеющие высокую стоимость, но в то же время маленький вес, а затем сортировать их по этим критериям. В задаче с дробным рюкзаком нам разрешено брать дробные части предмета.
Поскольку сортировка — самая дорогая операция, алгоритм работает за время O(n log n). Принимая в формате (стоимость, вес) три пары предметов — {(60, 10), (100, 20), (120, 30)} — и итоговую вместительность рюкзака W = 50, приведённый выше код выводит следующее:
жадный дробный рюкзак
максимальная ценность: 240.
➡️ @cpp_geek
Неиспользуемые переменные
Подобный макрос есть, например, в cocos2d-x, там он называется CC_UNUSED_PARAM. Из недостатков: теоретически, он может работать не на всех компиляторах. Тем не менее, в cocos2d-x он для всех платформ определен абсолютно одинаково.
Для чего? Этот макрос позволяет избежать предупреждения о неиспользуемой переменной, а читающему код он как бы говорит: «тот кто писал это — знал, что переменная не используется, все в порядке».
➡️ @cpp_geek
Подобный макрос есть, например, в cocos2d-x, там он называется CC_UNUSED_PARAM. Из недостатков: теоретически, он может работать не на всех компиляторах. Тем не менее, в cocos2d-x он для всех платформ определен абсолютно одинаково.
Для чего? Этот макрос позволяет избежать предупреждения о неиспользуемой переменной, а читающему код он как бы говорит: «тот кто писал это — знал, что переменная не используется, все в порядке».
➡️ @cpp_geek
В чем отличие malloc от new?
Ответ: malloc — выделение блока памяти в стиле Си, опасное с точки зрения приведения типов (non-typesafe), т.к. возвращает void * и требует обязательного приведения. new — выделение блока памяти и последующий вызов конструктора, безопасное с точки зрения приведения типов (typesafe), т.к. тип возвращаемого значения определен заранее.
➡️ @cpp_geek
Ответ: malloc — выделение блока памяти в стиле Си, опасное с точки зрения приведения типов (non-typesafe), т.к. возвращает void * и требует обязательного приведения. new — выделение блока памяти и последующий вызов конструктора, безопасное с точки зрения приведения типов (typesafe), т.к. тип возвращаемого значения определен заранее.
➡️ @cpp_geek
Могут ли статичные функции быть виртуальными в С++?
В C++ статическая функция-член класса не может быть виртуальной. Виртуальные функции вызываются, когда у вас есть указатель или ссылка на экземпляр класса. Статические функции не привязаны к экземпляру класса, но они привязаны к самому классу. C++ не имеет указателей на класс, поэтому нет сценария, в котором вы могли бы виртуально вызвать статическую функцию.
Например, программа с картинки в примере 1 выдаст ошибку во время компиляции.
Кроме того, статическая функция-член класса не может иметь одновременно идентификаторы const и volatile. Код из примера 2 тоже не скомпилируется.
➡️ @cpp_geek
В C++ статическая функция-член класса не может быть виртуальной. Виртуальные функции вызываются, когда у вас есть указатель или ссылка на экземпляр класса. Статические функции не привязаны к экземпляру класса, но они привязаны к самому классу. C++ не имеет указателей на класс, поэтому нет сценария, в котором вы могли бы виртуально вызвать статическую функцию.
Например, программа с картинки в примере 1 выдаст ошибку во время компиляции.
Кроме того, статическая функция-член класса не может иметь одновременно идентификаторы const и volatile. Код из примера 2 тоже не скомпилируется.
➡️ @cpp_geek
В чем разница между указателем и ссылкой в C++?
Указатель может быть переназначен n-раз, в то время как ссылка не может быть переназначена после бинда. Указатели могут указывать в NULL, тогда как ссылка всегда ссылается на объект. Программист не может получить адрес ссылки, как это возможно с указателями, но можно взять адрес объекта, на который указывает ссылка, и выполнить действия с ним.
➡️ @cpp_geek
Указатель может быть переназначен n-раз, в то время как ссылка не может быть переназначена после бинда. Указатели могут указывать в NULL, тогда как ссылка всегда ссылается на объект. Программист не может получить адрес ссылки, как это возможно с указателями, но можно взять адрес объекта, на который указывает ссылка, и выполнить действия с ним.
➡️ @cpp_geek
Функция all_of
Эта функция работает со всем диапазоном элементов массива и может сэкономить время на запуск цикла для проверки каждого элемента по одному. Она проверяет заданное свойство для каждого элемента и возвращает true, когда каждый элемент в диапазоне удовлетворяет указанному свойству, иначе возвращает false.
В приведенном выше коде отрицательный элемент -6 отрицает условие и возвращает false.
➡️ @cpp_geek
Эта функция работает со всем диапазоном элементов массива и может сэкономить время на запуск цикла для проверки каждого элемента по одному. Она проверяет заданное свойство для каждого элемента и возвращает true, когда каждый элемент в диапазоне удовлетворяет указанному свойству, иначе возвращает false.
В приведенном выше коде отрицательный элемент -6 отрицает условие и возвращает false.
➡️ @cpp_geek
Cтрого-типизированный enum
У «традиционных» перечислений в С++ есть некоторые недостатки: они экспортируют свои значения в окружающую область видимости (что может привести к конфликту имен), они неявно преобразовываются в целый тип и не могут иметь определенный пользователем тип.
Эти проблемы устранены в С++11 с введением новой категории перечислений, названных strongly-typed enums. Они определяются ключевым словом enum class. Они больше не экспортируют свои перечисляемые значения в окружающую область видимости, больше не преобразуются неявно в целый тип и могут иметь определенный пользователем тип (эта опция так же добавлена и для «традиционных» перечислений").
➡️ @cpp_geek
У «традиционных» перечислений в С++ есть некоторые недостатки: они экспортируют свои значения в окружающую область видимости (что может привести к конфликту имен), они неявно преобразовываются в целый тип и не могут иметь определенный пользователем тип.
Эти проблемы устранены в С++11 с введением новой категории перечислений, названных strongly-typed enums. Они определяются ключевым словом enum class. Они больше не экспортируют свои перечисляемые значения в окружающую область видимости, больше не преобразуются неявно в целый тип и могут иметь определенный пользователем тип (эта опция так же добавлена и для «традиционных» перечислений").
➡️ @cpp_geek
Что за оператор −−> в С++?
Это старый хитрый вопрос. В С++ нет оператора −−>.
Рассмотрим такой код:
if (p−−>m == 0) f(p);
Выглядит так, как будто и правда есть оператор −−>, и если правильно объявить переменные p и m, то код даже скомпилируется и запустится:
int p = 2;
int m = 0;
if (p−−>m == 0) f(p);
Это означает: если p−− больше чем m (а это так), то надо сравнить результат (true) с нулём. Ну, true != 0, так что результат всего выражения — false, и функция f() не вызовется. Другими словами:
if ((p−−) > m == 0) f(p);
Пожалуйста, не тратьте много времени на подобные вопросы. Они сбивали с толку новичков ещё до того, как появился С++.
➡️ @cpp_geek
Это старый хитрый вопрос. В С++ нет оператора −−>.
Рассмотрим такой код:
if (p−−>m == 0) f(p);
Выглядит так, как будто и правда есть оператор −−>, и если правильно объявить переменные p и m, то код даже скомпилируется и запустится:
int p = 2;
int m = 0;
if (p−−>m == 0) f(p);
Это означает: если p−− больше чем m (а это так), то надо сравнить результат (true) с нулём. Ну, true != 0, так что результат всего выражения — false, и функция f() не вызовется. Другими словами:
if ((p−−) > m == 0) f(p);
Пожалуйста, не тратьте много времени на подобные вопросы. Они сбивали с толку новичков ещё до того, как появился С++.
➡️ @cpp_geek