♫_-_♫ مارتن الگوریتم کامپیوتر ♫_-_♫

[joomine.com]

پاسخ : ♫_-_♫ مارتن الگوریتم کامپیوتر ♫_-_♫

خب یه چیزی
ممکنه سوال رو که میپرسیم جوابش بله باشه و کسی حذف نشه
اونوقت چی؟
مثلا n-1 سوال از یه نفر میپرسی جوابش باه هست ولی جواب سوال بعدی که میپرسی نه هست
اونوقت بعد n مرحله فقط دو نفر حذف شدن

ذکر شده رابطه دو حالته،
یا این اونو میشناسه
یا اون اینو
پس با هر سوال خیلی راحت یه نفر حذف میشه.
در مورد الگوریتم nlgn یکی از مسئله هایی هم که قرار بود بگم،
یکم‌سنگینه اما اگه کسی واقعا میخواد بدونه میتونه به کتاب کریتیو(فصل دنباله ها) مراجعه کنه.
با ارزوی موفقیت واس همه،
خداحافظ[emoji8]

 

[sa1378]

پاسخ : ♫_-_♫ مارتن الگوریتم کامپیوتر ♫_-_♫

# Irysc ۸
​

یک دنباله از اعداد به ما داده شده و ما می خوایم بدونیم که آیا امکانش هست حداکثر با ۱ swap , دنباله مرتب شود؟؟
مثلا توی دنباله ی 1 2 3 می تونیم با swap کردن 3 , 1 دنباله رو مرتب کنیم
و دنباله ی ۳ ۲ ۲ ۱ خودش مرتبه و نیازی به swap نداره

میایم این آرایه مون رو توی یه آرایه دیگه هم ذخیره میکنیم
حالا آرایه دومی رو سورت میکنیم
بعد میایم به ازای i از 1 تا n :
اگه عضو iام آرایه اول با آرایه دوم فرق داشت res++
آخر کار اگه res صفر یا دو بود جواب بله هست


# Irysc 9

یه صفحه n*m داریم که یه سری خونه هاش پر شده هستن
میخوایم اون خونه هایی که پر نشدن رو با دومینو های 1x2 پر کنیم
اگه نمیشه بگین نمیشه
اگه میشه پرش کنین
(خونه های پر * هستن و خونه های خالی . هست)
مثال: ( دومینو های عمودی با ^v نشون داده میشن و افقی ها با <> )

نکته:
اگه خونه های خالی مجاور رو به هم وصل کنیم یه گراف تشکیل میشه...تضمین میشه که اون گراف دور نداره

 

[sorooshz]

پاسخ : ♫_-_♫ مارتن الگوریتم کامپیوتر ♫_-_♫

جواب
# Irysc 9
اول میایم از بالا سمت چپ شروع می کنیم و هی می ریم جلو
به هر خونه ی خالی که رسیدیم چک می کنیم که تعداد خونه های مجاوش که خالی هستن چند تاست؟؟

۱
اگر فقط یکی از خونه های مجاوش خالی بود , و اگر قرار باشه ما بتونیم این جدولی که بهمون داده شده رو پر کنیم حتما باید یکی از دومینو ها شامل این دو خونه باشه
که عمودی بودن یا افقی بودنش نسبت به موقعیت دو عنصرمون معلوم می شه

۲ -
اگر هیچ کدوم از خونه های مجاورش خالی نبود که جواب می شه خیر

ولی اگر بیشتر از یکی از خونه های مجاورش خالی بود , اول می ریم عنصر های خالی ( . ) دیگه ی آرایه رو یه چک
می کنیم و شرط ۱ و ۲ رو براشون چک می کنیم و در صورت نیاز اعمال می کنیم

بعدش برمی گردیم به اون خونه ی اولی
و اگر هنوز هم بیشتر از یکی از خونه های مجاورش خالی بود
به دلخواه یکیشون + خود خونه رو ابعاد دومینو در نظر می گیریم و این دو خونه رو پر می کنیم
و تا زمانی که یا جدول کاملا پر بشه یا اینکه به جایی برسیم که شرط ۲ درست بشه کار رو ادامه می دیم




# Irysc 10
​

الگوریتمی طراحی کنید که با دریافت n , یکی از حالت های ممکن برای قرار دادن n وزیر در صفحه ی شطرنجی n * n را به طوری که هیچ دو وزیری یکدیگر را تهدید نکنند به دست آورده و آن را چاپ کند ( البته می شه سوال رو اینجوری عوض کرد که کلیه حالات ممکن رو چاپ کرد ولی به نظر من سوال بیخودیه! چون برای n های بزرگ , همین که یک حالت رو به دست بیاریم کلی طول می کشه چه برسه به اینکه کل حالات رو به دست آورد)
در ضمن توجه کنید که برای n = 2,3 چنین وضعیتی ممکن نیست
و خروجی باید به این صورت باشه که نقاط خالی با نقطه یا 0 و نقاطی که وزیر دارن با Q یا ۱ مشخص بشه

 

[alirezasaraei]

من خیلی الگوریتم و تحلیل الگوریتم نخوندم اما فک کنم وقتی میگیم o(n) ،
n میتونه ضریب عددی ثابت هم داشته باشه.
این طور نیست؟؟