ّبرنامه آموزشی: پیدا کردن مسیر

[zfarhad2003]

>از اینکه بالاخره این بخش از انجمن راه افتاد خوشحال شدم ولی به نظر می رسه که دوستان دیگه اشتیاق گذشته رو برای ادامه کار ندارن.
>
>من دو سه روز است که درگیر حل یک مسئله توی c++ هستم که مربوط به پیدا کردن مسیر درست حرکت است. درست مثل اون معماهایی که بچگی ها حل می کردین و مثلا خرگوشه به هویج می رسید.
>
>توی این مسئله 1 به منزله دیواره و 0 به منزله مسیر باز برای حرکته. مثلا توی داده های زیر مسیر حرکت رو مشخص می کنم.
>

>0 0 1 0
>0 1 0 1
>0 1 1 0
>1 0 1 1
>0 1 1 1

حالا من سعی کردم کمی تا قسمتی این برنامه رو شبیه سازی کنم ولی خوب کد من یک اشکال کوچیک داره که توی شرایط خاصی ایجاد می شه.

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

تقریبا 9 ماه می شد که اصلا توی محیط C++ نرفته بودم یکم سخت بود اوضاع رو جمع و جور کنم. شاید کدم اشکالاتی داشته باشه.
در کل بیاین سعی کنین این مسئله رو با بهترین و بهینه ترین راه حل به جواب برسونیم.

 

[saalek110]

من دانلود كردم. يك نگاهي مي كنم . بعد اطلاع مي دهم .
.

 

[stranger_in_rain]

خبرشو میدم سرم درد میکنه برا این کارا :d

 

[saalek110]

آموزش در كنار پروژه

اگه بيشتر توضيح بديد، من هم يك كمي ياد مي گيرم.
مثلا بگيد برنامه الان چكار مي كنه و بايد بعد اصلا چكار كنه.
پارتيشنهاي برنامه اتان را مشخص كنيد و بگيد هر قسمت چه كار مي كند و با قسمتهاي ديگر چطور ارتباط برقرار مي كنه.
اگه هم يك كم آموزشي كنيد قضيه را كه عاليه. مثلا توابع بكار رفته در برنامه اتان را تعريف كنيد و طرز بكار بردن هر يك را بگيد.
كلا بگم، من عيب رفع كن نيستم. و اين وسط مي خواهم يك چيزايي ياد بگيرم. ولي اگر توانستم هم دريغ نمي كنم.

 

[zfarhad2003]

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

در مورد ساختار برنامه ام چشم. الان بدجوری خوابم می یاد ساعت 2.30 نصف شبه فردا صبح در اولین فرصت که کانکت شدم می یام برنامه رو جز به جز توضیح می دم.

 

[zfarhad2003]

خوب همونطور که قول داده بودم این یه توضیح مختصر در مورد ساختار برنامه:

اول از همه یه آرایه دوبعدی به اسم Table تعریف می کنم که همون داده های اولیه یا نقشه ما رو شامل می شه. هیچ محدودیتی در تعداد سطر یا ستون نداره یعنی به هر بزرگی و کوچیکی که خواست می تونه باشه.
بعد یه تابع خیلی جمع و جور داریم به اسم isneighbour که بررسی می کنه ببینه آیا دوتا صفر که بهش داده می شه در کنار هم هستن یا نه (همسایه همند یا نه).
یه کلاس کلی هم به اسم node داریم که تقریبا کل بار برنامه روی این کلاسه است. این کلاس در واقع نماینده یک صفر است وقتی من داده ها رو بررسی می کنم هرجا یه صفر پیدا کردم یه object از این کلاس می سازم. این کلاس همونطور که می بینین یه xو y داره که مختصات صفر رو نگه می داره. که آرایه به اسم list داره که از نوع اشاره گره و به تمامی صفرهایی که در همسایگی این صفر ما هستند اشاره می کنه. یعنی اگه یه صفر داشته باشیم که دوروبرش 3 تا صفر باشه توی این آرایه سه مقدار غیر NULL داریم که به این صفرهای همسایه اشاره می کنن.
متغیر آخری هم که در کلاس است num تعداد همسایه های ما رو نگهداری می کنه.

نوبت می رسه به توابع داخلی این کلاس: چهارتا تابع اول که کار خاصی رو نمی کنن خیلی ساده هستن. تابع پنجم یعنی add در واقع وقتی من یه همسایه پیدا کردم با استفاده از این تابع آدرس اون رو به لیست خودمون اضافه می کنم و تابع del هم درست برعکس این یعنی از لیست هر همسایه ای رو که خواستم حذف می کنم.
و اما foundinlist این تابع بررسی می کنه تا ببینه آیا اون نقطه یا صفری که بهش داده می شه توی لیست است یا نه اگه توی لیست باشه محل اونو برمی گردونه واگر نبود 0 رو بیرون می ده.
دو تابع آخر هم که getnode و bestpath هستند قبلا یه تابع بودن که مجبور شدم از هم جداشون کنم ولی اگه با هم ادغام بشن هیچ فرقی به حالمون نمی کنه. getnode در واقع آخرین همسایه که در لیست است رو برمی گردونه و bestpath با یه محاسبه ساده بهترین همسایه رو برمی گردونه.
کلاس کارمون به همین راحتی تموم شد فکر نکنم زیاد نیازی به فکر کردن داشته باشه.

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

بعد از این مرحله نوبت می رسه به انجام محاسبات منطقی رو داده هامون تا مسیر رو از میان این صفرها پیدا کنیم.
در دوتا for بعدی می یان کلیه همسایه های صفرهای موجود در list رو پیدا کرده و به اونا اضافه می کنم.
بعد توی یه دونه while جالب میام ار میان این صفرها و همسایه هاشون که هستن اونهایی رو که مسیر انحرافی هستن پیدا کرده و حذف می کنم . این بخش از برنامه رو من خودم که خوشم اومر کلا اون صفرهایی که اصلا توی مسیر نیستن و ما رو منحرف می کنن از میان می بر و این کار رو با صفر کردن num که تعداد همسایه هاست می کنه یعنی وقتی صفر هیچ همسایه ای نداشته باشه دیگه توی هیچ محاسبه ای شرکت نمی کنه.

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

برگردیم سر برنامه توی این while پیچیده که گفتم می یام بررسی می کنم از اول مسیر که مشخصه جلو می ره اگه صفری یه همسایه داشت خوب مسیر درسته بریم جلو اگه چندتا همسایه داشت یعنی ما چندتا انتخاب داریم باید یکی رو که بهترین است انتخاب کنیم یعنی همون bestpath که بهترین همسایه رو انتخاب می کنه. این کار رو یعنی پیمایش مسیر رو اونقدر ادامه می دیم که یا به صفری برسیم که دیگه هیچ همسایه نداشته باشه یا به همون نقطه انتهایی مسیر برسیم. (البته توجه کنین من وقتی از یک نقطه می گذرم دیگه می یان کلیه راههای برگشت به اون رو پاک می کنم تا احیانا به اشتباه مسیر رو برنگردیم)

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

امیدوارم مشکل برنامه رو لو نداده باشم چون می خوام حداقل یکم فسفر بسوزونین تا به نتیجه ای برسیم.

فکر کنم توضیحات کامله( البته مختصر نشد) اگه باز توی بخشی از برنامه گیر کردین بگین تا توضیح بدم.

 

[zfarhad2003]

هیچ کی نتونست اشکال برنامه رو پیدا کنه.
حداقل بیاین بقین تا خودم بگم.
به خدا اصلا سخت نیست اشکالش خیلی تابلویه.

 

[stranger_in_rain]

من انقدر تو این هفته سرم شلوغ بوده که وقت نکردم نگاهش کنم، کلی امتحان دارم. یک مقدار دیگه وقت بده :d

 

[zfarhad2003]

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

 

[mr_mobile]

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

 

[hamed_nurian]

من ترم 2 مهندسی کامپیوترم نرم افزار . این برنامرو به ما تمرین دادن . تو کلاس کسی هم بلد نیست و همه چشم امیدشون به منه . ما تازه شروع کردیم و استاد هنوز کلاس هارو اموزش نداده . اگه میشه راهنماییم کنید این برنامرو به شکل ساده تری بنویسم . بدون استفاده از کلاس ها . مرسی