✤  مسئله 3n+1 Problem

آنچه در این نوشته می‌خوانید:
   •  مسئله 3n+1 Problem
       »  ورودی برنامه
       »  خروجی برنامه

الگوریتمی را در نظر بگیرید که با دریافت یک عدد $n$، دنباله‌ای از اعداد را تولید می‌کند. به این ترتیب که اگر $n$ زوج بود، تقسیم آن بر عدد 2 و اگر فرد بود، $ 3n + 1 $ را به عنوان جمله بعدی دنباله و مقدار جدید برای $n$ تولید کرده و عملیات را تا زمانی که مقدار $n$ برابر 1 شود، ادامه دهد. برای مثال، دنباله زیر با شروع از $ n = 22 $ تولید می‌شود:

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

حدس زده شده است که چنین دنباله‌ای به ازای هر عدد صحیح $n$ در نهایت به عدد 1 ختم خواهد شد. این حدس حداقل برای اعداد کمتر از 1000000 صحیح است.

برای هر ورودی $n$ منظور از cycle-length عدد $n$ تعداد اعدادی است که با شروع از آن عدد تا رسیدن به عدد 1 (شامل خود این عدد) توسط الگوریتم فوق تولید می‌شوند. به عنوان مثال، cycle-length به ازای $n = 22$ عدد 16 است. بر اساس این تعریف، برنامه شما باید با دریافت دو عدد $i$‌ و $j$، مقدار حداکثر cycle-length را به ازای اجرای الگوریتم روی اعداد این بازه (شامل خود $i$ و $j$) مشخص نماید.

  

ورودی برنامه

  [برگرد بالا]

هر خط ورودی برنامه شامل یک زوج اعداد $i$ و $j$ خواهد بود که مقدارشان بزرگتر از صفر و کمتر از 1000000 است.

  

1 10

100 200

201 210

900 1000

  

خروجی برنامه

  [برگرد بالا]

به ازای هر زوج ورودی $i$ و $j$، یک خط شامل این دو عدد به همان ترتیب که در ورودی آمده بود، در خروجی نیز چاپ شود. در ادامه نیز حداکثر مقدار cycle-length برای اجرای الگوریتم روی اعداد $i$ تا $j$ در همان خط چاپ شود.

  

1 10 20

100 200 125

201 210 89

900 1000 174

  

Link: UVa Online Judge, 100 - 3n+1 Problem

مسعود اقدسی فام

مسعود اقدسی فام هستم.

دانش‌آموخته‌ی علوم کامپیوتر و فعال حوزه‌های علم داده و یادگیری ماشین؛ علاقه‌مند به یاد دادن و یاد گرفتن :)

algs.ir/sp1gf9t     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
       ✦   مسئله Simple Addition
آخرین نوشته‌ها
       ✦   الگوریتم آنلاین
نوشته‌های پرمخاطب
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• علی
سه‌شنبه، ۱۷ بهمن ماه ۱۳۹۶، ساعت ۲۲:۰۸

121413120609070501010101010101

• رضا
سه‌شنبه، ۱۷ بهمن ماه ۱۳۹۶، ساعت ۲۲:۰۹

خوب نبود