دوشنبه ۱۲ آذر ۱۴۰۳
معمای المپیادی: مرتب سازی لغتنامه ای

معمای المپیادی: مرتب سازی لغتنامه ای

کد: m172
سطح دشواری این سؤال المپیاد کامپیوتر: متوسط
تاریخ انتشار: ۸ تیر ۹۵
وضعیت جواب: منتشر شده
تعداد بازدید: ۱
تعداد پاسخ: ۵
امتیاز کاربران: ۴.۲۱
تعداد آرا: ۲۴

چکیده:

مجموعه ای از کلمات یک تا شش حرفی متشکل از حروف a و b داریم و آنها را بصورت لغتنامه ای مرتب کرده ایم.

از مجموعه سؤالات المپیاد کامپیوتر کشور

مجموعه کلمات 1 تا 6 حرفی از حروف a و b را مانند کلمات لغت نامه مرتب می کنیم. 79 امین کلمه در این مجموعه مرتب کدام است؟

الف) baabba

  ب) abaaaa

  ج) baaabb

   د) baab

 هـ) baba

 

برای روشن شدن مفهوم مرتب کردن کلمات، مجموعه مرتب کلمات 1 تا 3 حرفی به ترتیب از چپ به راست برابر است با:

a, aa, aaa, aab, ab, aba, abb, b, ba, baa, bab, bb, bba, bbb 

نهمین کلمه در آن، ba می باشد.

امتیاز شما به این معما:

پاسخ معمای المپیادی 'مرتب سازی لغتنامه ای'

گزینه الف

تعداد کلماتی که حرف اول آنها برابر a است و یک حرفی، دو حرفی، ...و شش حرفی می باشند، به ترتیب برابر 20، 21، 22، 23، 24، 25 می باشند که مجموع آنها برابر 1-2یعنی برابر 63 می شود.

پس از کلمه شصت و چهارم به بعد همه کلمات با b شروع می شوند. تعداد کلماتی که با ba شروع می شوند 1-25 یعنی 31 می باشد. بنابرین از کلمه شصت و پنجم تا کلمه نود و پنجم (از جمله کلمه هفتاد و نهم) با ba شروع می شوند. تعداد کلماتی که با baa شروع می شوند برابر 1-2یعنی 15 می باشد. بنابراین از کلمه شصت و ششم تا کلمه هشتادم، از جمله کلمه هفتاد و نهم، با baa شروع می شوند. با همین استدلال معلوم می شود که کلمه هفتاد و نهم، کلمه baabba می شود.

جواب این سؤال المپیاد کامپیوتر، منتشر شده است.

نظراتی که درج می شود، صرفا نظرات شخصی افراد است و لزوماً منعکس کننده دیدگاه های آی هوش نمی باشد.
آی هوش: مرجع مفاهیم هوش و ریاضی و انواع تست هوش، معمای ریاضی و معمای شطرنج
 
در زمینه‌ی انتشار نظرات مخاطبان، رعایت برخی موارد ضروری است:
 
-- لطفاً نظرات خود را با حروف فارسی تایپ کنید.
-- آی هوش مجاز به ویرایش ادبی نظرات مخاطبان است.
-- آی هوش از انتشار نظراتی که در آنها رعایت ادب نشده باشد معذور است.
-- نظرات پس از تأیید مدیر بخش مربوطه منتشر می‌شود.
 
 
 
 
  1. احمد سه شنبه ۸ تیر ۱۳۹۵ --- ۱۹:۲۲:۲۱

    baabba
    'گزینه یک

  2. احمد چهارشنبه ۹ تیر ۱۳۹۵ --- ۱۹:۲۰:۴۶

    برای راه حل، ابتدا بهتر است تعداد کلمات سؤال را بدانیم (64 شش حرفی، 32 پنج حرف، ... 2 تک حرف و مجموعاً 126 کلمه)
    توجه شود که تعداد کل کلمات 126 را می توان مثل محاسبه تعداد زیرمجموعه ها یا از رابطه جمع جملات تصاعد حسابی هم بدست آورد.
    حالا حرف اول لغتنامه ای (از چپ) را در نظر بگیرید، این یا a است یا b. با توجه به توزیع یکنواخت، بنابراین آخرین کلمه ساخته شده با شروع a، در موقعیت 63 (نصف 126) قرار دارد.
    حال ساختار کلمات را با داشتن حرف اول (مثلاً b) بررسی می کنیم: اینجا دیگر نمی توانیم بگوییم حرف دوم یا a هست یا b! چون می تواند هیچ حرفی نباشد (کلمات تک حرفی).
    برای وقتی حرف دوم تهی باشد، یک حالت و برای وقتی حرف دوم a یا b باشد هر کدام 31 حالت (نصف 1-63) می باشد.
    همینطور وقتی حرف اول و دوم مشخص باشند، یک حالت برای دو حرفی و 15 حالت برای حرف سوم a یا b وجود دارد.
    بنابراین با اعداد 63 31 15 7 و 3 سروکار داریم و که مثل اسکناسهای پول می باشند که باید با آنها مبلغ 79 را بپردازیم!
    و باید تا حدامکان از اسکناسهای درشت تر استفاده کنیم و حواسمان هم باشد که برای نزول به هر مرتبه اسکناس پایین تر برای استفاده از یک اسکناس تک (با حرفهای بعدی تهی) هم الزام داریم.
    63+63=126
    (1+31+31)+63=126
    (31+(1+15+15)+1)+63=126

    با چینش از چپ داریم:
    79=63+1+1+14
    خب، این یعنی اینکه به حرف اول b وارد شده ایم، تک حرفی b را رد کرده ایم، به حوزه کلمات با شروع ba رسیده ایم، دو حرفی ba را رد کرده ایم و تقریباً به انتهای کلمات با شروع ba رسیده ایم. (آخرین کلمه با شروع ba یعنی babbbb) چون یکی قبل از این است (بجای 15 در موقعیت 14 هستیم) پس:
    babbba

    1. احمد چهارشنبه ۹ تیر ۱۳۹۵ --- ۱۹:۵۲:۰۹

      اصلاح می شود: حرف سوم بجای a با حرف b تایپ شده است. بنظرم امکان ویرایش وجود ندارد.
      baabba

  3. گزینه 3 چهارشنبه ۹ تیر ۱۳۹۵ --- ۲۲:۴۷:۳۹

    گزینه سوم درست است

  4. صادقانه يکشنبه ۲۰ تیر ۱۳۹۵ --- ۱۱:۳۱:۳۵

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

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

پاسخ شما

پرطرفدارترین معماهای امروز