المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۹

عمل شماره‌ی یک از رشته‌ی ‎$abcdef$‎، رشته‌ی $‎adbecf$‎ و عمل شماره‌ی دو از رشته‌ی $‎abcdef$‎، رشته‌ی ‎$daebfc$‎ را تولید می‌کند. با استفاده‌ی پی‌درپی و دلخواه از این دو عمل و با شروع از رشته‌ی $abcdef$ کدام یک از رشته‌های زیر را ‎نمی‌توان به دست آورد؟

  1. $dbafec$
  2. $fcbeda$
  3. $cabefd$
  4. $efdcab$
  5. $fedcba$

پاسخ

گزینه (۵) درست است.

گزینه‌های ۳٬۲٬۱ و ۴ را می‌توان به‌دست آورد. مراحل به دست آوردن هر کدام از رشته‌ها عبارت‌اند از:

$1)abcdef \xrightarrow{2} daebfc \xrightarrow{1} dbafec \\ 2)abcdef \xrightarrow{1} adbecf \xrightarrow{1} aedcbf \xrightarrow{2} cabefd \xrightarrow{1} ceafbd \xrightarrow{2} fcbeda \\ 3) abcdef \xrightarrow{1} adbecf \xrightarrow{1} aedcbf \xrightarrow{2} cabefd \\ 4) abcdef \xrightarrow{1} adbecf \xrightarrow{2} eacdfb \xrightarrow{1} edafcb \xrightarrow{1} efdcab$

گزینه‌ی ۵ را با استفاده از دو عمل فوق نمی‌توان به‌دست آورد.


ابزار صفحه