2011-gre-cs-practice-book.pdf/Q32 — различия между версиями

Версия 21:41, 8 января 2025

Вопрос: Q32-08c765

Тут вставьте перевод вопроса. Используйте возможности разметки, включая формулы и т.п, если будут графы — посмотрите как задать их текстом https://wiki.4intra.net/Graphviz . Если код — теги «code-pascal», «code-c» или «code-python».

Старайтесь нетривиальные понятия, особенно незнакомые вам, найти ссылку на википедию и вставить (нейросети лажают!). Это важно, чтобы найти корректный перевод (то, что в википедии, или на худой конец — точно массово гуглится).

Потом конечно сотрите инструкции, которые тут курсивом.

Ближайшие соседи: Дан неотсортированный массив из nn чисел с плавающей точкой. Необходимо найти две из них, которые ближе всего друг к другу по значению.

Самые дальние соседи: Дан неотсортированный массив из nn чисел с плавающей точкой. Необходимо найти две из них, которые дальше всего друг от друга по значению.

Предположим, что разрешены только следующие операции с данными:

• Сравнение значений двух элементов массива с целью определения большего из них;
• Сравнение расстояния между двумя элементами массива (абсолютное значение разности между значениями двух элементов) с расстоянием между двумя другими элементами массива;
• Перестановка двух элементов массива.

Также предполагается, что каждая разрешённая операция стоит единичную стоимость. Каковы наихудшие (в худшем случае) асимптотические временные сложности алгоритмов, решающих эти две задачи?

Ответы

Если ответы простые, однострочные, используйте простой способ задания ответов списком, типа так (префикс «Правильный ответ:» — это дословно, для правильного ответа, неважно, какой он будет в списке)

• Правильный ответ: тут реально правильный ответ
• неправильный ответ
• еще какой-то неправильный ответ
• еще какой-то неправильный ответ
• еще какой-то неправильный ответ

Если ответы длинные, многострочные, или там графы, используйте способ задания ответов разделами, Но такое очень редко встречается.

Объяснение

Сначала заполните номер страницы с этим вопросом Исходники — вопрос 32 на 30 странице книги «2011-gre-cs-practice-book.pdf»

Если все сделаете правильно, по ссылке выше будет открываться правильная страница в правильном PDFе.

Ну и наконец, вики-разметкой напишите ваше понимание, почему правильный ответ — правильный, а неправильные варианты — неправильны. Тут тоже могут быть полезны ссылки на википедию, решение вами рекуррентных уравнений в sympy.