نوشته شده توسط فاطـمه [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
نقل قل رو هم تو پست 14 زده بودم.
نوشته شده توسط فاطـمه [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
نقل قل رو هم تو پست 14 زده بودم.
سلام
کمکم کنین لطفا""
یه برنامه میخوام که ::
فرضا در یک مستطیل تعدادی نقطه به صورت تصادفی وجود داره
الگوریتمی طراحی کنید که بزرگترین دایره در بین نقاط این مستطیل جا میشه رو پیدا کنه بدون ایمکه هیچ نقطه ای در داخل دایره قرار بگیره
ممنونم میشم کمکم کنین
این در حد سوال المپیاده.
یه خرده فکر ریاضی می خواد.
اینو ببینید:
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
خب مسلما باید بیشترین فاصله بین نقاط رو پیدا کنینوشته شده توسط farshidshd [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
یعنی باید فاصله یه نقطه رو با همه نقاط به دست بیاری
از فورمول:
دایره رو می تونی جایی رسم کنی که کمترین فاصلش از بقیه نقاط بیشتر باشه
به طور مثال
اگه سه نقطه a,b,c داشته باشیم
اول فاصله a,b و a,c رو به دست میاری
بعد کمترین فاصله رو نگه می داری.
دفعه بعد فاصله b,a و b,c رو بدست میاری و کمترین فاصله رو نگه می داری
در مرحله بعد فاصله c,a و c,b رو بدست میاری و طبق روال کمترین فاصله رو نگه می داریم
در نهایت از بین فاصله هایی که بدست آوردیم بیشترینش رو پیدا می کنیم و اگر اون فاصله مربوط به a بود روی a رسم می کنیم و ...
البته این ایده من بود حتما راه های بهتری هم هست
Last edited by فاطـمه; 14-05-2009 at 19:12.
ممکنه بگین تو کدوم المپیاد این سوال مطرح شد؟؟نوشته شده توسط CppBuilder2006 [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
آخه اینو استادمون از ما میخواد!!
مرسینوشته شده توسط فاطـمه [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
خیلی کمکم کرد
فقط گفتم در حد المپیاد. یعنی اگه بخوایم خوب روش کار کنیم کار راحتی نیست.ممکنه بگین تو کدوم المپیاد این سوال مطرح شد؟؟
برنامه ای که یک ماتریس مجاورت را از ورودی خوانده و کمترین تعداد رنگ مورد نیاز برای رنگ آمیزی گراف متناظر با آن را در خروجی چاپ کند
مربوط به طراحی الگوریتمه واقعا دیگه ضروریه ممنون میشم کمکم کنین
سلاممیشه بیشتر توضضیح بدینواقعا متوجه نشدمتا اونجایی که من می دونم از هر ماتریس مجاورت فقط میشه یه شکل گراف کشید یعنی شکل به دست اومده یکتا میشهاشتباه می کنم؟نوشته شده توسط farshidshd [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
بی خیال امروز خواست که گفتم ننوشتم!!نوشته شده توسط فاطـمه [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
مرسی که توجه داری.
اینو ببین میشه چی کارش کرد؟؟
برنامه ای که به صورت غیر بازگشتی مرتب سازی سریع را روی یک آرایه n عنصری انجام دهد
و این
برنامه ای که ماتریس مجاورت n*n را خوانده چک کند آیا میتوان این ماتریس را با n-2 رنگ رنگ آمیزی نمود؟؟ در نهایت گراف این ماتریس هم به شکل ساده ( گرافیکی نه ) رسم کنه...
خو برنامه اول که خیلی سادس ، روش های مختلفی واسه مرتب سازی وجود دارهنوشته شده توسط farshidshd [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
اینجا اکثر مرتب سازیا رو با الگوریتماش گفته(ویکی پدیا)
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
به طور مثال
مرتب سازی حبابی:
که نتایجش به صورت زیره:کد:برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید
فرض کنید میخواهیم n داده به صورت صعودی مرتب شوند. عنصر اول را با با عنصر دوم مقایسه کرده، و در صورتی که عنصر اول بزرگتر باشد باشد جای عنصر اول و دوم را عوض میکنیم. همین کار را با عناصر دوم و سوم انجام میدهیم و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تمام شد بزرگترین عنصر بین دادهها به آخر لیست میرسد . حالا یک بار دیگر از اول این کار را انجام میدهیم اما این بار تا عنصر (n -۱)ام ادامه میدهیم (عنصر nام در مرحله اول در جای خودش قرار گرفته). باز هم این کار را تا عنصر (n - ۲)ام تکرار میکنیم ، و بازهم .... تا اینکه بالاخره دادهها مرتب میشوند. مثلا:
۰ - ۰) ۵ ۶ ۴ ۲
۱ - ۱) ۵ ۶ ۴ ۲
۱ - ۲) ۵ ۴ ۶ ۲
۱ - ۳) ۵ ۴ ۲ ۶
۲ - ۱) ۴ ۵ ۲ ۶
۲ - ۲) ۴ ۲ ۵ ۶
۳ - ۱) ۲ ۴ ۵ ۶
مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم میشوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:
۰ - ۰) ۰ ۷ ۱ ۳ ۵ ۴
۱ - ۱) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۲) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۳) ۰ ۱ ۳ ۷ ۵ ۴
۱ - ۴) ۰ ۱ ۳ ۵ ۷ ۴
۱ - ۵) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۱) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۲) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۳) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۴) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۲) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۳) ۰ ۱ ۳ ۴ ۵ ۷
۴ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
۴ - ۲) ۰ ۱ ۳ ۴ ۵ ۷
۵ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
همونطور که میبینید انتهای مرحله ۲ دادهها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحلهای رسیدیم که هیچ جابجایی در اون رخ نداد نتیجه میشه که دادهها مرتب هستن (مرحله سوم). پس بعد از مرحله ۳ مطمئن میشیم که داده هامون مرتب شدن و نیازی به مراحل ۴ و ۵ نیست. پیاده سازی (مرتب سازی حبابی) در c++
هم اکنون 1 کاربر در حال مشاهده این تاپیک میباشد. (0 کاربر عضو شده و 1 مهمان)