push_swap
1.0.0
จัดเรียงข้อมูลบนสแต็ก
โครงการนี้จะทำให้คุณเรียงลำดับข้อมูลบนสแต็กด้วยชุดคำสั่งที่ จำกัด โดยใช้จำนวนการกระทำที่ต่ำที่สุดเท่าที่จะเป็นไปได้ เพื่อให้ประสบความสำเร็จคุณจะต้องจัดการอัลกอริทึมประเภทต่างๆและเลือกโซลูชันที่เหมาะสมที่สุด (จากหลาย ๆ ตัว) สำหรับการเรียงลำดับข้อมูลที่ดีที่สุด Version: 6 .
คุณสามารถอ่านเรื่อง: push_swap.pdf
เรียงลำดับรายการสุ่มของจำนวนเต็มโดยใช้จำนวนการเคลื่อนไหวที่น้อยที่สุด 2 สแต็คและชุดการดำเนินงานที่ จำกัด
คุณเริ่มต้นด้วยสแต็คที่ว่างเปล่าสองแห่ง: A และ B คุณจะได้รับรายการสุ่มของจำนวนเต็มผ่านอาร์กิวเมนต์บรรทัดคำสั่ง
อนุญาตให้มีการเคลื่อนไหวเหล่านี้เท่านั้น:
sa : สลับ A - สลับองค์ประกอบ 2 ตัวแรกที่ด้านบนของสแต็ค ไม่ทำอะไรเลยถ้ามีองค์ประกอบเพียงหนึ่งหรือไม่มีเลย)sb : SWAP B - สลับองค์ประกอบ 2 ตัวแรกที่ด้านบนของสแต็ก b ไม่ทำอะไรเลยถ้ามีองค์ประกอบเพียงหนึ่งหรือไม่มีเลย)ss : sa และ sb ในเวลาเดียวกันpa : Push A - ใช้องค์ประกอบแรกที่ด้านบนของ B และวางไว้ที่ด้านบนของ a ไม่ทำอะไรเลยถ้า B ว่างเปล่าpb : Push B - ใช้องค์ประกอบแรกที่ด้านบนของ A และวางไว้ที่ด้านบนของ B ไม่ทำอะไรเลยถ้า A ว่างเปล่าra : หมุน - เลื่อนองค์ประกอบทั้งหมดของสแต็ก A โดย 1 องค์ประกอบแรกกลายเป็นองค์ประกอบสุดท้ายrb : หมุน B - เลื่อนองค์ประกอบทั้งหมดของสแต็ก B โดย 1 องค์ประกอบแรกกลายเป็นองค์ประกอบสุดท้ายrr : ra และ rb ในเวลาเดียวกันrra : ย้อนกลับหมุน - เลื่อนองค์ประกอบทั้งหมดของสแต็ก A โดย 1 องค์ประกอบสุดท้ายกลายเป็นองค์ประกอบแรกrrb : ย้อนกลับหมุน B - เลื่อนองค์ประกอบทั้งหมดของสแต็ก B โดย 1 องค์ประกอบสุดท้ายกลายเป็นองค์ประกอบแรกrrr : rra และ rrb ในเวลาเดียวกัน ในตอนท้าย สแต็ก B จะต้องว่างเปล่าและจำนวนเต็มทั้งหมดจะต้องอยู่ใน สแต็ก A เรียงลำดับตามลำดับจากน้อยไปมาก
สร้างสองโปรแกรม: checker และ push_swap
โปรแกรม checker อ่านรายการสุ่มของจำนวนเต็มจาก stdin เก็บไว้และตรวจสอบเพื่อดูว่าพวกเขาถูกจัดเรียงหรือไม่
โปรแกรม push_swap จะคำนวณการเคลื่อนไหวเพื่อจัดเรียงจำนวนเต็ม - การกด, popping, การแลกเปลี่ยน และ การหมุน ระหว่าง สแต็ก A และ สแต็ก B - และแสดงทิศทางเหล่านั้นบน stdout
คุณสามารถท่อ push_swap ลงใน checker และ checker จะตรวจสอบว่าคำแนะนำของ push_swap ประสบความสำเร็จ
ทั้งสองโปรแกรมจะต้องแยกวิเคราะห์อินพุตสำหรับข้อผิดพลาดรวมถึงสตริงที่ว่างเปล่าไม่มีพารามิเตอร์พารามิเตอร์ที่ไม่ใช่ตัวเลขการทำซ้ำและคำแนะนำที่ไม่ถูกต้อง/ไม่มีอยู่จริง
push_swap ต้องสอดคล้องกับ 42 บรรทัดฐาน
การใช้ฟังก์ชั่น libc ปกติเป็นสิ่งต้องห้ามอย่างเคร่งครัด อย่างไรก็ตามนักเรียนได้รับอนุญาตให้ใช้: write , read , malloc , free , exit จะต้องไม่มีการรั่วไหลของหน่วยความจำ ข้อผิดพลาดจะต้องจัดการอย่างระมัดระวัง
ไม่สามารถลาออกในลักษณะที่ไม่คาดคิดได้
ข้อผิดพลาดทั้งหมดเช่น: คำสั่งที่ไม่ถูกต้องอนุญาตให้ไฟล์และ ฯลฯ ต้องจัดการ
ผู้ทดสอบ
