1 1 1 1 1 1 1
2 1 1 1 1 1
3 1 1 1 1 1 1 4 1 1 1 1 1 5 1 1 1 1
6 1 1 1
7 1 1 1 1 8 1 1 1 1 1 9 1 1 1 1
10 1 1 1 1 1
11 1 1 1 1 1 1 12 1 1 1 1 1 13 1 1 1 1
14 1 1 1
15 1 1 1 1 16 1 1 1 1 1 17 1 1 1 1
18 1 1 1
19 1 1 1 1 20 1 1 1 21 1 1
22 1
23 1 1 24 1 1 1 25 1 1
26 1 1 1
27 1 1 1 1 28 1 1 1 29 1 1
30 1 1 1
31 1 1 1 1 32 1 1 1 1 1 33 1 1 1 1
34 1 1 1
35 1 1 1 1 36 1 1 1 37 1 1
38 1 1 1
39 1 1 1 1 40 1 1 1 1 1 41 1 1 1 1
42 1 1 1 1 1
43 1 1 1 1 1 1 44 1 1 1 1 1 45 1 1 1 1
46 1 1 1
47 1 1 1 1 48 1 1 1 1 1 49 1 1 1 1
50 1 1 1
51 1 1 1 1 52 1 1 1 53 1 1
54 1
55 1 1 56 1 1 1 57 1 1
58 1 1 1
59 1 1 1 1 60 1 1 1 61 1 1
62 1 1 1
63 1 1 1 1 64 1 1 1 1 1 65 1 1 1 1
66 1 1 1
67 1 1 1 1 68 1 1 1 69 1 1
70 1
71 1
72 1 1 73 1 1 1 74 1 1
75 1 1 1
76 1 1 1 1 77 1 1 1 78 1 1
79 1
80 1 1 81 1 1 1 82 1 1
83 1
84 1 1 85 1 86
За 85 ходов так и не получилось - реально за 86 ходов...видимо в рассчетах не берете крайний правый...

Решил задачу сначала на бумаге, затем обнаружил, что если идти задом наперёд, от выключенных к включённым, то (считая справа) первый выключатель нажимается каждые 2 шага, второй - каждые 4, третий - каждые 8 и т.д. Написал программу на Python, которая считает количество шагов для любого n. Работает, она, однако, только для нечётных n, но я полагаю, что в чётных она просто делает два лишних шага, то есть, из ответа нужно будет просто вычесть 2.

from math import pow def switch(x): if x==0: return 1 if x==1: return 0

n=int(input('Введите количество выключаетелей: ')) a=[] a1=[] b=[] for i in range(n-1): a.append(0) a1.append(1) b.append(int(pow(2,i))) a.append(1) a1.append(1) b.append(int(pow(2,i+1))) b.append(int(pow(2,i+2)))

k=1 i=0

while (a!=a1): for i in range(n): if (k%b[n-i]-b[n-i-1]==0): a[n-n+i]=switch(a[n-n+i]) k=k+1 break print(a) print(k)

Задача короткая и так как не силен в формулах, получилось 43 "хода". Для переключения крайнего левого тумблера необходимо последовательно переключать 6 тумблеров по одному за раз итого, получилось 12 итераций. Далее для переключения в нужное положение необходимо переключить 5 тумблеров по 2 раза в итоге имеем 12+10+8+6+4+2+1=43. Последняя итерация вернуть крайний правый тумблер в нужное направление. Скрин с экселя для понимания моей логики

Простенькая задача на линейные рекуренты: a(n)= целая часть(2^(n+1)/3) (в частности a(7)=85) То есть а(n) - все единицы перевести все 1 в 0. b(n) перевести 1000...000 в 0000...00 и c(n) перевести 00000...000 в 1000...0000. Не трудно видеть, что a(n)=a(n-2)+b(n-1)+1, b(n)=b(n-1)+c(n-1)+1=c(n), все нулевые 0, единичные 1. Дальше завершить решение задачи может любой, кто умеет складывать геометрические прогрессии. P.S. то что b=c можно заметить так же заметив, что все действия "обратимы".

757673 76757674 76757671 76757674 76757673 76757674 76757672 76757674 76757673 76757674 7675767 =85

7 выключателей дают 128 комбинаций, и для упрощения записи, эти комбинации можно записать в шестнадцатиричном коде. У нас исходное состояние 7F, и нужно прийти в состояние 00. Задача - найти длину пути, последовательности переходов Для того, чтобы туда прийти нужно сбросить в 0 самые старшие биты, то есть должны произойти переходы 7F - ... - 78 - 68 - ... - 60 - 20 - ... - 28 - 38 - ... - 30 - 10 - ... - 18 - 08 - ... - 00

Рассмотрим систему из 4 выключателей (младшие разряды) и опишем в 16-ричном коде, какие могут быть переходы между их состояниями:

0 - 1 - 3 - 2 - 6 - 7 - 5 - 4 - C - D - F - E - A - B - 9 - 8

При этом понятно, что состояние 8 позволяет сбросить младший бит старшего числа, а состояние 0 позволяет сбросить второй младший бит. Путь от F до 8 занимает 5 переключений, а путь от 0 до 8 занимает 15 переключений.

Теперь отметив на том же пути количество переключений, можно дать ответ 7F - (+5) - 78 - 68 - (+15) - 60 - 20 - (+15) - 28 - 38 - (+15) - 30 - 10 - (+15) - 18 - 08 - (+15) - 00 5 + 1 + 15 + 1 + 15 + 1 + 15 + 1 + 15 + 1 + 15 = 85

Решил задачку на C# Получилось 169 проходов. )

В main запустить следующее:

Thumblers thmblrs = new Thumblers(); thmblrs.run();

Класс Thumblers.cs:

using System; using System.Linq; using System.Collections.Generic; using System.Text;

namespace ConsoleApp1 { public class Thumbler { public int index; bool _value; public bool value { get { return _value; } set { if (thmblrs != null) { if (thmblrs != null && (index == 0 && thmblrs.Thumb2.value && !thmblrs.Thumb3.value && !thmblrs.Thumb4.value && !thmblrs.Thumb5.value && !thmblrs.Thumb6.value && !thmblrs.Thumb7.value || index == 1 && thmblrs.Thumb3.value && !thmblrs.Thumb4.value && !thmblrs.Thumb5.value && !thmblrs.Thumb6.value && !thmblrs.Thumb7.value || index == 2 && thmblrs.Thumb4.value && !thmblrs.Thumb5.value && !thmblrs.Thumb6.value && !thmblrs.Thumb7.value || index == 3 && thmblrs.Thumb5.value && !thmblrs.Thumb6.value && !thmblrs.Thumb7.value || index == 4 && thmblrs.Thumb6.value && !thmblrs.Thumb7.value || index == 5 && thmblrs.Thumb7.value || index == 6)) { _value = value; } else { throw new System.InvalidOperationException("Неверное расположение тумблеров (thmblrs)"); } } else { _value = value; } } } public Thumblers thmblrs; } public class Thumblers { public static Thumblers thumblers; public Thumbler Thumb1 = new Thumbler { index = 0, value = true, thmblrs = thumblers }; public Thumbler Thumb2 = new Thumbler { index = 1, value = true, thmblrs = thumblers }; public Thumbler Thumb3 = new Thumbler { index = 2, value = true, thmblrs = thumblers }; public Thumbler Thumb4 = new Thumbler { index = 3, value = true, thmblrs = thumblers }; public Thumbler Thumb5 = new Thumbler { index = 4, value = true, thmblrs = thumblers }; public Thumbler Thumb6 = new Thumbler { index = 5, value = true, thmblrs = thumblers }; public Thumbler Thumb7 = new Thumbler { index = 6, value = true, thmblrs = thumblers }; public static Thumbler GetThumblerByIndex(int index, Thumblers thmblrs) { if (thmblrs.Thumb1.index == index) { return thmblrs.Thumb1; } if (thmblrs.Thumb2.index == index) { return thmblrs.Thumb2; } if (thmblrs.Thumb3.index == index) { return thmblrs.Thumb3; } if (thmblrs.Thumb4.index == index) { return thmblrs.Thumb4; } if (thmblrs.Thumb5.index == index) { return thmblrs.Thumb5; } if (thmblrs.Thumb6.index == index) { return thmblrs.Thumb6; } if (thmblrs.Thumb7.index == index) { return thmblrs.Thumb7; } return null; } public int MoveCarretToStart(int preLastIndex) { try { preLastIndex = preLastIndex - 1; if (preLastIndex < 0) { preLastIndex = 6; } GetThumblerByIndex(preLastIndex, this).thmblrs = this; GetThumblerByIndex(preLastIndex, this).value = !GetThumblerByIndex(preLastIndex, this).value; } catch { return MoveCarretToStart(preLastIndex); } return preLastIndex; } public void run() { int preLastIndex = 6; int tempLastIndex; int i = 0; do { thumblers = this; try { preLastIndex = MoveCarretToStart(preLastIndex); } catch { GetThumblerByIndex(preLastIndex, this).value = !GetThumblerByIndex(preLastIndex, this).value; } Console.WriteLine(Convert.ToInt32(GetThumblerByIndex(0, this).value) + " " + Convert.ToInt32(GetThumblerByIndex(1, this).value) + " " + Convert.ToInt32(GetThumblerByIndex(2, this).value) + " " + Convert.ToInt32(GetThumblerByIndex(3, this).value) + " " + Convert.ToInt32(GetThumblerByIndex(4, this).value) + " " + Convert.ToInt32(GetThumblerByIndex(5, this).value) + " " + Convert.ToInt32(GetThumblerByIndex(6, this).value)); tempLastIndex = 0; if (!GetThumblerByIndex(0, this).value) { tempLastIndex = tempLastIndex + 1; } if (!GetThumblerByIndex(1, this).value) { tempLastIndex = tempLastIndex + 1; } if (!GetThumblerByIndex(2, this).value) { tempLastIndex = tempLastIndex + 1; } if (!GetThumblerByIndex(3, this).value) { tempLastIndex = tempLastIndex + 1; } if (!GetThumblerByIndex(4, this).value) { tempLastIndex = tempLastIndex + 1; } if (!GetThumblerByIndex(5, this).value) { tempLastIndex = tempLastIndex + 1; } if (!GetThumblerByIndex(6, this).value) { tempLastIndex = tempLastIndex + 1; } i = i + 1; } while (tempLastIndex < 7); if (tempLastIndex > 6) { Console.WriteLine(i); } } } }

Посчитаем ответ для случая с 1 и 2 тумблерами: f(1)=1 f(2) = 2 Пусть тумблеров n штук. Чтобы выключить самый левый, нужно, чтобы (n-1)-ый тумблер слева остался вкл, а остальные выкл. Чтобы выключить n-2 левых, нужно f(n-2) переключений. Также нужно переключить сам левый тумблер (т.е. еще одно переключение). Итого этими действиями мы привели тумблеры к виду: 0100...00, где 1 - вкл, 0 - выкл Чтобы выключить (n-1)-й тумблей, нужно включить все тумблеры правее него(т.е. нужно включить только (n-2)-й тумблер, но для его включения нужно включить (n-3)-й тумблей и т.д.). Чтобы включить все тумблеры правее (n-1)-го, необходимо также f(n-2) действий. Теперь тумблеры имеют вид 0111...11 Осталось перевести все тумблеры левее самого левого в режим выкл., на что понадобится f(n-1) действий. Итого получаем рекуррентную формулу: f(1)=1, f(2)=2, f(n)=f(n-2) * 2 + f(n-1) + 1 => f(7) = 85

f(n) = f(n-1) + 2*f(n-2) + 1, f(7) = 85

85 переключений для 7 тумблеров?