100 - The 3n + 1 problem :: مجموعه سوالات برنامه نویسی

این هم از نهمین سوال :

100 - The 3n + 1 problem

محدودیت زمانی : 3 ثانیه

مسئله “3n + 1”

الگوریتم زیر را در نظر بگیرید:

عدد n را ورودی بگیر.
عدد n را چاپ کن.
اگر n=1 : توقف کن.
اگر n فرد بود: n <-- 3n + 1
اگر n زوج بود: n <-- n/2
به شماره 2 برو.

اگر عدد 22 را ورودی بدهیم ، چنین دنباله ی اعدادی چاپ خواهد شد:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

این که الگوریتم بالا به ازای هر عدد صحیحی به عنوان ورودی پایان پذیرد(با چاپ عدد 1) ، یک حدس است.با وجود سادگی این الگوریتم هنوز درست بودن این حدس اثبات نشده است. اما در مورد اعداد صحیح مانند n به طوری که 0 < n < 1,000,000 تایید شده است.

در مورد ورودی n ، محاسبه ی تعداد اعدادی که چاپ می شوند ( با احتساب 1) ، امکان پذیر است. در مورد n ، این ویژگی ، طول چرخه ی n نامیده می شود. در مثال بالا طول چرخه ی 22 برابر با 16 است.

برای هر دو عدد i و j شما باید بزرگترین طول چرخه ی موجود در میان همه ی اعداد بین i و j را محاسبه کنید.

ورودی

ورودی شامل یک سری جفت اعداد صحیح i وj و هر جفت در خطی جداگانه می شود. همه ی اعداد صحیح کمتر از 1،000،000 و بیشتر از 0 هستند.

شما باید همه ی جفت های اعداد صحیح را پردازش کرده و برای هر یک بزرگترین طول چرخه ی موجود در میان همه ی اعداد صحیح بین i و j و خود آن ها را محاسبه کنید.

می توانید فرض کنید که در هیچ پردازشی عددی از عدد صحیح 32 بیتی (2147483647) بیشتر نمی شود.

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

خروجی

برای هر جفت ورودی اعداد صحیح i و j شما باید i و j و بزرگترین طول چرخه ی موجود در میان همه ی اعداد صحیح بین i و j و خود آن ها را خروجی دهید. این سه عدد باید در همه ی خط ها و به ازای هر خروجی برای هر ورودی، با دست کم یک space از یکدیگر جدا شوند. اعداد i و j باید با همان ترتیبی که در ورودی ظاهر شده اند، در خروجی چاپ شوند و در ادامه نیز در همان خط بزرگترین طول چرخه خواهد آمد.