تبدیل اعداد رومی به اعداد صحیح در جاوا اسکریپت – راهنمای کاربردی

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

شاید در ابتدا فکر کنید که اگر یک I و پس از آن یک V بیاید، باید آن‌ها را هم کم کنیم. همین طور اگر I و سپس X بیاید آن را نیز کسر می‌کنیم و همین طور تا آخر. اما در این روش باید قواعد بسیار زیادی نوشت. ایده بهتر شاید این باشد که اگر یک رقم رومی با رقم بعدی برابر باشد، می‌توانیم آن را به کل اضافه کنیم. اگر کمتر باشد از بعدی کم می‌کنیم و سپس به نتیجه کلی اضافه می‌کنیم.

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

تجزیه مسئله

ابتدا باید این مسئله را به مسائل کوچک‌تری تقسیم کنیم. به این ترتیب درک می‌کنیم که:

• ارقام منفرد رومی را می‌توان به معادل‌های ده‌دهی‌شان تبدیل کرد.
• قواعدی برای اضافه و کسر تعیین می‌کنیم.
• مجموع را بازگشت می‌دهیم.

گام 1: تبدیل اعداد رومی به مقادیر عددی صحیح

در این گام ابتدا I را به 1، V را به 5 و همین طور تا آخر تبدیل می‌کنیم. به این ترتیب لیست بلندی از ثابت‌ها خواهیم داشت:

مشکل اینجا است که I یک رشته است و یک متغیر نیست. اگر بخواهید آن را به یک متغیر تبدیل کنید، تعارض زیادی ایجاد می‌شود. ما باید مسائل را تا حد امکان ساده حفظ کنیم. یکی از ساده‌ترین روش‌ها به این منظور به صورت زیر است:

بنابراین کد زیر را می‌نویسیم:

اگر بخواهیم مقدار III را تست کنیم، ابتدا باید آن I ها را به طور منفرد دربیاوریم. بنابراین رشته را به یک آرایه افراز می‌کنیم:

و خروجی زیر را به دست می‌آوریم:

()IndexOf

اینک باید هر عنصر آرایه را بررسی کرده و اندیس آن را در آرایه romanNumerals بیابیم. سپس آن را به مقدار عددی ذخیره‌شده در همان اندیس آرایه integers ترجمه می‌کنیم. این کار با استفاده از متد ()IndexOf در جاوا اسکریپت ساده است. بدین ترتیب اگر به دنبال I بگردیم، اندیس آن رشته را می‌توانیم با کد زیر به دست بیاوریم که برابر با 6 است:

romanNumerals.indexOf(“I”)

برای تبدیل به یک مقدار عددی باید صرفاً آن اندیس را در آرایه integers به صورت زیر فراخوانی کنیم:

ntegers[6]

توجه کنید که ما نمی‌خواهیم بدانیم که اندیس برابر با 6 است، بلکه صرفاً می‌خواهیم بدانیم اندیس romanNumeral چیست. بنابراین از کد زیر استفاده می‌کنیم:

integers[romanNumerals.indexOf(“I”)]

که مقدار 1 را به دست می‌دهد. اینک باید این کار را در مورد همه کاراکترهای رشته عدد رومی انجام دهیم.

گام 2: شیوه افزودن مقادیر عددی به مجموع

به جای تعیین قواعدی برای موارد حذف/اضافه مقادیر، ابتدا برنامه‌ای می نویسیم که مقدار هر کاراکتر را به مجموع اضافه کند. کار خود را با کد زیر آغاز می‌کنیم:

اینک می‌بینیم که تست پاسخ داده است.

گام 3: تعیین زمان و شیوه حذف/اضافه مقادیر

در بخش قبل دیدیم که زمانی یک مقدار به مجموع اضافه می‌شود که بزرگ‌تر از مقدار بعدی باشد و در غیر این صورت از مقدار بعدی کم می‌شود و حاصل به مجموع اضافه می‌شود. بدین ترتیب متدی برای مقایسه مقدار کنونی با مقدار بعدی نوشتیم. اگر عنصر کنونی در آرایه array[i] باشد، در این صورت مقدار بعدی برابر با array[i+1] خواهد بود.

فیلم آموزش JavaScript ES6 جاوا اسکریپت در فرادرس

کلیک کنید

اگر مقدار عددی array[i] برابر با integers[romanNumerals.indexOf(array[i])]، در این صورت array[i+1] برابر با integers[romanNumerals.indexOf(array[i+1])] خواهد بود. بنابراین اگر بخواهیم ببینیم آیا مقدار کنونی بزرگ‌تر یا مساوی مقدار بعدی است، می‌توانیم چیزی مانند زیر بنویسیم:

کد فوق کمی گیج‌کننده است، بنابراین برای درک بهتر چند متغیر به آن اضافه می‌کنیم:

بدین ترتیب نوشتن بخش بعدی راحت‌تر می‌شود:

مشکلی به نام IX

حلقه for طوری تنظیم شده است که هر بار یک عنصر را پردازش کند و در مورد شیوه استفاده از آن برای تغییر مجموع تصمیم‌گیری کند، سپس به سراغ عنصر بعدی می‌رود. اما در بخش elde if کد، با دو عنصر سر و کار داریم که array[i] و array[i+1] هستند.

برای نمونه اگر یک I و سپس X داشته باشیم و I را به 1 و X را به 10 ترجمه کنیم، بر اساس قاعده ما از آنجا که 1 کمتر از 10 است، 1 را از 10 کم می‌کنیم و مقدار 9 به دست می‌آید و 9 را به مجموع اضافه می‌کنیم. اما در حلقه بعدی عنصر کنونی ما همان عنصر «بعدی» قبلی است که برابر با X است و مقدار آن 10 است. اما چنان که دیدیم 10 را قبلاً به مجموع اضافه کرده‌ایم. اگر آن را مجدداً 10 در نظر بگیریم، مجموع به هم می‌خورد.

این وضعیت بغرنجی محسوب می‌شود، چون ما در الگوریتم خود هرگز با دو رقم سر و کار نداشتیم. هر زمان که I جلوی X قرار می‌گرفت یا C جلوی D قرار می‌گرفت، مقدار عددی آن را از مجموع کم می‌کردیم. و سپس مقدار عددی را به حلقه بعدی اضافه می‌نمودیم. اینک چرا باید به روش متفاوتی عمل کنیم؟ چون IX در اعداد رومی به معنی 9 است و بهتر است آن را مانند اعداد صحیح یک عدد در نظر بگیریم تا این که 1 را از 10 کم کنیم.

گام 4: بازگشت مجموع

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

نتیجه اجرای این الگوریتم به صورت زیر بوده است:

آیا می‌توانیم سرعت الگوریتم را با یک هش افزایش دهیم؟

ما می‌توانیم به جای استفاده از آرایه، اطلاعات اعداد رومی و صحیح را به صورت هش نیز در نظر بگیریم:

کد فوق کمی کندتر اجرا می‌شود، گرچه از حافظه کمتری نیز استفاده می‌کند و از این رو رتبه استفاده از حافظه بهبود یافته، اما از نظر رتبه‌بندی سرعت با افت مواجه شده‌ایم:

بهبود عمده الگوریتم

بزرگ‌ترین بهبود این الگوریتم از پاکسازی بخش زیر به دست می‌آید:

این بخش را به صورت زیر بازنویسی می‌کنیم:

اما این کد کار نمی‌کند، زیرا یک حالت خاص وجود دارد که در آن currentValue آخرین مقدار در آرایه است. زمانی که این اتفاق بیافتد، هیچ nextValue وجود ندارد که با آن مقایسه کنیم و از این رو کد از ارزیابی آخرین مقدار رد می‌شود. برای اصلاح این مشکل کد زیر را اضافه می‌کنیم:

یعنی اگر مقدار دیگری وجود نداشته باشد، مقدار کنونی به مجموع اضافه خواهد شد.

بهینه‌سازی نهایی

اما این کد نیز موجب کند شدن زیادی در اجرا می‌شود. با بررسی راهکارهای مختلف متوجه می‌شویم که اگر گزاره if را به روش تمیزتر زیر بنویسیم، سرعت اجرایی بهبود عمده‌ای پیدا می‌کند:

در این حالت مواردی که currentValue آخرین مقدار هست را نیز در نظر گرفته‌ایم. بدین ترتیب کد نهایی به صورت زیر در می‌آید:

این تغییر نهایی تفاوت عمده‌ای در زمان اجرا ایجاد می‌کند:

به این ترتیب به پایان این مطلب رسیدیم.

فیلم مجموعه آموزش جاوا اسکریپت JavaScript – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های JavaScript (جاوا اسکریپت)
• آموزش جاوا اسکریپت (JavaScript)
• مجموعه آموزش‌های برنامه‌‌نویسی
• شیء (Object) در جاوا اسکریپت — راهنمای کاربردی
• آموزش جاوا اسکریپت مقدماتی: ساخت بازی حدس اعداد — به زبان ساده

==