อัลกอริทึมเชิงเส้น - โครงร่างโครงสร้างและการคำนวณ

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

ภาษาอัลกอริทึม

แนวคิดนี้เป็นคำสั่งที่แม่นยำสำหรับนักแสดงในการดำเนินการตามลำดับการกระทำ ซึ่งมุ่งเป้าไปที่การแก้ปัญหา

ภาษานี้เป็นวิธีการอธิบายอัลกอริธึมที่มักจะเน้นที่ผู้ใช้

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

การพัฒนาอัลกอริทึมเป็นกระบวนการที่ค่อนข้างซับซ้อนและใช้เวลานาน เป็นเทคนิคในการรวบรวม (พัฒนา) ลำดับของการกระทำที่มีไว้สำหรับการแก้ปัญหาด้วยความช่วยเหลือของคอมพิวเตอร์

คุณสมบัติของอัลกอริทึม

ท่ามกลางคุณสมบัติคือ:

• ความจำกัด - ประกอบด้วยการทำงานให้เสร็จของอัลกอริธึมทั้งหมดในจำนวน จำกัด ของขั้นตอน (ขั้นตอน);
• ความมั่นใจ (เอกลักษณ์) - แสดงถึงเอกลักษณ์ของการตีความกฎสำหรับการดำเนินการตลอดจนลำดับการดำเนินการ
• ประสิทธิภาพ - ได้รับผลลัพธ์ที่ต้องการในจำนวนขั้นตอนที่ จำกัด
• ความเข้าใจ - นักแสดงต้องเข้าใจคำแนะนำ;
• อักขระมวล - อัลกอริธึมควรจะสามารถแก้ปัญหาเฉพาะทั้งระดับด้วยคำสั่งปัญหาทั่วไป

อัลกอริธึมเชิงเส้น วิทยาการคอมพิวเตอร์เกรด 9

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

• เส้นตรง;
• แตกแขนง;
• ด้วยวงจร

เราสนใจอัลกอริธึมเชิงเส้น พวกเขาคืออะไร? ประกอบด้วยคำสั่งที่ต้องดำเนินการตามลำดับที่ชัดเจน

โครงสร้างเชิงเส้นของอัลกอริทึมสามารถเขียนได้ในรูปแบบวาจาและกราฟิก

นี่คือตัวอย่างที่เขียนในรูปแบบวาจา ดังนั้น ภารกิจ: เตรียมตัวให้พร้อมสำหรับการเรียน สารละลาย:

• เริ่ม.
• ตื่น.
• เรียกเก็บเงิน
• ล้างหน้าของคุณ.
• แต่งตัว.
• รับประทานอาหารเช้า.
• รับกระเป๋าเอกสาร
• ตอนจบ.

รูปแบบกราฟิกของกระบวนการข้างต้นจะเป็นดังนี้:

อัลกอริธึมเชิงเส้นในรูปแบบของโฟลว์ชาร์ต

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

• บล็อกของจุดเริ่มต้น-จุดสิ้นสุดของอัลกอริทึม บนบล็อกมีคำจารึกว่า "จุดเริ่มต้น" หรือ "จุดสิ้นสุด"
• บล็อก "ข้อมูลอินพุต-เอาต์พุต"บล็อกนี้แสดงเป็นรูปสี่เหลี่ยมด้านขนาน มีจารึกต่อไปนี้: "อินพุต", "เอาต์พุต", "พิมพ์" นอกจากนี้ยังมาพร้อมกับรายการตัวแปรอินพุตหรือเอาต์พุตตามลำดับ
• บล็อกเลขคณิตหรือบล็อกการตัดสินใจ มันสอดคล้องกับรูปสี่เหลี่ยมผืนผ้า บนบล็อกควรมีคำจารึก: "operation", "group of operation"

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

อัลกอริธึมการคำนวณเชิงเส้น

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

ตัวอย่างโซลูชันอัลกอริทึมเชิงเส้น

ให้เรายกตัวอย่างคำอธิบายกฎการหารเศษส่วนธรรมดาโดยใช้อัลกอริธึมเชิงเส้นซึ่งในหนังสือเรียนของโรงเรียนมีเนื้อหาดังต่อไปนี้:

• ตัวเศษ 1 ต้องคูณด้วยตัวส่วนของเศษ 2;
• ตัวส่วนของเศษ 1 ต้องคูณด้วยตัวเศษของ 2;
• จำเป็นต้องเขียนเศษส่วนซึ่งตัวเศษเป็นผลมาจากการกรอกจุดที่ 1 และตัวส่วนเป็นผลมาจากการดำเนินการในจุดที่ 2 รูปแบบพีชคณิตของกฎนี้มีดังนี้:

a / b: c / d \u003d (a * d) / (b * d) \u003d m / n

เรามาสร้างอัลกอริทึมสำหรับการหารเศษส่วนของคอมพิวเตอร์กันเพื่อไม่ให้สับสน เราจะใช้การกำหนดแบบเดียวกันสำหรับตัวแปรตามสูตรที่ระบุไว้ข้างต้น a, b, c, d – ข้อมูลเริ่มต้นในรูปแบบของตัวแปรจำนวนเต็ม ผลลัพธ์จะเป็นค่าจำนวนเต็มด้วย การแก้ปัญหาในภาษาอัลกอริธึมจะเป็นดังนี้:

alg การหารเศษส่วน

แต่แรก

เหมือนเดิม a, b, c, d, m, n

อินพุต a, b, c, d

m:= a * d

n:= b * c

เอาต์พุต m, n

คอน

รูปแบบกราฟิกของโซลูชัน

โครงร่างของอัลกอริธึมเชิงเส้นที่อธิบายไว้ข้างต้นมีลักษณะดังนี้:

คำสั่งกำหนดค่ามีรูปแบบต่อไปนี้:

ตัวแปร:=นิพจน์

เครื่องหมาย ":=" อ่านว่าได้รับมอบหมาย

การมอบหมายคือคำสั่งที่จำเป็นสำหรับคอมพิวเตอร์เพื่อทำสิ่งต่อไปนี้:

• การประเมินการแสดงออก
• การกำหนดค่าที่ได้รับให้กับตัวแปร

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

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

ในตัวอย่างของอัลกอริทึมที่กำหนด ยังมีคำสั่งอินพุต:

อินพุต a, b, c, d

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

อัลกอริธึมเชิงเส้น การเขียนโปรแกรมของเขา

ดังที่กล่าวไว้ในตอนต้นของบทความ โปรแกรมเชิงเส้นสามารถรวมข้อความดังกล่าวได้:

• งานที่มอบหมาย;
• ป้อนข้อมูล;
• ข้อสรุป.

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

ดังนั้นตัวดำเนินการมอบหมายในภาษาการเขียนโปรแกรมจึงเขียนดังนี้:

LET A = B โดยที่ A เป็นตัวแปร B คือนิพจน์ ตัวอย่างเช่น A = Y + 20

ตัวดำเนินการอินพุตมีลักษณะดังนี้:

INPUT เช่น INPUT C

ตัวดำเนินการสำหรับการส่งออกข้อมูล ค่า ถูกเขียนดังนี้:

พิมพ์. ตัวอย่างเช่น PRINT C.

ลองมาดูตัวอย่างง่ายๆ เราจำเป็นต้องเขียนโปรแกรมที่จะหาผลรวมของตัวเลข A และ B ที่ป้อนจากแป้นพิมพ์

ในภาษาการเขียนโปรแกรมเราจะได้โปรแกรมซึ่งมีข้อความแสดงอยู่ด้านล่าง

ตัวดำเนินการอินพุตและเอาต์พุตในภาษาโปรแกรม Pascal

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

เมื่อป้อนข้อมูล คำสั่งดังกล่าวจะใช้เพื่ออ้างถึงขั้นตอนการป้อนข้อมูลมาตรฐานที่สร้างไว้แล้วในโปรแกรม

อ่าน (A, B, C) โดยที่ A, B, C เป็นตัวแปรที่ต้องป้อนลงใน RAM เพื่อท่องจำ

Readlnn (x1, y, x2) - หลังจากป้อนข้อมูลเสร็จแล้ว เคอร์เซอร์จะย้ายไปที่จุดเริ่มต้นของบรรทัดใหม่

readlnn; - ระบุความคาดหวังของการกด "Enter" โดยปกติคำสั่งนี้จะถูกแทรกลงในข้อความก่อนสิ้นสุด "สิ้นสุด" เพื่อบันทึกผลลัพธ์ของโปรแกรมในหน้าจอเนื้อหา

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

เขียน (A, B, C) - โดยการระบุค่า A, B, C ในหนึ่งบรรทัด เคอร์เซอร์จะไม่ออกจากบรรทัดปัจจุบัน

Writeln (z, y, z2) - หลังจากเสร็จสิ้นการแสดงค่า เคอร์เซอร์ที่ตำแหน่งนี้จะย้ายไปขึ้นบรรทัดใหม่

ไรเติลน์; - ระบุการข้ามบรรทัดหนึ่งและการเปลี่ยนไปยังจุดเริ่มต้นของบรรทัดใหม่

ด้วยความช่วยเหลือของโอเปอเรเตอร์ง่ายๆ ที่ข้อมูลถูกป้อนและส่งออกในภาษาปาสกาล