فروردین
۳
۱۳۹۲

پاسخ مسابقه تمرینی بیان – اسپرسوی غیر عادی

این اولین نوشته من در سال ۹۲ در کدبلاگ است. امیدوارم سال ۹۲ برای همه مردم ایران مخصوصا همه دانشجویان و برنامه نویسان ایرانی سالی سرشار از موفقیت و شادی و خالی از  هرگونه غم و ناراحتی باشه.

——————————————————–

صورت مسئله اسپرسوی غیر عادی:

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

در کاتالوگ هر محصول پس از نام آن که از حروف کوچک و بزرگ انگلیسی تشکیل شده، نام علمی دانه‌های قهوه درون آن آمده که با علامت / از هم جدا شده اند. نام علمی هر دانه قهوه، با ۲ یا ۳ حرف از حرف‌های A ، M ، T یا L (حروف بزرگ) شروع شده است. پس از آن یک عدد بین سه رقمی(۱۰۰ تا ۹۹۹) آمده است. در برخی نامگذاری‌های جدیدتر، پس از این عدد، یک حرف انگلیسی، علامت نقطه و یک رقم ۱ تا ۹ نیز آمده است.

متاسفانه اخیرا در بازار محصولات تقلبی اسپرسو دیده شده است، ولی خوشبختانه هیچ کدام از آنها این قوانین را در کاتالوگ خود رعایت نکرده اند. لیستی از محصولات عنوان شده در کاتالوگ‌های مختلف به شما داده شده است و از شما خواسته شده است که تشخیص دهید کدامیک تقلبی و کدامیک اصلی هستند.

ورودی مساله:

در خط اول فایل ورودی یک عدد t قرار دارد(t بین یک تا صد می باشد) که مشخص کننده ی تعداد نام‌هایی است که باید بررسی شوند.. در هر یک از t خط بعدی یک نام برای بررسی کردن آمده است.

خروجی مساله:

به ازای هر بررسی در یک خط در صورت اصل بودن کلمه‌ی Genuine و در غیر این صورت Imitative را در خروجی بنویسید.

ورودی و خروجی مثال:
مثال خروجی مثال ورودی
Genuine
Imitative
۲
SummerEspresso ATM327P.7/LL119/ML981A.1
Golden A45.1/PO021O/455.6P-L31

 

پاسخ من به این سوال:

شاید حل این مسئله در نگاه اول ساده به نظر برسه و بگیم “این که چیزی نیست فقط چهار تا if و else لازم داره”  اما واقعیت اینه که حل اینگونه مسائل اگر با عجله همراه باشه شاید حتی برنامه نویسان قوی رو هم سردرگم کنه. علت این موضوع هم شرط ها و حالت های زیاد و خاصیه که ساده مطرح شده اما درصورت توجه نکردن به حتی یک مورد از این شرط ها کل راه حل خراب میشه. یعنی درسته که هر قسمت مسئله ساده به نظر میرسه (و واقعا هم سادست) اما در نظر گرفتن تمام این شرط ها در کنار هم موضوعیه که کار رو کمی پیچیده میکنه.اگر این موضوع رو قبول ندارید سعی کنید ذهنی و سریع این مسئله رو حل کنید.

دوستانی که دروس نظریه زبان ها و ماشین ها و طراحی کامپایلرها رو در دانشگاه پاس کردند با نمودار dfa آشنایی دارند. راه حل بسیار جالب و جذابی که برای حل این مسئله وجود داره استفاده از این نمودار برای مدل کردن مسئله و سپس پیاده سازیشه.

 

نمودار dfa برای مدل کردن سناریوی مطرح شده در صورت مسئله:

دیاگرام دی-اف-ای برای مسئله اسپرسوی غیر عادی

 

 

توضیح مراحل اجرای نمودار فوق:

q0مرحله آغازین کار است. با خواندن یکی از حروف A,T,M,L به مرحله q1 میرویم. دقت کنید که در هر مرحله اگر چیزی غیر از موارد نوشته شده بر روی فلش خوانده شود به معنی اتمام کار الگوریتم و Imitative بودن رشته ی ورودی است. در وضعیت q1نیز در صورت دریافت ورودی های قبلی به مرحله q2 میرویم.

در q2 در صورت خواندن یکی از حروف فوق به مرحله q3 و با خواندن اعدادی بین ۱ تا ۹ به وضعیت q4 میرویم. در q4 و q5 با خواندن اعدادی از ۰ تا ۹ به مرحله بعدی میرویم. در state ششم سه حالت متفاوت ممکن است رخ دهد. در این مرحله اگر رشته ورودی به اتمام رسیده باشد (Null از ورودی دریافت شده باشد)  به وضعیت q10 یا همان state پایان خواهیم رفت و مقدار Genuine بازگردانده خواهد شد اما در صورت خوانده شدن کاراکتر ‘/’ دوباره به وضعیت ابتدایی میرویم تا کار را مجددا آغاز کنیم و در صورت خوانده شدن یکی از حروف انگلیسی  به وضعیت  q7 میرویم. در q7 با گرفتن ‘.’ به وضعیت q8 میرویم. در q8 با خواندن اعدادی بین ۱ تا ۹ به وضعیت q9 خواهیم رفت. در q9 نیز با ‘/’ به q0 و با Null به وضعیت q10 که پایان اجرای الگوریتم میباشد میرویم.

بعد از رسم dfa با استفاده از switch و case، از روی نمودار به راحتی برنامه مورد نظر رو پیاده میکنیم. برای پیاده سازی هر یک از state ها از یک عبارت case استفاده میکنیم.

تمام مراحل بالا در روتین isSpresso از برنامه زیر پیاده سازی شده. این تابع رشته ای که از فایل ورودی خوانده شده را دریافت میکند و در صورت اصل بودن رشته ی دریافتی مقدار true  و در غیر اینصورت مقدار false به تابع main برمیگرداند.

 

 

اشتراک گذاری این مطلب:

نوشته‌های مرتبط

درباره نویسنده

برنامه‌نویس ++‏C/C‏ - برنامه‌نویس سیستم‌های گرافیکی با استفاده از کتابخانه ‏OpenGL - برنامه‌نویس #‏C و ..‏



فرستادن دیدگاه