مجموعه‌ی $A$‌ را بدین صورت تعریف می‌کنیم: مجموعه‌ی کلیه‌ی رشته‌های ناتهی دودویی.

فرض کنید رشته‌ی دودویی $s_1$ به‌طول $i$ و رشته‌ی دودویی $s_2$ به‌طول $j$ را داریم و $(i\leq j)$. می‌گوییم $s_1$ پیشوند $s_2$ است اگر و فقط اگر حروف $s_1$ با $i$ حرف ابتدایی $s_2$ یکی باشند. می‌خواهیم تابعی مثل $f$ بیابیم که هر کدام از عضوهای $A$ را با یک رشته‌ی ناتهی دودویی متناظر کند. در ضمن می‌خواهیم مجموعه‌ی برد تابع $f$، $prefix-free$ باشد؛ یعنی نتوان در برد $f$ دو رشته‌ی $s_1$ و $s_2$ پیدا کرد که یکی پیشوند دیگری باشد.

الف) تابع $f$ را به‌گونه‌ای بسازید که به ازای هر $s\in A$، طول رشته‌ی $f(s)$ حداکثر ۲ برابر طول رشته‌ی $s$ باشد.

ب) تابع $f$ را به‌گونه‌ای بسازید که به ازای هر $s\in A$، اگر طول $s$، $n$ باشد طول $f(s)$ حداکثر $n+2\lceil log_2(n+1) \rceil$ باشد.

• سوال بعد
• سوال قبل