یک معمای ریاضی و یک هک ساده! (آپدیت)

ZOOMIT

دیروز داشتم در اینترنت  می گشتم که به سایت خوب زومیت رسیدم در زومیت یک معما ریاضی – هوش مطرح شده که گفته بود:

آیا می‌توانید به کمک هشت عدد ۸، به عدد ۱۰۰۰ برسید؟ استفاده از هر نماد ریاضی در این رابطه مجاز است.

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

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

اول تصمیم گرفتم که رشته ای مانند :

درست کنم و مقدارش رو حساب کنم و اگر برابر هزار نشد علامت ها رو عوض کنم و دوباره محاسبه کنم .ولی این کار سه مشکل خیلی اساسی داشت :

۱ – بدون شک جواب دارای پرانتز است و پرانتز ترتیب محاسبه را عوض می کند و همین عبارت بالا را به دها روش می شه پرانتز گذاری کرد و پیدا  کردن الگوریتمی  که همه پرانتز گذاری ها رو برای  همه ی عبارات انجام بده کار خیلی سختیه و خیلی خیلی زمان گیر است.

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

۳ – تولید تمام حالت های عملگر ها مشکل است.

ولی راه حل :

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

که بردن عبارت رو ی درخت شرایط خاصی می خواد و هر مرحله از ساخت درخت قرار دادن ریشه برای ساخت درخت می تونه درخت های متفاوتی بسازه.

فرض کنید ما عبارت :

را روی درخت ببریم و به صورت درخت نمایش دهیم :

tree

آنگاه نمایش Preorder  درخت را بدست آوریم که می شود:

preorder  یعنی اول ریشه بعد بچه چپ و بعد بچه راست .

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

stack_calculate

همان طوری که می بینید جواب عبارت ۳ شد و اگر خودتان هم به صورت دستی عبارت اولیه را حساب می کردید جواب سه می شد .

ولی روی درخت بردن درخت و شکستن درخت کار مشکلی و هرچه عملگرها و پرانتز ها زیاد می شود تبدیل عبارت به درخت سختر و پیچیده تر می شود .

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

مانند  :

ساخت همه ی حالات هم خودش مشکلی برای این کار :

به  + مقدار ۰

به – مقدار ۱

به * مقدار ۲

به  / مقدار ۳

به ^ (توان) مقدار ۴

را اختصاص می دهیم و بعد از این کار اعداد  ۰۰۰۰۰۰۰  تا   ۴۴۴۴۴۴۴ را در مبنای ۵ تولید می کنیم که هر کدام از آن اعداد نشان دهده نمایش خاصی از عملگر ها است مانند :

اینم از این ! وقتی کد اجرا کردم متوجه شدم عملگر جذر را  جا گذاشتم ، گرفتن ریشه مثالا پنجم جز عملگر های مد نظر ما نیست چون باید عدد پنج بنویسیم و این دیگر هشت عدد هشت نیست ولی جذر یا همان ریشه دوم مجاز است چون ما در ریاضی قرار داد کردیم دو را  ننویسیم از اون جایی که  مجموع  عدد ۱۰۰۰ می شود پس باید دوتا رادیکال هشت ضرب در هم داشته باشیم ،برای حل این مشکل یک عملگر دیگه تعریف کردم که جذر دو عدد را در هم ضرب کند و کدش را عدد ۵ گذاشتم .

تمام مشکلات حل شد حالا بریم سراغ کد نهایی :

آپدیت : کد من تمام حالت های پرانتز گذاری حساب نمی کرد .یکی از دوستان به اسم نیما کد قبلی اصلاح کرد در واقع کد جدیدی نوشت .

اولی کد منه و دومی کد آقا نیما:

وقتی کد را اجرا کردن جواب زیر به دست اومد که اگر به حالت عادی درش بیاوریم این می شود :

پس با هشت تا هشت می شود به عدد هزار رسید این هم بعضی از جواب ها هست:

ZOOMIT-answer

puzzle

این هم ران از برنامه(با کلیک عکس را در اندازه اصلی ببینید):

ZOOMIT

برای اینکه دلیل استفادده از کلمه هک را بدانید به این پست مراجعه کنید:  معنای واقعی هک .

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)

۲۷ دیدگاه

  • عالی بود داداش فکرت عالی بود موفق باشی

  • خیلی جالب بود. اگر اجازه دهید یک معمای مشابه را معرفی کنم که کمی سخت تر است و در کتاب هوش مصنوعی راسل و نورویش نوشته شده :
    فرض کنید دنباله ای از چند عدد داریم مثل ۱،۳،۵،۷،۹ . یک روش جستجوی مناسب طراحی و پیاده سازی کنید که ضابطه عمومی دنباله ای را بیابد که این اعداد را تولید میکند. مثلا ضابطه عمومی دنباله فوق برابر است با:
    f(n) = 2*n-1

  • از دوستان بی کار و باهال خوشم اومد! حقیقتا کدنویس های بی کاری هستید.
    من با یه سرچ ساده توی گوگول زیر ۳۰ ثانیه جواب رو پیدا کردم! 🙂

    ۱۰۰۰=۸+۸+۸+۸۸+۸۸۸

  • avarin!
    vali algoritmesh ziad booooood!
    banabarin nakhondam 😀

  • این کد تغییر یافته‌ی کد خود شما هست که همه‌ی حالات پرانتز گذاری (همه‌ی prefix ها ) را حساب میکند. تابع make_tree() همه‌ی prefix ها را میسازد و تابع calculate() با stack نتیجه را حساب میکند … (برنامه کمی سنگین هست که فکر میکنم از تعداد زیاد prefix ها به ازای هر رشته‌ی عملگر ها باشه (۴۲۹ تا هست)

    ———————————-

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

      کدی که اینجا گذاشتی همون کد خودمه فکر کنم هنگامی می خواستی کپی پیست کنی کد قبلی رو کپی کردی ، خیلی ممنون می شم کدت رو بدی بذارم.

  • ۱۰۲۴ منهای ۲۴ میشه ۱۰۰۰
    ۲۴ که جمع ۳ تا ۸ است
    ۱۰۲۴ هم که ۲ به توان ۱۰ یا به عبارتی ۲به توان ۴ ضربدر ۲ به توان ۶
    ۲ به توان ۴ که برابر جمع ۲ تا ۸ است
    ۲ به توان ۶ هم که برابر ضرب ۲ تا ۸ است
    در نتیجه
    (۸+۸+۸) – ((۸+۸)*۸*۸)
    یعنی همونی که شما بهش رسیدی

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

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

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

  • واسم یه سوال پیش اومده.
    شما میای A و B رو با هم جمع می‌کنی. مثلا داری: ۰۰۰۰۰۰۰۸۸۸۸۸۸۸۸
    توی عملیات ریاضی prefix سه تا عملوند (عدد) کنار هم قرار نمیگیره شما الان ۸ تا عملوند رو کنار هم گذاشتی.
    برای اینکه این مشکل رو دور بزنی اومدی از k و آرایه‌ی C استفاده کردی. و از توی آرایه‌ی C یک عملگر رو هر بار داخل پشته push میکنی و بعد pop میکنی. در واقع اصلا از پشته! و prefix هیچ استفاده‌ای نکردی.

    نکته‌ی بعد هم اینه که شما گفتی که یکی از مشکلات هم استفاده از پرانتز‌ها بوده، در حالی که وقتی combination تمام حالات ریاضی رو برای ۸ عدد مشابه بخوای حساب کنی، اصلا پرانتز مطرح نمیشه.

    موفق باشی.

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

      http://open-mind.ir/wp-content/uploads/2014/04/DSC_1021.jpg
      در نمایش پرفیکس محدودیتی برای کنار هم قرار گرفتن عملوندها نیست و می شه به تعداد عملگر ها عملوند کنار هم گذاشت در عکسی که گذاشتم یا از نمایش ها prefix سه عملوند کنار هم است .
      همین طور تو عکس نحوه کار کرد استک کشیدم که دقیقا برنامه هم همون کار را می کند .
      تشکر از نظر خوبتون.

      • این دوست ما تا اندازه‌ای حق داره … هر جایگشتی از عملگر ها و عملوندها یک محاسبه‌ی جدید هست در حالی که شما فقط یک حالت پرانتزگذاری را در نظر گرفتید (یک نوع درخت دودویی) به عنوان مثالی نقض عبارت :
        ((۸*۸)*(۸+۸))*((۸*۸)+(۸+۸)) = ۸۱۹۲۰
        در الگوریتم شما جواب ندارد (شما فقط یک نوع پرانتز گذاری را در نظر گرفتید)

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

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

  • ایول حاجی 😀

  • سلام، از چه IDE استفاده کردید؟

  • خیلی خوب بود ،آفرین !

پاسخ دهید

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