سوالات ۱۳ و ۱۴
الگوریتم زیر که Zip نام دارد، رشتەای دودویی (از ارقام ۰ و ۱) را به عنوان ورودی میگیرد و به صورت زیر اجرا میشود:
S را مجموعەای تهی در نظر بگیر و ورودی را در z بریز.
اگر z یک رقمی است یا z∈S ،آن را برگردان و به پایان برس.
z را به S اضافه کن.
دو رقم سمت راست z را در نظر بگیر؛ اگر این دو رقم برابر باشند، رقم سمت راست z را حذف کن؛ در غیر این صورت، رقم سمت راست z را حذف کن و آن را به سمت چپ z اضافه کن.
به مرحلەی ۲ بازگرد.
برای مثال، اگر رشتەی ۱۱۱۰ را به عنوان ورودی به این الگوریتم بدهیم، مقدار z به این صورت تغییر میکند:
۱۱۱۰→۰۱۱۱→۰۱۱→۰۱→۱۰→۰۱
و در نتیجه، مقدار Zip(1110) برابر با ۰۱ میشود. دقت کنید که رقم سمت چپ رشتەی z میتواند صفر باشد.
سوال ۱۳
به ازای همەی رشتەهای دودویی یازده رقمی ممکن، این الگوریتم چند خروجی متفاوت را برمیگرداند؟
۱۰
۱۲
۲۲
۵
۲
سوال ۱۴
بزرگترین مجموعه از رشتەهای دودویی یازده رقمی متمایز که خروجی الگوریتم برای همەی اعضایش یکسان باشد، چه اندازەای دارد؟
۳۳۰
۲۵۲
۵۰۴
۹۲۴
۴۶۲