سلام من میلاد رضایی هستم از بچه های کرج 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/
بازم اگه توضیحم بد بود بزارین به حساب بی تجربگیم
راستی اگه کسی تو ترجمه کتاب ها مشکل داره می تونم کمکش کنم
بلاخره مرحله 2 هم خوب یا بد رفت همونطور که می دونید همه جا توصیه می کنن که مستقل از امتحان مرحله 2 یی که دادن بشینن و کد بزنن و الگوریتم کار کنن وخلاصه که باید به فکر مرحله 3 باشیم ، تاپیک برای صرفاً کد زنی زده شده و درسته مرحله 3 رو میشه بدون الگوریتم خاصی هم گذروند ولی بلد بودن الگوریتم ها میتونه کارمون رو خیلی راحت تر کنه. \/
برای همین ام خوبه که تو یه تاپیک از الگوریتم ها ساده شروع کنیم یه توضیحی برای هر کدومشون بدیم و یه سورس کدی هم براشون بذاریم[nb]بهتره که تو این تاپیک ایده هایی که تو اُردر کمک میکنن ولی ربطی به الگوریتم ندارن بررسی نشن چون بحث خیلی پراکنده میشه و نمیشه تموم ـِش کرد،پس فقط اگه واسه بهینه سازی ایده الگوریتمی داشتید مطرح کنید.[/nb] که اگه مشکلی تو کدش براتون مونده بود حل بشه و اردرش رو بررسی می کنیم بعد هم برای هر الگوریتم پیشنهاد هایی برای بهینه کردنش ارائه می دیم .
چون برای این که بتونیم تو سریع ترین زمان یه کد بدون نقص با اردر و زمان بندی درستی داشته باشیم نیازه با اردر تمام الگوریتم هایی که استفاده می کنیم آشنایی کامل داشته باشیم و اگه به اوردر برنامه در ابتدا توجه نکنیم ممکنه خیلی وقتا ایده هایی که می زنیم رو سوالا اُردر های خیلی زیادی داشته باشن و که باید موقع کد زدن به این چیزا توجه کنیم یه شکلی نشه که هِی کد بزنیم بعد ببینیم زود جواب میده یا نه ،یکی از دغدغه هامون باید الگوریتم و اُردرِش باشه.
از ساده ترین الگوریتم های هر کدوم شروع کنیم و به ترتیب اُردر جلو بریم.هر کس هم ایده ای واسه بهینه سازی هرکدوم داشت بیاد راجع بش بحث کنیم.
اولین الگوریتم مهم هم مرتب سازی هاست که به نظرم از اونا شروع کنیم و کم کم پیش بریم که تا مرحله 3 الگوریتم های گراف هم تموم کنیم.
۴ تا نکته.
۱- اون i ++ دوم باید j ++ باشه.
۲- این سگمنت می‌خوره! وقتی i = n - 1 و j = i اون if اجرا میشه و j + 1 = n هست که از آرایه می‌زنه بیرون.
۳- خط آخر a[i + 1] = p باید j + 1 باشه.
۴- i ++ خط اول باید i -- باشه.
بعداً نوشت:
یکی از مهم‌ترین نکات مرحله ۳ همین اشتباه‌های کوچیکه که می‌تونن به مشکلات بزرگ ختم بشن.
به عنوان مثال اگه یه نفر همین کد بالا رو تو یه کانتست می‌زد انقدر می‌فرستادش و دیباگ می‌کرد تا بالاخره اکسپت بشه. ولی فراموش نکنید که تو مرحله ۳ خبری از جاج نیست. یعنی اگه یه اشتباه کوچیک بکنید برنامتون غلط کار می‌کنه و تمام نمره اون سؤالو از دست می‌دید.
بنابراین وقت کد زدن حواستونو خیلی جمع کنید. (منظورم هم فقط این دوست بالایی نیست ها. همه اشتباه میکنن بالاخره. بله با شما هستم دوست عزیز. )
بعداً نوشت:
یکی از مهم‌ترین نکات مرحله ۳ همین اشتباه‌های کوچیکه که می‌تونن به مشکلات بزرگ ختم بشن.
به عنوان مثال اگه یه نفر همین کد بالا رو تو یه کانتست می‌زد انقدر می‌فرستادش و دیباگ می‌کرد تا بالاخره اکسپت بشه. ولی فراموش نکنید که تو مرحله ۳ خبری از جاج نیست
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 به مشکل بر می خورم.در صورتی که اگه از همون اول ذهنیت الگوریتمی کاملی پشتش باشه لازم به این کار نیست و خودمون می تونیم کدُ بدون سمپل دیباگ کنیم.
/
،یکی از دغدغه هامون باید الگوریتم و اُردرِش باشه. 
)
