صورت مسئله:

الف) یک مهندس برق مداری شامل n ترمینال در یک بورد دوبعدی طراحی نموده است. ترمینال دارای مختصات x و y در فضای دوبعدی می­باشد. باید ولتاژی معادل ۵ ولت به تمام ترمینال‌ها متصل گردد. ولتاژ ۵ ولت به یکی از ترمینال­ها وصل است. الگوریتمی طراحی کنید که به‌عنوان ورودی آرایه‌های x و y که هرکدام از 1 تا n اندیس گذاری شده‌اند، را دریافت کرده و کمترین سیم­بندی لازم در مدار برای اتصال ترمینال‌ها و همچنین نحوه اتصال ترمینال‌ها را محاسبه و چاپ کند.

ب) پیچیدگی زمانی الگوریتم ارائه‌شده در بخش (الف) را محاسبه نمایید.

ج) شکل زیر مداری با 7 ترمینال را نشان می‌دهد. فاصله هر سطر و ستون را یک سانتی‌متر در نظر بگیرید. کمترین سیم بندی لازم در مدار برای اتصال ترمینال‌ها و نحوه اتصال ترمینال‌ها را محاسبه و چاپ نمایید.

راهنمایی: بهتر است ابتدا یک مدل ریاضی برای مسئله پیدا کنید. فاصله اقلیدسی نیز در محاسبات مدنظر باشد.

فایل شامل توضیحات جواب هر قسمت به همراه سورس کد پروژه