Как решить эту задачу без «подбора» значений?

Здравствуйте!
Простите, за возможно столь глупый вопрос, но существует ли универсальный подход к решению этой задачи, например для 18-ти, 54-х и т.д. значных циферблатов? без перебора значений, естественно

bacf568308ea492684195c4838bc3f8b.JPG
  • Вопрос задан
  • 817 просмотров
Решения вопроса 2
@MarkusD
все время мелю чепуху :)
Легко. Но для этого на циферблат надо посмотреть под разными углами.

Сперва давай поглядим на него как на арифметическую прогрессию. А1 == 1; А12 == 12; D == 1.
Формула суммы прогрессии: S = (A1 + An) * n / 2;

Вычисляем сумму нашего ряда, она равна 78. И дальше все становится очень просто.

Теперь давай посмотрим на циферблат как на циферблат. У него 12 значений, связанных в кольцо.
Проведя линию и поделив циферблат на две части, мы как бы создаем две области арифметических прогрессий.
При чем сумма сумм этих прогрессий будет равна той сумме, что мы уже посчитали.
Стало быть, нам достаточно найти такой участок на циферблате, сумма чисел которого была бы равна ровно 39 - половине уже рассчитанной сверху суммы. Иначе условие задачи не выполнить.

Выходит так, что элементов в искомой последовательности у нас становится не 12, а 6. D тот же, а вот A1 и A6 у нас неизвестные. Найти их можно через все ту же формулу суммы.

39 == (A1 + A6) * 6/2
13 == A1 + A6
A6 == A1 + D*5
13 == 2*A1 + 5
8 == 2*A1
A1 == 4
A6 == 4 + 5 == 9

Всё. Первая группа - это [4..9], вторая - это [1..3,10..12], суммы обеих последовательностей будут равны 39, а вместе - 78.

UPD:
Почему именно 6 элементов... Смотрим.

Для множества циферблата сумма такова:
78 == ( 1 + 12 ) * 12 / 2

Для подмножества должна выполняться такая сумма:
39 == ( 2A1 + N - 1 ) * N / 2

Определим N из тожественного равенства двух сумм с поправкой что от первой нам надо только половину.
( 1 + 12 ) * 12 / 4 == ( 2A1 + N - 1 ) * N / 2

Замечаем тождественность составляющих выражения и теперь рассмотрим это равенство как систему уравнений:
1 + 12 == 2A1 + N - 1
12 / 4 == N / 2

Вуаля!
N == 6; а из первого равенства очень легко вывести A1, который равен 4.
Ответ написан
@yellowmew
Cloud infrastructure, monitoring engineer. SRE
Для произвольного циферблата :
1 2 3 4…K : получаем арифметическую прогрессию. В которой K – максимальное число на циферблате.
1. Надо убедиться, что сумму арифметической прогрессии можно разделить на 2 части
Сумма арифметической прогрессии : (1+K)*K/2.
Сумма её части(половина) – (1+K)*K/4 – должна быть целым числом.
Из этого следует вывод, что K=4N или K=4N-1 где N – любое число.
2. У нас есть условие, что мы делим циферблат прямой линией. Это значит, что в одной из половин остается часть прогрессии от члена под номером X(в нашем случае член под номером X равен X) до члена Y.
3. Из доказательства формулы суммы арифметической прогрессии (сумма первого члена с последним равна сумме второго члена с предпоследним и т.д.) мы видим, что для поиска решения(нужной суммы) нам надо отсечь p членов с начала и с конца прогрессии.
Для 4N первый член X=1+p, последний Y=4N-p
Для 4N-1 добавим (в прогрессию, не на циферблат) цифру 0. Первый член нужной прогрессии соответственно X=0+p, последний : 4N-1-p

Для 4N:
Сумма необходимой нам последовательности от X до Y : (1+p+4N-p)(4N-2p)/2
Половина суммы от 1 до 4N :4N*(4N+1)/4
4N*(4N+1)/4=(1+p+4N-p)(4N-2p)/2
4N*(4N+1)/2=(4N+1)*(4N-2p)
2N=4N-2p
2p=2N. p=N количество членов последовательности равно 2N
Соответственно первый член для 4N: N+1, последний : 4N-N
Аналогично считаются члены и для 4N-1
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 3
@DancingOnWater
Заход у Евгений Шатунов был правилен, но вот обоснования, что их 6 - нет. А это самое интересное!

Как показано выше, сумма у нас должна быть 39.

Рассмотрим ряд, который не переходит через 12, т.е. является арифметической прогрессией. Вновь вернемся к ее сумме и представим ее в общем виде:
S = k*n ,
где k и n целые числа. При этом есть два варианта: k - это сумма первого и последнего элемента, а 2n - это количество чисел в последовательности, либо наоборот. В общем случае количество возможных решений определяет число комбинаций множителей итоговой суммы S.

В нашем случае 39 имеет только одно разложение (39 = 13*3) 13 элементов у нас быть не может по условию задачи, значит это сумма,а следовательно число элементов n=2*3=6.
Ответ написан
Adamos
@Adamos
Как-то попадалась похожая задача, которая имела успешное решение с линией, разделяющей число 12 на 1 и 2 ;)
А так - простейшее решение именно перебором. Поскольку перебор-то невелик: считаем сумму, находим половину, предполагаем, что один из концов линии между 12 и 1, проверяем, можно ли куда-то поместить второй конец, затем перемещаем первый между 1 и 2, снова проверяем второй и т.д. Даже для очень больших циферблатов компьютер решит такую задачу за миллисекунды.

Если хочется интеллекта, пожалуйста: на первом проходе находим единственное решение либо два ближайших неподходящих варианта. На втором получается, что мы из суммы вычитаем то число, на котором начиналась последовательность, но добавляем по 1 на каждый член этой последовательности. Сравниваем результат с теми цифрами, в которые упирается второй конец... в общем, подозреваю, что расчет будет дольше, чем по выше предложенному примитиву.
Ответ написан
Комментировать
@cro096
а есть и общий способ, для циферблатов с четным количеством чисел- решение простое- берем середину между 1 и N (12 для простых часов) и центр циферблата, проводим линию, и через центр строим перпендикуляр к этой линии. все. решение готово.
сумма 6+7 (6,5-0,5 + 6,5+0,5 ) + 5+8 (6,5-1,5 + 6,5+1,5) + 4+9 ( 6,5 -2,5 + 6,5+ 2,5) =
3+10 (6,5-3,5 + 6,5+3,5) +2+11(6,5-4,5+6,5+4,5) + 1+12(6,5-5,5+6,5+5,5).
решение распространяется на любой циферблат с четным количеством чисел.
Если чисел нечетное количество на циферблате- то прямую строим через максимум (13 напрямер) и к ней строим перпендикуляр через центр. доказательство аналогично по структуре.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы