مبانی الگوریتم

اگر لامپ خاموش باشد و یک کلید را تغییر دهیم و باز هم لامپ روشن نشود دو کلید دیگر در دو وضعیت متفاوت هستند. (چرا؟)

همانطور که در راهنمایی گفتیم اگر لامپ خاموش بود کلید اول را تغییر وضعیت میدهیم اگر خاموش ماند میدانیم کلید دوم و سوم در دو وضعیت متفاوت هستند پس کلید دو را تغییر میدهیم حالا میدانیم کلید دو و سه در یک وضع هستند پس اگر لامپ بعد از اینکه کلید دو را تغییر دادیم باز هم خاموش باشد میفهمیم وضعیت کلید اول با دوتای دیگر فرق میکند پس کلید اول را تغییر میدهیم و لامپ روشن میشود.

هر بار که دوتا باتری رو میزاریم تو چراغ قوه اگر روشن نشه میفهمیم که حداقل یکی از اون دوتا باتری خرابن.

پاسخ - 4

باتری ها را با 1 تا 5 شماره گذاری میکنیم. ابتدا الگوریتمی ارائه میدهیم که با حداکثر 4 مرحله چراغ قوه را روشن کند. در دو مرحله اول به ترتیب باتری 1 و 2 و باتری های 3 و 4 را امتحان میکنیم. اگر لامپ در این دو مرحله روشن نشود میفهمیم که یکی از باتری های 1 و 2 خراب است و دیگری سالم است و همینطور یکی از باتری های 3 و 4 خراب است و دیگری سالم است و همچنین چون دوتا باتری خراب داریم پس باتری 5 سالم است. در مرحله 3 ام باتری 5 و 3 را امتحان میکنیم اگر روشن نشد یعنی باتری 3 خراب است چون باتری 5 سالم است حال از آن جایی که میدانستیم دقیقا یکی از 3 و 4 خراب هستند پس میدانی باتری 4 سالم است حال باتری 4 و 5 را امتحان میکنیم و چراغ قوه روشن میشود. حال ثابت میکنیم که با 3 بار امتحان کردن نمیتوان چراغ قوه را روشن کرد ابتدا دقت کنید اگر بخواهیم در مرحله 3 ام چراغ قوه را روشن کنیم حتما باید در دو مرحله قبلی دوتا باتری سالم را پیدا کرده باشیم. حال بدون از دست رفتن کلیت مساله فرض میکنیم در مرحله اول باتری 1 و 2 را امتحان کردیم و لامپ روشن نمیشود در مرحله بعدی یا یکی از 1 و 2 را با یکی از باتری های امتحان نشده امتحان میکنیم یا یا 1 و 2 را میزاریم کنار و دوتای دیگر را انتخاب میکنیم در حالت اول فرض کنید در مرحله دومی 1 و 3 را امتحان میکنیم و روشن نمیشود از انجایی که دو حالت رو به رو ممکن هستند برای باتری ها پس دو باتری سالم یکتا مشخص نیستند حالت اول اینکه 1 خراب باشد 2 و 3 و 5 سالم باشند و 4 هم خراب باشد. و حالت دوم اینکه 2 و 3 خراب باشند و 1 و 4 و 5 سالم باشند. حال میریم سراغ حالتی که بعد از مرحله اول دوتای جدید را امتحان کنیم فرض کنید 3 و 4 را امتحان کنیم و چراغ خاموش بماند ما میدانیم که 5 سالم است اما بین 3 و 4 و همینطور بین 1 و 2 نمیدانیم کدام خراب است کدام سالم پس فقط یکدونه سالم مشخص توانستیم بکنیم از انجایی که بعد دو مرحله نتوانستیم 2 تا سالم پیدا کنیم پس در مرحله سوم نمیتوانیم چراغ را روشن کنیم.

اگر عملیات برعکس کردن i رقم سمت چپ را بگوییم "عمل i"، میتوانیم فرض کنیم هر عمل حداکثر یک بار انجام شده و ترتیب عملیات ها هم مهم نیست. (چرا؟)

پاسخ - 5

اگر عمل 1 و 4 و 6 و 7 و 9 را انجام بدهیم میتوانیم بررسی کنیم که S به T تبدیل میشود. حال اثبات میکنیم با کمتر از 5 عمل نمیتوان خواسته مساله را برقرار کرد. اگر رقم دهم از سمت چپ را در نظر بگیریم چون فقط عمل 10 روی آن تاثیر دارد پس و از انجایی که در دو رشته با هم برابر است نتیجه میگیریم عمل 10 نباید انجام شود حال رقم 9 را اگر در نظر بگیریم چون تفاوت دارند و عمل 10 هم انجام ندادیم پس باید عمل 9 را انجام بدهیم این استدلال را اگر تا عمل 1 ادامه دهیم میتوان نتیجه گرفت که عمل های 1 و 4 و 6 و 7 و 9 را باید انجام دهیم.

عدد n را در مبنای دو بررسی کنید.

پاسخ - 7

اگر n را در مبنای دو در نظر بگیریم خط 3 راست ترین بیت n را در r میریزد و در خط 4 بیت سمت راست را با بیت قبلی مورد بررسی مقایسه میکند (در حالتی که اولین بار به خط 4 برسیم راست ترین بیت n را با 0 مقایسه میکند) و اگر فرق داشتند عدد خروجی را یکی زیاد میکند (b در خط 5 مساوی سمت راست ترین بیت میشود و در مراحل بعدی به عنوان بیت قبلی مورد بررسی استفاده میشود) سپس بیت سمت راست n از n کنده میشود در خط 6.

پس این عملیات در واقع تعداد بیت های متوالی متفاوت را میشمرد. (بیت اول اگر 1 باشد نیز یکی به خروجی اضافه میشود) حال هر عدد کوچکتر از 128 حداکثر 7 بیت دارد پس حداکثر 6 جفت بیت متوالی دارد پس s حداکثر 7 است (اگر بیت اول 1 باشد هم یکی اضافه میشود به s) همچنین میبینیم که عدد (1010101)2 = (85)10 مقدار s را 7 میکند پس جواب مسئله 7 است.