نقل قول:
نقل قل رو هم تو پست 14 زده بودم.
Printable View
نقل قول:
نقل قل رو هم تو پست 14 زده بودم.
سلام
کمکم کنین لطفا""
یه برنامه میخوام که ::
فرضا در یک مستطیل تعدادی نقطه به صورت تصادفی وجود داره
الگوریتمی طراحی کنید که بزرگترین دایره در بین نقاط این مستطیل جا میشه رو پیدا کنه بدون ایمکه هیچ نقطه ای در داخل دایره قرار بگیره
ممنونم میشم کمکم کنین
این در حد سوال المپیاده.
یه خرده فکر ریاضی می خواد.
اینو ببینید:
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
خب مسلما باید بیشترین فاصله بین نقاط رو پیدا کنینقل قول:
یعنی باید فاصله یه نقطه رو با همه نقاط به دست بیاری
از فورمول: [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
دایره رو می تونی جایی رسم کنی که کمترین فاصلش از بقیه نقاط بیشتر باشه
به طور مثال
اگه سه نقطه a,b,c داشته باشیم
اول فاصله a,b و a,c رو به دست میاری
بعد کمترین فاصله رو نگه می داری.
دفعه بعد فاصله b,a و b,c رو بدست میاری و کمترین فاصله رو نگه می داری
در مرحله بعد فاصله c,a و c,b رو بدست میاری و طبق روال کمترین فاصله رو نگه می داریم
در نهایت از بین فاصله هایی که بدست آوردیم بیشترینش رو پیدا می کنیم و اگر اون فاصله مربوط به a بود روی a رسم می کنیم و ...
البته این ایده من بود حتما راه های بهتری هم هست
ممکنه بگین تو کدوم المپیاد این سوال مطرح شد؟؟نقل قول:
آخه اینو استادمون از ما میخواد!!
مرسینقل قول:
خیلی کمکم کرد:10:
فقط گفتم در حد المپیاد. یعنی اگه بخوایم خوب روش کار کنیم کار راحتی نیست.نقل قول:
ممکنه بگین تو کدوم المپیاد این سوال مطرح شد؟؟
برنامه ای که یک ماتریس مجاورت را از ورودی خوانده و کمترین تعداد رنگ مورد نیاز برای رنگ آمیزی گراف متناظر با آن را در خروجی چاپ کند
مربوط به طراحی الگوریتمه واقعا دیگه ضروریه ممنون میشم کمکم کنین
سلاممیشه بیشتر توضضیح بدینواقعا متوجه نشدمتا اونجایی که من می دونم از هر ماتریس مجاورت فقط میشه یه شکل گراف کشید یعنی شکل به دست اومده یکتا میشهاشتباه می کنم؟نقل قول:
بی خیال امروز خواست که گفتم ننوشتم!! :دینقل قول:
مرسی که توجه داری.
اینو ببین میشه چی کارش کرد؟؟
برنامه ای که به صورت غیر بازگشتی مرتب سازی سریع را روی یک آرایه n عنصری انجام دهد
و این
برنامه ای که ماتریس مجاورت n*n را خوانده چک کند آیا میتوان این ماتریس را با n-2 رنگ رنگ آمیزی نمود؟؟ در نهایت گراف این ماتریس هم به شکل ساده ( گرافیکی نه ) رسم کنه...
خو برنامه اول که خیلی سادس ، روش های مختلفی واسه مرتب سازی وجود دارهنقل قول:
اینجا اکثر مرتب سازیا رو با الگوریتماش گفته(ویکی پدیا)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
به طور مثال
مرتب سازی حبابی:
که نتایجش به صورت زیره:کد:void bubble_sort (int arr [ ] , int n)
{
register int i , j , t , c;
(-- for (i = n - ۲ ; i >= ۰ ; i
{
c = ۰;
(++ for (j = ۰ ; j <= i ; j
if (arr [ j ] > arr [ j + ۱ ])
{
; ] t = arr [ j
arr [ j ] = arr [ j + ۱ ];
; arr [ j + ۱ ] = t
C++;
}
(if (c == ۰
; break
}
}
فرض کنید می‌خواهیم n داده به صورت صعودی مرتب شوند. عنصر اول را با با عنصر دوم مقایسه کرده، و در صورتی که عنصر اول بزرگتر باشد باشد جای عنصر اول و دوم را عوض می‌کنیم. همین کار را با عناصر دوم و سوم انجام می‌دهیم و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تمام شد بزرگترین عنصر بین داده‌ها به آخر لیست می‌رسد . حالا یک بار دیگر از اول این کار را انجام می‌دهیم اما این بار تا عنصر (n -۱)ام ادامه می‌دهیم (عنصر nام در مرحله اول در جای خودش قرار گرفته). باز هم این کار را تا عنصر (n - ۲)ام تکرار می‌کنیم ، و بازهم .... تا اینکه بالاخره داده‌ها مرتب می‌شوند. مثلا:
۰ - ۰) ۵ ۶ ۴ ۲
۱ - ۱) ۵ ۶ ۴ ۲
۱ - ۲) ۵ ۴ ۶ ۲
۱ - ۳) ۵ ۴ ۲ ۶
۲ - ۱) ۴ ۵ ۲ ۶
۲ - ۲) ۴ ۲ ۵ ۶
۳ - ۱) ۲ ۴ ۵ ۶
مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می‌شوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:
۰ - ۰) ۰ ۷ ۱ ۳ ۵ ۴
۱ - ۱) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۲) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۳) ۰ ۱ ۳ ۷ ۵ ۴
۱ - ۴) ۰ ۱ ۳ ۵ ۷ ۴
۱ - ۵) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۱) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۲) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۳) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۴) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۲) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۳) ۰ ۱ ۳ ۴ ۵ ۷
۴ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
۴ - ۲) ۰ ۱ ۳ ۴ ۵ ۷
۵ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
همونطور که می‌بینید انتهای مرحله ۲ داده‌ها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحله‌ای رسیدیم که هیچ جابجایی در اون رخ نداد نتیجه میشه که داده‌ها مرتب هستن (مرحله سوم). پس بعد از مرحله ۳ مطمئن می‌شیم که داده هامون مرتب شدن و نیازی به مراحل ۴ و ۵ نیست. پیاده سازی (مرتب سازی حبابی) در c++