مروری بر الگوریتم

[MiladRZ]

سلام من میلاد رضایی هستم از بچه های کرج http://acm.sgu.ru/teaminfo.php?id=051583

خوب هدفم از این پست یه جورایی معرفی خودم و همچنین معرفی یکی از مسئله های خیلی قشنگ تو گراف به اسم توپولوژیکال سرت هستش البته فکر کنم بیشترتون بلد باشین

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

ورودی : یه n که تعداد کله درس هاست و , یه m که تو m خط بعدی تو هر خط 2 به صورت a , b میاد که نشون میده a پیش نیاز b هستش

خروجی : یه ترتیب که بتونیم بر اساس اون برنامه درس خوندنمونو بچینیم

خوب باید یه الگوریتم بدیم که مسئله رو حل کنه ولی چه جوری؟

بی مقدمه می رم سره اصله مطلب :
سعی می کنیم از روی مسئله یک گراف جهت دار بسازیم به صورتی که اگر درس a پیش نیاز درس b بود یه یال از a به b میکشیم
شرح الگوریتم:
در مرحله اول سعی می کنیم راسی را پیدا کنیم که درجه آن 0 باشد واضح است که این راس در هر گونه گرافی وجود دارد (سعی کنید با اکسترمال اثبات کنید) این راس را حذف می کنیم و آن را چاپ می کنیم وقتی این راس حذف می شود راس های خروجی از آن نیز حذف می شه خوب دوباره به مرحله اول برمی گردیم و اینکار را تا جایی ادامه میدهیم که همه راس ها چاپ شده باشند
اثبات الگوریتم: سعی کنید با استقرا اثبات کنید (منظورم ثابت حلقست فکرکنم!!!)

اگر اشتباه نکنم برنامه از (O(V + E هستش

خوب اینم یه سری تمرین براتون که برین توپوژیکال سرت رو کامل یاد بگیرین با حله اینا(البته دومی زیاد ربط نداره ها!!!)
http://acm.timus.ru/problem.aspx?space=1&num=1022
http://acm.timus.ru/problem.aspx?space=1&num=1280

اینم کدهای منه برای سوال ها که جفتش اکسپت هم شدن
http://paste.ubuntu.com/1400162/
http://paste.ubuntu.com/1400165/

بازم اگه توضیحم بد بود بزارین به حساب بی تجربگیم

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

 

[most wanted]

با سلام

بلاخره مرحله 2 هم خوب یا بد رفت همونطور که می دونید همه جا توصیه می کنن که مستقل از امتحان مرحله 2 یی که دادن بشینن و کد بزنن و الگوریتم کار کنن وخلاصه که باید به فکر مرحله 3 باشیم ، تاپیک برای صرفاً کد زنی زده شده و درسته مرحله 3 رو میشه بدون الگوریتم خاصی هم گذروند ولی بلد بودن الگوریتم ها میتونه کارمون رو خیلی راحت تر کنه. \/

برای همین ام خوبه که تو یه تاپیک از الگوریتم ها ساده شروع کنیم یه توضیحی برای هر کدومشون بدیم و یه سورس کدی هم براشون بذاریم[nb]بهتره که تو این تاپیک ایده هایی که تو اُردر کمک میکنن ولی ربطی به الگوریتم ندارن بررسی نشن چون بحث خیلی پراکنده میشه و نمیشه تموم ـِش کرد،پس فقط اگه واسه بهینه سازی ایده الگوریتمی داشتید مطرح کنید.[/nb] که اگه مشکلی تو کدش براتون مونده بود حل بشه و اردرش رو بررسی می کنیم بعد هم برای هر الگوریتم پیشنهاد هایی برای بهینه کردنش ارائه می دیم .
چون برای این که بتونیم تو سریع ترین زمان یه کد بدون نقص با اردر و زمان بندی درستی داشته باشیم نیازه با اردر تمام الگوریتم هایی که استفاده می کنیم آشنایی کامل داشته باشیم و اگه به اوردر برنامه در ابتدا توجه نکنیم ممکنه خیلی وقتا ایده هایی که می زنیم رو سوالا اُردر های خیلی زیادی داشته باشن و که باید موقع کد زدن به این چیزا توجه کنیم یه شکلی نشه که هِی کد بزنیم بعد ببینیم زود جواب میده یا نه ،یکی از دغدغه هامون باید الگوریتم و اُردرِش باشه.

از ساده ترین الگوریتم های هر کدوم شروع کنیم و به ترتیب اُردر جلو بریم.هر کس هم ایده ای واسه بهینه سازی هرکدوم داشت بیاد راجع بش بحث کنیم.

اولین الگوریتم مهم هم مرتب سازی هاست که به نظرم از اونا شروع کنیم و کم کم پیش بریم که تا مرحله 3 الگوریتم های گراف هم تموم کنیم.

 

[most wanted]

پاسخ : مروری بر الگوریتم های مفید مرحله سوم

تقریباً ساده ترین الگوریتم واسه مرتب سازی ، بابل سورت(bubble sort) هست که با اون شروع می کنیم :

for (int i = n-1 ; i = > 0 ; i++)
  	for (int j = 0; j < = i  ; i++)
       if (a[j] > a[j + 1])
	   {
          int p = a[j];
          a[j] = a[ j + 1];
          a[i + 1] = p;
          }

ب.ن::- عبرتی برای دیگران :-[ ( عجله ام زشته می دونم )

 

[kia.celever]

پاسخ : مروری بر الگوریتم های مفید مرحله سوم

۴ تا نکته.
۱- اون i ++ دوم باید j ++ باشه.
۲- این سگمنت می‌خوره! وقتی i = n - 1 و j = i اون if اجرا می‌شه و j + 1 = n هست که از آرایه می‌زنه بیرون.
۳- خط آخر a[i + 1] = p باید j + 1 باشه.
۴- i ++ خط اول باید i -- باشه.


بعداً نوشت:
یکی از مهم‌ترین نکات مرحله ۳ همین اشتباه‌های کوچیکه که می‌تونن به مشکلات بزرگ ختم بشن.
به عنوان مثال اگه یه نفر همین کد بالا رو تو یه کانتست می‌زد انقدر می‌فرستادش و دیباگ می‌کرد تا بالاخره اکسپت بشه. ولی فراموش نکنید که تو مرحله ۳ خبری از جاج نیست. یعنی اگه یه اشتباه کوچیک بکنید برنامتون غلط کار می‌کنه و تمام نمره اون سؤالو از دست می‌دید.
بنابراین وقت کد زدن حواستونو خیلی جمع کنید.
(منظورم هم فقط این دوست بالایی نیست ها. همه اشتباه می‌کنن بالاخره. بله با شما هستم دوست عزیز. )

 

[Dark Eagle]

پاسخ : مروری بر الگوریتم های مفید مرحله سوم

بچه ها کد هایی رو بزارید که تو مرحله 3 بدرد بخوره

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

درنتیجه کسی تو مرحله 3 چنین کدی رو نمیزنه(مگر در شرایط خاص)
_____________

کد هایی که تو مرحله 3 لازمه یه چیزایی مثله : (با این که میدونم میدونید)

بیگ نام / بی اف اس / دی اف اس/بی اس تی/ هیپ سورت /کوئیک سورت .....

پ ن:شیوه جدید پست دادنم خوبه ؟ (مخاطب رضا)

 

[informatic]

پاسخ : مروری بر الگوریتم های مفید مرحله سوم

بعداً نوشت:
یکی از مهم‌ترین نکات مرحله ۳ همین اشتباه‌های کوچیکه که می‌تونن به مشکلات بزرگ ختم بشن.
به عنوان مثال اگه یه نفر همین کد بالا رو تو یه کانتست می‌زد انقدر می‌فرستادش و دیباگ می‌کرد تا بالاخره اکسپت بشه. ولی فراموش نکنید که تو مرحله ۳ خبری از جاج نیست

خیلــــی حرفِ خوبی زدی !!! البتـــه اون آخـــرای امتحــان مثن 15و20 دقیقــه‌ی آخـــر یه جـــاج میذارن کـــه اگـــه بفهمی هم باگ زدی شـــاید وقتِ زیــادی نداشتــه بــاشی کــه دیبـاگ کنی !!! تــازه خودشون میگن زیاد هم به جاج اعتمـاد نکنید ، ممکنــــه غلط بـــاشه ! یعنی خنده‌دار تر از این حرف پـیدا نمیشـــه !!!

البتـــه چون آیدین دیگــه نیست (فک کنم !!!) حدس می‌زنم(همینچوری ! ) شــاید امسـال از اول جـاج باشه ! خلــاصه اینکــه کــار ُ بــارشون معلوم نیست اصلــاً ... شما باید آماده باشید حتی اگه مثِ پارسال برقــا بره !!!

درستـــه شرایط برای همــه یکســـانه ، امــا اگـه یه جـاج ِ درست حســابی میذاشتن ، انتخـــاب ِ بچــه‌هـــا با عدالت انجـام میشد !!!


ضمنــــا شمـــا کــه ســرِ مرحلــه 3 نبــاید بیــاید تابع ِ سورت بنویسید کـــه ! مثلـاً شمــا بخواید مـِــرج سورت بزنید ، شــاید خیلی طول بکشـــه ! میتونید راحت بیــاید از توابع ِ سورت ِ خود ِ ++C استفـــاده کنـــید کـــه هم اردرش خفنـــه و هم دیگــه زمــانی برای نوشتن تابع صرف نمیکنید !!! مگــر در شرایط ِ خــاصی کــه مثلا بیاید یه struct تعریف کنید ، کـــه بعید می‌دونم لـازم بشــه اصلــا !!!

همین ...

 

[most wanted]

پاسخ : مروری بر الگوریتم های مفید مرحله سوم

کد صحیح:

for (int k = 1; k < size; k++)
  for (int i = 0; i <size -1 - k; i++)
       if (a[i] > a[i +1]){
          int temp = a[i];
          a[i] = a[i + 1];
         a[i + 1] = temp;
      }

روش کار الگوریتم: الگوریتم از عنصر اول آرایه شروع کرده و بار اول تا عنصر آخر پیش می رود و در هر مرحله آن عنصر را با عنصر بعدی چک می کند و اگر بزرگ تر بود جای آنها را عوض می کند با اجرای این کار در هر بار اجرا شدن حلقه به ترتیب آولین بزرگترین ، دومین بزرگترین ... سر جای خود میروند.در ضمن پس آز i بار اجرای حلقه i امین بزرگترین سر جای خود می رود بنابراین عناصر i ام تا n ام نیاز به چک شدن ندارند.
اُردر:حلقه در هر بار n, n-1 , n-2 ...1 بار انجام میشود که تعداد عملیات های آن n*n+1/2 میشود که از اُردر n^2 است.(عملیات های سواپ فقط به ضریب میدهند و در اُردر تاثیر ندارند.
الگوریتم را می توانستیم از عنصر آخر شروع کنیم و با تغییر نامساوی شرط آرایه را ابتدا از عنصر اوّل مرتب کنیم.

پ.ن 1 : در رابطه با کد درسته اشتباهای بدی کردم که دلیلشم
پ.ن 2 : ببینید درسته ممکنه این الگوریتم ها مورد نیاز نباشه ولی فرض کنید به شما یه دفعه تابع سورت پیشفرض سی پلاس پلاس می گفتن. این کاملاً بی منطق ِ و فک نکنم معلمی این کارُ کنه. باید ذهنیت الگوریتمی برامون شکل بگیره و این فکر کردن راجع به الگوریتم ها به تشکیل ِش کمک زیادی می کنه. ببینید هدف از این تاپیک معرفی الگوریتم های شاخ و با اُردر خوب نیست. هدف اینه الگوریتم یاد بگیریم.
پ.ن 3 : یه کاری که خودمم تو کد زدن انجام میدم و خیلی ام اشتباه ِ اینه که مثلاً وقتی سوالُ میبینم هر چی به ذهنم میرسه می زنم بعد با سمپل ها امتحان می کنم ُ درستش میکنم. که این جوری یه جا مثل مرحله 3 به مشکل بر می خورم.در صورتی که اگه از همون اول ذهنیت الگوریتمی کاملی پشتش باشه لازم به این کار نیست و خودمون می تونیم کدُ بدون سمپل دیباگ کنیم.

 

[Phanntom]

پاسخ : مروری بر الگوریتم های مفید مرحله سوم

میشه بی زحمت الگوریتم های dfs رو توضیح بدید

 

[Dark Eagle]

پاسخ : مروری بر الگوریتم های مفید مرحله سوم

الگوریتم dfs و کاربرد های dfs ....

کتاب آشنایی با الگوریتم فاطمی فصل 7 هم bfs گفته هم dfs ... یه سری کاربرداشم گفته ....

تو bfs مجاورا رو هم زمان میریم ... تو dfs تا اون جایی که بتونیم یکی رو میریم, بعد بر میگردیم عقب اولی رو که نرفتیم میریم ....

توصیه: نیازمند یاد داشتن وکتوری از آرایه ها و کیوو میباشید ....