نوشته های Arash

Art Of Programming : #1 مسئله شماره

Arash — Thu, 22 Aug 2019 13:32:23 +0430

تو این مسئله درباره یافتن عنصر کمینه تو یه آرایه n عنصری غیر تکراری با اعداد مثبت که مرتب شدن (صعودی) اما بصورت خاصی این مرتب سازی انجام شده که اصطلاحا بهش میگن آرایه sorted rotated هست ، اینطوری میشه گفت که فرض کنید یه آرایه مرتب مثل 1,2,3,4,5,6 داریم بعد از دوبار چرخوندن این آرایه مثل میشه 5,6,1,2,3,4 . ایده اول این هستش که با پیمایش خطی آرایه عنصر کمینه رو پیدا کنیم و این مسئله رو تو مرتبه بیگ اُ n حل کنیم اما سوال اینجاست که آیا میشه این مسئله رو تو مرتبه زمانی بهتر از خطی حل کرد ؟ کلا سوال هایی که راجع به ارائه یک راه حل بهتر هستش برمیگرده به اینکه چقدر شما با نمونه مسائل مختلف سر و کار دارید بطور مثال چه روش های حل مسئله مثل ( تقسیم و غلبه ، پویا ، حریصانه و ... ) رو می دونید آیا همیشه برای یافتن یک عدد تو آرایه شروع می کنید از ابتدا تا انتها دنبالش گشتن ؟ چقدر با مدل سازی های مختلف داده ها آشنا هستید ؟ به عبارت داده ساختارها رو چقدر می شناسید ؟ پس اگه دنبال این هستید که از پس این جور مسائل بربیاید باید مسئله های کلاسیکی که مطرح شدن و خیلی معروف هستن و شروع کنید به حل کردن و یجورایی با طرز فکر این راه حل ها آشنا بشید بعدش کم کم خودتون مدل فکری که دارید عوض میشه البته دنیای الگوریتم انتها نداره همیشه مسئله هایی هستن که واقعا ارائه یک راه حل بهینه براشون سخته ولی در کل به ما یه خط فکری خوبی میده که چطوری باید فکر کنیم.خب حالا برسیم سراغ ایده ی حل این مسئله ، چیزی که من برای پیدا کردن یه عنصر اونم تو شرایطی که آرایه مرتب باشه به ذهنم میرسه استفاده از جستجوی دودویی هستش البته میدونم اینجا مرتب بودن به اون معنا که ما فکر میکنیم نیست اما این ارایه یه خاصیتی داره که بازم میشه از همین روش استفاده کرد ، بطور خلاصه من میگم در یک آرایه مرتب عنصر اولی کمینه هست چه خاصیتی داره ؟ همیشه از عنصرهای بعدی خودش کوچکتر هست حالا عنصرهای آرایه رو بچرخون باز این عنصر کمینه چه خاصیتی داره ؟ این عنصر علاوه بر اینکه از عنصرهای بعدی خودش کوچکتر هست از عنصر های قبلی خودش هم کوچکتر است ! بگذارید اینو با یه مثال شرح بدم : آرایه 1,2,3,4 عنصر 1 کمینه هست از 2و3و4 هم کوچکتر است حالا فرض کنید یک چرخش انجام بشه آرایه میشه 4,1,2,3 همچنان این عنصر از عناصر قبل و بعد خودش کوچکتر هست حالا ما باید به کمک جستجوی دودویی دنبال این عنصر باشیم و با یه شرط ساده برای هر عنصر بررسی کنیم که آیا عنصری وجود دارد که از قبل و بعد خودش کوچکتر باشد ؟ تو جستجوی دودویی عنصر میانه پیدا می کردیم الان هم باید همین کارو بکنیم ، پس اول میانه پیدا میشه اینطوری :int mid = (from + to) / 2;یعنی من میگم from و to اگه اندیس شروع و آخر آریه باشه mid میشه اندیس میانه .بعد میام شرط زیر و برای این عنصر میانه چک میکنم :if (array[mid] < array[mid + 1] && array[mid - 1] > array[mid]) { return array[mid]; }حالا ممکنه این شرط برقرار باشه پس خود عنصر میانه همون کمینه است ، فرضا" اگه آرایه ورودی 4,1,2,3 باشه . میانه میشه عنصر 1 که دقیقا تو این شرط صدق میکنه !قبل از این موارد یه چنتا حالت خاص رو لازم هستش بررسی کرده باشیم . اینکه آرایه تک عنصری باشه یا میانه ۰ حساب بشه if (from == to) { return array[from]; } int mid = (to + from) / 2; if (mid == 0) { if (array[mid] < array[mid + 1]) { return array[mid]; } return array[mid + 1]; }توضیحات کدهای بالا بنظرم دیگه آسون باشه براتون تو شرط اول گفتیم که اگه به یه ارایه تک عنصری رسیدیم خب همون عنصر کمینه هست و یکی و برگردون . دوم اینکه اگه میانه صفر بدست اومد یعنی به یه ارایه دو عضوی رسیدیم کافیه مینیمم اون دوتا برگردونیمآخر سر باید روی آرایه بازگشتی بزنیم حالا اینکه عناصر بالای میانه باشه یا عناصر پایینش با یه مقایسه بدست میاد ، یعنی همون استراتژی که تو جستجوی دودویی بود اینجا استفاده میشهif (array[mid] < array[to]) { return findMin(array, from, mid - 1); } return findMin(array, mid + 1, to);اخر سر کدی که من نوشتم اینطوریه :private static int findMin(int array[], int from, int to) { if (from == to) { return array[from]; } int mid = (to + from) / 2; if (mid == 0) { if (array[mid] < array[mid + 1]) { return array[mid]; } return array[mid + 1]; } if (array[mid] < array[mid + 1] && array[mid - 1] > array[mid]) { return array[mid]; } if (array[mid] < array[to]) { return findMin(array, from, mid - 1); } return findMin(array, mid + 1, to); }یافتن عدد تو یه آرایه مرتب ( شبه مرتب) میتونه تو زمان بهتر از خطی هم حل بشه ، همین مسئله رو تعمیم بدید به یافتن عنصر کمینه ، بیشینه و ... مسئله های این مدلی باز هم هست بعدا اگه شد حل میکینماثبات مرتبه زمانی این الگوریتم هم آسونه :T(n) = T(n/2) + teta(c)کلا استراتژی حل با جستجوی دودویی اینطوری هست که یکسری عملیات روی عنصر میانه انجام میده بعدش طبق همون روی نیمه بالا یا پایین میانه بازگشتی میزنه تا به اون عنصر مورد نظر برسه

The Art Of Programming : مسئله #0

Arash — Sun, 18 Aug 2019 22:07:32 +0430

Donald Knuth American computer scientistشاید شما هم مثل من علاقه مند باشید که بدونید شرکتهای بزرگ نرم افزاری مثل گوگل ، فیسبوک ، مایکروسافت و ... چه چیزایی تو مصاحبه هاشون از برنامه نویس ها میپرسن ! اغلب هم شنیدیم که ابزار برای خیلی از این شرکت ها مهم نیست برخلاف اکثر شرکت های داخل ایران که تو آگهی ها می نویسن برنامه نویس مسلط به فریمورک فلان و بیسار !!! پس چی برای اونا مهمه ؟ خب معلومه الگوریتم ! هرچقدر شما خوش فکر باشید شانس بیشتری برای پذیرفته شدن تو مصاحبه این شرکت ها دارید . اسم این مجموعه پست ها که امیدوارم ادامه دار هم باشه و گذاشتم The Art Of Programming ، دلیلش هم خب واسه این بود که این کتاب کلا" در رابطه با الگوریتم هست علاوه بر اون جناب کنوث نویسنده این کتاب آدم جالبیه :) .مسئله #0 به این صورت طرح شده که میگه بعنوان ورودی یک رشته از اعداد داده میشه و خروجی باید بزرگترین مقداری باشه که تنها بوسیله ی عملگرهای * ، + بشه بدست آورد ، مثلا" فرض کنید ورودی باشه 123456 طبیعتا" باید اعداد 2تا 6 جوری ضرب کنیم که آخر سر مقدار ماکسیمم بشه و البته به 1 که تو ضرب عنصر خنثی ایی هستش همینطور 0 هم توجه کنیم ! پس چالش این مسئله توجه به اعداد 0 و 1 هستش .من پیشنهاد میکنم اول خودتون به مسئله فکر کنید اصلا" کدهای زیر رو هم نگاه نکنید بعدش کد خودتون و با چیزی که من نوشتم مقایسه کنید :) public static void main(String[] args) { String str = "123456"; int maxNumber = str.charAt(0) - '0'; // جهت بدست آوردن مقدار عدد از کاراکتر اول for (int i = 1; i < str.length(); i++) { int currentNumber = str.charAt(i) - '0'; // بدست آوردن عدد جاری در رشته if (currentNumber == 0 || currentNumber == 1 || maxNumber <= 1) { maxNumber += currentNumber; } else { maxNumber *= currentNumber; } } System.out.println(maxNumber); }نکته ای که مهم بود در حل این مسئله توجه به اعداد 0 و 1 در ابتدا ، وسط و اخر رشته هست که باید همیشه با مقدار قبلی جمع بشه اگه دقت کنید اولین عدد به متغیر maxNumber اضافه شده و بعد از اینکه از کاراکتر بعدی تا آخر رشته پیمایش میشه توجه میکنیم که مقدار قبلی همیشه عددی بزرگتر از 1 باشه و اگه 0 یا 1 بود همیشه عملگر + برای مقدار قبلی استفاده میشه در غیراینصورت * می کنیماز پست های این مجموعه :http://vrgl.ir/jQzrX

چگونه کدهای PHP را با XDebug در محیط VSCode دیباگ کنیم

Arash — Sun, 18 Aug 2019 11:24:34 +0430

اگه به عنوان برنامه نویس PHP برای بررسی و دیباگ کدهای خودتون دچار مشکل شدید غالبا" با روش هایی مثل استفاده کردن از echo برای نمایش مقدار یه متغیر یا var_dump گرفتن از Array های PHP مثل SESSION_$ جهت بررسی و دیباگ کدتون استفاده کردید که خیلی هم جالب و راحت نیست و حالا فرض کنید که کدهای شما بسیار پیچیده باشه و حتی باگی که گزارش شده نیاز به بررسی خط به خط کدهای شما رو داشته باشه . یکی از قابلیت هایی که VS Code داره این هستش که میشه به کمک Extension XDebug کدهای خودمون و مثل زبون هایی مثل C#.NET خط به خط دیباگ کنیم و Watcher تعریف کنیم ببینیم فلان متغیر چه مقداری داره و خلاصه خیلی راحتتر از قبل بتونیم دیباگ کنیم.تو این پست سعی میکنم مرحله به مرحله توضیح بدم که خیلی سریع به این قابلیت دست پیدا کنیم :اول اینکه فرض میکنم شما PHP رو از قبل نصب کردید ، مثلا من خودم با XAMPP این کارو انجام دادم . حالا باید مطمئن باشید که Extension مربوط به XDebug فعال باشه یا اینکه ممکنه اصلا فایل dll مربوط به این Extension و هم نداشته باشید ، اگه مثل من از XAMPP استفاده می کنید یا Web Server های دیگه کافیه به محل نصب فایل های PHP برید و پوشه Extension هارو پیدا کنید ، بطور مثال برای من در این مسیر قرار داره :C:\xampp\php\ext\php_xdebug.dllحالا با توجه به OS شما و یا اینکه از چه Web Server استفاده می کنید ممکنه این مسیر متفاوت باشه ، برای اینکه زیاد سردرگم نشید کافیه یه سری به phpinfo بزنید . همونطوری که تو عکس زیر مشاهده میکنید برای من این Extension فعال هستش حالا به هر دلیل اگه نیاز به نصبش داشتید به سایتش https://xdebug.org/download.php میتونید برید و آخرین نسخه اون یا نسخه ای که با ورژن PHP شما متناسب هستش و بگیرد و تو همون مسیری بالایی که گفتم قرارش بدید ، بعد از این کار نیازه که فایل php.ini اصلاح بشه ، به این صورت که اولا مشخص کنیم فایل dll. مربوط به اون کجا قرار داره که یکبار بالا گفتم ( حالا واسه شما یه چیز دیگه هست ) [xdebug]zend_extension=""xdebug.remote_enable=1xdebug.remote_port="" (the default port is 9000)تو تنظیماتش مسیر فایل ، port number و اینکه بصورت ریموت بشه دیباگ کرد و براش تنظیم میکنیم. ترجیحا" این تنظیمات و در انتهای فایل php.ini قرار بدید که با کانفیگ های دیگه تداخل پیدا نکنه. به این نکته توجه کنید که باید Web Server شما ریست بشه که الان تنظیمات جدید و بخونه پس این کار و هم انجام بدید .خب حالا شما میتونید تو هر محیطی این قابلیت و داشته باشید که خط به خط کدهای خودتون و دیباگ کنید مثلا اگه از PHPStorm استفاده می کنید اونجا هم میتونید با کانفیگ کردنش از این قابلیت استفاده کنید ولی خب من الان میخوام تنظیم کردن VS Code توضیح بدم پس حالا بریم سراغ VS Code ، اول اینکه نیاز هستش یه Extension برای VS Code نصب کنیم که کافیه کلیدهای میانبر Ctrl+Shift+X انتخاب کنید تا فرم جستجوی Extension ها برای شما نمایش داده بشه و PHP رو تایپ کنید :چیزی که ما باید نصب کنیم PHP Debug هستش . بعدش برای تست یه فایل PHP ایجاد کنید و به سراغ پنل دیباگ برید که از این طریق بتونیم کد و دیباگ کنیم برای این ما باید یه فایل launch.json بسازیم که با انتخاب Add Configuration ابتدا میگیم که عاقا یه کانفیگی برای این داستان میخوایم ایجاد کنیم.حالا محیطی که باید انتخاب بشه رو باید تعیین کنیم اینجا میشه PHP :بعدش نیاز هستش مسیری که php.exe در اون وجود داره مشخص بشه این تنظیمات و تو همون فایل launch.json مشخص کنیم در نهایت چیزی به صورت زیر خواهد بود :در نهایت کافیه هر کجا که لازم هست break point بذارید و به مرورگر برید و برنامه و اجرا کنید ، مشاهده می کنید که VS Code اومده به جایی که شما break point قرار دادید حالا راحت میتونید برنامه رو خط به خط دیباگ کنید :)