![خطر پرتوهای فرابنفش، آلاینده ازون و گرمای بیسابقه | چرا کمیته اضطرار تشکیل نمیشود؟](/files/fa/news/1403/5/5/1236632_213.jpg)
رئیس مرکز تحقیقات آلودگی هوای دانشگاه علوم پزشکی تهران در گفتوگو با جام جم آنلاین:
اگر مساله برای 4 یا 5 روستا طراحی شود، راهحل دستی آن چندان دشوار نخواهد بود، اما اگر تعداد روستاها بیش از 10 باشد، آنوقت این مساله در زمره مسائل «بسیار دشوار برای حل» قرار خواهد گرفت و بنابراین ارائه یک الگوریتم مناسب برای برنامهنویسان اجتنابناپذیر است.
ورودی
ورودی با یک عدد int مثبت تکی (تعداد روستاها) آغاز میشود و روی خطی که حاکی از تعداد حالتهای آزمون است با یک خط خالی (جاخالی) ادامه مییابد.
پس اولین خط هر حالت تست شامل 0<
100<n است که تعداد روستاهای موجود روی نقشه است. برای هر روستا خط ادامه مییابد. ادامه خط شامل 2 عدد حقیقی متوالی برای مرتب کردن روستاهاست.میان هر حالت پیدرپی در آزمایش، یک خط خالی وجود دارد.
خروجی
برنامه شما برای هر حالت آزمایشی باید یک عدد حقیقی تک به دو مکان اعشاری را چاپ کند:
- طول حداقل مجموع خطهای جوهری که با تمام روستاها ارتباط دارد.
- خروجی هر دو حالت متوالی باید توسط یک خط خالی جدا شود.
ورودی نمونه
1
3
1.0 1.0
2.0 2.0
2.0 4.0
خروجی نمونه
3.41
و اما راه حل
همانطور که مشاهده میشود دادههای ورودی مساله یکسری نقطه در فضای دو بعدی است که شامل یک x و یک y است. برای حل مساله باید با استفاده از نقاط داده شده در فضای دو بعدی یک گراف کامل رسم کنیم که وزن هر یال آن برابر با طول بردار مستقیم بین دو نقطه مشخص از ورودی است. بهطور مثال برای ورودی نمونهای که در بالا آورده شده فرض کنیم نقاط ما بهصورت زیر باشد:
A(1.0,1.0)
B(2.0,2.0)
C(2.0,4.0)
ما کشیدن گراف را آغاز میکنیم. طول یال AB برابر 41/1 است این مقدار از فرمول زیر بهدست میآید:
sqrt(math.pow(b(x)-a(x),2)+math.pow(b(y)-a(y),2
فرمول محاسبه طول بردار برای بردارهای دیگر بهترتیب برای AC برابر 16/3 و برای BC برابر 2 است. بسیار خب، ما یک گراف وزندار داریم و با توجه به صورت مساله اینطور برداشت میشود که باید تمام شهرها بههم وصل شوند (یعنی پیدا کردن یک دور در یک گراف که از همه رئوس بگذرد که در اصطلاح به آن دور همیلتونی میگویند) و باید کمترین میزان مصرف جوهر (یا راه پیمودهشده) را داشته باشیم، پس باید در این گراف کوتاهترین دور را حساب کنیم. پس راهحل مساله پیدا کردن کوتاهترین دور همیلتونی است.
شبه کد این برنامه بدین صورت درمیآید:
struct{
double x;
double y;
}point;
struct{
point self;
dictionary«point,double» connectedPoint;
}edge;
point points[n];
edge edges[n];
double calculatelength(point p1,point p2){
return sqrt(pow(p2.x-p1.x,2)+pow(p2.y-p1.y,2));
}
void initializeEdges(point[] points,point current){
edge _edge;
edge.point = current;
foreach(point p in points){
_edge.connectedPoint.add
(p,calculatelength(current,p));
}
}
double calculateShortestPath();
foreach(point p in points){
initializeEdges(points.where(_point=»_point!=p),p);
}
caculateShortesPath();
امیربهاءالدین سبطالشیخ
رئیس مرکز تحقیقات آلودگی هوای دانشگاه علوم پزشکی تهران در گفتوگو با جام جم آنلاین:
سخنگوی کمیسیون بهداشت و درمان مجلس در گفتوگو با جام جم آنلاین:
در یادداشتی اختصاصی برای جام جم آنلاین مطرح شد
جواد فروغی در یادداشتی اختصاصی برای جام جم آنلاین مطرح کرد
گفتوگو با منوچهر آذری، بازیگر،گوینده،مجری وصداپیشه پیشکسوت رادیو و تلویزیون
فاطمه مجلل در گفتوگو با «جامجم»:
رئیس مرکز تحقیقات آلودگی هوای دانشگاه علوم پزشکی تهران در گفتوگو با جام جم آنلاین: