بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی CodeCup 2018

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسئله‌ی انتخابات

مسئله‌ی 3n+1 Problem - الگوریتمستان
الگوریتمستان
000.005.00
  »  

       

متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge

آنچه در این نوشته می‌خوانید:
   •  مسئله‌ی 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


نوشته‌های مرتبط
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        بررسی مسئله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        بررسی مسئله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        بررسی مسئله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
        بررسی مسئله‌ی بشکه‌های آب (Water Barrels)، از سوالات مسابقات برنامه‌نویسی بیان
        متن فارسی مسئله‌ی شماره‌ی 343 از UVa Online Judge، ار سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی
        بررسی مسئله‌ی تاریخچه‌ی جدول (Grid History)، از سوالات مسابقات برنامه‌نویسی بیان
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left