เครื่องอัลกอริทึม: 13 ขั้นตอน (พร้อมรูปภาพ)

2024 ผู้เขียน: John Day | [email protected]. แก้ไขล่าสุด: 2024-01-30 13:04

ฉันสอนวิทยาการคอมพิวเตอร์ในระดับวิทยาลัยมา 15 ปีแล้ว และถึงแม้ว่าความเชี่ยวชาญของฉันจะมากกว่าในด้านการเขียนโปรแกรม แต่ฉันก็ยังใช้เวลาค่อนข้างมากในการครอบคลุมอัลกอริธึมมาตรฐานสำหรับการค้นหาและการจัดเรียง จากมุมมองของการสอน ประเด็นหลักคือความซับซ้อนในการคำนวณ: แต่ละอัลกอริทึมต้องใช้เวลาเท่าใด เมื่อป้อนข้อมูลในขนาดที่กำหนด แต่มีความแตกต่างมากมาย ตัวอย่างเช่น อัลกอริธึมมีรันไทม์ที่แตกต่างกันขึ้นอยู่กับค่าอินพุตเฉพาะหรือไม่ (ตรงข้ามกับขนาด) คุณจะเลือกอัลกอริธึมการจัดเรียงแบบใดแบบหนึ่งมากกว่าแบบอื่นในกรณีใดบ้าง แม้ว่าเราจะพูดถึงประเด็นเหล่านี้ในเชิงนามธรรม แต่ก็มักจะทำให้ฉันสับสนว่าไม่มีวิธีง่าย ๆ ที่จะดูว่าอัลกอริทึมต่างๆ ทำงานอย่างไรภายใต้เงื่อนไขต่างๆ

เป้าหมาย

เป้าหมายที่ครอบคลุมของฉันสำหรับโครงการนี้คือการสร้างการแสดงผลแบบโต้ตอบสำหรับนักเรียนเพื่อแสดงภาพและสำรวจอัลกอริธึม ฉันจำกัดตัวเองให้อยู่ในอัลกอริทึมที่ทำงานบนอาร์เรย์ของค่า (จำนวนเต็ม) ดังนั้นฉันจึงสามารถใช้แถบ LED RGB LED ที่กำหนดแอดเดรสได้เพื่อแสดงภาพเนื้อหาอาร์เรย์ อาร์เรย์มีองค์ประกอบ 100 รายการ และจำนวนเต็มแต่ละจำนวนจะถูกจับคู่กับสีในลำดับสีรุ้ง เพื่อให้เห็นได้ชัดเจนในทันทีเมื่อมีการจัดเรียงอาร์เรย์ จัดเรียงบางส่วน หรือสุ่ม อย่างไรก็ตาม นอกเหนือจากค่าแล้ว ฉันยังต้องการวิธีแสดงภาพด้านการควบคุมของอัลกอริธึม ตัวอย่างเช่น องค์ประกอบใดของอาร์เรย์ที่กำลังถูกเปรียบเทียบหรือสลับกัน

เป้าหมายเฉพาะคือ:

- จัดเตรียมอัลกอริธึมการค้นหาและการเรียงลำดับที่หลากหลาย

- เห็นภาพค่าในอาร์เรย์ในลักษณะที่เน้นความคืบหน้าของอัลกอริทึม

- แสดงภาพการควบคุมอัลกอริธึม โดยเฉพาะองค์ประกอบที่กำลังพิจารณา

- อนุญาตให้ผู้ใช้เลือกรูปแบบข้อมูลอินพุตแทนที่จะสร้างค่าสุ่มเสมอ

- อนุญาตให้ผู้ใช้ควบคุมความเร็วและหยุดอัลกอริทึมชั่วคราว

- อนุญาตให้ผู้ใช้บังคับกรณีที่ดีที่สุด กรณีที่เลวร้ายที่สุด กรณีเฉลี่ย (เฉพาะอัลกอริทึม)

- แสดงจำนวนขั้นตอนตามขั้นตอนวิธีดำเนินการ

การสร้างภาพ

จากมุมมองการออกแบบทางกายภาพ ส่วนที่น่าสนใจที่สุดของโครงการนี้คือการสร้างภาพข้อมูลของอาร์เรย์ ฉันมีปัญหากับการแสดงข้อมูลและการควบคุม และวิธีสร้างอุปกรณ์แสดงผลเอง เป้าหมายของฉันคือการแสดงค่าข้อมูลเป็นวงกลมสีและจุดควบคุมเป็นลูกศรสีที่ชี้ไปที่ค่าข้อมูล หลังจากการทดลองบางอย่าง ฉันตัดสินใจเลือกการออกแบบที่มีแถบคู่ขนาน 100 RGB LEDs (WS2812) โดยมีมาสก์ทรงกลมเหนือ LED ข้อมูลแต่ละ LED และมาสก์รูปสามเหลี่ยมเหนือ LED ควบคุมแต่ละ LED ฉันสร้างแบบจำลอง 3 มิติของหน้ากากด้วยวงกลมและสามเหลี่ยม 10 คู่ จากนั้นพิมพ์ 3 มิติ 10 โมดูลเหล่านี้รวมเป็น 100 วงกลมและ 100 สามเหลี่ยม ขนาดและระยะห่างของหน้ากากของฉันออกแบบมาสำหรับแถบที่มีไฟ LED 100 ดวงต่อเมตร ไฟล์โมเดล 3 มิติมีให้ในคำอธิบายนี้ในภายหลัง

อิเล็กทรอนิกส์และตู้

ส่วนที่เหลือของอุปกรณ์นั้นตรงไปตรงมาจากมุมมองทางอิเล็กทรอนิกส์ นอกจากแถบ LED สองแถบแล้ว ยังมีปุ่มชั่วขณะหนึ่ง ตัวเข้ารหัสแบบหมุน (สำหรับควบคุมความเร็ว) และจอแสดงผล 7 ส่วน (เพื่อแสดงขั้นตอน) ด้วยปุ่มและส่วนควบคุมมากมาย ฉันเลือกใช้ไมโครคอนโทรลเลอร์ ESP32 เพราะมันมีหมุดจำนวนมากและเพราะมันค่อนข้างทรงพลัง ฉันจะพูดถึงกลยุทธ์การเดินสาย แต่มันค่อนข้างพื้นฐาน คุณอาจทำสิ่งที่ชาญฉลาดด้วย shift register หากคุณต้องการใช้พินน้อยลง

คุณสามารถสร้างกล่องหุ้มสำหรับอุปกรณ์นี้ได้ในหลายรูปแบบ ตอนแรกฉันคิดว่ามันเป็นกระดานสี่เหลี่ยมขนาดใหญ่ที่มีแถบ LED อยู่ด้านบน และมีปุ่มตารางอยู่ตรงกลาง แบบฟอร์มที่ฉันลงเอยด้วยได้รับแรงบันดาลใจจากมุมมองของเทคโนโลยียุคอวกาศในปี 1960 คุณยังสามารถสร้างด้วยแถบ LED ในแนวตั้งได้ หรือทำให้ส่วน LED ใหญ่ขึ้นมาก -- เติมทั้งผนัง -- ด้วยแผงควบคุมแยกต่างหาก

ซอฟต์แวร์

รหัสสำหรับอุปกรณ์นี้มีให้ใช้ฟรีบน GitHub และฉันได้พยายามอย่างเต็มที่เพื่อบันทึกวิธีการทำงานและวิธีกำหนดค่า ไลบรารีภายนอกเพียงแห่งเดียวที่คุณต้องการคือ FastLED เพื่อขับเคลื่อนแถบ WS2812

เสบียง

อิเล็กทรอนิกส์

1 บอร์ดพัฒนา ESP32 (เช่น

2 WS2812 หรือแถบ LED ที่คล้ายกัน ความหนาแน่น 100 LEDs ต่อเมตร (เช่น

1 ปุ่ม "เริ่ม" สามเหลี่ยม (เช่น

12 ปุ่มชั่วขณะ (เช่น https://amzn.com/B01N4D4750) -- รูปทรงต่างๆ ถ้าคุณต้องการ

1 แพ็ค (20) ตัวเชื่อมต่อแบบมีสาย (เช่น

ขั้วต่อ JST 1 ชุด (เช่น

1 ตัวเข้ารหัสแบบหมุน (เช่น

1 ปุ่มสำหรับเข้ารหัสแบบหมุน (เช่น

ขั้วต่อดูปองท์ 1 ชุด (เช่น https://amzn.com/B014YTPFT8) -- การซื้อเครื่องมือย้ำก็คุ้มค่าเช่นกัน

แจ็ค 1 กระบอก (สำหรับจ่ายไฟ) (เช่น

1 TM1637 การแสดงตัวเลข 7 ส่วน (เช่น

อุปกรณ์บัดกรีและสายไฟ

ไฟล์โมเดล 3 มิติ

คุณสามารถค้นหาโมเดล 3 มิติสำหรับโมดูลไฟ 10 คู่บน Thingiverse:

www.thingiverse.com/thing:4178181

คุณจะต้องพิมพ์โมเดลนี้ 5 ครั้ง รวมเป็น 10 โมดูล

ซอฟต์แวร์

github.com/samguyer/AlgorithmMachine

สิ่งที่ส่งมาด้วย

ไม้ ลูกแก้ว สลักเกลียวและสกรูสแตนเลส

วัสดุการแพร่กระจาย สิ่งที่ฉันชอบคือ Lee Filters #216 full white diffusion แต่มีตัวเลือกอื่นๆ แม้แต่กระดาษขาวธรรมดาก็ทำงานได้ดี

ขั้นตอนที่ 1: อัลกอริทึม 101

หลายคนคิดว่าวิทยาการคอมพิวเตอร์เป็นการศึกษาการเขียนโปรแกรมเป็นหลัก แต่หัวใจและจิตวิญญาณที่แท้จริงของสาขานี้คืออัลกอริธึม: การศึกษาขั้นตอนที่เป็นระบบสำหรับการแก้ปัญหาและค่าใช้จ่าย (โดยทั่วไปจะใช้เวลานานแค่ไหน) บุคคลที่มีชื่อเสียงในภาคสนาม เช่น Alan Turing, Alonzo Church และ Edsger Dijkstra กำลังคิดเกี่ยวกับแนวคิดเหล่านี้ก่อนคอมพิวเตอร์เพราะเรารู้ว่าแนวคิดเหล่านี้มีอยู่จริง

คุณลักษณะสำคัญของอัลกอริทึมในการแก้ปัญหาเฉพาะคือมีรายละเอียดและแม่นยำ เพื่อให้ผู้อื่นสามารถใช้อัลกอริทึมนี้เพื่อแก้ไขปัญหาโดยไม่เข้าใจวิธีการทำงานเลย เพียงทำตามขั้นตอนในลักษณะกลไก แล้วคุณจะได้คำตอบที่ถูกต้อง คุณสามารถดูว่าสิ่งนี้ช่วยได้อย่างไรในการเขียนโปรแกรมคอมพิวเตอร์ เนื่องจากพวกเขาต้องการรายละเอียดในระดับนี้ คอมพิวเตอร์ไม่สามารถกรอกรายละเอียดที่ขาดหายไปหรือตัดสินในแบบที่บุคคลสามารถทำได้

มันจะใช้เวลานานเท่าไหร่?

เมื่อเราได้ขั้นตอนโดยละเอียดแล้ว คำถามที่เป็นธรรมชาติจะใช้เวลานานแค่ไหนจึงจะได้คำตอบ เราไม่สามารถใช้หน่วยเวลาธรรมดาได้ เนื่องจากขึ้นอยู่กับว่าใครทำงาน (เปรียบเทียบว่าบุคคลสามารถคำนวณบางสิ่งได้เร็วเพียงใดกับซูเปอร์คอมพิวเตอร์) นอกจากนี้ยังขึ้นอยู่กับจำนวนข้อมูลที่เรามี เห็นได้ชัดว่าการค้นหารายการหมายเลขโทรศัพท์หนึ่งล้านหมายเลขใช้เวลานานกว่ารายการหนึ่งร้อย

ในการอธิบายต้นทุนของอัลกอริทึม ก่อนอื่นเราเลือกการดำเนินการบางอย่างในขั้นตอนที่แสดงถึง "ขั้นตอน" หนึ่งขั้นตอน ซึ่งมักจะเป็นสิ่งที่ง่าย เช่น การเปรียบเทียบหรือบวกตัวเลขสองตัว ซึ่งใช้เวลาดำเนินการในระยะเวลาที่แน่นอน จากนั้นเราจึงคิดสูตรที่อธิบายจำนวนขั้นตอนที่อัลกอริธึมจะดำเนินการเมื่อพิจารณาจากรายการข้อมูลจำนวนหนึ่ง ด้วยเหตุผลทางประวัติศาสตร์ เรามักจะระบุจำนวนรายการข้อมูลที่มีตัวพิมพ์ใหญ่ N

ตัวอย่างเช่น การดูรายชื่อหมายเลขโทรศัพท์ N จะใช้เวลา N ขั้นตอน การดูรายการสองครั้งต้องใช้ขั้นตอน 2N ทั้งสองสิ่งนี้เรียกว่าอัลกอริธึมเวลาเชิงเส้น - จำนวนขั้นตอนทั้งหมดคือขนาดอินพุตหลายเท่า อัลกอริธึมอื่น ๆ เป็นกำลังสอง (N กำลังสอง) หรือลูกบาศก์ (N ลูกบาศก์) หรือลอการิทึม (log N) หรือการรวมกันของสิ่งเหล่านี้ ปัญหาการคำนวณที่ยากที่สุดบางอย่างต้องใช้อัลกอริธึมเวลาแบบเอ็กซ์โปเนนเชียล (2^N)

โอเค แล้วไง

เมื่อจำนวนของรายการข้อมูล N มีขนาดเล็กก็ไม่สำคัญมากนัก ตัวอย่างเช่น สำหรับ N=10 10N คือชื่อนั้นว่า N กำลังสอง แต่แล้ว N=1000 ล่ะ? หรือ N=1000000? ล้านกำลังสองเป็นจำนวนที่ค่อนข้างมาก แม้แต่บนคอมพิวเตอร์ที่เร็วมาก อัลกอริธึมกำลังสองก็อาจใช้เวลานานหากอินพุตมีขนาดใหญ่พอ อัลกอริธึมแบบเอ็กซ์โปเนนเชียลลำบากกว่ามาก: สำหรับ N=50 อัลกอริทึมแบบเอ็กซ์โปเนนเชียลจะใช้เวลาสองสัปดาห์กว่าจะเสร็จสิ้นแม้บนคอมพิวเตอร์ที่แต่ละขั้นตอนมีเพียงหนึ่งนาโนวินาที (1 พันล้านวินาที) อุ๊ย!

อีกด้านหนึ่งของมาตราส่วน เรามีอัลกอริทึมเวลาลอการิทึมซึ่งเร็วมาก เวลาบันทึกเป็นสิ่งที่ตรงกันข้ามกับเวลาแบบเอ็กซ์โปเนนเชียล: เมื่อให้ขนาดอินพุต N จำนวนขั้นตอนคือเลขชี้กำลัง T ในสูตร 2^T = N ตัวอย่างเช่น หากขนาดอินพุตของเราคือหนึ่งพันล้าน อัลกอริธึมเวลาบันทึกจะต้องการเพียง 30 ขั้นตอนตั้งแต่ 2^30 = 1, 000, 000, 000 ช่างหวานอะไรอย่างนี้?!?!

คุณอาจสงสัยว่าใครจะสนเรื่องขนาดอินพุตเป็นล้านหรือพันล้าน? ลองคิดดู: มีผู้ใช้บน Facebook กี่คน? Google จัดทำดัชนีหน้าเว็บกี่หน้า ในจีโนมมนุษย์มีคู่เบสกี่คู่? การจำลองสภาพอากาศมีการวัดจำนวนเท่าใด

ขั้นตอนที่ 2: อัลกอริทึม

ปัจจุบัน Algorithm Machine ใช้อัลกอริธึมต่อไปนี้ สองวิธีคืออัลกอริธึมการค้นหา (ค้นหาค่าเฉพาะในรายการ) ที่เหลือคืออัลกอริธึมการเรียงลำดับ (ใส่ค่าตามลำดับ)

ค้นหาเชิงเส้น

ค้นหารายการค่าทีละรายการโดยเริ่มจากจุดเริ่มต้น ต้องใช้เวลาเชิงเส้น

ค้นหาไบนารี

ค้นหารายการโดยแบ่งครึ่งซ้ำๆ ต้องใช้เวลาบันทึก แต่ต้องจัดเรียงรายการเพื่อให้ทำงาน

การเรียงลำดับฟอง

เรียงลำดับรายการแลกเปลี่ยนองค์ประกอบที่อยู่ใกล้เคียงซ้ำ ๆ ที่ไม่อยู่ในลำดับ ต้องใช้เวลากำลังสอง

การเรียงลำดับการแทรก

เรียงลำดับรายการโดยวางแต่ละองค์ประกอบในตำแหน่งที่เหมาะสมในรายการของค่าที่จัดเรียงแล้ว ต้องใช้เวลากำลังสอง

Quicksort

เรียงลำดับรายการโดยแบ่งรายการออกเป็นครึ่งๆ ซ้ำๆ และย้ายค่าทั้งหมดที่น้อยกว่าค่ามัธยฐานไปที่ครึ่งแรก และค่าทั้งหมดที่มากกว่าค่ามัธยฐานไปยังครึ่งหลัง ในทางปฏิบัติ เราไม่สามารถหาค่ามัธยฐานได้อย่างมีประสิทธิภาพ ดังนั้นเราจึงเลือกค่าโดยการสุ่ม ผลที่ได้คือ อัลกอริธึมนี้สามารถเป็นกำลังสองในกรณีที่เลวร้ายที่สุด แต่โดยทั่วไปต้องใช้เวลา N * logN

ผสานการเรียงลำดับ

เรียงลำดับรายการโดยแบ่งครึ่ง เรียงลำดับสองส่วนแยกกัน (โดยใช้การเรียงลำดับแบบผสาน) แล้วรวมเข้าด้วยกันโดยแทรกค่าเข้าไป ต้องใช้เวลา N * logN เสมอ

การเรียงลำดับฮีป

จัดเรียงรายการโดยสร้างโครงสร้างข้อมูลที่เรียกว่าฮีป ซึ่งช่วยให้คุณสามารถค้นหาค่าที่น้อยที่สุดในเวลาบันทึก ต้องใช้เวลา N * logN เสมอ

Bitonic sort

คล้ายกับการผสานการเรียงลำดับและการเรียงลำดับอย่างรวดเร็ว แบ่งรายการออกเป็นสองส่วน จัดเรียงครึ่งหนึ่ง และรวมรายการใหม่ อัลกอริทึมนี้ต้องใช้เวลา N * logN * logN แต่มีข้อได้เปรียบที่ง่ายต่อการขนาน

ขั้นตอนที่ 3: แถบ LED: พิมพ์หน้ากาก 3 มิติ

ขั้นตอนแรกในการสร้างแถบ LED คือการพิมพ์หน้ากาก 3 มิติที่ให้แสงเป็นรูปร่าง แต่ละโมดูลครอบคลุมสิบองค์ประกอบของอาร์เรย์ 10 ค่า (วงกลม) และ 10 ตัวบ่งชี้ (สามเหลี่ยม) ดังนั้นคุณจะต้องมี 10 โมดูลทั้งหมด ไฟล์ STL ที่ฉันให้ไว้ที่นี่ประกอบด้วยโมดูลสองอินสแตนซ์ ดังนั้น คุณจะต้องทำการพิมพ์ห้ารอบ ฉันไม่มีเครื่องพิมพ์ 3 มิติที่ดีที่สุด ดังนั้นฉันจึงต้องทำความสะอาดเครื่องพิมพ์ด้วยตนเองโดยใช้ไฟล์และกระดาษทราย สิ่งที่สำคัญที่สุดคือรูกลมและสามเหลี่ยมนั้นสะอาด

ในรูปภาพ คุณจะเห็นการตั้งค่าการทดสอบของฉัน: ฉันติดแถบ LED สองแถบแล้วต่อเข้ากับบอร์ดทดลองด้วยไมโครคอนโทรลเลอร์ ขั้นตอนนี้ไม่จำเป็น แต่ฉันต้องการดูว่ามันจะเป็นอย่างไรก่อนที่จะเริ่มประกอบกล่องหุ้ม ฉันจัดเรียงโมดูลมาสก์บนแถบ LED สองแถบแล้วรันแบบร่างง่ายๆ ด้วยสีแบบสุ่ม ด้วยแถบวัสดุกระจายแสง รูปร่างและสีจึงดูโดดเด่น

ขั้นตอนที่ 4: ทางเลือกแถบ LED

เมื่อฉันเริ่มโครงการนี้ครั้งแรก ฉันได้ทดลองด้วยวิธีอื่นๆ ในการทำหน้ากาก LED หากคุณไม่มีเครื่องพิมพ์ 3 มิติ คุณอาจพิจารณาตัวเลือกใดตัวเลือกหนึ่งเหล่านี้ พูดตามตรง การผลิตชิ้นส่วนเหล่านี้เป็นเรื่องที่เจ็บปวดอย่างมาก

สำหรับวงกลม ฉันซื้อท่อทองเหลืองขนาด 13/32 ซึ่งมีเส้นผ่านศูนย์กลางเกือบ 1 ซม. ฉันตัดมันเป็นส่วนหนึ่งร้อย 1 ซม. แล้วพ่นสีขาว

สำหรับรูปสามเหลี่ยม ฉันใช้อลูมิเนียมฟอยล์หนาที่ตัดจากถาดอบแบบใช้แล้วทิ้ง ฉันทำรูปสามเหลี่ยมจากไม้ จากนั้นพันแถบกระดาษฟอยล์สั้นๆ รอบๆ แบบฟอร์มแล้วพันเทปไว้ อีกครั้ง คุณจะต้องมีสิ่งเหล่านี้หลายร้อยรายการ จึงต้องใช้เวลาและความอดทน

ขั้นตอนที่ 5: กล่องใส่แถบ LED

ตู้ของฉันค่อนข้างเรียบง่าย: ไม้สองแถบสำหรับด้านข้างและลูกแก้วสองแถบสำหรับด้านบนและด้านล่าง ชิ้นส่วนทั้งหมดมีความยาวประมาณ 102 ซม. (1 เมตรสำหรับ LED บวกเพิ่มอีกเล็กน้อยเพื่อรองรับการเดินสาย) ด้านข้างควรสูงกว่า 1 ซม. เล็กน้อยเพื่อให้มีที่ว่างสำหรับแถบ LED หลังจากตัดแถบแล้ว ฉันประกบชิ้นหน้ากากที่พิมพ์ 3 มิติระหว่างพวกมันเพื่อวัดความกว้างของลูกแก้ว ตัดลูกแก้วสองชิ้นตามความกว้างและความยาวของแท่ง สุดท้าย ตัดแถบวัสดุกระจายเพื่อให้พอดีกับหน้ากาก

สำหรับการแพร่กระจาย ฉันชอบ Lee Filters #216 (full white diffusion) มาก เป็นแผ่นพลาสติกบางๆ ที่กระจายแสงได้ทั่วถึงโดยไม่สูญเสียแสง แต่เป็นของแพง บางครั้งคุณสามารถหาแผ่นงานขนาดเล็กสำหรับขายทางออนไลน์ แต่ทั้งม้วนจะทำให้คุณได้รับเงินคืนประมาณ 125 เหรียญ ตัวเลือกอื่นๆ ได้แก่ กระดาษสีขาวหรือผ้าซาตินหรือพลาสติกเคลือบด้าน ทางเลือกที่นิยมคือแผ่นรองตัดพลาสติกแบบบาง

ก่อนที่คุณจะประกอบแถบ LED ตรวจสอบให้แน่ใจว่าคุณมีขั้วต่อที่เหมาะสมที่บัดกรีเข้ากับแถบ LED แถบจำนวนมากมาพร้อมกับลีดที่บัดกรีไว้ล่วงหน้า คุณจึงสามารถใช้มันได้

ฉันเริ่มการประกอบโดยขันชิ้นลูกแก้วด้านบนเข้ากับด้านไม้ (ดูรูป) จากนั้นฉันก็พลิกกลับและวางแถบการแพร่เข้า ตามด้วยหน้ากาก 10 ชิ้น เมื่อฉันพอใจกับการเว้นวรรคแล้ว ฉันก็ตรึงมันไว้กับที่ด้วยกาวร้อนสองสามจุด

ถัดไป วางแถบ LED สองแถบเคียงข้างกันที่ด้านบนของมาสก์ ตรวจสอบให้แน่ใจว่าไฟ LED คว่ำลง และตรวจสอบให้แน่ใจว่า LED แต่ละดวงเรียงตรงกับรูที่สอดคล้องกันในหน้ากาก เพิ่มกาวร้อนหรือเทปกาวเพื่อยึดแถบ LED ให้เข้าที่ สุดท้าย ขันสกรูชิ้นหลังของลูกแก้ว

เรียกใช้รูปแบบการทดสอบ งานที่ดี! คุณได้ทำส่วนที่ยากที่สุดแล้ว!

ขั้นตอนที่ 6: แผงควบคุม

แผงควบคุมเป็นส่วนที่ให้อิสระในการสร้างสรรค์มากที่สุด เพียงแค่มีตัวควบคุมและอุปกรณ์อิเล็กทรอนิกส์ทั้งหมดพร้อมกับแถบ LED การออกแบบที่เรียบง่ายที่สุดคือแผงสี่เหลี่ยม: เจาะรูสำหรับปุ่มและตัวควบคุม และติดแถบ LED ฉันชอบผสมผสานไม้ ลูกแก้ว และวัสดุอื่นๆ เข้าด้วยกันเพื่อให้ดูเป็นสไตล์สตีมพังค์/ย้อนยุค-สมัยใหม่ ในกรณีนี้ ฉันตัดลูกแก้วสำหรับงานหนักชิ้นหนึ่งเพื่อเก็บปุ่มตัวเลือกอัลกอริธึมหลัก และแท่งไม้สำหรับเก็บอุปกรณ์อิเล็กทรอนิกส์ที่เหลือ ฉันเจาะรูให้พอดีกับขนาดของปุ่มอาร์เคด สายไฟโชว์ด้านหลัง แต่ชอบ!

ฉันยังเจาะพื้นที่สำหรับจอแสดงผล 7 ส่วน ตัวเข้ารหัสแบบโรตารี่ และสายไฟบางส่วนที่ด้านหลังด้วย ฉันตัด dado ที่ด้านบนเพื่อยึดแถบ LED

ขั้นตอนที่ 7: สายรัดปุ่ม

การเดินสายไฟหลายปุ่มอาจทำให้เจ็บปวดได้ โชคดีที่ผู้สร้างเครื่องอาร์เคดมีตัวเชื่อมต่อมาตรฐานที่คุณสามารถใช้ได้ สายเคเบิลตัวเชื่อมต่อแต่ละปุ่มมีสายไฟสองเส้น สายหนึ่งสำหรับ VCC และอีกสายหนึ่งสำหรับกราวด์ ปลายด้านหนึ่งมีขั้วต่อจอบที่พอดีกับสายนำที่ด้านหลังของปุ่ม - ติดกราวด์กับตะกั่วที่ "เปิดตามปกติ" และ VCC กับตะกั่ว "ทั่วไป" ในการกำหนดค่านี้ เมื่อผู้ใช้กดปุ่ม วงจรจะเสร็จสมบูรณ์และไมโครคอนโทรลเลอร์จะอ่านค่า HIGH บนขาอินพุตที่เกี่ยวข้อง

ปลายสายอีกด้านมีขั้วต่อ JST (สิ่งเล็กๆ สีขาว) ข้อดีของตัวเชื่อมต่อเหล่านี้คือเสียบเข้าไปในเต้ารับในทางเดียวเท่านั้น ดังนั้นจึงไม่มีทางที่จะย้อนกลับ VCC และกราวด์โดยไม่ได้ตั้งใจ

สิ่งที่ฉันทำคือสร้างสายรัดเล็กๆ สำหรับตัวเชื่อมต่อเหล่านี้ ฉันประสานชุดของเต้ารับ JST ไว้บนชิ้นส่วนของโปรโตบอร์ดแล้วเรียกใช้สายไฟกลับไปที่ตัวเชื่อมต่อดูปองท์ที่ฉันจะเสียบเข้ากับไมโครคอนโทรลเลอร์ สายสีแดงคือสาย VCC และเชื่อมต่อกับเต้ารับ JST ทั้งหมด สายสีน้ำเงินเป็นสายที่แยกจากกันสำหรับแต่ละปุ่ม

ขั้นตอนที่ 8: ตัวเข้ารหัสแบบหมุน

ตัวเข้ารหัสแบบหมุนช่วยให้ผู้ใช้ควบคุมความเร็วของอัลกอริทึมได้ ฉันใช้โมดูลที่มาเป็นบอร์ดฝ่าวงล้อมที่มีตัวต้านทานแบบดึงขึ้นสำหรับสายข้อมูลสองสาย (สายสีเหลือง) สิ่งนี้เกิดขึ้นเป็นปุ่มด้วย แต่ฉันไม่ได้ใช้คุณสมบัตินั้น อีกสองสายคือ VCC และกราวด์ ฉันยังมีปุ่มอ้วนที่ดี

สิ่งที่ฉันชอบเกี่ยวกับตัวเข้ารหัสแบบโรตารี่ ซึ่งต่างจากโพเทนชิออมิเตอร์ก็คือมันแค่ส่งสัญญาณการหมุน (ตามเข็มนาฬิกาเทียบกับทวนเข็มนาฬิกา) ไปยังไมโครคอนโทรลเลอร์ ดังนั้นจึงง่ายที่จะเปลี่ยนวิธีการตีความค่า ตัวอย่างเช่น คุณสามารถให้ความรู้สึกเร่งความเร็ว (เช่นเมาส์) เมื่อผู้ใช้หมุนเร็ว

ขั้นตอนที่ 9: การแสดงผล 7 ส่วน

ไม่มีอะไรจะพูดมากที่นี่ สิ่งเหล่านี้มีอยู่ทุกที่ LED ถูกควบคุมโดยชิปที่เรียกว่า TM1637 ซึ่งสื่อสารกับไมโครคอนโทรลเลอร์ผ่านโปรโตคอลอนุกรมอย่างง่าย ฉันใช้ห้องสมุดที่มีอยู่แล้ว ซึ่งบอกได้ว่าต้องการให้แสดงหมายเลขใด และส่วนที่เหลือจะแสดง

ด้านหลังมีสี่พิน: VCC, กราวด์ และสายไฟสองเส้นสำหรับโปรโตคอลอนุกรม ฉันบัดกรีส่วนหัว 4 พินซึ่งเชื่อมต่อกับตัวเชื่อมต่อ Dupont ที่เชื่อมต่อกับไมโครคอนโทรลเลอร์

ขั้นตอนที่ 10: บอร์ดควบคุมหลัก

บอร์ดควบคุมหลักประกอบด้วยไมโครคอนโทรลเลอร์และตัวเชื่อมต่อทั้งหมดไปยังส่วนควบคุม (ปุ่ม, จอแสดงผล, ไฟ LED) ไมโครคอนโทรลเลอร์คือ ESP32 ซึ่งให้พลังการประมวลผลและหน่วยความจำจำนวนมาก และเผยให้เห็นพินจำนวนมาก การเดินสายนั้นค่อนข้างมาตรฐาน แต่ฉันจะชี้ให้เห็นบิตที่น่าสนใจสองสามข้อ

หมายเหตุ: คุณอาจต้องการดูโค้ด (https://github.com/samguyer/AlgorithmMachine) ก่อนที่คุณจะเริ่มเดินสายเมนบอร์ด เพื่อให้การกำหนดค่าพินของคุณตรงกับของฉัน

ฉันบัดกรีแม่แรงแบบบาร์เรลบนกระดานเพื่อจ่ายไฟ และต่อสายทองแดงเนื้อแน่นสองเส้นเข้ากับรางจ่ายไฟและรางกราวด์ของบอร์ด เหตุผลก็คือแถบ LED สามารถดึงพลังงานได้มากหากตั้งความสว่างไว้สูง และฉันไม่ต้องการดึงพลังงานทั้งหมดนั้นผ่านขั้วต่อ USB บนไมโครคอนโทรลเลอร์

เพื่อลดความซับซ้อนของการเดินสายปุ่ม ฉันบัดกรีแถบส่วนหัวมุมขวาชายกับหญิงลงไปที่ด้านข้างทั้งหมดของไมโครคอนโทรลเลอร์ (ด้านบนของบอร์ดตามที่แสดง) ตัวเชื่อมต่อ Dupont จากสายรัดปุ่มเสียบเข้ากับส่วนหัวนี้โดยตรง

สำคัญ: ต้องต่อไฟสำหรับปุ่ม (สายสีแดง) กับสายไฟ 3.3V บนไมโครคอนโทรลเลอร์ ESP32 เป็นชิป 3.3V ดังนั้นจึงควรแนบแหล่งสัญญาณ 3.3V เข้ากับหมุดข้อมูลเท่านั้น

ไมโครคอนโทรลเลอร์ดึงพลังงาน (หรือดันพลังงาน) ไปที่ราง (ด้านล่างของบอร์ดตามที่แสดง) ผ่านพิน USB 5V และกราวด์ สายไฟสีแดง/ดำอื่นๆ ทั้งหมดเป็น VCC และกราวด์

สายสีน้ำเงินสองเส้นคือสายข้อมูลสำหรับแถบ LED (WS2812)คู่สีเหลือง/สีเขียวคือสายข้อมูลสำหรับเครื่องเข้ารหัสแบบโรตารี่ และคู่สีเหลืองคือการเชื่อมต่อแบบอนุกรมกับจอแสดงผล 7 ส่วน

ขั้นตอนที่ 11: การประกอบ

ภาพถ่ายชุดนี้แสดงการประกอบขั้นสุดท้ายและการเดินสาย ฉันยังติดบอร์ดควบคุมหลักไว้ที่ด้านหลังที่ด้านบน

ก่อนที่จะเปิดเครื่อง ฉันได้ตรวจสอบบางอย่างเพื่อหลีกเลี่ยงความประหลาดใจที่น่ารังเกียจ โดยเฉพาะอย่างยิ่ง เพื่อให้แน่ใจว่าฉันไม่มีคอนเน็กเตอร์จ่ายไฟ/กราวด์ด้านหลัง และไม่มีไฟฟ้าลัดวงจร ตั้งค่ามัลติมิเตอร์ของคุณเพื่อทดสอบความต่อเนื่อง โดยจะส่งเสียงบี๊บเมื่อมีเส้นทางไฟฟ้าระหว่างลีดทั้งสอง แนบหนึ่งนำไปสู่สาย VCC ทั่วไปกับปุ่ม จากนั้นแนบตะกั่วอีกอันเข้ากับหมุดแต่ละอันของสายรัดทีละอัน มัลติมิเตอร์ควรส่งเสียงบี๊บเมื่อคุณกดปุ่มเท่านั้น หากคุณได้รับเสียงบี๊บอื่นๆ แสดงว่าคุณมีการกลับรายการหรือสั้น ติดตามและแก้ไขก่อนเปิดเครื่อง!

ขั้นตอนที่ 12: รหัส

ขั้นแรก เปิด Arduino IDE ของคุณและตรวจดูให้แน่ใจว่าคุณได้ติดตั้งไลบรารี FastLED แล้ว

ดาวน์โหลดรหัสเครื่องอัลกอริทึมจาก GitHub:

github.com/samguyer/AlgorithmMachine.git

คุณสามารถโคลนได้โดยตรงในโฟลเดอร์ Arduino หรือคัดลอกด้วยมือ

ก่อนอัปโหลด ตรวจสอบให้แน่ใจว่าการตั้งค่าพินตรงกับการกำหนดค่าฮาร์ดแวร์ของคุณ ฉันได้วางการตั้งค่าพินทั้งหมดไว้ที่ด้านบนสุดของไฟล์แล้ว

อัปโหลดและสนุก!

ขั้นตอนที่ 13: วิธีใช้งาน

Algorithm Machine นั้นใช้งานง่ายและแทบทุกปุ่มก็ใช้ได้!

ขั้นแรก ใช้ปุ่มข้อมูลเพื่อเริ่มต้นค่าในอาร์เรย์ มีสามตัวเลือก: (1) สุ่ม (2) เพิ่มค่าสุ่มหนึ่งค่า และ (3) ย้อนกลับอาร์เรย์ โปรดทราบว่าค่าจะคงอยู่ ดังนั้นคุณสามารถทำสิ่งต่างๆ เช่น เรียงลำดับก่อน จากนั้นจึงเพิ่มจุดรบกวน จากนั้นเรียกใช้อัลกอริธึมการจัดเรียงหรือค้นหาแบบอื่น

เลือกอัลกอริธึมการค้นหาหรือเรียงลำดับจากตัวเลือกปุ่มอื่นๆ ขณะนี้ยังไม่มีข้อเสนอแนะเมื่อคุณทำการเลือกนี้ (บางอย่างสำหรับการทำงานในอนาคต) จากนั้นกดปุ่ม "เล่น"

ปุ่มควบคุมความเร็ว คุณยังสามารถกด "เล่น" เพื่อหยุดชั่วคราวและยกเลิกการหยุดอัลกอริทึม

จะหยุดโดยอัตโนมัติเมื่อเสร็จสิ้น คุณยังสามารถกดปุ่มอัลกอริธึมอื่นได้ตลอดเวลา เครื่องจะหยุดอัลกอริธึมปัจจุบันและเริ่มต้นอัลกอริธึมใหม่ แต่เก็บข้อมูลให้เหมือนกับที่อัลกอริธึมก่อนหน้าทิ้งไว้

รางวัลใหญ่ในการประกวด STEM