بزرگترین مرجع دانشجویان ایران

advertise
Date نوامبر 4, 2016

تعداد روش های خواندن یک عدد n رقمی

با سلام

در این پست قصد داریم یکی از مسائل پیاده سازی (implement) را در مسابقات برنامه نویسی ACM مطرح و بررسی کنیم.
با ما در ادامه مطلب همراه باشید.

فرض کنید عددی مثل 8884441100 داریم . حال میخواهیم این عدد را بخوانیم به شرطی که بلد نیستم عدد 25 را بیست و پنج بخوانیم و انرا یک 2 و یک 5 مینامیم و یاعدد  22555 را دوتا 2 و سه تا 5 میخوانیم . حال برخی عادت بر این دارند ابتدا اعداد را بزرگ بزرگ بخوانند ، مثلا برای مثال 8884441100 :
میگویند 3تا 8
3تا4
2تا 1
و 2تا صفر
که این یک سبک خواندن است و یا میگویند :
دوتا 8
یک 8
سه تا 4
یک 1
یک 1
دوتا صفر
و به همین روال دیگر سبک هایی نیز وجود دارد.
حال سوال اینجاست که با گرفتن عددی مثل  به عنوان ورودی ، به چند روش مینوان آن را خواند ؟

مثال :

input : 8884441100
output :64

input:11111
output:16

حل مسئله :
این مسئله با استفاده از قانون ضرب و جایگشت به راحتی قابل حل است. فرض کنید عدد 11 باشد .
آن را میتوان به صورت تکی تکی و یا 2تایی خواند . (2 حالت)
اگر عدد 22 باشد نیز به همین روش 2 حالت میشود .
حال اگر عدد 1122 باشد چی ؟
آنرا میتوان به 4 روش 1 1 22 ، 11 22 ، 1 1 2 2 ، 11 2 2 خواند.(فاصله ها نشان دهنده ی نحوه خواندن ماست)
یا به عبارت دیگه 2*2 روش.2 روش برای 11 و 2 روش هم برای 22
حال اگر عدد 112233 باشد چی ؟
مبشه 2*2*2 روش یا 8 روش(امتحان کنید)
حال قسمتی از مسئله حل شده و مانده چگونه تعداد روش هر تیکه عدد را بدست بیاریم.
با توجه به اینکه ما اعداد رو بر اساس تعداد تکرار یک رقم میشکنیم، یعنی عدد 115555 را به 2 عدد 11 و 5555 میشکنیم و تعداد حالات خواندن 11 و 5555 را در هم ضرب میکنیم،باید تعداد حالات 5555 را بدست بیاویم .
ار آنجا که هر تکه عدد ما مثل 11 و 5555 از تعدادی رقم بکسان تشکیل شده اند ، میتوان گفت که تعداد حالات آن میشه :
(تعداد ارقام -1) 2
مثلا برای 11 داریم 21 که میشه 2 حالت.
یا برای 5555 میشه 23 که میشه 8 حالت و در کل 8*2 میشه 16 حالت مختلف.
یا برای عدد 11111 میشه 24 یا همون 16 حالت .

سورس کد این الگوریتم به زبان C++ : 

نویسنده : امیر محمد رستمی زمان ارسال مطلب: 6 ماه پیش
برچسب‌ها

مطالب مرتبط سایت

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

* Copy This Password *

* Type Or Paste Password Here *