المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۶:سوال ۹

رشته‌ی موزون

یک رشته‌ی موزون را به صورت زیر تعریف می‌کنیم:

  1. $x$ یک رشته‌ی موزون است.
  2. اگر $A$ و $B$ دو رشته‌ی موزون باشند، $(AB)$ هم یک رشته‌ی موزون است.

برای مثال، با تعریف فوق $((xx)x)$ و $(((x(xx))(x(xx)))$ دو رشته‌ی موزون هستند.

الف) در یک رشته‌ی موزون به هر $x$ عددی به نام عمق آن نسبت می‌دهیم. همق یک $x$ تعداد جفت پرانتزهای باز و بسته‌ی متناظر هم است که در دو طرف آن $x$ قرار دارند. به عنوان مثال، عمق هر $x$ در رشته‌های موزون فوق به صورت زیر است:

$$((\overset{2}{x} \overset{2}{x})\overset{1}{x}),(((\overset{3}{x}(\overset{4}{x}‌ \overset{4}{x}))(\overset{3}{x} \overset{3}{x}))(\overset{2}{x} (\overset{3}{x} \overset{3}{x})))$$

عمق یک رشته‌ی موزون را بیش‌ترین عمق $x$ ها در آن رشته تعریف می‌کنیم. بنابراین عمق دو رشته‌ی موزون فوق به ترتیب ۲ و ۴ است. کم‌ترین عمق هر رشته‌ی موزون با $n$ تا $x$ را بر حسب $n$‌به‌دست آورید.

ب) یک رشته‌ی موزون خلاصه شده یک رشته‌ی موزون است که نویسه‌های ( از آن حذف شده‌اند. به عنوان مثال $((xxx$ و $(((x(xx(xx(x(xx$ رشته‌های موزون خلاصه شده‌ی دو رشته‌ی موزون فوق هستند. نشان دهید که از یک رشته‌ی موزون خلاصه شده می‌توان رشته‌ی موزون اولیه را به‌دست آورد.

پاسخ

الف) کم‌ترین عمق رشته‌های موزون به طول $n$ را با $T_n$ نشان می‌دهیم. (منظور از طول یک رشته، تعداد $x$ های آن است.) با استقرا ثابت می‌کنیم:

$$T_n=\lceil log_2n \rceil$$

حالت پایه برای $n=1$ بدیهی است. فرض می‌کنیم که به ازای تمامی مقادیر $k$ کم‌تر از $n$ حکم برقرار است. اکنون یک رشته‌ی به طول $n>1$ را در نظر می‌گیریم. این رشته از کنار هم قرار دادن دو زیررشته‌ی موزون $A$ و $B$ به صورت $(AB)$ به وجود آمده است. اگر طول رشته‌ی $A$ برابر $x$ و طول $B$ برابر $n-x$ باشد، داریم:

$$T_n=min\{\underset{0\leq x \leq n}{max} \{T_x,T_{n-x}\}\}+1$$

که $T_n$ صعودی است، $max\{T_x,T_{n-x}\}$ هنگامی کم‌ترین مقدار را داراست که داشته باشیم :

$$T_n=T_{\lceil \frac{n}{2} \rceil}+1=\lceil log_3 {\lceil \frac{n}{2} \rceil} \rceil +1= \lceil log_2 \frac{n}{2}+1 \rceil=\lceil log_2 n \rceil$$

لم: در هر رشته‌ی موزون به طول $n$، تعداد پرانتز‌های باز برابر $n-1$ است.

اثبات لم: تعداد پرانتزهای باز یک رشته‌ی موزون به طول $n$ را $P(n)$ می‌نامیم. برای اثبات از استقرا استفاده می‌کنیم. حالت $n=1$ بدیهی است. فرض کنیم که به ازای همه‌ی مقادیر $k$ کم‌تر از $n$‌داشته باشیم $P(k)=k-1$. اکنون رشته‌ای به طول $n>1$ را در نظر می‌گیریم. این رشته از دو رشته‌ی موزون $A$ و $B$ تشکیل شده که طول هر کدام کم‌تر از $n$ است. پس داریم:

$$P(n)=P(|A|)+P(|B|)+1=n_A-1+n_B-1+1=n-1$$

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

اگر $n=1$، رشته‌ی اولیه همان $x$ است. فرض می‌کنیم تمام رشته‌های خلاصه شده به طول کم‌تر از $n$ را می‌توان به صورت منحصر به فرد به رشته‌ی موزون اولیه تبدیل کرد. اکنون یک رشته‌ی موزون خلاصه شده به طول کم‌تر از $n$ را در نظر می‌گیریم. این رشته، مسلما به صورت $AB$ می‌باشد که در آن $A$ و $B$ رشته‌های موزون خلاصه شده با طول کم‌تر از $n$ می‌باشند. اکنون در رشته‌ی خلاصه شده‌ی مورد نظر، اولین پرانتز را کنار می‌گذاریم و در رشته‌ آن‌قدر جلو می‌رویم که به جایی برسیم که تعداد پرانتزهای باز یکی کم‌تر از تعداد $x$ ها باشد. این نقطه، انتهای $A$ را مشخص می‌کند. بنابراین می‌توانیم $A$ و $B$ را پیدا نموده، طبق فرض استقرا آن‌ها را به طور منحصر به فردی به رشته‌ی موزون اولیه تبدیل کنیم. سپس با قرار دادن رشته‌های حاصل در کنار هم در درون یک جفت پرانتز، به طور یکتا به رشته‌ی اولیه مورد نظر خواهیم رسید.


ابزار صفحه