https://virgool.io/feed/@s.h.siadaty دکترای علوم کامپیوتر از NYU. یاد می گیرم و یاد می دهم . آچار بدست هستم. دانلود کتاب http://dorostcode.com fa 2026-06-16 13:31:40 https://files.virgool.io/upload/users/29681/avatar/ZNuaJ8.png?height=120&width=120 https://virgool.io/@s.h.siadaty https://virgool.io/@s.h.siadaty/%D8%A7%D8%B1%D8%B2%DB%8C%D8%A7%D8%A8%DB%8C-%DB%B3%DB%B6%DB%B0-%D8%AF%D8%B1%D8%AC%D9%87-%D8%AA%D8%AC%D8%B1%D8%A8%D9%87-%DA%A9%D8%A7%D8%B1-%D8%AF%D8%B1-%DA%AF%D9%88%DA%AF%D9%84-%D9%88-%D9%86%D9%82%D8%AF-%D8%B5%D8%AD%D8%A8%D8%AA-%D9%85%D8%AC%D8%AA%D8%A8%DB%8C-%D8%B4%DA%A9%D9%88%D8%B1%DB%8C-ejjl2ilfssqf مجتبی شکوری را دوست دارم. جوان مطلع، خوش سخن و خوش تیپ که ترکیبش با سروش صحت با اون قلب مهربونش غوغا می کنه. برنامه کتاب باز و صحبت هایش را دنبال می کنم. خیلی حرف های دلنشینی می زنه بخصوص در مورد نگاه به زندگی. الزاما همه اش دقیق نیست. یکی از نادقیق ترین جلسات گفتگوهاش با سروش جلسه ای با عنوان 'فیلسوفی در تعمیرگاه' بود. هدفم از این نوشته بیان دیدگاه خودم در مورد نکته خاصی است که ایشون در این گفتگو گفتند و بصورت بدیهی یک خطا بود.حرفهای زیادی گفت در مزیت کار عملی یا همون دستهای روغنی در برابر کار فکری یا همون دستهای جوهری. من به عنوان کسی که هر دو کار رو تجربه کرده به هیچ کدام وزن ذاتی خاصی به هیچ کدام نمی دم و جانبداری نمی کنم.مجتبی شکوری در مورد نحوه ارزیابی افراد در دو موقعیت شغلی وزن بهتر رو به کار عملی دادند به این استناد که افراد مشغول در کار فنی تنها بر اساس کارشون (مثلا تعمیر یک وسیله) ارزیابی میشن ولی در کارهای اداری افراد بصورت ۳۶۰ درجه ارزیابی می شن. برداشت مجتبی شکوری از این اصطلاح شناخته شده این بود که این کارمندان از همه جنبه ها حتی اخلاق و رفتار و خصوصیات شخصی شون ارزیابی میشن. تعریف مجتبی شکوری از ارزیابی ۳۶۰ درجه، با توجه به اینکه با این اصطلاح توی محیط کارم در خارج از کشور آشنا هستم، مثل گوسفند صورتی بود و برای اینکه بگم غلط یا درسته فقط چند صدم ثانیه بهش فکر کردم. یعنی در واقع اینقدر این تعریف اشتباه بود که در حال رانندگی پشت فرمون توی تونلها و خیابونها شرق به غرب منهتن در حالی که گوگل مپ هم داشت راهنماییم می کرد و دنبال مسیر می گشتم باز هم مثل یک گوسفند صورتی جلوی یکی از مغازه های لوکس منهتن بود.و از اون جمله توی ذهنم شروع کردم مرور ارزیابی ۳۶۰ درجه. ارزیابی ۳۶۰ درجه اسمش رو از روی این گرفته که توی سازمان همه هم رو ارزیابی می کنند. مثلا توی گوگل، هر ۶ ماه یک ارزیابی انجام می شه که افراد خودشون رو، دیگران رو، و حتی مدیران خودشون که مستقیم باشون کار می کنند رو ارزیابی می کنند. این یعنی همون ۳۶۰ درجه بالا به پایین و پایین به بالا. تعریف ارزیابی ۳۶۰ درجه اینجا تموم میشه. قابل توجه این هست که یکی از اهداف اصلی این ارزیابی ارائه پیشنهاد دقیق برای بهبود و رشد کارکنان هست.این ارزیابی ها فراتر از ارزیابی مستقیم قابلیت های فنی (مثلا در کار من کد برنامه) هست اما همشون بگونه ای به کارایی فنی یا تجاری سازمان مرتبط هستند. یعنی در واقع هر چه که درجه شغلی میره بالاتر اون فاکتورهای فنی (مثلا برنامه نویسی) کمتر می شه و اهمیت مهارت های نرم بیشتر و بیشتر میشه. این مهارت ها بخصوص شامل مهارت راهبری دیگران هست. یعنی شما چقدر توانایی این رو دارید که دیگران را با هم هماهنگ کنید که یک کار پیچیده انجام بشه یا اینکه چقدر پیشقدم برای اجرای پروژه ها بودید. برای اثبات هر کدام از این خصوصیات باید شواهدی از پروژه هایی که در ۶ ماه گذشته انجام شده بیارید و بگید که فرد ارزیابی شونده چقدر از این خصوصیات رو داشته. البته نکته جالب دیگر این هست که ابتدا خود فرد ارزیابی شونده فعالیتهای مهمش رو در ۶ ماه گذشته لیست می کنه و بقیه با خوندن اون و مشاهدات خودشون نسبت به اون کیفیت های گفته شده نمره می دن.بنابراین کسی در مورد لباس پوشیدن نظر نمی ده، رنگ پوست یا جنسیت و ملیت و غیره جایگاهی ندارند. البته اگر کسی کاری یا رفتار تبعیض آمیز بکنه توی ارزیابی 'گوگلی بودن' ضعیف خواهد بود.اینها فاکتورهایی است که نهایتا فرهنگ سازمان رو می سازه و روی کارفنی تاثیر می گذاره. برخلاف گفته مجتبی شکوری که تنها باید کارمندان یا کارگران رو از نظر فنی ارزیابی کرد، بنظر من اون فاکتورهای مهارت نرم که در بالا قطره ای از اون رو گفتم بسیار مهم یا خیلی مهمتر هستند. یک تعمیر کار عالی اما بداخلاق مشتری ها رو فراری می ده، همکار ها رو ازار می کنه و بازدهی کار رو با ایجاد درگیری های شخصی پایین می اره، و مدیر ها رو خسته می کنه. یک تعمیر کار عالی که فقط کارهایی که بهش رو می گن انجام می ده خیلی فرق می کنه با اونی که حواسش هست و گاهی کارهایی انجام می ده که ازش خواسته نشده. بنابر این بنظر من چسب یک سازمان فرهنگ کاری سالم اون هست تا این موجود زنده بتونه خوشنام بشه، نیروی خوب و مشتری وفادار جذب کنه و بهبود پیدا کنه، محصول خوب تحویل بده و خوب پول بسازه.درباره نویسنده: حسین سیادتی دکتری علوم کامپیوتر از دانشگاه نیویورک دارد و مهندس شرکت گوگل می باشد. Hossein Siadati Hossein Siadati Sat, 30 Jan 2021 14:30:00 +0330 https://virgool.io/512words/%D8%AA%DB%8C%D8%B2%D8%B1-%D8%A8%D8%B1%D8%A7%DB%8C-%DA%A9%D8%AA%D8%A7%D8%A8-%D8%B2%D9%85%D8%B3%D8%AA%D8%A7%D9%86-%DB%B6%DB%B3-%D9%86%D9%88%D8%B4%D8%AA%D9%87-%D8%A7%D8%B3%D9%85%D8%A7%D8%B9%DB%8C%D9%84-%D9%81%D8%B5%DB%8C%D8%AD-oviu72mox0j6 اگر خارج‌نشین هستید و هنوز شعله‌یِ خدمت به کشور در وجودتان شعله‌ور است، احتمالا شما نیز مانند من هر روز از خود این سوالات را می‌پرسید: «اگر به ایران برگردم، آیا می‌توانم کارِ مفیدی برایِ کشور انجام دهم؟» یا «چه سرنوشتی آنجا به انتظارِ من نشسته است؟»داستانِ دکتر فرجامی (شخصیتِ ساختگی) متخصصِ کامپیوتر که در بحبوحه‌یِ جنگِ تحمیلی به خوزستان برمی‌گردد، مظهرِ نسخه‌اي کابوس‌گونه از آینده‌یِ احتمالیِ بازگشتِ یک متخصص به کشور است. جایي که همه به شما می‌گویند که به تخصص‌تان نیازمندیم و حتی ماموریتي برایِ راه‌اندازیِ مرکزِ آموزشِ کامپیوتر با وعده‌وعیدِ حقوقِ خوب، امکانات، بودجه و پرسنل می‌دهند. شما مستقیماً با چند آدمِ ظاهرالصلاح کار می‌کنید که بعد از انقلاب با تغییرِ چهره مصدرِ امور نشسته‌اند ولی حتی صداقتِ کافی برایِ پیگیریِ وعده‌هایي که به شما داده‌اند ندارند یا خود اسیرِ یک سیستمِ بیمارند. روایت از وقت تلف کردن‌ها در ادارات و پرکردنِ در و دیوار با شعارهایِ هیجانی که هزینه‌اش را فقط دیگران باید بدهند. صورت‌هایي خندان و چشم‌هایي پرسان که «نه، واقعا چرا برگشتی؟» قصه‌یِ آشنایی است؟ آیا دکتر فرجامی می‌تواند به برنامه‌هایي که روزها و شب‌ها برایِ تهیه‌یِ آن‌ها زحمت کشیده بود جامه‌یِ عمل بپوشاند؟ آیا دکتر فرجامی هرگز حقوقي دریافت خواهد کرد؟اما دکتر فرجامی واقعا برای چه به میهن بازگشته است؟ آیا از جانش سیر شده است؟ آیا برایِ این‌که به مادرش نزدیک باشد به کشور برگشته است؟ چرا خانه و زندگی‌اش در مینه‌سوتا را رها کرده؟ آیا او یک جاسوس است که از سازمان‌هایِ جاسوسیِ آمریکا و اسرائیل پول می‌گیرد؟ اگر این نیست او حتما یک دیوانه است؟اینها سوالاتي است که برایِ راننده و همراهِ او هم به وجود می‌آیند و داستانِ این کتاب، که در جنگ می‌گذرد، شرحِ آشنایی‌ها با زندگیِ آدمهایِ مختلف است. خرمشهر زیرِ بمباران! زني که شوهرش بعد از انقلاب اعدام شده و اموالشان توسط یک آدمِ پلید مصادره شده و عنقریب عذرش را می‌خواهند تا شغلش را نیز از دست بدهد. چرا حداقل پاسپورتش را به او نمی‌دهند تا بتواند جانش را بردارد و از کشور خارج شود؟داستانِ پسرِ یک کارگرِ ساکنِ تهران که در جنگ گمش شده است و راننده‌یِ دکتر می‌جویدش تا برایِ پدرش خبري از او ببرد. تنها چیزي که از او می‌داند این است که سالم نیست! چه بر سرِ این جوانِ کارگر آمده است؟دکتر فرجامی چگونه می‌تواند در این شرایط به کشورش کمک کند؟ آیا او هم نهایتاً باید به خطِ مقدم برود و بجنگد؟این داستانِ هیجان‌انگیز شما را به عمقِ زندگیِ آدم‌هایِ درگیرِ جنگ می‌برد، با کنایه‌ها و متلک‌های تلخ و شیرین قلقلک می‌دهد و می‌خنداند، و گاهي شدیداً متاثر می‌کند. گاهي شما را نیز با کابوس خود شریک می‌کند و رویِ اعصابتان راه می‌رود و نهایتاً کیش و مات‌تان می‌کند.نهایتاً شما می‌مانید و این سوال که اگر من هم به کشور برگردم آیا چنین سرنوشتي در انتظارم خواهد بود؟ اگر دقیقا همان اتفاقاتي که برایِ دکتر فرجامی افتاد برایِ شما هم بیافتد آیا باز هم می‌خواهید که برگردید؟ آیا دکتر فرجامی آدمِ خوش‌خیالي بود یا فرشته‌اي که فقط دو بال کم داشت و با وجودِ وقوف به آن‌چه ممکن است اتفاق بیافتد گام در راه نهاد؟با تشکر از محمد فرزانه بخاطر تصحیح و ویرایش متن Hossein Siadati Hossein Siadati Tue, 21 Jan 2020 09:39:19 +0330 https://virgool.io/@s.h.siadaty/%D9%87%D8%B2%DB%8C%D9%86%D9%87-%D9%85%D9%88%D9%81%D9%82%DB%8C%D8%AA-cost-of-success-imbhhkulpqdq هزینه موفقیت کمتر از هزینه شکست است.من یک مهندس شرکت گوگل هستم، اما کارم را از اینجا شروع نکردم. کمی قبل تر یک محقق دوره پسا دکتری دانشگاه نیویورک بودم، کمی قبلش دانشجوی دکتری، قبلش محقق در دانشگاه ملی سنگاپور، قبلش استاد دانشگاه در ایران، قبلش مدرس حق التدریس، قبلش دانشجوی کارشناسی ارشد در ایران و برنامه نویس ساعتی، قبلش دانشجوی کارشناسی و برنامه نویس ساعتی.قبلش هم مثل بقیه تحصیلاتم را از ابتدایی تا دبیرستان خواندم. با این تفاوت که تقریبا هر تابستان به کاری مشغول بودم. راستش پدرم همیشه توصیه می کرد که باید فن و حرفه ای را یادبگیریم که بتوانیم کار پیدا کنیم. یکسال در دوچرخه سازی، سال دیگر نجاری، سال دیگر آلومینیوم کاری کار کردم. یک مدت هم در یک مغازه بقالی. سالهای بعدش دنبال پول در آوردن بودم و کارهای ساختمانی می کردم. حرفه مورد علاقه ام ضدزنگ زدن اسکلت ساختمانها بود. گاهی هم با برادرم کار برق ساختمان می کردم.وقتی دانشجوی کارشناسی و ارشد بودم همزمان با درس کار برنامه نویسی می کردم و پول نسبتا خوبی در می آوردم. وقتی هم دانشجوی دکتری در نیویورک بودم هر تابستان کارآموزی می کردم و حداقل نصف کل درآمد سالیانه دانشجوییم را از تابستان در می آوردم.همه این تلاش ها در کنار هم ذره ذره و در یک دنباله طولانی از نقاط به ظاهر نامرتبط من را به هدفم نزدیک تر و نزدیک تر کردند. مطمینم اگر حاضر نبودم که هزینه موفقیت که کار و تلاش است را بپردازم هرگز به هدفم نمی رسیدم.هزینه موفقیت یک اصطلاح جالب هست که آن را در گوگل یاد گرفتم. معنای آن در زمینه نرم افزار این است که برای اینکه بتوانی یک بخش جدید به پروژه نرم افزاری اضافه کنی باید کارهای روزمره مربوط به نگهداری بخش های کنونی سیستم را به دل و جان بخری. سیستم کنونی در واقع محلی است که از آن درآمد کسب می کنی و بدون آن نمی توانی شانس این را پیدا کنی که روی بخش های جدید سیستم کار کنی. این مفهوم در مورد خیلی از حرفه های دیگر هم صادق است.این اصطلاح را در زندگی روزمره هم می توان معنا کرد. گاهی برای اینکه در طولانی مدت به جایی که می خواهیم برسیم باید قبول کنیم که از مهارت های کنونی مان استفاده کنیم، شاید لازم باشد یک مقدار مسیرمان را کج کنیم، کارهایی را انجام بدهیم که الزاما خیلی از انجام آنها لذت نمی بریم و یا اینکه طاقت فرسا و شاید فکر کنیم که در شان ما نیستند. اما در عین حال این کارها پاسخگوی خرج روزمره ما هستند و کمک می کنند که بتوانیم امورات را بگذارنیم تا بتوانیم زمانی را هم برای رسیدن به هدف مطلوب خود بگذاریم. این دیدگاه در بین جوانان غربی جا افتاده است. نوجوانهای خوشتیپی رو می بینم که توی رستورانها، کتابخانه ها، یا فروشگاه بصورت ساعتی کار می کنند و یا خدماتی مثل رانندگی ماشین یا پرستاری بچه ها یا سالمندان رو انجام می دن. با همین کارهای ساعتی برای خودشون درس می خوانند، سفر می کنند، می خوردن و می پوشند، و خلاصه زندگی خود رو پیش می برند. هرگز هم ندیدم که به اصطلاح کار برایشان عار باشد. حتی گاهی وقت ها اینقدر کارخود را جالب تبلیغ می کنند که آدمی دوست دارد آن حرفه را برای چند ساعت هم که شده امتحان کند.سهم این دیدگاه در فرهنگ ایران بخصوص ساکنین ایران بسیار کم است. این امر موجب شده که افراد دیر تجربه کاری پیدا کنند و اغلب انتظار برای پیدا کردن کار و درآمد خیالی بدون اینکه سختی آماده شدن برای آن را به جان بخرند باعث می شود که نهایتا هرگز به هدفی که می خواهند نرسند.موفقیت هزینه دارد و گاهی برای رسیدن به هدف باید از گذرگاههایی بگذریم که انتظارش را نداریم اما پل ما برای رسیدن به اهدف عالیمان هستند! در نهایت باید به یاد داشته باشیم که هزینه موفقیت کمتر از هزینه شکست است. بنابر این برای موفق شدن همه تلاش خود را باید مبذول کنیم. Hossein Siadati Hossein Siadati Wed, 11 Dec 2019 07:16:22 +0330 https://virgool.io/@s.h.siadaty/%D9%BE%D9%86%D8%AC-s-%D8%A2%D8%B1%D8%A7%D9%85-%DA%A9%D8%B1%D8%AF%D9%86-%D8%A8%DA%86%D9%87-%D8%B4%D8%A7%D8%AF%D8%AA%D8%B1%DB%8C%D9%86-%D8%A8%DA%86%D9%87-%D9%85%D8%AD%D9%84-i3wf29xohtwo دو ماهی هست که خداوند یک ماهی کوچولو بهم داده. اسم دخترم رو دیانا به معنای نیکی بخش گذاشتیم.از اونجایی که دور از پدر و مادر ها و آدمهای با تجربه خانواده بودیم دست به کار شدیم و شروع کردیم به خوندن کتابهای مختلف که بفهمیم چطوری بچه رو بزرگ کنیم.کتابهای این زمینه خیلی متنوعند از مراحل پزشکی و خوراکی های هر ماه تا روانشناسی کودک و غیره.یکی از کتابهایی که باش آشنا شدم به اسم The Happiest Baby on the Block هست که یاد میده چطوری بچه رو آروم کنید. نویسنده روشش رو به عنوان پنج S معرفی می کنه که بیشتر بر اساس روشهای تجربی و سنتی است. اسامی این پنج تکنیک از کلمات انگلیسی تشکیل شده اند که همگی با S شروع می شوند: Swaddle (قنداق کردن)، Suck (مکیدن)، Shush (هاش هاش کردن با دهان)، swing (تاب دادن)، side (به پهلو خواباندن)فلسفه کلی این روشها بر اساس این مفهوم هست که فضای شکم مادر رو برای بچه شبیه سازی کنیم چون بچه ۹ ماه توی اون اروم گرفته بوده و به اونها عادت داشته. نویسنده پا رو فراتر از این توجیه میگذاره و می گه که باید اینطور تصور کنید که بچه اصولا باید ۱۲ ماه توی شکم مادر می مونده و بنابر این نیاز به این مراقبت ها داره. شکم مادر بچه رو سفت و محکم داخل خودش می گیره (کاری که قنداق کردن انجام می ده)، صدای زیادی توی گوش بچه هست (تقریبا معادل بلندی صدای ماشین چمن زنی)، با حرکت مادر بچه تاب می خوره، و بچه می تونه حرکت کنه و پهلو به پهلو بشه. شاید عجیب براتون ولی از هفته ۲۱ به بعد بچه هر روز چندین انس از مایع آمونیاک مادر رو قرقره می کنه و می خوره که این هم در واقع جزوی از خوردن و مکیدن هست.قنداق کردن چنیدن روش داره که تعداد زیادیشون با پارچه نخی انجام میشه. این پایین یکی از روشهای خوبه.قنداق کردن چنیدن روش داره که تعداد زیادیشون با پارچه نخی انجام میشه.علاوه براین چندین مدل قنداق آماده هم هست که من از یکی مثل این استفاده کردم.قنداق آماده بپیچ و ببردر مورد هاش هاش کردن و صدا در آوردن هم که میشه صداهایی با دهان در اورد که ظاهرا کم هزینه ترینه ولی شاید به دلیل نیاز به عمل حنجره در آینده گرون ترین در بیاد (اغراق کردم یکم). توصیه می کنم که از اپلیکیشن های تولید نویز سفید استفاده کنید. من همچنین برای دخترم موسیقی می گذارم. یکی دو تا آهنگ هستن که او عاشقشونه و خیلی سریع با اونها آروم میشه. حدس می زنید کدوم آهنگ ها هستن؟آهنگ نازگل بابای حبیبآهنگ یک دختر دارم شمایی زادهآهنگ بوم به به بوم بم فریدون فرخ زادشما هم می تونید سلیقه موسیقیایی بچتون رو کشف کنید و ازش برای آروم کردن و ترکیب اون با تاب دادن استفاده کنید.امیدوارم که بچه های همتون شادترین بچه های محله باشند و همسایه هاتون هم بتونن اندکی بدون صدای 'زیبای' بچتون استراحت کنن. Hossein Siadati Hossein Siadati Tue, 22 Oct 2019 12:20:42 +0330 https://virgool.io/@s.h.siadaty/%D8%A7%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF-%DB%B1%DB%B1-%D8%AC%D8%A7%DB%8C%D8%B2%D9%87-%D9%86%D9%82%D8%AF%DB%8C-%DB%B5%DB%B0-%D9%87%D8%B2%D8%A7%D8%B1%D8%AA%D9%88%D9%85%D8%A7%D9%86-%D8%B2%D9%85%D8%A7%D9%86%D8%A8%D9%86%D8%AF%DB%8C-%D8%AF%D8%B1%D8%B3%D9%87%D8%A7-llmqjke6zoqk اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.دسترسی و حل سوال از منبع اصلیپرسش: یک تعداد درس و پیشنیازهای آنها بصورت یک لیست داده شده اند. عنصر [1, 0] به این معناست که درس 1 پیشنیاز درس 0 است. تعداد درسها و ارتباط پیش نیازی آنها داده شده اند، مشخص کنید که آیا درسها اتمام پذیر هستند؟ مثال: اگر دو درس با رابطه پیشنیازی [[1, 0], [0, 1]] باشند آنگاه دروس اتمام ناپذیرند. اما اگر دو درس با رابطه پیشنیازی [[1, 0]] داده شده باشند آنگاه اتمام پذیرند.توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز ۱۵ ژوئننکات مهم:انتخاب برنده هر هفته بر اساس اولین پاسخ کامل هست که شرح حل مساله را فراهم آورد. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح حل خود را زیر پست بنویسید. تنها زبان برنامه نویسی مورد قبول پایتون می باشد.طبق روال برنده مسابقه هر هفته پس از انتخاب باید شرح کامل حل مساله را بنویسد. در انتها من شرح مساله نوشته شده را ویرایش و ارسال خواهم کرد. لطفا خودتان مسایل را حل کنید و پاسخ را ارسال نمایید. استفاده از پاسخ های دیگر و ارسال آن جهت الگونوردی با اهداف این حرکت مغایرت دارد. لطفا در این زمینه همکاری نمایید. با ارسال پاسخ زیر این پست تایید می کنید که کد متعلق به خودتان هست و آنرا شخصا حل کرده اید.بحث های علمی زیر این پست کاملا آزاد است. اگر در مورد نحوه مدیریت این حرکت پیشنهادی دارید به ایمیل من s.h.siadaty@gmail.com ارسال نمایید.قوانین اهدای جایزه:مبلغ جایزه نقدی 50,000 تومان می باشد.تنها یک نفر برنده برای هر هفته اعلام خواهد شد که طبق اولین پاسخ درست و شرح خلاصه می باشد.جهت ایجاد مشارکت، در هر فرد تنها می تواند یکبار برنده جایزه در طول یک ماه باشد.جایزه نقدی تنها در صورت نوشتن شرح کامل مساله تقدیم خواهد شد. Hossein Siadati Hossein Siadati Mon, 10 Jun 2019 03:12:55 +0430 https://virgool.io/@s.h.siadaty/%D9%86%D8%B5%D8%A7%DB%8C%D8%AD-%D8%A7%DB%8C%D9%85%D9%86%DB%8C-%D9%BE%D8%B1%D9%88%D9%81%D8%B3%D9%88%D8%B1-%D8%B3%D9%8F%D9%88%D8%A7%D9%86%D8%B3%D9%88%D9%86-%D8%B4%D9%85%D8%A7%D8%B1%D9%87-%DB%B2-%D9%86%D8%B5%D8%A8-%DA%86%DB%8C%D8%B2%D9%87%D8%A7%DB%8C-%D9%85%D8%AC%D8%A7%D9%86%DB%8C-vyd1ynf8nbvw مواظب برنامه هایی که نصب می کنید باشید!آهای شما! مواظب چیزهایی که نصب می کنی باش!!(مثال ۱ از فضای غیر مجازی)مشتری گرامی: لطفا این درب بازکن گاراژ را نصب کنید! با تشکر. (و دزد به شما نمی گوید که خودش هم ریموت را دارد) کَلَکِ جالبی است. اما کیه که گولش رو بخوره؟ (مثال ۲ از فضای غیر مجازی)۳. مشتری گرامی: لطفا این دوربین مجانی را در اتاق خواب خود نصب نمایید.۴. کَلَکِ جالبی است. اما کیه که گولش رو بخوره؟ (اما در فضای مجازی)۵. اسکرین سیور(Screen Saver) مجانی. تنها یک کلیک کنید!۶. (و کاربر با خود می اندیشد) گربه قشنگیه. نمی تونه آسیبی برسونه. درسته؟ این تنها یک تصویره.۷. اوه. نه. واقعا هیچ چیز مجانی وجود نداره! یک اسکرین سیور، منظورم اینه که، من تعداد زیادی از اسکرین سیور ها را دیده ام که کارهای زیاد دیگری نیز در کنار نمایش تصاویر زیبا، انجام می دهند... (مثلا پسوردهای شما را می دزدند، ایمیل شما را هک می کنند، پول از حساب شما جابجا می کنند ...) Hossein Siadati Hossein Siadati Fri, 07 Jun 2019 16:28:45 +0430 https://virgool.io/@s.h.siadaty/%D9%86%D8%B5%D8%A7%DB%8C%D8%AD-%D9%BE%D8%B1%D9%88%D9%81%D8%B3%D9%88%D8%B1-%D8%B3%D9%8F%D9%88%D8%A7%D9%86%D8%B3%D9%88%D9%86-%D8%B4%D9%85%D8%A7%D8%B1%D9%87-%DB%B1-r7eor8n93jnp فریب شاهزاده نیجریه را نخورید! سال 1907، بروکلین، نیویورک. بله ، این پل بسیار با شکوه است ولی برای من خیلی بزرگه و نمی تونم تمیز نگهش دارم. بنابر این تصمیم گرفتم اون رو به قیمت 10 دلار، همینجا بفروشم. نظرت چیه؟!اوه، پیشنهاد خیلی خوبیه!صد سال بعد(یک ایمیل ...)فرستنده: Bintaبه: Eddy Cookموضوع: Bitna replyای عزیزترین،من خانم Binta همسر ژنرال مرحوم Sanni هستم. من به کمک شما نیاز دارم تا مبلغ 23,000,000 دلار را به کشور شما منتقل کنم.در ازای این کار 15% از این مبلغ را به شما خواهم داد. ....۶. کاربر اینترنتی: اوه! چه پیشنهاد خوبی!!"Reproduced with permission. Please visit www.SecurityCartoon.com for more material." Hossein Siadati Hossein Siadati Wed, 05 Jun 2019 02:31:31 +0430 https://virgool.io/@s.h.siadaty/%D8%A7%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF-%DB%B1%DB%B0-%D8%AC%D8%A7%DB%8C%D8%B2%D9%87-%D9%86%D9%82%D8%AF%DB%8C-%DB%B5%DB%B0-%D9%87%D8%B2%D8%A7%D8%B1%D8%AA%D9%88%D9%85%D8%A7%D9%86-%D8%AA%D8%B9%D8%AF%D8%A7%D8%AF-%D8%A7%D8%B9%D8%AF%D8%A7%D8%AF-%D8%A8%D8%A7-%D8%A7%D8%B1%D9%82%D8%A7%D9%85-%DB%8C%DA%A9%D8%AA%D8%A7-ck80325iilxn اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.دسترسی و حل سوال از منبع اصلیپرسش: یک عدد صحیح نامنفی n داده شده است. تعداد اعداد با ارقام یکتا بین صفر تا ۱۰ به توان n را بیابید.توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز 8 ژوئننکات مهم:انتخاب برنده هر هفته بر اساس اولین پاسخ کامل هست که شرح حل مساله را فراهم آورد. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح حل خود را زیر پست بنویسید. تنها زبان برنامه نویسی مورد قبول پایتون می باشد.طبق روال برنده مسابقه هر هفته پس از انتخاب باید شرح کامل حل مساله را بنویسد. در انتها من شرح مساله نوشته شده را ویرایش و ارسال خواهم کرد. لطفا خودتان مسایل را حل کنید و پاسخ را ارسال نمایید. استفاده از پاسخ های دیگر و ارسال آن جهت الگونوردی با اهداف این حرکت مغایرت دارد. لطفا در این زمینه همکاری نمایید. با ارسال پاسخ زیر این پست تایید می کنید که کد متعلق به خودتان هست و آنرا شخصا حل کرده اید.بحث های علمی زیر این پست کاملا آزاد است. اگر در مورد نحوه مدیریت این حرکت پیشنهادی دارید به ایمیل من s.h.siadaty@gmail.com ارسال نمایید.قوانین اهدای جایزه:مبلغ جایزه نقدی 50,000 تومان می باشد.تنها یک نفر برنده برای هر هفته اعلام خواهد شد که طبق اولین پاسخ درست و شرح خلاصه می باشد.جهت ایجاد مشارکت، در هر فرد تنها می تواند یکبار برنده جایزه در طول یک ماه باشد.جایزه نقدی تنها در صورت نوشتن شرح کامل مساله تقدیم خواهد شد.حل مسالهالگونورد برتر: الگونورد برتر الگونورد 9، کاربر با ای دی ariaman5 هست.ایشون درست و کامل مساله را حل کردن و تشریح راه حل رو نوشتند. شرح مساله را با ویرایش من می خونید.به ایشون تبریک می گم و بهش می گم: عالی هستی! ادامه بده!و حالا شرح پاسخ:حل مساله را با یک مثال شروع میکنیم تا مطمئن شویم که مسئله را فهمیده ایم. اگر n برابر 1 باشد باید اعداد یک رقمی (شامل 0 تا 9) که رقم تکراری ندارند را بشماریم. این تعداد برابر ۱۰ می باشد. ساده ترین روش حل این مساله این است که اعداد 0 تا  را یک به یک بررسی کنیم و آنهایی که رقم تکراری ندارند را بشماریم. قطعه کد زیر این الگوریتم جستجوی کامل را پیاده سازی می کند.علت اینکه نیاز به بررسی اعداد بزرگتر از نمی باشد آن است که برای اعداد با تعداد ارقام بزرگتر از ۱۰ حتما یک رقم تکراری دارند. این الگوریتم بسیار کند است زیرا در بدترین حالت نیاز به مقایسه میلیارد عدد می باشد.روش سریعتر استفاده از اصول شمارش در ریاضیات گسسته می باشد. برای این کار باید تعداد اعداد X رقمی با ارقام یکتا را برای X های بین 1 تا n (که در آن n حداکثر 10 می باشد) محاسبه کنیم. مثلا برای شمارش تعداد تا 5 رقم که ارقام تکراری ندارند باید تعداد اعداد یک رقمی، دو رقمی، سه رقمی، چهار رقمی و ۵ رقمی که رقم تکراری ندارند را جدا از هم بشماریم و نهایتا با جمع این تعداد حاصل را محاسبه نماییم. حال باید راه حلی را بیابیم که تعداد اعداد X رقمی با ارقام یکتا را بشماریم. به عنوان مثال تعداد اعداد سه رقمی با ارقام یکتا با استفاده از اصل شمارش به این صورت است: از چپ به راست اولین رقم می تواند یک از ارقام 1 تا 9 باشد. بنابر این 9 انتخاب داریم. رقم بعدی می تواند یکی از 9 رقمی که قبلا استفاده نشده اند (یعنی 8 رقم باقیمانده مابین 1 تا 9 و همچنین 0 که در رقم سمت چپ استفاده نشد). بنابراین 9 انتخاب داریم. برای موقعیت بعدی یکی از 8 رقم استفاده نشده در دو جایگاه قبلی قابل استفاده اند. بنابر این جواب نهایی 9x9x8 می باشد. برای یک عدد 4 رقمی این فرمول برابر است با 7*8*9*9 بنابر این از نتایج محاسبات برای تعداد ارقام عدد X رقمی می توان برای محاسبه تعداد اعداد X+1  رقمی با ارقام غیر تکراری استفاده نمود.بنابراین برای هر عدد یک تا n رقمی این فرمول رو حساب کنیم و تعداد آنها را به هم جمع کنیم و جواب نهایی را بدست آوریم. Hossein Siadati Hossein Siadati Mon, 03 Jun 2019 03:37:14 +0430 https://virgool.io/@s.h.siadaty/%D8%A7%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF-%DB%B9-%D8%AC%D8%A7%DB%8C%D8%B2%D9%87-%D9%86%D9%82%D8%AF%DB%8C-%DB%B5%DB%B0%DB%B0%DB%B0%DB%B0-%D8%AA%D9%88%D9%85%D8%A7%D9%86-%D9%85%D8%AD%D8%A7%D8%B3%D8%A8%D9%87-h-index-etpo7slbzbzp اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.دسترسی و حل سوال از منبع اصلیپرسش: آرایه ای از تعداد ارجاع ها (citation) به مقالات یک محقق داده شده است. برنامه ای بنویسید که H-Index محقق را محاسبه نماید. تعریف H-Index این است: یک محقق دارای ایندکس h هست اگر h مقاله از ‌N مقاله وی حداقل h ارجاع داشته باشند و هیچ یک از N-h مقاله دیگر وی بیش از h ارجاع نداشته باشند.توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز 1 ژوئننکات مهم:انتخاب برنده هر هفته بر اساس اولین پاسخ کامل هست که شرح حل مساله را فراهم آورد. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح حل خود را زیر پست بنویسید. تنها زبان برنامه نویسی مورد قبول پایتون می باشد.طبق روال برنده مسابقه هر هفته پس از انتخاب باید شرح کامل حل مساله را بنویسد. در انتها من شرح مساله نوشته شده را ویرایش و ارسال خواهم کرد. لطفا خودتان مسایل را حل کنید و پاسخ را ارسال نمایید. استفاده از پاسخ های دیگر و ارسال آن جهت الگونوردی با اهداف این حرکت مغایرت دارد. لطفا در این زمینه همکاری نمایید. با ارسال پاسخ زیر این پست تایید می کنید که کد متعلق به خودتان هست و آنرا شخصا حل کرده اید.بحث های علمی زیر این پست کاملا آزاد است. اگر در مورد نحوه مدیریت این حرکت پیشنهادی دارید به ایمیل من s.h.siadaty@gmail.com ارسال نمایید.قوانین اهدای جایزه:مبلغ جایزه نقدی 50,000 تومان می باشد.تنها یک نفر برنده برای هر هفته اعلام خواهد شد که طبق اولین پاسخ درست و شرح خلاصه می باشد.جهت ایجاد مشارکت، در هر فرد تنها می تواند یکبار برنده جایزه در طول یک ماه باشد.جایزه نقدی تنها در صورت نوشتن شرح کامل مساله تقدیم خواهد شد.حل مسالهالگونورد برتر: الگونورد برتر الگونورد 9، کاربر با ای دی Fatemeh هست.ایشون درست و کامل مساله را حل کردن و تشریح راه حل رو نوشتند. شرح مساله را با ویرایش من می خونید.به Fatemeh تبریک می گم و بهش می گم: عالی هستی! ادامه بده!و حالا شرح پاسخ:حل مساله را با یک مثال شروع می کنیم تا مطمین شویم آن را بدرستی درک کرده ایم.  برای مثال، اگر محققی ۵ مقاله A, B, C, D, E با تعداد استنادات ۸، ۳، ۵، ۱۰، ۴ داشته باشد، H-index مقالات وی ۴ می باشد زیرا ۴ مقاله وی حداقل دارای چهار استناد (ارجاع) می باشند و هیچ مقاله دیگری بیش از ۴ ارجاع ندارد. به عنوان مثالی دیگر، اگر تعداد ارجاعات ۳، ۳، ۲۵، ۸، ۵ باشند، آنگاه H-index نویسنده برابر با ۳ است.روش جستجوی کاملارایه الگوریتم را با روش جستجوی کامل شروع می کنیم. در روش جستجوی کامل باید تمام H-index ها را از مقدار حداکثر شروع کنیم. حداکثر H-index یک محقق برابر با تعداد مقالات وی (N) می باشد (یعنی حالتی که تعداد ارجاعات هر مقاله حداقل به تعداد مقالات وی باشد) و حداقل آن صفر می باشد(اگر هیچ مقاله ای ارجاعی نداشته باشد). بنابر این در روش جستجوی کامل هر بار بررسی می کنیم که  آیا نویسنده i مقاله دارد که حداقل i ارجاع داشته باشند. اگر این کار را از N که حداکثر ممکن است شروع کنیم آنگاه اولین مقدار i که شرط گفته شده را برآورد پاسخ می باشد.برای هر مقدار i باید کل آرایه ارجاعات مقالات  را بررسی کنیم. بنابر این مرتبه اجرایی این الگوریتم N^2 می باشد.اشکال این روش همان جستجوی بررسی مجدد کل آرایه است.بهبود با استفاده از مرتب سازیاگر لیست تعداد ارجاعات را مرتب نماییم آنگاه نیاز نیست که لیست را بصورت کامل بررسی کنیم.و. به عنوان مثال برای نویسنده با مقالات ۸، ۳، ۵، ۱۰، ۴ پس از مرتب سازی به لیست [3, 4, 5, 8, 10] می رسیم. اگر H-index یک نویسنده h باشد آنگاه مقدار اندیس h-1 آن حداقل باید برابر h باشد زیرا در این صورت همه h عنصر اول دارای h یا تعداد بیشتری ارجاع می باشند. از این رو، در این الگوریتم بهبود یافته ابتدا آرایه را مرتب می کنیم. سپس از مقدار i برابر N شروع می کنیم و هر بار مقدار عنصر i-1 را بررسی می کنیم. در صورتی که مقدار بزرگتر یا مساوی i بود، مقدار i پاسخ می باشد.توضیح کد: در خط 5 آرایه citations که تعداد استنادات به مقاله‌ها است را به صورت نزولی مرتب کردیم. سپس i را با مقدار اولیه N مقداردهی اولیه کرده ایم و هر بار یک شرط را بررسی می کنیم تا بینیم i مقاله با حداقل i ارجاع وجود دارد. پیچیدگی زمانی این الگوریتم به دلیل مرتب سازی لیست ((O(n*log(n و پیچیدگی حافظه آن(O(1 است.کاهش پیچیدگی زمانی با استفاده از یک تکنیک مفید روش مرتب سازی از مقایسه استفاده می کند تا عناصر را مرتب نماید. بجای مرتب سازی مقایسه ای می توان از یک مرتب سازی لانه ای استفاده کرد. این روش در واقع بیشتر شبیه جستجوی عناصر به ترتیب مرتب شده آنهاست. مثلا لیست 3, 6, 1, 8, 6, 2 را می توان به این صورت مرتب نمود:ابتدا یکبار کل لیست را بررسی می کنیم که مقادیر ماکزیمم (یعنی 8) و مقدار مینیمم (یعنی 1) را بیابیم. در ضمن یک دیکشنری می سازیم و هر یک از مقادیر را در آن قرار می دهیم به این صورت که کلید برابر با مقدار عنصر لیست و مقدار عنصر دیکشنری برابر تعداد مشاهده شده عنصر در لیست می باشد (در واقع هر بار یک واحد به شمارنده اضافه می کنیم).سپس از یک شمارنده با مقدار اولیه 1(برابر با مینیمم مقادیر لیست)  شروع می کنیم و هر بار بررسی می کنیم که آیا شمارنده به عنوان کلید در دیکشنری وجود دارد و در صورت وجود مقدار آن (تعداد بارهای مشاهده مقدار در لیست اصلی) چند تا است.الگوریتم بهبود یافته ما از چنین تکنیکی استفاده می کند. این الگوریتم به این طریق است که تعداد استنادات بزرگتر N را جداگانه نگهداری می‌کنیم (N تعداد عناصر آرایه است)، همینطور تعداد تکرار استنادات کوچکتر مساوی N را در قالب یک دیکشنری نگهداری می کنیم، تا در صورت احراز شرایط مناسب به  استنادات بزرگتر N اضافه کنیم.در انتها به صورت نزولی با یک حلقه از اندیس بزرگترین کلید که طبق تعریف قبل می بایست کوچکتر مساوی N بوده باشد، تعداد تکرار استنادات کوچکتر مساوی N را به مقدار تعداد استنادات بزرگتر N اضافه می‌کنیم، هر زمان که اچ ایندکس بزرگترمساوی اندیس i آن شد، i جواب مسئله است.با این توضیحات شروع به نوشتن برنامه می کنیم.  در خط 3 طول آرایه استنادات ورودی، متغیر h با مقدار اولیه صفر جهت نگهداری تعداد استنادات بزرگتر N  و یک مجموعه به صورت دیکشنری با مقدار پیش فرض تعریف کردیم، مجموعه c تکرار تعداد استنادات کوچکتر مساوی N را با کلید نگهداری خواهد کرد.در خط 5 و 6 هر جا که مقدار تعداد استنادات یک مقاله بزرگتر N باشد به متغیر h یک واحد اضافه کرده ایم (زیرا در هر صورت به تعداد H-index یک واحد اضافه می کنند) وگرنه تعداد مقالات با تعداد ارجاعات x  را یک واحد اضافه می کنیم. در انتها کلیدهای دیکشنری c در بازه 0 تا N می باشند.پس از خروج از این حلقه حداقل H-index در متغیر h قرار گرفته است. حال باید با بررسی مقالاتی که کمتر از N ارجاع دارند H-index  را بروزرسانی کنیم.برای این کار در خط 8 تا 10 به صورت نزولی از بزرگترین استناد ممکن یعنی N شروع می کنیم. در صورتی که مقاله i ام کمتر از h ارجاع داشته باشد به مقدار نهایی h دسته یافته ایم.مزیت استفاده از defaultdict عدم چک کردن کلید و مقدار دهی اولیه مجموعه است.پیچیدگی زمانی این الگوریتم به جهت استفاده  نکردن از مرتب سازی(O(n و پیچیدگی حافظه به دلیل استفاده از مجموعه(O(n  است.توضیحات بیشتر طبق تعریف ویکی پدیا، به طور رسمی اگر f تابع متناظر با تعداد استنادات برای هر مقاله باشد، اچ ایندکس را به شکل زیر محاسبه می‌کنیم:ابتدا مقادیر f را به ترتیب نزولی مرتب می‌کنیم، سپس به دنبال آخرین مکانی می‌گردیم که در آن f بزرگتر یا مساوی با آن مکان است (این مقدار را h می‌نامیم).برای مثال، اگر محققی داریم که ۵ مقاله A, B, C, D, E با تعداد استنادات ۳، ۴، ۵، ۸، ۱۰ دارد، اچ ایندکس آن برابر ۴ است زیرا چهارمین مقاله دارای ۴ استناد و پنجمین مقاله دارای ۳ استناد است. در مقابل اگر همین مقالات دارای ۳، ۳، ۵، ۸، ۲۵ استناد باشند، آنگاه اچ ایندکس نویسنده برابر با ۳ است زیرا مقاله چهارم تنها ۳ استناد دارد.دو مثال از نحوه محاسبه اچ ایندکساگر تابع f را به شکل نزولی از بالاترین مقدار تا پایین‌ترین مقدار داشته باشیم، می‌توانیم اچ ایندکس را به شکل زیر محاسبه کنیم:حل مساله را به دو قسمت می توانیم تقسیم می کنیم.قسمت اول: می دانیم که i بیشتر N که تعداد عناصر آرایه باشد نخواهد شد (i یک شمارنده از بزرگترین تعداد استناد است)، عملا زمانی که (f(i بزرگتر N هست، تنها مقدار i عمل خواهد نمود، زیرا i کوچکتر خواهد بود و داریم بین (min(f(i),i  را می گیریم و زمانی که max آنها را بگیریم، مثل یک شمارنده عمل خواهد نمود.قسمت دوم: اگر به عمق یک مثال محاسبه اچ ایندکس توجه کنیم، می بینیم که چند واحد کم داریم، اگر تعداد نتایج تکراری بزرگترین (f(i کوچکتر مساوی N را به نتیجه قسمت اول اضافه کنیم، تا زمانی که قسمت اول بزرگتر مساوی i شود، i جواب مسئله ما خواهد بود. Hossein Siadati Hossein Siadati Sun, 26 May 2019 17:13:34 +0430 https://virgool.io/@s.h.siadaty/%D8%A7%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF-%DB%B8%D8%AC%D8%A7%DB%8C%D8%B2%D9%87-%D9%86%D9%82%D8%AF%DB%8C-%DB%B5%DB%B0-%D9%87%D8%B2%D8%A7%D8%B1-%D8%AA%D9%88%D9%85%D8%A7%D9%86-%D9%81%D8%A7%D8%B5%D9%84%D9%87-%D9%86%D8%B2%D8%AF%DB%8C%DA%A9%D8%AA%D8%B1%DB%8C%D9%86-%D8%B5%D9%81%D8%B1-%D8%AF%D8%B1-%D9%85%D8%A7%D8%AA%D8%B1%DB%8C%D8%B3-oky51rfhm5av اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.دسترسی و حل سوال از منبع اصلیپرسش: یک ماتریس از مقادیر صفر و یک داده شده است. برای هر خانه فاصله نزدیکترین صفر به آن را بیابید.توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز 25 مینکات مهم:انتخاب برنده هر هفته بر اساس اولین پاسخ کامل هست که شرح حل مساله را فراهم آورد. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح حل خود را زیر پست بنویسید. تنها زبان برنامه نویسی مورد قبول پایتون می باشد.طبق روال برنده مسابقه هر هفته پس از انتخاب باید شرح کامل حل مساله را بنویسد. در انتها من شرح مساله نوشته شده را ویرایش و ارسال خواهم کرد. لطفا خودتان مسایل را حل کنید و پاسخ را ارسال نمایید. استفاده از پاسخ های دیگر و ارسال آن جهت الگونوردی با اهداف این حرکت مغایرت دارد. لطفا در این زمینه همکاری نمایید. با ارسال پاسخ زیر این پست تایید می کنید که کد متعلق به خودتان هست و آنرا شخصا حل کرده اید.بحث های علمی زیر این پست کاملا آزاد است. اگر در مورد نحوه مدیریت این حرکت پیشنهادی دارید به ایمیل من s.h.siadaty@gmail.com ارسال نمایید.قوانین اهدای جایزه:مبلغ جایزه نقدی 50,000 تومان می باشد.تنها یک نفر برنده برای هر هفته اعلام خواهد شد که طبق اولین پاسخ درست و شرح خلاصه می باشد.جهت ایجاد مشارکت، در هر فرد تنها می تواند یکبار برنده جایزه در طول یک ماه باشد.جایزه نقدی تنها در صورت نوشتن شرح کامل مساله تقدیم خواهد شد.این هفته برنده ای نداشتیم. بنابر این راه حل خودم را اینجا شرح می دهم.حل: روش جستجوی کامل برای این مساله به این صورت است:برای هر خانه غیر صفر، فاصله آن تا تمام خانه های ماتریس با مقدار صفر را بدست آور و کمترین فاصله را به عنوان نتیجه برگردان. در این الگوریتم برای بدست آوردن کمترین فاصله هر خانه غیر صفر همه خانه های ماتریس را باید بررسی کنیم. بنابر این پیچیدگی محاسباتی آن N^4 می باشد.مشکل این کار آن است که از محاسبات قبلی برای بدست آوردن نتیجه برای خانه های دیگر استفاده نمی شود. با توجه به اینکه این مساله شباهتهایی با مساله یافتن کوتاهترین مسیر درگراف بین یک راس و تمام راس های دیگر دارد، می توانیم از روش حل دایجکسترا ایده بگیریم. در الگوریتم دایجکسترا از یک گره شروع می کنیم و هر بار مقدار گره های دیگر (که در واقع فاصله آنها تا نقطه شروع را نشان می دهند) را بروز می کنیم. در هر بار یک گره که مقدارآن نهایی نشده است و دارای کمترین مقدار هست را انتخاب می کنیم و مقدار آن را نهایی می کنیم.در این مساله هر خانه با مقدار صفر یک نقطه شروع است. بنابر این آنها را به یک لیست که شامل خانه های مورد بررسی است قرار می دهیم. با شروع از هر خانه هر بار فاصله خانه های بعدی (بالا-پایین-راست-چپ) را از آن محاسبه و در صورت نیاز بروز می کنیم. در صورتی که مقدار خانه ای بروز شود آن را به لیست خانه های مورد بررسی اضافه می کنیم و این کار را تکرار می کنیم تا جایی که مقدار هیچ خانه ای قابل بروز رسانی نباشد. در این حالت مطمین خواهیم بود که فاصله کمینه برای همه خانه ها را محاسبه کرده ایم. این راه حل را می توان به عنوان یک پیمایش BFS از هر خانه با مقدار صفر در تصویر نمود با این تفاوت که پیمایش با رسیدن به خانه هایی که مقدار آنها نهایی شده است متوقف می شود. بنابر این پیچیدگی محاسباتی این الگوریتم برابر با اندازه ماتریس یعنی clen*rlen می باشد.قطعه کد زیر پیاده سازی این الگوریتم را نشان می دهد. Hossein Siadati Hossein Siadati Sun, 19 May 2019 18:08:18 +0430 https://virgool.io/@s.h.siadaty/%D8%A7%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF%DB%8C-%DB%B5-%D8%AC%D8%A7%DB%8C%D8%B2%D9%87-%D9%86%D9%82%D8%AF%DB%8C-%DB%B5%DB%B0-%D9%87%D8%B2%D8%A7%D8%B1-%D8%AA%D9%88%D9%85%D8%A7%D9%86-%DB%8C%D8%A7%D9%81%D8%AA%D9%86-%D8%B9%D9%86%D8%A7%D8%B5%D8%B1-%D8%A7%DA%A9%D8%AB%D8%B1%DB%8C%D8%AA-s8jytbnqbmst اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.دسترسی و حل سوال از منبع اصلیپرسش: یک آرایه به طول N از اعداد صحیح داده شده است. همه عناصری را بیابید که بیش از [n/3] بار تکرار شده اند.مثال: برای آرایه [3, 2, 3] خروجی [3] می باشد. اگر ورودی [2,2,2,3,3,1,1,1] باشد پاسخ [2,1] می باشد.توجه کنید که الگوریتم باید خطی باشد و پیچیدگی فضا (O(1.توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز 18 مینکات مهم:انتخاب برنده هر هفته بر اساس اولین پاسخ کامل هست که شرح حل مساله را فراهم آورد. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح حل خود را زیر پست بنویسید. تنها زبان برنامه نویسی مورد قبول پایتون می باشد.طبق روال برنده مسابقه هر هفته پس از انتخاب باید شرح کامل حل مساله را بنویسد. در انتها من شرح مساله نوشته شده را ویرایش و ارسال خواهم کرد. لطفا خودتان مسایل را حل کنید و پاسخ را ارسال نمایید. استفاده از پاسخ های دیگر و ارسال آن جهت الگونوردی با اهداف این حرکت مغایرت دارد. لطفا در این زمینه همکاری نمایید. با ارسال پاسخ زیر این پست تایید می کنید که کد متعلق به خودتان هست و آنرا شخصا حل کرده اید.بحث های علمی زیر این پست کاملا آزاد است. اگر در مورد نحوه مدیریت این حرکت پیشنهادی دارید به ایمیل من s.h.siadaty@gmail.com ارسال نمایید.قوانین اهدای جایزه:مبلغ جایزه نقدی 50,000 تومان می باشد.تنها یک نفر برنده برای هر هفته اعلام خواهد شد که طبق اولین پاسخ درست و شرح خلاصه می باشد.جهت ایجاد مشارکت، در هر فرد تنها می تواند یکبار برنده جایزه در طول یک ماه باشد.جایزه نقدی تنها در صورت نوشتن شرح کامل مساله تقدیم خواهد شد.حل مسالهبرنده هفته ۷ الگونورد کاربر با ای دی Iman می باشند.به Iman تبریک می گم!و حالا شرح پاسخ:هدف در این مسئله پیدا کردن عددهای در یک لیست  هست که بیشتر از n/3 (یک سوم طول لیست) تکرار را دارند، در اینجا n برابر تعداد عناصر آرایه است. حل مسئله را با یک مثال ساده شروع می‌کنیم تا مطمئن شویم که مسئله را به خوبی درک کرده‌ایم، اگر ورودی زیر را داشته باشیم:[3,3,3,2,1,1]در این صورت تعداد عناصر آرایه برابر n=6 در نتیجه n/3=2 و پاسخ خروجی برابر با [3,1] خواهد بود، زیرا تعداد تکرار عدد 3 و 1 برابر 3 و تکرار عدد 2 برابر 1 است.ساده ترین روش حل این مساله آن است که تعداد تکرار هر مقدار را بشماریم و در انتها برای هر مقدار بررسی کنیم که آیا تعداد تکرار از یک سوم طول آرایه بیشتر است. برای شمارش تعداد تکرار هر عنصر می‌توان از یک دیکشنری استفاده نمود که عناصر لیست کلیدهای آن را تشکیل می دهند و مقدار متناظر هر کلید تعداد تکرار آن  در لیست نگهداری می‌کند. برای این کار می توان یک دیکشنری ساخت و با استفاده از یک حلقه تکرار تعداد تکرارهای عناصر را شمرد. روش متناظر استفاده از ساختار Counter پایتون می باشد که با دریافت یک لیست یک دیکشنری می سازد و تعداد تکرار عناصر را در آن قرار می دهد. پس از انجام شمارش با استفاده از یک حلقه بررسی می کنیم که اگر تعداد تکرار یک عدد بیشتر از n/3 باشد سپس آن را به یک لیست خروجی اضافه می کنیم. قطعه برنامه زیر پیاده سازی این روش را نشان می دهد.وضیح کد:در خط 3 با استفاده از متد items دیکشنری را به یک لیست که هر عنصر آن یک تاپل هست تبدیل کردیم و با یک حلقه عناصر تاپل این آرایه را بررسی کرده‌ایم.پیچیدگی زمانی و حافظه‌ای:پیچیدگی زمانی این الگوریتم برابر (O(n و پیچیدگی حافظه آن به دلیل استفاده کردن از دیکشنری برابر (O(n می‌باشد. این الگوریتم محدودیت صورت مساله مبنی بر استفاده از تنها (O(1 حافظه را برآورده نمیکند. بنابراین باید حل مساله را بهبود ببخشیم.نحوه بهبود:اگر بیشتر روی مسئله تامل کنیم در می یابیم حداکثر 2 عنصر لیست محدودیت مورد نظر یعنی تکرار بیش از یک سوم بار در لیست را برآورده می کنند. دلیل آن این است که اگر سه عنصر بیش از یک سوم بار تکرار می شدند آنگاه شمارش تعداد آنها از طول لیست بیشتر می شد که یک تناقض است. می توانیم از این خاصیت استفاده نماییم و از استفاده از دیکشنری پرهیز کنیم. یک الگوریتم  مشهور که کمک می کند این کار را انجام دهیم الگوریتم معروف رای اکثریت (majority vote algorithm) بویر- مور  (Boyer–Moore) است که  عنصری که بیش از نصف طول یک لیست تکرار می شود را می یابد. پیچیدگی زمانی این الگوریتم (O(n و پیچیدگی فضایی آن (O(1  می باشد.این الگوریتم به این نحو عمل می‌کند که عناصر لیست را می خواند و تنها از یک متغیر m برای نگهداری یک عنصر کاندید و یک شمارنده i برای شمارش تعداد رای به عنصر کاندید استفاده می‌کند. مقدار اولیه این دو متغیر در ابتدا صفر است. سپس در یک حلقه تکرار عناصر لیست را می‌خوانیم. چنانچه شمارنده برابر صفر باشد مقدار عنصر کاندید m را را برابر عنصر کنونی، تنظیم می کنیم مقدار شمارنده را یک می کنیم. در غیر این صورت (شمارنده بزرگتر از صفر)  چنانچه عنصر کنونی برابر عنصر کاندید باشد یک واحد به شمارنده اضافه می‌کنیم و در غیر اینصورت (چنانچه مقدار برابر عنصر کاندید نباشد) شمارنده را یک واحد کاهش خواهیم داد. شبه الگوریتم این الگوریتم را در زیر مشاهده می‌کنید:الگوریتم یافتن عنصر اکثریت بویر مویر - مرجع Wikipediaبا پایان پیمایش لیست و اجرای الگوریتم، مقداری در متغیر m خواهد بود فارغ از اینکه که آیا لیست یک عنصر اکثریت دارد. اما چنانچه عنصر اکثریت داشته باشد، مقار آن m می باشد. برای اطمینان، باید یکبار دیگر لیست را پیمایش کنیم و تعداد تکرار m را بشماریم و نهایتا با طول لیست مقایسه نماییم.  تصویر زیر حالت الگوریتم رای حداکثریت بویر-مور را برای یک مثال از لیست مقادیر (که با اشکال دایره، مربع و ستاره مشخص شده اند) نشان می دهد، ورودی‌ها در امتداد محور افقی نشان داده شده اند و   محور عمودی مقدار متغیر شمارنده i را نشان می دهد:یک مثال از اجرای الگوریتم بویر مویر -- مرجع Wikipediaالگوریتم بویر-مور را می توان برای حل مساله یافتن عناصر بیش از یک سوم استفاده نمود. به جای استفاده از یک عنصر کاندید دو عنصر کاندید (t) در نظر می گیریم. همچنین دو عنصر شمارنده (c) در نظر می گیریم.  با این اوصاف شروع به نوشتن برنامه زیر می کنیم. در خط 2 متغیرهای مورد نیاز را تعریف می کنیم. در خط 3 تا 14 الگوریتم بویر مور را جهت به دست آوردن دو عددی که بیشترین تکرار را دارند، تعریف پیاده کرده ایم با این تفاوت که شرط های شمارش را برای دو عنصر کاندید تغییر داده ایم. در خط 16 تا 21 تعداد تکرار این دو عدد را در رشته محاسبه کرده‌ایم. در خط 23 تا 26 شروطی گذاشته‌ایم که اگر تعداد تکرار این دو متغیر توالی بیشتر n/3 بود آن را به بردار خروجی نهایی اضافه کند.پیچیدگی زمانی و حافظه‌ای:پیچیدگی زمانی این الگوریتم برابر(O(n و پیچیدگی حافظه آن برابر(O(1 می‌باشد. Hossein Siadati Hossein Siadati Sun, 12 May 2019 22:05:19 +0430 https://virgool.io/@s.h.siadaty/%D8%A7%D9%85%D8%AA%DB%8C%D8%A7%D8%B2-%D9%BE%D8%B1%D8%A7%D9%86%D8%AA%D8%B2%D9%87%D8%A7-ivzaeqonbxev اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.دسترسی و حل سوال از منبع اصلیپرسش: یک رشته متشکل از پرانتزها داریم که پرانتزبندی آن درست می باشند. امتیاز پرانتزبندی را با توجه به قواعد زیر محاسبه کنید.۱- پرانتز بندی () امتیاز 1 دارد.۲- امتیاز AB می شود امتیاز A بعلاوه امتیاز B.۳- امتیاز (A) می شود دو برابر امتیاز A.مثلا، امتیاز ()()() برابر با 3 و امتیاز ((())) برابر با 4 می باشد. توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز 5 مِییادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.توجه توجه: ممکن است که حل این مساله بصورت آنلاین در سایت لیت کد وجود داشته باشد. در الگونوردی منظور این است که خودمان مساله را حل کنیم. بنابر این استفاده از آن راه حل ها مجاز نمی باشد. راه حل هایی که مشابه باشند در الگونوردی پذیرفته نخواهند شد. Hossein Siadati Hossein Siadati Sun, 28 Apr 2019 17:13:19 +0430 https://virgool.io/@s.h.siadaty/%D8%A7%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF-%DB%B5-%D8%A7%D8%B2-%D9%87%DA%A9-%D8%B4%D8%AF%D9%86-%DB%8C%DA%A9-%D8%A7%DA%A9%D8%A7%D9%86%D8%AA-%D8%AC%D9%84%D9%88%DA%AF%DB%8C%D8%B1%DB%8C-%DA%A9%D9%86%DB%8C%D8%AF-mxkrttfe3jqx اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.دسترسی و حل سوال از منبع اصلیپرسش: یک کلمه عبور داده شده است. یک کلمه عبور خوب است اگر که یک هکر نتواند به راحتی آن را حدس بزند. اینجا ضابطه خاصی برای یک کلمه عبور خوب داریم :۱- طول آن باید حداقل ۶ و حداکثر ۲۰ باشد.۲- باید شامل حداقل یک حرف بزرگ، یک حرف کوچک، یک رقم باشد.۳- شامل هیچ سه حرف متوالی یکسان نباشد.برنامه ای بنویسید که یک کلمه عبور را دریافت کنند و حداقل تعداد تبدیلات (درج، حذف، و جایگزینی) حروف برای تبدیل آن به یک کلمه عبور خوب را برگرداند.توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز 27 آوریلیادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.حل مسالهالگونورد برتر: الگونورد برتر الگونورد 4، کاربر با ای دی Iman هست.ایشون درست و کامل مساله را حل کردن و تشریح راه حل رو نوشتند. تشریح حل مساله رو خودشون بصورت کامل نوشتن.ایمان فراحی http://professionalProgrammer.ir یک برنامه نویسی فوق العاده است و ریاضی اش هم خیلی خوبه و می تونه هم مسایل رو فرمول کنه و هم پیاده سازی کنه!به Iman تبریک می گم و بهش می گم: عالی هستی! ادامه بده!و حالا شرح پاسخ:حل مسئله را با چند مثال شروع می‌کنیم تا مطمئن شویم که مسئله را درستی درک کرده ایم.هدف پیدا کردن کمینه تغییراتی که کاربر می‌تواند، اعمال کند تا برحسب محدودیت‌های بالا یک کلمه عبور، کلمه عبور مستحکمی بشود. به جدول تهیه شده  زیر توجه کنید:همان گونه که در جدول فوق مشاهده کردید ما با سه دسته محدودیت عمده سروکار داریم:1-نوع حروف معتبر 2- متوالی نبودن سه حرف تکراری. 3- طول رشته ورودیحروف معتبر ورودی شامل سه محدودیت می باشد:1-یک محدودیت حرف بزرگ 2- یک محدودیت حرف کوچک 3- یک محدودیت عدد؛ که مجموع  آنها سه محدودیت را به وجود می آورد.متوالی نبودن سه حرف تکراری که هر سه حرف تکراری یک محدودیت را به وجود می آورد.طول رشته ورودی که می توان آن را به سه بازه تقسیم کرد:بازه 0 تا 5 که شامل 6-len(n) محدودیت اضافه هست.بازه 6 تا 20 که محدودیت اضافه‌ای ایجاد نمی‌کند.بازه 20 به بالا که هر حرف اضافه یک محدودیت و تصحیح این حرف بر روی سه حالت زیر تاثیر می گذارد:برای یک مورد زیر رشته تکراری پیوسته که طول آن ضریب ۳ است ( از 3n منظور زیررشته‌های با حروف تکراری پیوسته به صورت "aaa" است) حذف یک حرف اضافی موجب کاهش محدودیت یک مورد از این زیر رشته تکراری می‌شود. برای یک مورد زیر رشته تکراری پیوسته که طول آن ضریب ۳ بعلاوه ۱ است (3n+1 به عنوان مثال "aaaa") حذف دو حرف اضافی موجب کاهش محدودیت یک مورد از این زیررشته تکراری می‌شود.برای یک مورد زیر رشته تکراری پیوسته که طول آن ضریب ۳ بعلاوه 2 است (3n+2 به عنوان مثال "aaaaa") حذف سه حرف اضافی موجب کاهش محدودیت یک مورد از این زیررشته تکراری می‌شود.به عنوان مثال:برای زیر رشته 3n حرفی پیوسته خواهیم داشت: "1aaaaaaA…2" که حذف یک حرف اضافه می‌تواند، موجب کاهش محدودیت تنها یک زیر رشته 3 حرفی تکراری شود، که این حالت می‌تواند "1aaaaaA...2" باشد.برای زیر رشته 3n+1 حرفی پیوسته خواهیم داشت: "12aaaaaaaA...2" که حذف دو حرف اضافه می‌تواند، موجب کاهش محدودیت تنها یک زیر رشته 3 حرفی تکراری شود، که این حالت می‌تواند "12aaaaaA...2" باشد.برای زیر رشته 3n+2 حرفی پیوسته خواهیم داشت: "123aaaaaaaaA...2" که حذف سه حرف اضافه می‌تواند، موجب کاهش محدودیت تنها یک زیر رشته 3 حرفی تکراری شود، که این حالت می‌تواند "123aaaaaA...2" باشد.نکته: دقت شود که در مثال های بالا حداقل تعداد تغییرات باید مورد ملاک باشد.برای روشن شدن موضوع مثال شماره 4 جدول فوق را بررسی می کنیم:اگر داشته باشیم:aaaabbaaabbaaa123456Aاین رشته شامل 21 حرف یا کاراکتر هست، که شامل 3 محدودیت حروف تکراری (که شامل 2 توالی 3n حرفی و 1 توالی 3n+1 حرفی) و 1 محدودیت حرف حذفی است که اگر بخواهیم با حداقل تغییرات رشته فوق را معتبر کنیم، این دسته بندی این‌گونه است:که برای حذف حرف اضافی از رشته فوق یک محدودیت از محدودیت‌های زیررشته 3 حرفی از مثال بالا کاهش می یابد، اگر برای معتبر شدن رشته حرف a  را از توالی تکراری سمت راست را حذف کنیم، خواهیم داشت:و دو محدودیت از سه محدودیتی که داشتیم و یکی را برطرف کردیم، باقی می‌ماند. که حداقل اصلاح مورد نیاز برای اینکه کلمه عبور فوق معتبر شود، سه محدودیت می باشد.یا در مثال aaaaaa1234567890123Ubefg با طول 24 که شامل 4 حرف اضافه، 2 محدودیت حروف تکراری (که شامل 1 توالی 3n حرفی است) که جمعا حداقل به 4 تغییر احتیاج خواهیم داشت.یا در مثال aaaaaaaaaaaaaaaaaaaaa با طول 21 که شامل 1 حرف اضافه، 7 محدودیت حروف تکراری (که شامل 1 توالی 3n حرفی است) که جمعا حداقل به 7 تغییر احتیاج خواهیم داشت.در نتیجه مقدار حروف اضافه که محدودیت ایجاد می کنند ثابت است، و این مقدار اضافه شده محدودیت توالی سه حرفی است، که باید در حالتی که رشته ما بیشتر از 20 حرف طول دارد، اصلاح شود.توضیح الگوریتماین تابع از را به سه بخش تقسیم کرده ایم:1-حالتی که اندازه رشته ورودی ما کمتر 6 هست.2-حالتی که اندازه رشته ورودی ما بین 6 تا 20 کاراکتر هست.3-حالتی که رشته ما بیش از 20 کاراکتر دارد.حالت اول و دوم بسیار ساده است.در حالت اول کافیست مقدار حداکثر بین تعداد محدودیت های ناشی از نوع حرف یا 6-len(s) را به خروجی برگردانیم.در حالت دوم نیز مقدار حداکثر بین محدودیت هر 3 حرف تکراری که باید اصلاح شوند یا محدودیت های نوع را به خروجی برمی گردانیم.حالت سوم که مشکل ترین، مرحله الگوریتم هست، می بایست به ازای هر حرف اضافه یک محدودیت اضافه در نظر بگیریم، که این محدودیت اضافه می‌تواند بر روی توالی های 3n، 3n+1 و 3n+2 تاثیر بگذارد.در خط 2 متغیرهای اصلی الگوریتم را تعریف کرده‌ایم:متغیر str_len جهت نگهداری اندازه رشته متنی ورودی با مقدار اولیه برابر طول رشته ورودی.متغیر change جهت نگهداری محدودیت تعداد کل زیررشته‌های سه حرفی تکراری پیوسته با مقدار اولیه برابر صفر.متغیر triple جهت نگهداری تعداد سه حرف تکراری پیوسته یک زیر رشته با مقدار اولیه برابر صفر.متغیر seq باقیمانده تقسیم بر 3 را نگهداری می‌کند، با مقدار اولیه برابر صفر.متغیر i اندیس رشته برای پیمایش با مقدار اولیه برابر صفر.متغیر length اندازه حروف یک زیر رشته تکراری پیمایش شده با مقدار اولیه برابر یک.متغیر delete تعداد حروف اضافی را نگهداری می‌کند، با مقدار اولیه برابر صفر.آرایه types یک آرایه با 4 عنصر هست، که عنصر اول آن را برای خروجی تابع get_missing_type بی ارزش تلقی کردیم، و عناصر آن را با یک مقدار دهی نموده ایم، که جمع سه عنصر اولیه برابر 3 محدودیت نوع ورودی است، که با یافتن هر حرفی که این محدودیت را از بین می‌رود اندیس مورد نظر را صفر می‌کنیم.در خط 3 تابع get_missing_type را تعریف نموده‌ایم که اندیس مورد نظر هر محدودیت نوع را برای آرایه types  به ما می‌دهد.در خط 4 یک حلقه برای پیمایش حروف رشته تعریف نموده‌ایم.خط 5 جهت به دست آوردن طول زیررشته تکراری پیوسته تعریف شده است.در خط 6 محدودیت نوع را چک می‌کنیم و هرجا که محدودیت بر طرف شد، پرچم 1 محدودیت نوع حرف را صفر می‌کنیم. دقت شود که وقتی حروف تکراری هست، چک کردن آخرین حرف مانند چک کردن تمام حروف تکراری ماقبل است.در خط 7 تعداد زیر رشته‌های 3 حرفی تکراری را شمارش کرده‌ایم.در خط 8 یک شرط گذاشته‌ایم، که اگر تعداد زیر رشته‌های 3 حرفی داشتیم. آن را به عنوان محدودیت تغییر به متغیر change اضافه کن، منتهی اگر حروف اضافی داشتیم باید تغییراتی در آن اعمال شود.در خط 10 مقدار  باقیمانده تقسیم بر 3 را برای زیر رشته‌های پیوسته با یک حرف تکراری به دست آورده‌ایم؛ اگر این باقیمانده برابر صفر بود و حداقل یک حرف اضافی داشتیم، یک واحد از مقدار محدودیت زیررشته‌های 3 حرفی تکراری کم و یک واحد نیز از حروف اضافی موقتی کم می‌کنیم. اگر نیز باقیمانده برابر یک بود، یک واحد از مقدار محدودیت زیررشته‌های 3 حرفی تکراری کم و دو واحد نیز از حروف اضافی موقتی کم می‌کنیم و در خط 18 کد، تعداد حروف اضافی باقیمانده نیز به ازای هر سه حرف یک واحد از مقدار محدودیت زیررشته‌های 3 حرفی تکراری کم می‌کنیم.در خط 16 مجموع محدودیت‌های نوع را به دست آورده‌ایم که حداکثر 3 می‌شود.در خط 21 اگر رشته ورودی ما بیشتر 20 حرف داشت، تعداد حروف اضافی که ایجاد محدودیت می‌کنند بعلاوه حداکثر بین محدودیت نوع و محدودیت‌های سه حرفی اصلاح شده جواب مسئله ما است.خط 22 اگر رشته ورودی ما بین 6 تا 20 حرف داشت، حداکثر بین محدودیت نوع و محدودیت‌های سه حرفی بدون نیاز به  اصلاح جواب مسئله ما است.خط 22  اگر رشته ورودی ما تا 5 حرف داشت حداکثر بین محدودیت نوع و تعداد حروفی که وارد نشده است، جواب مسئله است.یک نمونه از تحلیل الگوریتم فوق را در جدول زیر می توانید، مشاهده کنید: Hossein Siadati Hossein Siadati Mon, 22 Apr 2019 09:40:06 +0430 https://virgool.io/@s.h.siadaty/%D8%A7%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF%DB%8C-%DB%B4-%D9%85%D8%B3%D8%A7%D8%AD%D8%AA-%D9%85%D8%B1%D8%A8%D8%B9-%D9%85%D8%A7%DA%A9%D8%B2%DB%8C%D9%85%D9%85-%D8%B1%D8%A7-%D8%A8%DB%8C%D8%A7%D8%A8%DB%8C%D8%AF-srpi1vhbtwzr اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.یکی از مفیدترین روزهای کاری ام روزی بود که هزار خط برنامه را دور ریختم!دسترسی و حل سوال از منبع اصلیپرسش: یک ماتریس دوبعدی باینری (مقادیر عناصر صفر یا یک می باشند) داده شده است. مساحت بزرگتری مربعی در آن که تنها از 1 تشکیل شده است را بیابید.توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز 20 آوریلیادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.حل مسالهالگونورد برتر: الگونورد برتر الگونورد 4، کاربر با ای دی Iman و Tohid و Mahdi Dehghani هست.اولین فردی که الگوریتم رو نوشت مهدی بود اما برای نوشتن راه حل نتونست وقت بگذاره. بنابر این توحید و ایمان دست به دست هم دادن و شرح مساله را خیل زیبا نوشتن. من هم ویرایش کردم.به هر سه نفر تبریک می گم و می گم: عالی هستید! ادامه بدید!و حالا شرح پاسخ:برای حل مسئله با یک مثال شروع می کنیم تا مطمئن شویم که مسئله را درست درک کرده ایم.اگر ماتریس 5x6 زیر را در نظر بگیریم:در درون آن 12 مربع 1x1 (همه خانه های با مقدار 1)  و دو مربع 2x2 (.دو مربع آبی و سبز) مشاهده می کنیم. هیچ مربعی با اندازه بزرگتر وجود ندارد. بنابراین مساحت بزرگترین مربع 4 می باشد. این مثال و مشاهده ایده حل مسئله به ساده ترین روش یعنی جستجوی کامل را می دهد.برای جستجوی کامل در واقع باید تمام مربع های ممکن با اندازه های از 1 تا بزرگترین مربع ممکن (یعنی حداکثر اندازه کوچکترین ضلع ماتریس) را بسازیم. برای این منظور به ازای هر خانه A (یا خانه مرجع) که مقدارش 1 می باشد بزرگتری مربعی که A گوشه سمت راست-پایین آن (جنوب شرقی) قرار می گیرد را می سازیم. مثلا برای خانه سطر 3 و ستون 3 (که با ستاره مشخص شده است) بزرگترین مربع با رنگ آبی نشان داده شده است.گامهای این الگوریتم بصورت زیر است:گام اول: عنصر بعدی A از عناصر ماتریس که مقدار آن 1 می باشد را به عنوان خانه مرجع در نظر میگیریم. اگر چنین عنصری وجود نداشت به گام پنجم الگوریتم می رویم.گام دوم: از طول 2=L شروع می کنیم و بررسی می کنیم که آیا می توان مربعی با این اندازه درست کرد که A جنوب شرقی آن باشد.گام دوم: هر بار L را یک واحد افزایش می دهیم و دوباره بررسی می کنیم تا زمانی که دیگر نتوانیم مربع با اندازه L تشکیل دهیم. گام سوم: مقدار 1-L بزرگتری مربعی است که A جنوب شرقی اش قرار می گیرد .گام چهارم:‌ پاسخ به دست آمده را با اندازه بزرگترین مربعی که در کل به دست آمده مقایسه می کنیم. در صورت بزرگتر بودن از بزرگترین پاسخ به دست آمده، اندازه مربع اخیر را جایگزین می کنیم و بعد به گام اول می رویم.گام پنجم: بزرگتری مربع بدست آمده پاسخ صحیح می باشد..قطعه کد زیر الگوریتم جستجوی کامل را پیاده سازی می کند.اگر اندازه ماتریس MxN باشد، آنگاه پیچیدگی زمانی این الگوریتم ( O((MxN)^2 می باشد. پیچیدگی حافظه ای( O(1 می باشد.اشکال این روش آن است که محاسبات برای بدست آوردن اندازه بزرگترین مربع که A در سمت جنوب شرقش می باشد تکرار می کند. اما بر اساس مشاهده زیر می توان از تکرارهای محاسبه بیجا خودداری کرد. به عنوان مثال اگر ماتریس زیر به عنوان ماتریس ورودی باشد:و محاسبه اندازه بزرگتری مربع متشکل از 1 برای خانه ها از (0, 0) تا خانه (2, 2) محاسبه کرده باشیم، آنگاه می توانیم به صورت انتزاعی مربع های زیر را ببینیم:که در آن مربع سبز مربوط به بزرگتری مربع خانه شمال A، مربع قرمز مربوط به بزرگتری مربع خانه غرب A، و خانه نارنجی برای خانه شمال غرب A می باشد. همانطور که می توان دید:1- اندازه ضلع  بزرگترین مربع مربوط به A حداقل به اندازه کوچکترین ضلع مربوط به سه مربع دیگر است.2- اندازه ضلع بزرگترین مربع مربوط به A نمی تواند بزرگتر  از کوچکترین ضلع مربوط به سه مربع دیگر نمی تواند بزرگتر باشد.3- از 1 و 2 نتیجه میگیریم که بزرگترین ضلع مربوط به خانه A برابر است با مینیمم اندازه ضلع مربوط به سه مربع شمال، غرب، و شمال غربی.این نتیجه در واقع یک الگوریتم استقرایی را پیشنهاد می دهد که در آن مقدار عنصر (j, i) بر اساس محاسبات مربوط به خانه های (i-1, j) و (i, j-1) و (i-1, j-1) می تواند بر اساس فرمول ساده زیر محاسبه شود:dp[i, j] = min(dp[i-1, j], dp[i-1, j-1], dp[i, j-1])+1در فرمول فوق از اسم dp برای جدول جدیدی که محاسبات مربوط به بزرگترین مربع ممکن را در خود نگه می دارد استفاده کرده ایم. این اسم اختصار Dynamic Programming می باشد و یادآوری می کند که در ساختن آن از مفهوم برنامه نویسی پویا استفاده کرده ایم. مثال زیر یک ورودی و جدول تکمیل شده با روش الگوریتم استقرایی را نشان می دهد.Input:dp:با توجه با این الگوریتم، شروع به نوشتن برنامه می کنیم. ابتدا حالت خاص ماتریس خالی را بررسی می کنیم (خط 2). این کار برای این خوب است که از خطاهای احتمالی در ورودی پارامتر جلوگیری کنیم. سپس ابعاد ماتریس ورودی را بدست می آوریم (خط 3). آنگاه یک ماتریس کمکی به اسم dp در نظر می گیریم که قرار است اندازه بزرگترین مربع ممکن را در خود نگه دارد (خط 5). در این خط از یک ترفند استفاده شده است که نیاز به بررسی حالت خاص برای سطر اول و ستون اول نباشد. بنابر این یک سطر و ستون جعلی با مقادیر 0 در نظر می گیریم که نوشتن برنامه را سر راست کند. سپس بصورت سطری از بالای گوشه راست ماتریس اصلی شروع می کنیم و مقدار مربوط به عنصر dp متناظر آن را مطابق با فرمول استقرایی فوق محاسبه می کنیم (سطرهای 6 تا 10). نهایتا مقدار نهایی را به عنوان پاسخ بر می گردانیم. با توجه به اینکه همه عناصر ماتریس را یکبار برریس می کنیم، پیچیدگی زمانی این الگوریتم (O(MxN می باشد. پیچیدگی حافظه این الگوریتم( O(MxN می باشد.در این راه حل برای محاسبه سطر i  ام ما از مقدار عنصر قبلی و سطر i-1 ام استفاده می کردیم، بنابراین نیازی به ماتریس دو بعدی نداریم  و می توان مسئله را با یک بردار ستونی حل کرد.بردار dp خود را با صفر مقدار دهی می کنیم، همانگونه که عناصر ماتریس ورودی را به صورت ردیفی می خوانیم، درایه های ماتریس را با استفاده از فرمول زیر محاسبه می کنیم. برای هر ردیف prev به مقدار قدیمی dp[j- 1]ارجاع می دهد.dp[j]= min(dp[j-1], dp[j], prev)+1Input:dp:قطعه برنامه زیر پیاده سازی بهینه سازی شده الگوریتم بروش برنامه نویسی پویا می باشد.این روش میزان حافظه اجرایی را به سایز تعداد سطرهای ماتریس کاهش می دهد.دنباله خروجی زیر جزییات اجرای الگوریتم را نشان می دهد. Hossein Siadati Hossein Siadati Mon, 15 Apr 2019 04:38:50 +0430 https://virgool.io/@s.h.siadaty/%D8%A7%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF%DB%8C-%DB%B3-%DA%A9%D9%88%DA%86%DA%A9%D8%AA%D8%B1%DB%8C%D9%86-%D9%85%D8%A8%D9%86%D8%A7%DB%8C-%D8%AE%D9%88%D8%A8-%D8%B1%D8%A7-%D8%A8%DB%8C%D8%A7%D8%A8%DB%8C%D8%AF-tlqavpq270uv اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.دسترسی و حل سوال از منبع اصلیپرسش: برای یک عدد صحیح n، یک مبنای خوب k مبنایی است که همه ارقام عدد n در آن مبنا 1 باشد. برنامه ای بنویسید که یک رشته از ارقام را به عنوان n دریافت کند و کوچکتری مبنای خوب آن را برگرداند.مثال: برای عدد 'n='13 پاسخ `3` می باشد زیرا ۱۳ در مبنای ۳ برابر 111 می باشد.توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز 13 آوریلیادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.حل مسالهالگونورد برتر: الگونورد برتر الگونورد ۳، کاربر با ای دی Iman هست. ایشون درست و کامل مساله را حل کردن و تشریح راه حل رو نوشتند. تشریح حل مساله رو من در ویرایش و ساده سازی کردم.ایمان فراحی http://professionalProgrammer.ir یک برنامه نویسی فوق العاده است و ریاضی اش هم خیلی خوبه و می تونه هم مسایل رو فرمول کنه و هم پیاده سازی کنه!به Iman تبریک می گم و بهش می گم: عالی هستی! ادامه بده!و حالا شرح پاسخ:حل مساله را با یک مثال شروع میکنیم تا مطمئن شویم که مسئله را خوب درک کرده ایم. برای ورودی n=13 در مبنای  10، می توانیم آن را در مبناهای دیگر در نظر بگیریم. کوچکترین مبنای ممکن 2 می باشد. نمایش 13 در مبنای 2 به صورت 1101، و در مبنای 3 بصورت 111 می باشد. در این روند، با توجه به اینکه مبنای 3 اولین مبنایی است که تبدیل 13 به آن تنها شامل 1 می باشد، 3 جواب درست می باشد. بعنوان مثال دیگر، برای n=12 تبدیل آن به مبناهای دیگر را از مبنای 2 تا یافتن عددی متشکل از تنها 1 نشان می دهیم:1100, 110, 30, 22, 20, 15, 14, 13, 12, 11اولین مبنا که در آن 12 تنها از 1 تشکیل می شود مبنای 11 است. بنابراین پاسخ 11 می باشد. با این مثال همچنان متوجه می شویم که نمایش عدد 12 در مبنای 1-12=11 تنها شامل رقم 1 می باشد. اگر دقیق تر نگاه کنیم، نمایش هر عدد n در مبنای n-1 بصورت 11 می باشد. بنابراین برای هر ورودی n ، این مسئله یک پاسخ دارد که عددی است بین 2 تا n-1.شناسایی مسئله در قالب این مثالها کمک می کند که ساده ترین الگوریتم، یعنی جستجوی کامل را ارائه نماییم. در این روش از مبنای دو شروع می کنیم و برای مبناها حداکثر تا مبنای n-1 مقدار عدد داده شده n رو توی اونها بدست می آوریم. هر وقت به یک عدد با همه ارقام 1 رسیدیم آن مبنا را به عنوان حاصل برمی گردونیم. در این روش n-2 (در بدترین حالت) مبنا برای یک عدد حساب می شود که برای محاسبه هر کدام (log(n محاسبه لازم است، زیرا سقف لگاریتم x در مبنای 2 برابر طول رشته اعداد ما در مبنای 2 (بدترین حالت) است.. بنابر این پیچیدگی کل این الگوریتم (O(log(n)*n می باشد.مشکل این روش آن است که  باید معادل عدد داده شده را در همه 2-n مبنا بین 2 تا 1-n محاسبه کند در حالی که تنها log(n)-1 رشته ممکن به عنوان نمایش عدد در مبنایی که پاسخ مسئله هست  وجود دارد. بعنوان مثال، نمایش های مرتبط معادل 12 شامل 1111، 111 و 11 می باشند.این مشاهده جرقه ارائه راه سریع تری برای حل این مسئله است.  در واقع باید از طولانی ترین نمایش محتمل برای عدد n که شامل تنها 1 باشد شروع کنیم. برای هر چنین نمایشی باید بررسی کنیم که آیا مبنایی وجود دارد که این نمایش در آن معادل با مقدار n باشد. این کار را تا  کوتاهترین نمایش محتمل عدد n که شامل تنها 1 می باشد (یعنی "11") ادامه می دهیم. بنابر این اولین نمایش متشکل از تنها 1 که مبنایی برای آن یافت شود پاسخ مسئله می باشد.به عنوان مثال، برای یافتن پاسخ برای عدد 12 باید از طولانی ترین نمایش محتمل آن یعنی 1111 شروع کنیم. تعداد ارقام مربوط به طولانی ترین رشته احتمالی از 1 ها، سقف لگاریتم 12  در مبنای 2 می باشد. یک روش برای بررسی اینکه آیا مبنایی وجود دارد که در آن مقدار 1111 برابر 12 شود آن است که از مبنای 2 شروع کنیم و عدد 1111 را به آن مبناها محاسبه کنیم. در این صورت، با محاسبه 1111 در مبنای 2 به مقدار 15 میرسیم که از عدد 12 بیشتر است. مطمئنا تبدیل 1111 به مبناهای بزرگتر عدد بزرگتری را تولید خواهد کرد. به این دلیل نتیجه می گیریم که هیچ مبنایی وجود ندارد که در آن 1111 معادل عدد 12 شود. با اندکی تامل متوجه می شویم که اگر برای طول رشته m+1 متشکل از تنها ارقام 1 مبنای k ای وجود داشته باشد که برابر n شود، خاصیت زیر برای آن صادق است:بر اساس فرمول اصلی، مشاهده می کنیم که:همچنیندر نتیجه نامساوی زیر برقرار است:اگر از طرفین ریشه m ام بگیریم خواهیم داشت:بنابر این ریشه mام n بین دو عدد متوالی k و k+1 قرار می گیرد. در نتیجه خواهیم داشت:نتیجه اصلی این است که اگر برای رشته با m رقم 1 مبنای k ای وجود داشته باشد که در آن مقدار رشته معادل n شود، آن مبنا برابر است با ریشه m ام مقدار n.می توانیم الگوریتم را با همین مشاهده بصورت زیر پیاده سازی نماییم.ابتدا رشته ورودی عددی را به عدد تبدیل می کنیم (خط 3). سپس در یک حلقه کاهشی از رشته با حداکثر طول تا رشته با طول 2 (مربوط به رشته در مبنای n-1)  متشکل از رقم 1 محاسبات زیر را تکرار می کنیم (خط 4 تا 7). برای هرچنین رشته ای مبنای k که گزینه ممکن برای تبدیل احتمالی آن به n در مبنای 10 هست را بدست می آوریم (خط 5). آنگاه محاسبه می کنیم که آیا رشته در مبنای k  واقعا معادل n در مبنای 10 می باشد؟ (خط 6).برای این کار از عبارت سمت راست فرمول اصلی استفاده می کنیم. اگر رشته به طول m متشکل از تنها 1 در مبنای k معادل n در مبنای 10 شد، آنگاه مقدار k پاسخ مورد نظر است.در الگوریتم ارایه شده، برای هر m باید مقدار k را بدست آوریم و سپس بررسی کنیم که آیا رشته متشکل از m تا رقم 1 برابر با n  می شود. برای این کار باید رشته را طبق عبارت سمت راست فرمول اصلی تبدیل به مبنای 10 کنیم که زمان بر است. اما یک مشاهده کمک می کند که این محاسبه را تسریع کنیم. عبارت سمت راست فرمول اصلی در واقع یک دنباله هندسی است. با استفاده از فرمول جمع دنباله هندسی خواهیم داشت:بنابر این تبدیل رشته با تمام ارقام 1 به راحتی با استفاده از فرمول فوق انجام می شود.با جایگزینی فرمول بالا در خط 6 برنامه خواهیم داشت:با توجه به اینک در الگوریتم فوق یک حلقه تکرار داریم که (log(n بار تکرار می شود، درنتیجه پیچیدگی محاسباتی این الگوریتم ((O(log(n می باشد. Hossein Siadati Hossein Siadati Sun, 07 Apr 2019 20:58:27 +0430 https://virgool.io/coderlife/%D8%A7%D9%8E%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF%DB%8C-%DB%B2-%D8%A8%D8%A7%D8%B2%D9%87-%D9%87%D8%A7-%D8%B1%D8%A7-%D8%A8%D8%A7-%D9%87%D9%85-%D8%AA%D8%B1%DA%A9%DB%8C%D8%A8-%DA%A9%D9%86%DB%8C%D8%AF-cairxvmg3dal اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.کد بد را کامنت گذاری نکنید. باز نویسی کنید!دسترسی و حل سوال از منبع اصلیسوال: تعدادی بازه داده شده اند. بازه هایی که همپوشانی دارند را ترکیب کنید.مثال: اگر بازه های [5, 3] و [6, 4] و [0, 2-] داده شده باشند، برنامه باید [6, 3] و [0, 2-] را برگرداند. توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز 6 آوریلیادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.حل مسالهالگونورد برتر: الگونورد برتر الگونورد ۲، کاربر با ای دی alireza.sharifianzadeh هست. ایشون درست و کامل مساله را حل کردن و خلاصه راه حل رو نوشتند. تشریح حل مساله رو من در نقاط بسیاری ویرایش کردم.به alireza.sharifianzadeh تبریک می گم و بهش می گم: خیلی خوبی! ادامه بده!و حالا شرح پاسخ:پاسخ: حل مسئله با یک مثال شروع میکنیم تا مطمئن شویم که مسئله را فهمیده ایم. مثلا اگر سه بازه [5, 3] و [6, 4] و [0, 2-] داده شده باشند، آنگاه بازه های [5, 3] و [4, 6] که همپوشانی دارند را باید با هم ترکیب کنیم تا بازه جدید [6, 3] بوجود آید. از آنجا که این بازه جدید و بازه [0, 2-] همپوشانی ندارند نمی توانند با هم ترکیب شوند.  نهایتا برنامه باید [6, 3] و [0, 2-] را برگرداند.ارائه راه حل را از روش جستجوی کامل شروع می کنیم. در این روش هر بازه را به بازه های دیگر مقایسه می کنیم و اگر همپوشانی دارند آنها را با هم ترکیب کرده و یک بازه جدید ایجاد می کنیم. این بازه جدید را جایگزین دو بازه های که آن را بوجود آورده اند می کنیم. بنابر این برای هر بازه باید همپوشانی آن با تمام بازه های دیگر را بررسی کنیم. این کار با استفاده از دو حلقه تو در تو قابل انجام است، به این صورت که حلقه ی بیرونی، عناصر را پیمایش می‌کنه و حلقه داخلی عنصر جاری رو با بازه های دیگر مقایسه می‌کنه و درصورت امکان آنها را با هم ترکیب می کند . پیچیدگی محاسباتی این الگوریتم (O(n^2 می باشد.اشکال این روش آن است که همه بازه هایی نمی توانند با هم ترکیب شوند را نیز با هم مقایسه می کند. همچنین، نمی تواند یک بازه را بصورت کامل و تنها با یک پیمایش بسازد. به عنوان مثال اگر بازه های [6, 3] [4, 0] [7, 5] را از چپ به راست در نظر بگیریم و شروع به ترکیب بازه ها کنیم، آنگاه در نگاه اول بازه [7, 5] و [4, 0] با هم ترکیب نمی شوند. اما وقتی که ]7, 5] را با [6, 3] را با هم ترکیب کنیم و به بازه [7, 3] برسیم. تنها در دور ترکیب بازه هاست که متوجه می شویم که [4, 0] هم می توانست با این دو بازه ترکیب شود و بازه نهایی [7, 0] را بوجود آورد. تامل در این نکته که چرا ترکیب برای بازه اول و سوم اتفاق افتاد اما برای بار دوم اتفاق نیفتاد کلید ارائه یک الگوریتم با سرعت بالاتر است.در واقع اگر این سه بازه بصورت [7, 5] [6, 3]  [4, 0] بودند آنگاه تنها یک دور پیمایش لیست بازه ها برای تشکیل بازه های ترکیبی جدید کافی بود. این برای هر تعداد بازه متوالی که بر اساس مقدار شروع بازه مرتب شده باشند صادق است. در واقع چنانچه قبل از انجام عملیات ترکیب، بازه ها را  بر اساس مقدار شروع بازه ( start) مرتب کنیم، دیگر لازم نیست هر بازه با همه ی بازه های دیگه مقایسه کنیم زیرا:مقدار end هر بازه از مقدار start در همون بازه بزرگتر استمقدار start هر بازه از مقدار start بازه ی قبلی قطعا بزرگتر استدرنتیجه قطعا مقدار end هر بازه از مقدار start بازه قبلی کوچکتر است و می توانیم به این نتیجه برسیم که در صورت مرتب بودن بازه ها، اگر بازه ای با بازه ی بعدی خودش هم پوشانی نداشت، قطعا با بازه های بعد تراز اون نیز هم پوشانی نخواهد داشت.پس شرط همپوشانی ساده می شود به این صورت که:current.start <= prev.endبا این ترتیب شروع به نوشتن برنامه می کنیم و همزمان خطوط برنامه را توضیح می دهیم. ابتدا لیست رو بر اساس مقدار start هر بازه مرتب می‌کنیم (خط 2).  سپس یک لیست خالی (result) برای بازه های ترکیب شده در نظر میگیریم (خط 3). در یک حلقه تکرار هر عنصر را با آخرین عنصر لیست بازه های ترکیبی (list) مقایسه می‌کنیم. در صورتی که عنصر کنونی با آخرین عنصر لیست بازه های ترکیبی همپوشانی داشته باشد، آندو را با بروز رسانی انتهای آخرین بازه ترکیبی، با هم ترکیب می کنیم (خط 5 و 6).چون عنصر اول لازم نیست با عنصر قبلی مقایسه شود مستقیما داخل result قرار می‌گیرد.و در صورتی که هم پوشانی وجود نداشته باشد، به این معناست که این عنصر با هیچ عنصر دیگه ای در آرایه همپوشانی نداره، پس این عنصر رو به پاسخ اضافه می‌کنیم (خط 8). در انتهای لیست ترکیبی جدید را به عنوان پاسخ برمی گردانیم.الگوریتم فوق دارای یک حلقه تکرار است که تنها یک بار عناصر لیست را پیمایش می کند. یک اشتباه رایج آن است که پیچیدگی محاسباتی این الگوریتم را (O(n ارزیابی نماییم. اما نکته مهم آن است که ابتدا باید لیست را مرتب نماییم که خود دارای پیچیدگی محاسباتی ((O(n*log(n می باشد. بنابر این پیچیدگی محاسباتی الگوریتم نیز ((O(n*log(n می باشد.یک پیاده سازی دیگر این الگوریتم که با توضیح روش مرتب کن و ترکیب کن سازگارتر است در زیر ارایه شده است. حلقه داخلی (خط 7 تا 10) تا جایی ادامه می یابد که دنباله ای از همه بازه های قابل ترکیب را با هم ترکیب کند و یک بازه جدید ترکیبی بسازد. Hossein Siadati Hossein Siadati Mon, 01 Apr 2019 04:47:28 +0430 https://virgool.io/@s.h.siadaty/%D8%A7%D9%8E%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF%DB%8C-%DB%B1-%D8%B2%DB%8C%D8%B1-%D8%A2%D8%B1%D8%A7%DB%8C%D9%87-%D8%A8%D8%A7-%D9%85%D8%AC%D9%85%D9%88%D8%B9-%D9%85%D8%A7%DA%A9%D8%B2%DB%8C%D9%85%D9%85-%D8%B1%D8%A7-%D8%A8%DB%8C%D8%A7%D8%A8%DB%8C%D8%AF-o2b85zt8x2jp اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.قانون اول الگونوردی: با ترس خود رودر رو شوید!گروه الگونوردی قوانینی دارد. قانون اول الگونوردی آن است که باید با ترس خود رودر رو شوید. آدمی از نقطه ضعف هایش می ترسد. الگو نوردان انسانهای با شهامتی هستند. بجای اینکه بگذارند که یک تکنیک الگوریتمی آنها را از پادرآورد، در تمرینات خود روی نقطه ضعف خود تمرکز می کنند. آنقدر تمرین می کنند که نقطه ضعفشان به نقطه قوتشان تبدیل شود. بله، مثلا داینامیک پروگرمینگ خودمان بر بدن خیلی ها لرزه می اندازه. این هفته می خواهیم با این ترس رو برو شویم و تمرین کنیم تا اندکی خود را قوی تر کنیم. این هفته را خوب دوام بیاورید. قول می دهم دیگر از داینامیک پروگرمینگ یا هیچ مساله دیگری نترسید!دسترسی و حل سوال از منبع اصلیپرسش: یک آرایه از اعداد صحیح داده شده است. برنامه ای بنویسید که زیر آرایه پیوسته ای (با حداقل یک عنصر) که مجموع مقادیرش (sum) ماکزیمم هست را بیابد و sum را برگرداند.مثال: اگر لیست [1, 1-, 2-, 5, 7-, 2] داده شود، باید مقدار 5 را برگرداند. زیر آرایه [5] ماکزیمم است.توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۸۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.زمان بندی: ارسال پاسخ ها تا پایان روز ۳۰ مارچیادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.حل مسالهالگونورد برتر: الگونورد برتر الگونورد 1، کاربر با ای دی Iman هست. ایشون درست و کامل مساله را حل کردن و تشریح راه حل رو نوشتند. تشریح حل مساله رو من در نقاطی ویرایش و ساده سازی کردم.به Iman تبریک می گم و بهش می گم: خیلی خوبی! ادامه بده!و حالا شرح پاسخ:حل مسئله را با یک مثال ساده شروع می‌کنیم تا مطمئن شویم که مسئله را به خوبی متوجه شده‌ایم. فرض کنید یک آرایه حاوی 4 عضو داریم به صورت زیر:A=[3, -2, 5, -1]می خواهیم مجموع زیر آرایه به هم پیوسته از آرایه A را بیابیم به گونه‌ای که مجموع عناصر آن از مجموع مرتبط با سایر زیر آرایه‌ها بیشتر باشد (مقدار ماکزیمم). شروع زیر آرایه می‌تواند از هر یک از اندیس های 0 تا n-1 و انتهای آن نیز مربوط به هریک از عناصر بعد آن در آرایه باشد. بنابراین تعداد کل این زیرآرایه‌های پیوسته برابر با n*(n+1)/2  که در آن n تعداد عناصر آرایه هست. به عنوان مثال، تعداد 10 زیرآرایه‌ پیوسته برای A  وجود دارند که در زیر به همراه مجموع عناصر هر یک نشان داده شده اند:[3]=>S[0]=3 [3,-2]=>S[1]=1 [3,-2, 5]=>S[2]=6 [3, -2, 5, -1]=>S[3]=5 [-2]=>S[4]=-2 [-2,5]=>S[5]=3 [-2,5,-1 ]=>S[6]=2 [5]=>S[7]=5 [5,-1 ] =>S[8]=4[-1]=>S[9]=-1 ماکزیمم برابر 6 برای رشته [S[2 می‌باشد، که اندیس شروع عنصر اول آن برابرi=0 و اندیس عنصر پایانی آن  j=2 می‌باشد. ارائه الگوریتم برای حل این مساله را از الگوریتم جستجوی کامل شروع می‌کنیم. روش‌ جستجوی کامل همه زیر آرایه‌های پیوسته ممکن را تشکیل می‌دهد. برای این کار می‌توانیم یک متغیر i برای حلقه بیرونی (جهت دسترسی به عناصر به ابتدای زیر آرایه) و یک متغیر j برای حلقه میانی (جهت انتخاب عنصر پایان زیر آرایه) و یک متغیر k برای حلقه داخلی جهت پیمایش عناصر زیر آرایه پیوسته از i تا j در نظر می گیریم. حاصل جمع عناصر زیر آرایه را در متغیر s می گذاریم. در واقع برای هر زیر آرایه، s مجموع تمام عناصر در زیر آرایه را در خود نگه می‌دارد. پس از محاسبه مجموع زیر آرایه اگر s بزرگتر از ماکزیممی باشد که تا بحال بدست آمده است، آن را جایگزین ماکزیمم کنونی می‌کنیم. به این دلیل که دو حلقه تکرار داریم و هر بار باید مجموع تمام عناصر زیر آرایه را محاسبه کنیم، مرتبه اجرایی الگوریتم (O(n^3خواهد بود. مشکل این روش این است که در هر تکرار حلقه میانی، مجموع زیر آرایه جدید (یعنی از i تا j جدید) را با استفاده از حلقه داخلی، از نو شروع می کنیم. در حالی که زیر آرایه جدید تنها یک عنصر از زیر آرایه قبلی بیشتر دارد. بنابر این می توان با استفاده از مجموع زیر آرایه قبلی (یعنی i تا j-1 ) و افزودن مقدار عنصر j ام، مجموع زیر آرایه جدید یعنی از i تا j  را محاسبه نمود. به این ترتیب، عملا نیاز به حلقه داخلی نیست. در نتیجه مرتبه اجرایی الگوریتم جدید به (O(n^2 کاهش خواهد یافت. قطعه کد زیر پیاده سازی الگوریتم بهینه شده جستجوی کامل را نشان می دهد.اشکال روش جستجوی کامل آن است که محاسبات اضافی انجام می دهد. متاسفانه نحوه فرمول کردن راه حل بصورت جستجوی کامل، غیر از بهینه سازی ای که ذکر شد، اجازه نمی دهد که نتایج بعدی را از روی نتایج قبلی بسازیم. برای یافتن روش بهتر، باید دیدگاه خاصی را در ذهن خود پرورش بدهیم که اجازه می دهد راه حل جدید را بدهد.این نگاه خاص 'روش تفکر استقرایی' است.در این مساله تفکر استقرایی به این معناست که:اگر فرض کنیم که راه حل را برای یک آرایه i عنصری بدانیم، چگونه می توانیم راه حل را برای آرایه i+1 عنصری (ایجاد شده با افزودن یک عنصر به انتهای آرایه i عنصری) بیابیم؟یک نگاه خاص تر استقرایی آن است که:اگر فرض کنیم که زیرآرایه با مجموع ماکزیمم که به عنصر i ام ختم می شود را بدانیم، چگونه می توانیم زیرآرایه با مجموع ماکزیمم تا عنصرi+1 ام را محاسبه کنیم؟به عبارت دقیق تر، اگر از روی آرایه اصلی A داده شده آرایه جدید L را بگونه ای بسازیم که عنصر i ام آن مجموع زیرآرایه‌ با مجموع ماکزیمم که به عنصر i ام ختم می شود را در خود ذخیره کند، آنگاه چگونه می توانیم مقدار عنصر i+1 ام را از روی عنصر i ام بیابیم؟ با فرض اینکه زیر آرایه با مجموع ماکزیمم خاتمه یافته به عنصر i ام را می دانیم (یعنی [L[i)، ممکن است دو حالت زیربرای Li+1 بوجود آید:مقدار [A[i+1از مجموع محاسبه شده تا عنصر i ام (یعنی [L[i) بزرگتر است. بنابر این [L[i+1برابر با [A[i+1خواهد بود.مقدار [A[i+1از مجموع محاسبه شده تا عنصر i ام کوچکتر است. بنابر این [L[i+1برابر با [L[i]+A[i+1خواهد بود.  به عبارت دیگر، با در نظر گرفتم ]L[0]=A[0 , فرمول محاسبه مقدار زیر آرایه ماکزییم که بعنصر iام (i > 1) ختم می شود به این صورت است:L[i+1]=max⁡(A[i+1], A[i+1]+L[i])با اجرای استقرای گفته شده روی مثال آرایه A که در بالا داده شد، مقادیر زیر یکی بعد از دیگری محاسبه می شوند:مقدار دهی اولیه:[3]=>L[0]=3و بر این اساس مقادیر بعدی به این صورت خواهند بود:[3, -2]=>L[1]=max(-2,-2+3) =1[3, -2, 5]=>L[2]=max(5,5+1) =6[3, -2, 5, -1]=>L[3]=max(-1,-1+6) =5پاسخ روش استقرایی با روش جستجوی کامل همخوانی دارد. با توجه به این که در این روش تنها یکبار لیست A را پیمایش می کنیم و هر بار مقدار ماکزیمم را محاسبه می کنیم، پیچیدگی محاسباتی این الگوریتم (O(n می باشد.بر این اساس، شروع به پیاده سازی الگوریتم می کنیم. به خاطر داشته باشید که در زمان مصاحبه، خطوط برنامه را بصورت همزمان برای مصاحبه کننده توضیح می دهیم. در سطر 1 تابع maxSubArray یک آرایه حاوی اعداد دریافت می‌کند.در سطر 2 دو متغیر تعریف شده که متغیر local_max همان Li و متغیر global_max که ماکزیمم کل کنونی دا در خود نگه می دارد را مقدار دهی اولیه می کنیم. در سطر 3 یک حلقه از عنصر دوم آرایه تعریف شده است. در سطر 4 و 5 فرض استقراء تعریف شده است.و در سطر 6 مقدار sum که همان بیشینه سراسری است، بازگشت داده شده است.شاید برای شما شگفت آور باشد، اما به این سادگی اولین سوال برنامه نویسی پویا را حل کردید. تفکر استقرایی قلب برنامه نویسی پویاست. سعی کنید آن را در ذهن خوب بپرورانید. Hossein Siadati Hossein Siadati Sun, 24 Mar 2019 17:06:38 +0430 https://virgool.io/@s.h.siadaty/%D8%A7%D9%84%DA%AF%D9%88%D9%86%D9%8E%D9%88%D9%8E%D8%B1%D8%AF-%D8%AA%D9%85%D8%B1%DB%8C%D9%86-%D8%AC%D9%85%D8%B9%DB%8C-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%86%D9%88%DB%8C%D8%B3%DB%8C-kahja7zeyaeh مهارت برنامه نویسی را بجز با تمرین نمی توان کسب کرد و بدون تمرین حل مسایل الگوریتمی نمی توان برنامه نویسی خوبی شد. بی تعارف!از سوی دیگر شاید خیلی ها دسترسی به یک مربی-راهنما-پایه (یا هرچه اسمش را می گذارید) برای دل دادن به این کار ندارند. بخصوص که آدم جاهایی گیر می کند و نیاز به یک راه بلد دارد.هِچ عیبی ندارد. من راهبَلَد الگوریتمی شما هستم.برای اینکه این کار مقیاس پذیر و قابل مدیریت باشد، دوست دارم یک حرکت الگونَوَردی را با شما شروع می کنم. خیلی شبیه به کوهنوردی دسته جمعی که یک راهنما دارد و تعدادی علاقه مند پایه هم در کوهها حرکت می کنند، در الگونَوَردی من راهنما خواهم بود و هرفرد دیگری که علاقه مند هست می تواند به این حرکت بپیوندد تا یک پیمایش زیبا در فضای الگوریتم ها داشته باشیم. بی تعارف اگر زیباتر از کوهنوردی نباشد، شوق و هیجان آن را دارد. با این کار ماهیچه های برنامه نویسی و حل مساله خود را قوی می کنید. برنامه الگونَوَردی۱- هر هفته یک سوال الگوریتمی مشخص می کنم. معمولا این سوال را تا انتهای روز یکشنبه هر هفته در یک پست جدید در ویرگول قرار خواهم داد.۲- الگونَوَردان عزیز شروع به حل مساله می کنند و پاسخ های خود را همراه با شرح کوتاهی در قسمت 'پاسخ' ها زیر پست ویرگول می گذارند. برای این کار تا انتهای روز شنبه وقت دارید.۳- من اولین پاسخ کامل را انتخاب می کنم.۴- یک فایل گوگل داک تشکیل می دهم و فردی که بهترین پاسخ را نوشته دعوت می کنم که با هم شرح مبسوط حل را مشابه روش حل مسایل در مجموع پست های گذشته یا کتاب آمادگی برای مصاحبه های برنامه نویسی به سبک شرکت های بزرگ دنیا بنویسیم.۵- در انتهای روز یکشنبه تشریح حل مساله را با ذکر نامه الگونَوَرد برتر هفته روی ویرگول می گذاریم.اگر علاقه مندید که به جمع الگونوردی بپیوندید، لطفا زیر این پست یک پیغام بگذارید.الگونوردی ۲ حل نشده! شما حل کنید! الگونوردی ۱ حل شد توسط Iman Hossein Siadati Hossein Siadati Sat, 23 Mar 2019 17:21:07 +0430 https://virgool.io/ketabaz/%DA%A9%D8%AA%D8%A7%D8%A8-%D8%A8%D8%B1%D9%86%D8%A7%D9%85%D9%87-%D9%86%D9%88%DB%8C%D8%B3%DB%8C-%D9%87%D8%AF%DB%8C%D9%87-%D8%B9%DB%8C%D8%AF-%D9%86%D9%88%D8%B1%D9%88%D8%B2-%D9%88-%D8%B1%D9%88%D8%B2-%D9%BE%D8%AF%D8%B1-j7dy690luhat از این لینک دانلود کنید!توجه: لطفا اشکالات نوشتاری و الگوریتمی رو با یک ایمیل به آدرس s.h.siadaty@gmail.com بفرستید تا در نسخه بعدی اصلاح کنم. حتما با ذکر اسم در کتاب از فردی که هر اشکال رو برای اولین بار گزارش کنه قدردانی خواهد شد. لطفا شماره صفحه و حتی المقدور شماره خط نیز ذکر شود که بتوانم محل اشکال را به راحتی پیدا کنم.هدیه چیز خوبی است! دلها را به هم نزدیک می کند. هدیه می تواند به سادگی یک لبخند و احوال پرسی یا به وضوح یک اسکناس باشد. در دنیای امروز دانش و اطلاعات پولی است که سخت می توان برای آن قیمتی گذاشت.در آستانه ساله جدید، من برای شما برنامه نویس ایرانی هدیه ای دارم و آن کتابی است که کمک می کند مهارت های برنامه نویسی خود را افزایش دهید، به استانداردهای جهانی نزدیک تر کنید، و با اماده شدن برای مصاحبه های برنامه نویسی، احتمالا بتوانید شغلی با درامد بهتر بیابید. امیدوارم این کتاب قدمی موثر در پرورش برنامه نویسانی باشد که بتوانند نرم افزارهای بیشتر و بهتری جهت کسب و کار و بهبود کیفیت زندگی در ایران و جهان بسازند.راستش را بخواهید چندین انگیزه شخصی نیز برای نوشتن این کتاب دارم. یکی از آنها توصیه پدرم، در سفر اخیرم به ایران، به اینکه خدمت موثری برای آموزش در کشور انجام دهم. البته که خیلی از اساتید و بزرگان در این راستا کارهای برجسته ای انجام داده اند اما کار آنها چیزی از وظیفه من نمی کاهد. بنابر این تصمیم گرفتم اولین گام را هرچند کوچک در این راستا بردارم. از قضا امروز روز پدر نیز هست. با خود فکر کردم که این کتاب بهترین هدیه به پدرم خواهد بود. راستش خبر اتمام نوشتن کتاب را پشت تلفن به او گفتم و خیلی ذوق کرد و خوشحال شد. این کتاب را تقدیم می کنم به پدر خودم و همه پدرهای خوب و مهربان ایرانی! بخش بزرگی از این کتاب را در قالب پستهای متعددی در سایت ویرگول منتشر کرده ام. نسخه پی دی اف نسخه اول این کتاب که شامل همه آن مطالب بعلاوه مقدمه ای کوتاه در مورد ساختمان های داده در ابتدای هر فصل هست را می توانید از لینک زیر دانلود کنید.دانلود کنید.این کتاب بصورت رایگان عرضه می شود. اگر از این کتاب خوشتان آمد لطفا به دیگران معرفی کنید. پیشاپیش عید را به شما و خانواده محترمان تبریک می گویم و امیدوارم که سالی پر از موفقیت و شادی پیش رو داشته باشید. آخرین روز سال ۹۷ -- به امید دیدار مجدد در سال ۹۸ Hossein Siadati Hossein Siadati Wed, 20 Mar 2019 23:21:29 +0330 https://virgool.io/@s.h.siadaty/%DB%8C%DA%A9-%DA%A9%D9%84%D9%85%D9%87-%D8%B1%D8%A7-%D8%AF%D8%B1-%D8%AC%D8%AF%D9%88%D9%84%DB%8C-%D8%A7%D8%B2-%D8%AD%D8%B1%D9%88%D9%81-%D8%A8%DB%8C%D8%A7%D8%A8%DB%8C%D8%AF-wg3qafen41n9 پرسش: یک جدول از حروف و یک کلمه کلیدی داریم. الگوریتمی بنویسید که مشخص کنید آیا کلمه کلیدی در جدول وجود دارد بگونه ای که حروف آن در جدول مجاور باشند. دو حرف مجاورند اگر بالا، راست، پایین، یا سمت چپ یکدیگر باشند. نمی توانیم از یک حرف در یک نقطه از جدول دوبار استفاده کنیم.پاسخ: برای درک بهتر مساله حل آن را با یک مثال شروع می کنیم. اگر کلمه کلیدی Faces و جدول زیر را داشته باشیم، آنگاه الگوریتم باید مقدار True را برگرداند زیرا می توان کلمه Faces را از کنار هم گذاشتن حروف مجاور جدول (همانطور که با رنگ مشخص شده است) ساخت.مثالی از جدول کلمات و کلمه ای که با دنبال آن هستیمابتدا الگوریتم جستجوی کامل را مطرح می کنیم. برای این پرسش الگوریتم جستجوی کامل شامل ایجاد همه کلمات ممکن متشکل از حروف مجاور را بسازیم. اگر کلمه کلیدی میان کلمات تولید شده باشد آنگاه مقدار True را برمی گردانیم. برای ساختن تمام کلمات متشکل از حروف مجاور در جدول باید از هر نقطه جدول شروع کنیم و به 4 جهت بالا، پایین، راست، و چپ حرکت کنیم. در حرکت به هر سمت به خانه جدیدی از جدول می رسیم. باید حرکت به بالا و پایین، راست و چپ بگونه ای انجام دهیم که به خانه قبلی برنگردیم. این کار را تا زمانی انجام می دهیم که به طول کلمه ایجاد شده معادل طول کلمه کلیدی باشد. پس از ایجاد یک کلمه آن را با کلمه کلیدی مقایسه می کنیم. این روش را می توانیم با مقایسه تدریجی حروف کلمه ایجاد شده با کلمه کلیدی تسریع کنیم. با این صورت که خانه اول را با حرف اول کلمه کلیدی مقایسه می کنیم. چنانچه برابر نبودند عمل ایجاد کلمات از آن خانه را ادامه نمی دهیم. بنظر می رسد که راه حلی جز پیمایش کل ماتریس به این روش نداریم. اما چیزی که این بین کمک می کند راه حل را بهتر درک کنیم در نظر گرفتن مشابهت ارتباط بین خانه های جدول و یک گراف است. در واقع هر خانه جدول یک گره در گراف است و به گره هایی که در سمت راست، چپ، بالا، و پایین آن هستند متصل می شوند. بنابر این الگوریتم تعریف شده در واقع یک جستجوی عمقی در گراف از هر گره آن می باشد. برای پیاده سازی نیاز به ساختن گره ها و اتصالات آنها به روش مرسوم ساخت گراف نمی باشد. شماره سطر ستون یک خانه از جدول برای یافتن گره هایی که در گراف همسایه هستند استفاده می شوند.بنابر این شروع به پیاده سازی برنامه می کنیم. ابتدا نام تابع و پارامترهای مناسب را تعریف می کنیم (خط 1). سپس تعداد سطر و ستون جدول را در متغیر هایی می گذاریم که بعدا بتوانیم راحت از آنها استفاده کنیم (خط 2 و 3). به دلیل مشابه طول کلمه کلیدی را در متغیری می گذاریم (خط 4). سپس یک ماتریس به عنوان سایه ماتریس اصلی با مقادیر اولیه False برای همه خانه های می سازیم (خط 5 و 6). در ادامه پیاده سازی با تغییر مقدار خانه های این جدول به True از استفاده مجدد یک حرف در ایجاد یک کلمه جلوگیری می کنیم. برای فرمول کردن حرکت به راست، چپ، بالا، و پایین از یک لیست از لیست ها استفاده می کنیم (خط 7). هر عنصر لیست دارای دو عنصر است که اولین عنصر میزان حرکت در سطر و دومی در ستون را برای رسیدن به عنصر مجاور مناسب نشان می دهد. تابع داخلی dfs در واقع از خانه (i , j)جدول شروع به یافتن ادامه کلمه کلیدی (از اندیس seq به بعد) می کند (خط 9). قبل از تشریح داخل این تابع سراغ مابقی سطرهای برنامه می کنیم. خط 25 تا 28 در دو حلقه تکرار تو در تو ماتریس را می پیماید و امتحان می کند که آیا می توان کلمه کلیدی را از یک خانه ماتریس ساخت. برای تشخیص این امر هر بار تابع داخلی را فراخوانی می کند (خط 27). حال به تشریح تابع داخلی ادامه می دهیم. این یک تابع بازگشتی است و خود را فراخوانی می کند تا جایی که با انتهای کلمه کلیدی نرسیده ایم و همچنان حروف جدول در مسیر پیموده شده با حروف کلمه کلیدی برابرند. به این دلیل هر بار حرف در موقعیت (i, j)ماتریس را با عنصر موقعیت seq در کلمه کلیدی مقایسه می کنیم. در صورتی که برابر نباشند این مسیر را ادامه نمی دهیم (خط 22 و 23). در صورتی که برابر باشند و این آخرین حرف در کلمه کلیدی باشد با این معناست که کلمه کلیدی در جدول موجود است (خط 11 و 12). اگر به انتهای کلمه کلیدی نرسیده باشیم باید این خانه (i, j) را نشان گذاری کنیم تا در ادامه مسیر کنونی از آن دوباره استفاده نکنیم (خط 13). سپس برای هر یک از جهت های حرکت در یک حلقه تکرار (خط 14) اندیس موقعیت های بعدی را می سازیم (خط 15 و 16). آنگاه بررسی می کنیم که اندیس ها خارج از ماتریس نیفتاده باشند و همچنین خانه مورد نظر قبلا در این مسیر استفاده نشده باشد (خط 17 و 18). در صورت امکان حرکت به نقطه جدید تابع را بصورت بازگشتی فراخوانی می کنیم (خط 19). در صورتی که حاصل جستجو موفقیت آمیز باشد به جستجو خاتمه می دهیم (خط 20). در صورتی که جستجو موفقیت آمیز نبود نشان خانه (i, j) را به false تنظیم می کنیم تا مسیر بعدی بتواند برای تشکیل کلمات از آن استفاده نماید (خط 22). Hossein Siadati Hossein Siadati Mon, 11 Mar 2019 07:37:38 +0330