۱-حل سوال “The 3n+1 ” کتاب programming challenge

حل سوال The 3n+1   کتاب programming challenge

امروز می خواهیم اولین و آسان ترین سوال کتاب programming challenges را حل کنیم  ،یک سوال خوب برای تمرینبرنامه نویسی. اگر نمی دانید کتاب programming challenges چیست و یا در مورد حل سوال های آن توسط ما چیزی نمی دانید ابتدا این جا کلیک کنید.

این سوال آسان ترین سوال کتاب است که بیشتر برای دست گرمی است

سوال :  The 3n +1Problem

کد PC/UVa IDs سوال : ۱۱۰۱۰۱/۱۰۰

درصد موفقیت Success rate : زیاد

متن انگلیسی سوال:

Consider the following algorithm to generate a sequence of numbers. Start with an integer n. Ifn is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22:

۲۲ ۱۱ ۳۴ ۱۷ ۵۲ ۲۶ ۱۳ ۴۰ ۲۰ ۱۰ ۵ ۱۶ ۸ ۴ ۲ ۱ It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1,000,000. For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.

Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

Output

For each pair of input integers i and j, output i, j in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input. Sample Input 1  ۱۰

۱۰۰  ۲۰۰

۲۰۱  ۲۱۰

۹۰۰  ۱۰۰۰ Sample Output 1 10 20

۱۰۰  ۲۰۰  ۱۲۵

۲۰۱  ۲۱۰  ۸۹

۹۰۰  ۱۰۰۰  ۱۷۴

ترجمه تقریبی به فارسی :

الگوریتم  زیر را که برای تولید دنباله ای از اعداد است را در نظر بگیرید.شروع با عدد صحیح N است .اگر N زوج بود تقسیم بر ۲ می کنیم اگر فرد بود ضرب در ۳ به علاوه ۱ می کنیم.عدد جدیدی که به دست می آید را دوباره این کار را باهاش انجام می دهیم تا زمانی که N=1 شود . فرض بر این است که که اگر این کار را با اعداد زیر ۱۰۰۰۰۰۰ انجام دهیم به N=1 می رسیم.برای مثال دنباله ای از اعدا د را که از N=22  شروع می شود و به ۱ ختم می شود را در نظر بگیرید طول این دنباله ۱۶ است :

۲۲  ۱۱  ۳۴  ۱۷  ۵۲  ۲۶  ۱۳  ۴۰  ۲۰  ۱۰  ۵  ۱۶  ۸  ۴  ۲  ۱

وظیفه ی شما این است که برنامه ای بنویسید که تعدادی عدد را به صورت جفت می گیرد مثلا جفت ۱۰  ۱  و شروع می کند برای اعداد از ۱ تا ۱۰ دنباله را درست می کند ، وظیفه برنامه این است که طول طولانی ترین دنباله ای که با این اعداد تولید می شود را پیدا کند.

ورودی :

ورودی شامل یک سری از جفت اعداد هست که در هر سطر یک جفت عدد قرار دارد که عداد صحیح بزرگ تر از ۰ و کوچک تر مساوی ۱۰۰۰۰۰۰ است .

خروجی و ورودی نمونه :

 

خروجی:

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

Sample Input 1  ۱۰

۱۰۰  ۲۰۰

۲۰۱  ۲۱۰

۹۰۰  ۱۰۰۰

Sample Output 1 10 20

۱۰۰  ۲۰۰  ۱۲۵

۲۰۱  ۲۱۰  ۸۹

۹۰۰  ۱۰۰۰  ۱۷۴

من در این برنامه از وکتور استفاده کردم البته اگه شما می خواهید خود برنامه را بنویسید بهتر است از فایل استفاده کنید یا هر چیز دیگر که خود می دانید. اگر سوال را حل کردید و از سایت UVa توانستید AC بگیرید برنامه تان را برای بفرستید تا در همین صفحه قرار دهیم من هم کد خود را در زیر گداته ام شاید در حین نوشتن برنامه به دردتان خورد.

نکته : برای توقف دادن ورودی  کلید CTRL+z را بزنید شرح آن در خط  ۲۴  آماده است:

این هم عکسی از ورودی و خروجی من :

ورودی

خروجی

 

کد این سوال را آقا سعید با زبان پیتون python  برامون ارسال کرده :

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۱۵ دیدگاه

  • سلام من از این الگوریتم چیزی سر درنیاوردم ولی چیزی که مسلمه اینه که کد پایتون اشتباه نوشته شده چون در هر زبان برنامه نویسی ما در ساختار if…else فقط و فقط یکبار میتونیم از else استفاده کنیم…
    اگه امکانش هست در موردش بیشتر توضیح بدین
    ممنون

  • داداش اون پیتون نیست، پایتون تلفظشه چه فارسی چه انگلیسی 😐

  • دمت گرم داداش . با قدرت ادامه بده . خیلی خیلی خیلی ممنون از زحماتت

    • فرهاد دلیرانی

      سعید @ حالا که می بینم زبان پیتون خیلی زیباست و نظم و ترتیبی خوب داره دیگه ازش نمیشه گذشت :)) , تشکر کدتون را به مطلب اضافه کردم.

      • درسته :دی ! برای هایلایت کردن کدها از افزونه Crayon Syntax Highlighter استفاده میکنی که پیتون هم ساپورت میکنه اگر کد رو باهاش هایلایت کنید خیلی زیباتر میشه مثل کدهای خودتون که تو مطلب گذاشتید

        • فرهاد دلیرانی

          سعید @ بله شما درست می گویی آقا سعید ولی یک مشکل پیش آمد کد که اضافه کردم همش می رفت بالای مطلب هر کاری کردم درست نشد برای اینکه بد قولی نشه موقت کد اونطوری گذاشتم تا مشکل رو برطرف کنم باز هم شرمنده

        • فرهاد دلیرانی

          سعید @ آپدیت نظر قبلی : مشکل برطرف شد

  • خیلی وقت بود یک وبسایت جدید ندیده بودم که هدفش فقط آموزش است .تشکر

    • فرهاد دلیرانی

      gatsby @ تشکر نظرات شما باعث دلگرمی ماست نمی دونید وقتی این همه زمان می گذاریم و از طرف خوانندگان و سایر بلاگر ها بازخوردی دریافت نمی کنیم چقدر سخت است.

  • کامنت نویسید منو کشته ولی در کل ایدش خوبه من عاشق اینم که خودمو به چالش بکشم پس تا مسیله بد صبر می کنم 🙂

    • فرهاد دلیرانی

      حتما باید بیای منو جلو جمع ضایع کنی تو ، جور دیگه نمی تونستی بگی 😀 خودم وقتی پست زدم فهمیدم کامنت ننوشتم 😀 از برنامه های بعد می نویسیم.

پاسخ دهید

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