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

[sa1378]

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

# Irysc 1
الگوریتمی ارائه بدین که عدد n رو بهش بدی و توی خروجی مقسوم علیه های اول اونو چاپ کنه.

 

[joomine.com]

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

یه سوال اوردر الگوریتمی که ارایه میدیم مهمه؟؟
این یه ایده :
اول میایم تمام مقسوم علیه هاشو به دست میاریم.به این شیوه که باقیمانده ی عدد رو بر اعداد کوچکتر حساب میکنیم.اگه صفر بود میشه مقسوم علیه اون عدد.
بعد این مقسوم علیه ها(که به ترتیب خودشون سورت شدن) رو میایم از اولش شروع می کنیم و با ترتیب مضارب اون رو از لیست حذف می کنیم و روندو ادامه میدیم .
در اخر اعدادی که باقی میمونن جواب مسئله هستند.
توی پیاده سازی از یه سری ترفند ها برای بهبود الگوریتم میشه استفاده کرد که واقعا بیان کردنش خیلی سخته به صورت فارسی تو اینجا.
فکر کنم گند زدم با این جواب دادنم.
جواب نمیدادم بهتر بود!!
من برم یه سوال خوب پیدا کنم.
اگه بد جواب دادم یا ایدم بد بود بگید که دیگه جواب ندم به سوالا.
بازم ببخشید.
...........................................
...........................................
سوال دوماینو دقیقا از یه جا کپی کردم)(دوستان قوی اطلاع دارن)
امیدوارم سوال مناسبی انتخاب کرده باشم:
# Irysc 2
دنباله ای از اعداد حقیقی را در نظر بگیرید.الگوریتمی ارایه دهید که زیردنباله ای به هم چسبیده را بیابد به گونه ای که حاصل ضرب اعداد در بین همه ی زیر دنباله ها بیشینه باشد.(حاصل ضرب دنباله ی تهی ۱ است)
سوال تاکید کرده که از o(n) باشه اما شما هر چی ارایه بدید قبوله

 

[sa1378]

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

یه سوال اوردر الگوریتمی که ارایه میدیم مهمه؟؟
این یه ایده :
اول میایم تمام مقسوم علیه هاشو به دست میاریم.به این شیوه که باقیمانده ی عدد رو بر اعداد کوچکتر حساب میکنیم.اگه صفر بود میشه مقسوم علیه اون عدد.
بعد این مقسوم علیه ها(که به ترتیب خودشون سورت شدن) رو میایم از اولش شروع می کنیم و با ترتیب مضارب اون رو از لیست حذف می کنیم و روندو ادامه میدیم .
در اخر اعدادی که باقی میمونن جواب مسئله هستند.
توی پیاده سازی از یه سری ترفند ها برای بهبود الگوریتم میشه استفاده کرد که واقعا بیان کردنش خیلی سخته به صورت فارسی تو اینجا.
فکر کنم گند زدم با این جواب دادنم.
جواب نمیدادم بهتر بود!!
من برم یه سوال خوب پیدا کنم.
اگه بد جواب دادم یا ایدم بد بود بگید که دیگه جواب ندم به سوالا.
بازم ببخشید.
...........................................
...........................................
سوال دوماینو دقیقا از یه جا کپی کردم)(دوستان قوی اطلاع دارن)
امیدوارم سوال مناسبی انتخاب کرده باشم:
دنباله ای از اعداد حقیقی را در نظر بگیرید.الگوریتمی ارایه دهید که زیردنباله ای به هم چسبیده را بیابد به گونه ای که حاصل ضرب اعداد در بین همه ی زیر دنباله ها بیشینه باشد.(حاصل ضرب دنباله ی تهی ۱ است)
سوال تاکید کرده که از o(n) باشه اما شما هر چی ارایه بدید قبوله

نه خوب بود الگوریتمت حالا
ولی یه راه بهترم هست که مد نظر من بود:
میایم از عدد 2 شروع میکنیم و هربار یدونه زیاد میکنیمش
حالا توی هر مرحله اگه n بر عدد ما بخش پذیر بود این عدد رو چاپ میکنیم و تا جایی که امکان داره n رو بر عدد تقسیم میکنیم...

خیلی هم شیک و مجلسی

.....................................

برای سوال شما هم تا فردا شب بقیه وقت دارن جواب بدن بعدش خودم میدم

 

[sorooshz]

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

جواب # Irysc 2

​

برای این سوال می تونیم تمام جفت های اعداد رو در نظر بگیریم و اگر حاصل ضرب اعداد آرایمون( از اولین عدد تا دومین عدد) بیشتر از max شد , با مقدار max جایگزین می شه و در آخر زیر دنباله ی نهایی که مقدارش از max بیشتر شد رو چاپ می کنیم
( مقدار max اولیه 1 هستش )

# Irysc 3​

برای سوال بعدی هم خیلی فکر کردم که چه سوالی انتخاب کنم و بالاخره یکی پیدا کردم! امیدوارم خوب باشه
سوال اینه که ما دو تا رشته (‌string) داریم به اسم a , b
می خوایم بدونیم به چند طریق می تونیم رشته ی b رو به دو قسمت تقسیم کنیم به صورتی که توی هر دو قسمت بتونیم با حذف تعدادی از حروف به رشته ی a برسیم !
خودم هم نفهمیدم چی گفتم!
بذارین مثال بزنم
فرض کنین a = hello , b = hellohello باشه
خوب ما فقط به یک طریق می تونیم رشته ی b رو به دو قسمت hello , hello تقسیم کنم به صورتی که با حذف ۰ کاراکتر از اون دو قسمت بتونیم رشته ی a رو ببینیم
ولی اگر داشته باشیم a = hello , b = helloHellllllo باید یه تعدادی از l ها رو حذف کنیم ولی بازم جواب ۱ هستش
و اگر داشته باشیم a = hello , b = hello جواب طبیعتا می شه ۰
به عنوان آخرین مثال اگر a = a , b = aaaaaaaaaaaaaa باشه جواب می شه 13
(البته فکر نکنین سوال رو خودم طراحی کردم ها!)

 

[sa1378]

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

# Irysc 2
دنباله ای از اعداد حقیقی را در نظر بگیرید.الگوریتمی ارایه دهید که زیردنباله ای به هم چسبیده را بیابد به گونه ای که حاصل ضرب اعداد در بین همه ی زیر دنباله ها بیشینه باشد.(حاصل ضرب دنباله ی تهی ۱ است)

راه حل O(N) برای علاقه مندان

متغییر ها : ans=1,pos=1,neg=1
میایم از اول آرایه شروع میکنیم تا آخرش
توی هر مرحله اگه

بود که یعنی اگه ضرب کنیمش حاصلمون زیادتر میشه:

​

و همچنین اگه

و

یعنی اینکه اگه حاصلمون رو در این عضو ضرب کنیم بهتر از هیچی هست و از مقدار اولیه که 1 هست بیشتره پس بازم همون کار بالایی رو میکنیم

حالا اگه

ولی

بود یعنی اینکه بهتره از اول شروع کنیم پس مینویسیم:

و همچنین اگه

بود هم که اگه ضرب کنیم کل حاصلمون میشه صفر پس بازم همون کار بالا رو میکنیم و از ضربمون رو ریست میکنیم

و در حالت آخر اگه

یا همون مفنی بود میایم اینکارو میکنیم:

​

حالا این یعنی چی...
میدونیم که اگه تعداد زوجی منفی در هم ضرب بشن مثبت میشن و چیز خوبی هست
پس اولین عدد منفی که بهش رسیدیم حاصل تا اینجای کار رو ذخیره میکنیم تا اگه بعدا به یه منفی دیگه رسیدیم بریزیمش توی pos و اگه نرسیدیم که هیچی
کد رو هم اینجا گذاشتم:
Ubuntu Pastebin

اگه اشکالی هست بگین لطفا

 

[joomine.com]

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

الان من باید حل کنم یا منتظر بمونم یکی دیگه حل کنه؟؟

 

[sa1378]

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

الان من باید حل کنم یا منتظر بمونم یکی دیگه حل کنه؟؟

حل کن اگه دوس داری

 

[Yousefi]

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

سلام.

خب خوبه که این‌جا رو راه انداختین، هر چند که خیلی شلوغ نیست. ولی خب این یه سوال رو داشته باشین:

# Irysc 4
الگوریتمی ارائه دهید که عدد n را از ورودی بگیرد و مجموع تمام (f(iها از ۱تا n را خروجی دهد. (f(i را کوچک‌ترین مقسوم‌علیه اول عدد i تعریف می‌کنیم.
آپدیت توسط sa1378 : اوردر پیشنهادی

 

[joomine.com]

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

جواب # Irysc 2

​

برای این سوال می تونیم تمام جفت های اعداد رو در نظر بگیریم و اگر حاصل ضرب اعداد آرایمون( از اولین عدد تا دومین عدد) بیشتر از max شد , با مقدار max جایگزین می شه و در آخر زیر دنباله ی نهایی که مقدارش از max بیشتر شد رو چاپ می کنیم
( مقدار max اولیه 1 هستش )

# Irysc 3​

برای سوال بعدی هم خیلی فکر کردم که چه سوالی انتخاب کنم و بالاخره یکی پیدا کردم! امیدوارم خوب باشه
سوال اینه که ما دو تا رشته (‌string) داریم به اسم a , b
می خوایم بدونیم به چند طریق می تونیم رشته ی b رو به دو قسمت تقسیم کنیم به صورتی که توی هر دو قسمت بتونیم با حذف تعدادی از حروف به رشته ی a برسیم !
خودم هم نفهمیدم چی گفتم!
بذارین مثال بزنم
فرض کنین a = hello , b = hellohello باشه
خوب ما فقط به یک طریق می تونیم رشته ی b رو به دو قسمت hello , hello تقسیم کنم به صورتی که با حذف ۰ کاراکتر از اون دو قسمت بتونیم رشته ی a رو ببینیم
ولی اگر داشته باشیم a = hello , b = helloHellllllo باید یه تعدادی از l ها رو حذف کنیم ولی بازم جواب ۱ هستش
و اگر داشته باشیم a = hello , b = hello جواب طبیعتا می شه ۰
به عنوان آخرین مثال اگر a = a , b = aaaaaaaaaaaaaa باشه جواب می شه 13
(البته فکر نکنین سوال رو خودم طراحی کردم ها!)

جواب # irysc 3
اول یه مقایسه میکنیم که طول b حد اقل ۲ برابر a باشه.در غیر این صورت جواب صفره .
حالا از سمت چپه b شروع میکنیم و به دنبالاولین کارکتر رشته ی a می گردیم(*)اگه پیدا نشد که باز جواب صفره.اگه پیدا شد،تمام کارکتر های اول تا خود اون کارکتری که پیدا کردیمو از b حذف میکنیم.
حال به شیوه ی قبل دنبال دومین کارکتر a در b می گردیم.
این روند ادامه پیدا می کنه تا موقعی که یا کل a پیدا بشه یا وسط کار یکی از کارکتر ها نباشه که در این صورت جواب صفره
در این مرحله بر عکس مرحله ی قبل عمل می کنیم:
به این صورت که از سمت راست b شروع می کنیم و به دنبال کارکتر اخر a میگردیم.
و روند رو ادامه میدیم.اگه جایی کارکتری از a پیدا نشد جواب صفر خواهد بود.
در غیر این صورت جواب سوال برابر طول رشته ی باقی مانده+۱ خواهد بود.
سوال بعدی رو هم که یکی از دوستان زحمتشو کشید.
موفق باشید.

 

[joomine.com]

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

سلام.

خب خوبه که این‌جا رو راه انداختین، هر چند که خیلی شلوغ نیست. ولی خب این یه سوال رو داشته باشین:

# Irysc 4
الگوریتمی ارائه دهید که عدد n را از ورودی بگیرد و مجموع تمام (f(iها از ۱تا n را خروجی دهد. (f(i را کوچک‌ترین مقسوم‌علیه اول عدد i تعریف می‌کنیم.
آپدیت توسط sa1378 : اوردر پیشنهادی

سلام به همه دوستان.
امیدوارم بقیه هم بیان تو این تاپیک فعالیت کنن که یکم رونق بگیره،

جواب# Irysc 4
یه متغیر با مقدار صفر داریم،
حالا میایم غربال اراتستن را برای n انجام میدیم،
در هر مرحله که میخوایم عددی رو از لیست حذف کنیم به اندازه ی عدد مرحله به متغیرمون اضافه میکنیم.(منظورم از عدد مرحله عددیه که داریم مضرباشو خط میزنیم)
در اخر هم باید مجموع اعداد باقی مانده(اعداد اول ۱ تا n ) رو هم اضافه کنیم.
من فعلا برم دنبال یه سوال بدرد بخور.
موفق باشید

--------------------------------------------
# Irysc 5
یک دنباله از اعداد به شما داده شده است و شما باید طول طولانی‌ترین زیردنباله‌ی صعودی آن را پیدا کنید.
(توجه کنید که قرار نیست زیردنباله ی پیدا شده متوالی باشه برای مثال در دنباله ی ۱،۵،۳،۴،۲،۷ جواب برابر ۴(۱،۳،۴،۷) می باشد)
اوردر ذکر نمیکنم اما سعی کنید یه ایده ی خوب ارایه بدید.

 

[sa1378]

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

# Irysc 5
یک دنباله از اعداد به شما داده شده است و شما باید طول طولانی‌ترین زیردنباله‌ی صعودی آن را پیدا کنید.
(توجه کنید که قرار نیست زیردنباله ی پیدا شده متوالی باشه برای مثال در دنباله ی ۱،۵،۳،۴،۲،۷ جواب برابر ۴(۱،۳،۴،۷) می باشد)
اوردر ذکر نمیکنم اما سعی کنید یه ایده ی خوب ارایه بدید.

خب اوردرش رو بگو دیگه
الان من با n^2 میتونم جواب بدم
بهترم میشه؟

 

[joomine.com]

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

راستش با nlgn هم میشه.اما به نظرم الگوریتمتو بگی ضرر نداشته باشه[emoji5]

 

[sa1378]

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

راستش با nlgn هم میشه.اما به نظرم الگوریتمتو بگی ضرر نداشته باشه[emoji5]

جواب # Irysc 5
خب من اینو میگم صبر میکنیم بقیه Nlogn رو بگن
اول یه آرایه برا جوابمون میگیریم اسمشو میزاریم dp[] که مقدار اولیه برای همه اعضا صفر هست(قراره توی این متغییر به ازای هر عضو حداکثر طول دنباله مورد نظرمون که به این عضو ختم میشه رو ذخیره کنیم)
میایم از اول آرایه شروع میکنیم تا آخرش
به ازای هر عضو

میایم dp عضو های قبلشو چک میکنیم و ماکسیمم dp برای عضو هایی که شرط

رو دارن رو ذخیره میکنیم(توی یه متغییر مثلا max)
حالا

رو میکنیم max+1
یعنی میایم این عضو رو توی دنباله ای که بیشترین طول رو داره در نظر میگیریم

این حلقه مون که تموم شد میایم از اول تا آخر آرایه dp رو میگردیم و ماکسیمم مقدار رو چاپ میکنیم

 

[joomine.com]

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

سوال بعدی رو خودت میزاری یا اون کسی که nlogn ارایه داد بزاره؟؟
به نظرم خودت بزاری بهتر باشه،اخه اون nlgn یه کوچولو سخته.این جا هم که کاربر فعال زیاد نداریم!!

 

[sa1378]

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

سوال بعدی رو خودت میزاری یا اون کسی که nlogn ارایه داد بزاره؟؟
به نظرم خودت بزاری بهتر باشه،اخه اون nlgn یه کوچولو سخته.این جا هم که کاربر فعال زیاد نداریم!!

# Irysc 6
یک آرایه از اعداد 1و2و3 داریم که میخوایم سورتشون کنیم
کمترین تعداد swap برای اینکار را پیدا کنین
اوردر:

 

[joomine.com]

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

# Irysc 6
یک آرایه از اعداد 1و2و3 داریم که میخوایم سورتشون کنیم
کمترین تعداد swap برای اینکار را پیدا کنین
اوردر:

جواب# Irysc 6

اول یه بار رشته رو طی می کنیم و تعداد ۱ و ۲ و۳ ها رو به طور جداگانه می شماریم.
حال رشته باید به سه بلوک تقسیم شود که طول هر کدام را می دانیم(با توجه به تعداد ۱ ها ۲ ها و ۳ ها)طول ها را به ترتیب با a و b و c نمایش می دهیم.

حال یک بار دیگر رشته را طی می کنیم و در این راه این ها را حساب می کنیم.
تعداد ۱ های موجود در بلوک ۱(x)
تعداد ۳ های موجود در بلوک یک(y)
تعداد ۱ های موجود در بلوک ۳(z)
تعداد ۳های موجود در بلوک ۳(t)
بدیهی است که برای اینکه تمام ۱ ها در سر جای خودشان قرار بگیرند باید باید a-x حرکت انجام بگیرد.
در طی این حرکت ها چنانچه روش درستی انتخاب کنیم ، min(y,z) ۳ هم در جای خود قرار می گیرند پس برای مرتب کردن بلوک سوم به c-(min(x,y)+t) حرکت انجام خواهیم داشت و پس از انجام انها کل رشته مرتب خواهد شد.
________________________________________
# Irysc 7

در یک مهمانی، n نفر حضور دارند. بین هر دو نفر A,B یک رابطه به این صورت برقرار است که یا A نفر B را می‌شناسد، یا بالعکس. می‌خواهیم با تعدادی پرسش، به صورت زیر، متوجه بشویم که آیا شخصی وجود دارد که همه را بشناسد یا خیر. 
پرسشهایی که میتوانیم بپرسیم اینگونه اند:
: آیا شخص A شخص B را می‌شناسد؟
اوردر پیشنهادی o)n) می باشد.
_______________________________________
راه حل بهینه ی سوال ۵ رو هم فردا میزارم اگه کسی تا اون موقع نزاشت.
پایدار باشید.

 

[sa1378]

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

# Irysc 7
در یک مهمانی، n نفر حضور دارند. بین هر دو نفر A,B یک رابطه به این صورت برقرار است که یا A نفر B را می‌شناسد، یا بالعکس. می‌خواهیم با تعدادی پرسش، به صورت زیر، متوجه بشویم که آیا شخصی وجود دارد که همه را بشناسد یا خیر.
پرسشهایی که میتوانیم بپرسیم اینگونه اند:
: آیا شخص A شخص B را می‌شناسد؟
اوردر پیشنهادی o)n) می باشد.

سوال رو خوب نفهمیدم
یعنی الان باید با n پرسش بفهمیم کسی آیا همه رو میشناسه؟

 

[joomine.com]

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

سوال رو خوب نفهمیدم
یعنی الان باید با n پرسش بفهمیم کسی آیا همه رو میشناسه؟

من خیلی الگوریتم و تحلیل الگوریتم نخوندم اما فک کنم وقتی میگیم o(n) ،
n میتونه ضریب عددی ثابت هم داشته باشه.
این طور نیست؟؟
درست یادم‌نیست ولی برای این سوال فکر کنم با یه چیز حدود 2n یا 3n پرسش جواب رو پیدا کرد.
چه‌دو چه سه و چه بیشتر از این ۲ اوردرشون میشه o(n).

 

[sorooshz]

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

جواب

# Irysc 7
​

می تونیم با پرسیدن هر سوال یک نفر رو حذف کنیم ( منظور از حذف کردن اینه این فرد که از لیست افرادی که شاید یکی از اونها همه افراد دیگه رو بشناسه حذف بشه )
آخر کار یه نفر باقی می مونه و می تونیم برای این ۱ نفر بیایم چک کنیم که آیا همه رو می شناسه یا نه ؟ اگر می شناخت جواب می شه بله و در غیر این صورت جواب می شه خیر

# Irysc ۸
​

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

 

[sa1378]

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

جواب

# Irysc 7
​

می تونیم با پرسیدن هر سوال یک نفر رو حذف کنیم ( منظور از حذف کردن اینه این فرد که از لیست افرادی که شاید یکی از اونها همه افراد دیگه رو بشناسه حذف بشه )
آخر کار یه نفر باقی می مونه و می تونیم برای این ۱ نفر بیایم چک کنیم که آیا همه رو می شناسه یا نه ؟ اگر می شناخت جواب می شه بله و در غیر این صورت جواب می شه خیر

# Irysc ۸
​

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

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