/42_PushSwap

Primary LanguageC

42_PushSwap

Потому что Swap_push не такой естественный

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

Содержание

  1. Предисловие
  2. Вступление
  3. Цели
  4. Общие инструкции
  5. Обязательная часть
  6. Бонусная часть
  7. Представление и Экспертная оценка

Глава 1

Предисловие

  • C

1

  • ASM

2

  • LOLCODE

3

  • PHP

4

  • BrainFuck

5

  • C#

6

  • HTML5

7

  • YASL

8

  • OCaml

9

Глава 2

Вступление

Проект Push_swap - очень простой и очень эффективный алгоритм алгоритма: данные будут нужно отсортировать. В вашем распоряжении набор значений типа int, 2 стека и абор инструкций для управления обоими стеками.

Ваша цель? Напишите программу на языке C под названием push_swap, которая вычисляет отображает в стандартном выводе самую маленькую программу, используя язык инструкций Push_swap, который сортирует полученные целочисленные аргументы.

Легко?

Посмотрим...

Глава 3

Цели

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

Алгоритмы сортировки и их сложность являются частью классических вопросов, обсуждаемых во время собеседований. Вероятно, сейчас самое время взглянуть на эти концепции, потому что вам придется столкнуться с ними в какой-то момент.

Цели обучения этого проекта - строгость, использование C и использование базовых алгоритмов. Особенно если посмотреть на сложность этих базовых алгоритмов.

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

Глава 4

Общие инструкции

  • Этот проект будут исправлять только настоящие люди. Таким образом, вы можете свободно организовывать и называть свои файлы по своему усмотрению, хотя вам необходимо соблюдать некоторые требования, перечисленные ниже.
  • Исполняемый файл должен называться push_swap.
  • Вы должны отправить Makefile. Этот Makefile должен скомпилировать проект и содержать обычные правила. Он может только перекомпилировать программу при необходимости.
  • Если вы умен, вы будете использовать свою библиотеку для этого проекта, отправьте также свою папку libft, включая собственный Makefile в корне вашего репозитория. Ваш Makefile должен будет скомпилировать библиотеку, а затем скомпилировать ваш проект.
  • Глобальные переменные запрещены.
  • Ваш проект должен быть написан на C в соответствии с Нормой.
  • Вы должны осторожно обращаться с ошибками. Ни в коем случае ваша программа не может завершиться неожиданным образом (Segmentation fault, bus error, double free и т. Д.).
  • Ни одна из программ не может иметь утечек памяти.
  • В обязательной части вам разрешено использовать следующие функции:
    • write
    • read
    • malloc
    • free
    • exit
  • Вы можете задавать вопросы на форуме и в Slack ...

Глава 5

Обязательная часть

Правила игры

  • Игра состоит из 2 стеков, названных a и b.

  • Начать с:

    • a содержит случайное число положительных или отрицательных чисел без каких-либо дубликатов.
    • b пустой

  • Цель состоит в том, чтобы отсортировать числа в порядке возрастания в стеке a.

  • Для этого в вашем распоряжении следующие операции:

    sa: swap a - поменять местами первые 2 элемента на вершине стека a. Ничего не делать, если есть только один или нет элементов).

    sb: swap b - поменять местами первые 2 элемента наверху стека b. Ничего не делать, если есть только один или нет элементов).

    ss: sa и sb одновременно.

    pa: push a - возьмите первый элемент вверху b и поместите его вверху a. Ничего не делать, если b пусто.

    pb: push b - возьмите первый элемент вверху a и поместите его вверху b. Ничего не делать, если a пусто.

    ra: rotate a - сдвинуть вверх все элементы стека a на 1. Первый элемент становится последним.

    rb: rotate b - сдвинуть вверх все элементы стека b на 1. Первый элемент становится последним.

    rr: ra и rb одновременно.

    rra: reverse rotate a - сдвинуть вниз все элементы стека a на 1. Последний элемент становится первым.

    rrb: reverse rotate b - сдвинуть вниз все элементы стека b на 1. Последний элемент становится первым.

    rrr: rra и rrb одновременно.

Пример

Чтобы проиллюстрировать действие некоторых из этих инструкций, давайте отсортируем случайный список целых чисел. В этом примере мы будем считать, что оба стека растут справа.

10

В этом примере целые числа сортируются из 12 инструкций. Вы можете лучше?

Программа "push_swap"

  • Вам нужно написать программу с именем push_swap, которая будет получать в качестве аргумента стек, отформатированный как список целых чисел. Первый аргумент должен быть наверху стека (будьте осторожны с порядком).
  • Программа должна отображать наименьший список инструкций, возможных для сортировки стека a, наименьшее число должно быть вверху.
  • Инструкции должны разделяться символом "\ n" и никак иначе.
  • Цель состоит в том, чтобы отсортировать стек с минимально возможным количеством операций. Во время защиты мы сравним количество инструкций, найденных вашей программой, с максимально допустимым количеством операций. Если ваша программа отображает слишком большой список или список не отсортирован должным образом, вы не получите баллов.
  • В случае ошибки вы должны отобразить ошибку, за которой следует '\ n' для стандартной ошибки. К ошибкам относятся, например: некоторые аргументы не являются целыми числами, некоторые аргументы больше целого числа и / или есть дубликаты.

11

Во время защиты мы предоставим двоичный код для правильной проверки вашей программы. Это будет работать следующим образом:

12

Если программа checker_OS отображает KO, это означает, что ваш push_swap выдал список инструкций, которые не сортируют список. Программа checker_OS доступна в ресурсах проекта в интранете. Вы можете найти в бонусном разделе этого документа описание того, как это работает.

Глава 6

Бонусная часть

Мы рассмотрим вашу бонусную часть тогда и только тогда, когда ваша обязательная часть ОТЛИЧНО. Это означает, что вы должны выполнить обязательную часть, от начала до конца, а управление ошибками должно быть безупречным, даже в случаях неправильного или неправильного использования. Если это не так, ваши бонусы будут полностью ИГНОРИРОВАНЫ.

Насколько интересно было бы самому написать свой чекер? Оооооочень интересно !!

Программа "Чекер"

  • Напишите программу с именем checker, которая получит в качестве аргумента стек, отформатированный как список целых чисел. Первый аргумент должен быть наверху стека (будьте осторожны с порядком). Если аргумент не задан, проверка останавливается и ничего не отображает.
  • Затем checker будет ждать и читать инструкции на стандартном вводе, за каждой инструкцией будет следовать ’\ n’. После того, как все инструкции будут прочитаны, программа проверки выполнит их в стеке, полученном в качестве аргумента.
  • Если после выполнения этих инструкций стек a фактически отсортирован, а b пуст, тогда программа проверки должна отобразить на стандартном выходе "OK", за которым следует a ’\ n’. Во всех остальных случаях программа проверки должна отображать "KO", за которым следует '\ n ’в стандартном выводе.
  • В случае ошибки вы должны отобразить ошибку, за которой следует '\ n' для стандартной ошибки. К ошибкам относятся, например: некоторые аргументы не являются целыми числами, некоторые аргументы больше целого числа, есть дубликаты, инструкция не существует и / или имеет неправильный формат.

Благодаря программе проверки вы сможете проверить, действительно ли список инструкций, которые вы создадите с помощью программы push_swap, правильно сортирует стек.

13

Вы НЕ ОБЯЗАНЫ воспроизводить то же поведение, что и двоичный файл, который мы вам предоставляем. Обработка ошибок является обязательной, но решать вам, как вы решите анализировать аргументы.

Глава 7

Представление и Экспертная оценка

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

Всем удачи!