Задачка: как выключить духовку?

Пред­ставь­те, что у вас есть элек­три­че­ская духов­ка с одной меха­ни­че­ской кноп­кой. Кноп­ка по оче­ре­ди вклю­ча­ет режи­мы рабо­ты от сла­бых к силь­ным, затем выклю­ча­ет духов­ку, а при сле­ду­ю­щем нажа­тии сно­ва вклю­ча­ет самый сла­бый режим. Так мож­но щёл­кать по кру­гу сколь­ко угод­но — в зави­си­мо­сти от коли­че­ства щелч­ков духов­ка будет про­хо­дить все ста­дии работы. 

И вот ситу­а­ция: вы дома, вам ско­ро уез­жать, духов­ка рабо­та­ет на пер­вом режи­ме. Вне­зап­но отклю­ча­ет­ся электричество.

Про­бле­ма в том, что когда элек­три­че­ство вклю­чит­ся, духов­ка зара­бо­та­ет на том режи­ме, на кото­ром сто­ит кноп­ка. Вас дома уже не будет.

Сей­час вам нуж­но нажать меха­ни­че­скую кноп­ку столь­ко раз, что­бы при вклю­че­нии све­та духов­ка ока­за­лась в выклю­чен­ном режи­ме. Вы не помни­те, сколь­ко имен­но у духов­ки режи­мов рабо­ты, но их точ­но не боль­ше четы­рёх (вклю­чая выключенный).

Вопрос: сколь­ко раз нуж­но сей­час нажать на кноп­ку, что­бы духов­ка точ­но ока­за­лась в выклю­чен­ном режиме?

Решение

Про­бле­ма этой ситу­а­ции в том, что нам нуж­но щёлк­нуть столь­ко раз, сколь­ко потре­бу­ет­ся, что­бы гаран­ти­ро­ван­но выклю­чить духов­ку, вне зави­си­мо­сти от того, сколь­ко у неё режи­мов работы. 

Един­ствен­ное, что нам извест­но — что режи­мов 4 или мень­ше. Это зна­чит, что их может быть 2, 3 или 4. Один режим рабо­ты быть не может, пото­му что это будет режим «Выклю­че­но».

Пред­ставь­те, что сей­час духов­ка выклю­че­на и у неё от 2 до 4 режи­мов рабо­ты. Давай­те посмот­рим, сколь­ко раз нуж­но нажать на кноп­ку из каж­до­го состо­я­ния, что­бы сно­ва выве­сти её в выклю­чен­ное состояние: 

2 режи­ма рабо­ты: пер­вая мощ­ность → выключено.

3 режи­ма рабо­ты: пер­вая мощ­ность → вто­рая мощ­ность → выключено.

4 режи­ма рабо­ты: пер­вая мощ­ность → вто­рая мощ­ность → тре­тья мощ­ность → выключено.

Полу­ча­ет­ся, что нам нуж­но най­ти такое чис­ло, кото­рое после столь­ких нажа­тий даст нам выклю­чен­ную духов­ку в каж­дом слу­чае. Таким свой­ством обла­да­ет наи­мень­шее общее крат­ное — оно наце­ло делит­ся на каж­дое чис­ло из спис­ка кратных. 

У нас есть три вари­ан­та нажа­тий от выклю­чен­но­го состо­я­ние в выклю­чен­ное: 2, 3 и 4. Их наи­мень­шее общее крат­ное рав­но 12. Это зна­чит, что 12 — мини­маль­ное чис­ло, кото­рое делит­ся наце­ло одно­вре­мен­но на 2, 3 и 4.

Но мы один раз уже нажа­ли на кноп­ку, когда вклю­чи­ли духов­ку на самый пер­вый режим, зна­чит, нам оста­лось нажать 11 раз. Духов­ка выклю­че­на, мож­но спо­кой­но уезжать.

Зачем мне это знать, дорогой Код?

А вот зачем:

  1. Пра­виль­но обхо­дить мас­си­вы (огром­ная про­бле­ма для начи­на­ю­щих, что­бы не терять пер­вые и послед­ние эле­мен­ты массива).
  2. Стро­ить эффек­тив­ные алго­рит­мы, кото­рые рабо­та­ют на боль­ших мас­си­вах данных. 
  3. Что­бы не было пожара.

Текст:

Миха­ил Полянин

Редак­тор:

Мак­сим Ильяхов

Худож­ник:

Даня Бер­ков­ский

Кор­рек­тор:

Ири­на Михеева

Вёрст­ка:

Мария Дро­но­ва

Соц­се­ти:

Олег Веш­кур­цев