การนำอัลกอริทึมอาร์เรย์ไปปฏิบัติ
แนะนำใหม่| English | ความหมาย |
|---|---|
| traversal/træˈvɜːsl/ | การ遍历 ( traversal ) |
| index/ˈɪndeks/ | ดัชนี |
| linear search/ˈlɪnɪə sɜːtʃ/ | การค้นหาแบบเชิงเส้น |
อัลกอริทึม array มาตรฐาน
- ส่วนใหญ่งาน array เป็นการ遍历 plus其中一个มาตรฐาน patterns.
- Sum / average: รวบรวมยอดรวม แล้วหารด้วย
length. - Count: เพิ่มเมื่อองค์ประกอบตรงตามเงื่อนไข.
- Min / max: ติดตามค่าที่น้อยที่สุดหรือมากที่สุดที่เห็นมาจนถึงตอนนี้.
การหาค่าสูงสุด
- เริ่มต้นที่
max = a[0](องค์ประกอบแรก), แล้ว遍历จาก index1. if (a[i] > max) { max = a[i]; }ภายในลูป- หลังจบลูป,
maxจะเก็บค่าที่ใหญ่ที่สุดใน array. - เริ่มจาก องค์ประกอบแรก, ไม่ใช่
0—0อาจมากกว่าทุกค่า.
การค้นหาค่า
- เพื่อตรวจสอบว่ามีค่านั้นอยู่จริง,遍历และเปรียบเทียบแต่ละองค์ประกอบ.
- คืนค่า index ที่พบ, หรือ
-1ถ้าลูปจบโดยไม่พบ. if (a[i] == target) return i;ภายในลูป;return -1;หลังลูป.- นี่คือ linear search (Unit 4.14 อธิบายละเอียด).
การเลื่อนและการแก้ไข
- บางอัลกอริทึมย้ายหรือเปลี่ยนองค์ประกอบ — เช่น เลื่อนทุกอย่างไปทางซ้าย, หรือคูณสองทุกค่า.
- การแก้ไขต้องใช้ indexed loop เพื่อให้คุณสามารถ assign
a[i] = .... - ระวังขอบเขตเมื่ออ่าน
a[i+1]— ดัชนีสุดท้ายไม่มีเพื่อนข้าง. - Trace ดัชนีอย่างระมัดระวังเพื่อหลีกเลี่ยงการเข้าถึงที่ผิดขอบเขต.
Initialize a min/max search with the FIRST element, not 0. int max = 0; ล้มเหลวหากทุกค่าน้อยกว่าศูนย์ (มันจะรายงาน 0 ผิดพลาด). ใช้ int max = a[0]; และเริ่มลูปที่ index 1. และเมื่ออัลกอริทึมอ่าน a[i+1], หยุดลูปที่ i < a.length - 1, มิฉะนั้นรอบสุดท้ายจะอ่านเกินปลาย.
การหาค่าสูงสุดของ a:
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }- สำหรับ
a = {3, 9, 5}: max จะกลายเป็น9.
Algorithms ของ array รวมการ遍历กับ pattern: sum/average, count, min/max, หรือ search (คืนค่า index หรือ -1). Initialize min/max กับ องค์ประกอบแรก, ไม่ใช่ 0. การแก้ไของค์ประกอบต้องใช้ indexed loop, และการอ่าน a[i+1] ต้องการขอบเขตที่แคบลงเพื่อให้อยู่ในระยะ.
การหาค่าสูงสุด
max เริ่มต้นที่ a[0]=3 เปลี่ยนเป็น 9 แล้วคงอยู่ (a = {3,9,5})
ในการหาค่าสูงสุดของอาร์เรย์ คุณควรเริ่มต้น max ที่...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
เริ่มต้นที่ 0 จะล้มเหลวหากทุก值是ติดลบ
สำหรับ a = {3, 9, 5}, ค่าสูงสุดคืออะไร?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
9 เป็นองค์ประกอบที่ใหญ่ที่สุด
การค้นหาเชิงเส้นจะคืนค่าอะไรหากไม่พบเป้าหมาย?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ตามธรรมเนียม -1 หมายถึง 'ไม่พบ'
อัลกอริทึมที่อ่าน a[i+1] ควรลูปจนกว่า...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
หยุดล่วงหน้าหนึ่งครั้งเพื่อให้ a[i+1] อยู่ในขอบเขต
การแก้ไของค์ประกอบอาร์เรย์ (a[i] = ...) ต้องใช้ลูปที่มีดัชนี ไม่ใช่ for-each
Difficulty 1/5 · 100 coins + a small bonus on first completion today
for-each ไม่สามารถ assign กลับเข้าไปในอาร์เรย์ได้