پروژه پایتون 70232

شرح پروژه

: 

سلام وقت بخیر

الگوریتم و برنامه ای با پایتون برای کوتاه ترین مسیر از بازه اول تا بقیه بازه ها ( از لحاظ وزن)با مرتبه خطی n ؟ هر بازه وزن دارد و بازه ای با وزن صفر وجود ندارد.

شروع و پایان بازه ها عدد صحیح مثبت است و با روش counting sort بازه ها بر اساس انتها مرتب شود 

سپس با مرتبه خطی ، یک successor تعریف کرده که successor هر بازه اولین بازه ای که زمان پایان اش بزرگ‌تر مساوی زمان شروع بازه مورد نظر باشد 

سپس دو تا پشته در نظر گرفته فعال و غیر فعال 

بازه اول همیشه در پشته فعال قرار می گیرد و برای اضافه کردن بازه بعدی اگر successor اش خودش بود یعنی (بازه ای وجود نداشت که انتهاش بعد از شروع این بازه باشد) در پشته غیر فعال قرار می گیرد در غیر اینصورت در پشته فعال قرار می گیرد.

در ادامه هر بازه ای که میخواست اضافه شود ابتدا find successor پیدا کرده یعنی successor  اصلی آن بازه چه بازه ای است.اگر find successor ، فعال بود و بازه ای در پشته غیر فعال وجود داشت با استفاده از disjoint set با آن بازه ادغام می شود و نماینده را بازه ای که انتها بیشتری دارد در نظر می گیریم (یعنی اگر هر یک از این بازه ها successor بازه ای باشند find successor آن بازه میشه بازه ای که بین این دو تا نماینده است)سپس هر دو در پشته فعال درج می شوند یا اگر بازه ای در پشته غیر فعال وجود نداشت ، خود بازه به تنهایی درج می شود

سوال کلی و روند حل اینه استفاده از ساختمان داده های مورد نظر خیلی مهمه

و طبق روندی که گفته شده میخواستم با مرتبه n نه الگوریتم های دیگه مثل دایجسترا

اگر امکان داره براتون بهم بگید که جزییات بیشتر هم بفرستم و تا کی میتونید انجام بدید

مهارت ها و تخصص های مورد نیاز

درباره کارفرما

nikotex

عضویت سه سال پیش

25478 پروژه ثبت شده ،

20 پروژه در حال انجام ،

137 پروژه آماده دریافت پیشنهاد ،

نرخ پذیرش پیشنهاد 14%