مسئله 3n+1 Problem

متن فارسی حدس کولاتز یا حدس 3n+1

✤    ۸ اردیبهشت ۱۳۹۶

الگوریتمی را در نظر بگیرید که با دریافت یک عدد $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

نام: *  
پست الکترونیک (محرمانه):
پیام: *  
• علی
۱۷ بهمن ۱۳۹۶، ساعت ۲۲:۰۸

121413120609070501010101010101

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

خوب نبود