مقدمه
قصد دارید در جنگل نزدیک خانهتان یک خانهی درختی بسازید تا بتوانید طلوع و غروب خورشید را تماشا کنید.
از یک شرکت نقشهبرداری محلی دادههایی به دست آوردهاید که ارتفاع هر درخت را در هر بخش مستطیلی نقشه نشان میدهند.
باید هر شبکه روی نقشه را تحلیل کنید تا درختهای مناسب برای خانهی درختی خود را پیدا کنید.
درخت مناسب هر دو ویژگی زیر را دارد:
- از هر درختی در شرق و غرب بلندتر است تا بهترین منظرهی ممکن از طلوعها و غروبهای خورشید را داشته باشید.
- از هر درختی در شمال و جنوب کوتاهتر است تا میزان بالا رفتن از درخت را به کمترین حد برسانید.
دستورالعملها
وظیفهی شما این است که درختهای بالقوهای را پیدا کنید که بتوانید خانهی درختی خود را روی آنها بسازید.
شرکت دادهها، دادهها را به شکل جدولهایی ارائه میدهد که ارتفاع درختها را نشان میدهند.
سطرهای جدول جهت شرق-غرب و ستونهای آن جهت شمال-جنوب را نشان میدهند.
یک درخت قابلقبول، بزرگترین درخت در سطر خود و در عین حال کوچکترین درخت در ستون خود است.
ممکن است جدولی اصلاً هیچ درخت مناسبی نداشته باشد.
یا ممکن است یکی داشته باشد، یا حتی چندین درخت.
این جدولی است که دقیقاً یک درخت نامزد دارد.
↓
1 2 3 4
|-----------
1 | 9 8 7 8
→ 2 |[5] 3 2 4
3 | 6 6 7 1
- سطر ۲ مقادیر ۵، ۳، ۲ و ۴ را دارد. بزرگترین مقدار ۵ است.
- ستون ۱ مقادیر ۹، ۵ و ۶ را دارد. کوچکترین مقدار ۵ است.
پس نقطهی [2, 1] (سطر: ۲، ستون: ۱) جای بسیار خوبی برای خانهی درختی است.
ایندکس در Rust از ۰ شروع میشود
طبق قرارداد، محتویات دنبالههای مرتب مقادیر در Rust از ۰ شمارهگذاری میشوند («ایندکس» میشوند). این موضوع صرفنظر از آنچه بقیهی توضیحات تمرین در این README میگوید اعمال میشود، مثلاً اشاره به ایندکسهایی که از ۱ شروع میشوند، بنابراین برای تبدیل آن شمارههای ایندکس به شمارههای ایندکس Rust باید ۱ کم کنید.
نکتهی کارایی
این تمرین برای ذخیرهی محتوای ماتریسها از یک وکتورِ وکتورها استفاده میکند. در حالی که این تمرین برای کمک به دانشآموزان در درک مفاهیم پایه دربارهی وکتورها طراحی شده است، مانند ایندکس کردن و اینکه انواع دادهی تودرتو مجاز هستند، وکتورِ وکتورها انتخاب غیربهینهای برای جبر ماتریسی با کارایی بالا و هر پردازش کارآمد مشابه روی حجم بیشتری از داده است.
توضیح مفصل این ناکارآمدی فراتر از حیطهی این تمرین و بهطور کلی این مسیر یادگیری است. این جنبه به محلیت کش معروف است و اگر میخواهید دربارهی جزئیات معماری رایانهی مدرن بیشتر بدانید، میتوانید با کلیک روی آن پیوند یک مقدمهی خوب دربارهی آن پیدا کنید.
