Комментарии 31
> И чтобы развлечь себя до конца поездки, я изобрел концепт «Несчастливого билета».
Черт! А я книгу в телефоне читаю, чтобы скоротать время :-(
Черт! А я книгу в телефоне читаю, чтобы скоротать время :-(
По вашей логике:
9-8/3 = 6
Отбрасывать хорошо — округлять интереснее…
9-8/3 = 6
Отбрасывать хорошо — округлять интереснее…
Расширте до игры Ландау.
Жалко, что в приведенном решении перебор вариантов идет вручную. Самый сок задачи был бы в том, чтобы именно алгоритмически перебрать все возможные комбинации знаков и скобок.
P.S. Не нашел комбинации
P.S. Не нашел комбинации
a * (b - c).
Спасибо. Добавил, но на результат не повлияло. Буду рад, если кто-нибудь откликнется и опубликует собственный вариант решения.
Перестановка и обратная польская запись позволяют перебрать все варианты, правда с избытком из-за коммутативности сложения и умножения.
Вот я попробовал решить задачу перебора комбинаций операций.
Я играл ещё с факториалами, корнями и степенями.
Есть известная вариация: расставляя знаки арифметических действий и скобки, получить в результате 100. Знаки само собой не обязательно расставлять между всеми цифрами, то есть для билета 777777 допустимым решением является (777-77)/7. Решения есть для значительной доли билетов (если мне не изменяет память, по опыту выходило где-то треть или половина), но зачастую очень хитрые.
У меня получилось раз 10… из 10. Может повезло. Но использовал все (если сравнить с игрой Ландау то далеко не все).
Закодил перебор. Если нигде не ошибся, то счастливыми являются 906735 билетов. Так что результат 10 из 10 кажется не сильно удивительным. Но, если честно, я поражён, что у вас так легко получилось. Порой я убивал всю поездку, чтобы найти сотню. Поэтому попробовал специально поискать сложные билеты (сам билет в заголовке спойлера, ответ внутри):
Я постарался отсортировать их в порядке возрастания сложности.
P.S. Если запретить использовать многозначные числа (то есть требовать расставить все 5 знаков), то счастливых билетов остается 716270.
101048
(10+10/4)*8
399940
(3-9/(9+9))*40
146778
(14-6/7)*7+8
198797
1-9*(8/(7-9)-7)
Я постарался отсортировать их в порядке возрастания сложности.
P.S. Если запретить использовать многозначные числа (то есть требовать расставить все 5 знаков), то счастливых билетов остается 716270.
У меня тоже получается почти в 100% случаев, когда часто ездил на автобусе, специально собирал билетики, для которых не получилось в уме составить. За год поездок штук 10 таких билетов накопилось, из них для 7 или 8 решения и вправду не существует (проверял самописной программкой)
422400. Годами думал, не решил
Предложенный алгоритм обхода можно слегка улучшить. Первое, что бросается в глаза — много ненужных операций с листом тикетов — почти каждый кандидат добавляется в лист, и почти каждый потом из листа убирается. Немного переписав цикл, можно оставить только добавление, которое будет происходить после внутреннего for, с заменой break на continue на внешний цикл. Второе — можно сравнивать forward-only (комбинацию с самой собой сравнивать не имеет смысла, комбинацию BA рассматривать после того как раньше рассмотрели AB тоже не имеет смысла), добавляя сразу comb1 + comb2 и comb2 + comb1.
for (int comb1Index = 0; comb1Index < combinations.size(); comb1Index++)
{
nextPair: // labeling for early exit from nested loop
for (int comb2Index = comb1Index + 1; comb2Index < combinations.size(); comb2Index++)
{
Combination comb1 = combinations[comb1Index];
Combination comb2 = combinations[comb2Index];
for (Integer x: comb1.getValues())
{
if (comb2.getValues().contains(x))
{
continue nextPair;
}
}
tickets.add(comb1.toString() + comb2.toString());
tickets.add(comb2.toString() + comb1.toString());
}
}
P.S. Прошу прощение за корявые отступы. Не могу использовать тэги, а пробелы и табы почему-то игнорируются.
for (int comb1Index = 0; comb1Index < combinations.size(); comb1Index++)
{
nextPair: // labeling for early exit from nested loop
for (int comb2Index = comb1Index + 1; comb2Index < combinations.size(); comb2Index++)
{
Combination comb1 = combinations[comb1Index];
Combination comb2 = combinations[comb2Index];
for (Integer x: comb1.getValues())
{
if (comb2.getValues().contains(x))
{
continue nextPair;
}
}
tickets.add(comb1.toString() + comb2.toString());
tickets.add(comb2.toString() + comb1.toString());
}
}
P.S. Прошу прощение за корявые отступы. Не могу использовать тэги, а пробелы и табы почему-то игнорируются.
Еще как вариант (если много свободной памяти) можно заранее посчитать мэп обратных зависимостей (в то же время, когда прямые считаются) — от арифметического результата к списку триад. По этим данным легко быстро построить лист билетов, не удовлетворяющим условию задачи. Можно для этого создать массив из миллиона булов, в который писать тру, на каждую такую найденную комбинацию. В конце пройти по массиву, выбрав те индексы, где значение false.
Я в детстве еще факториал себе разрешал. И тогда несчастливых билетов не остается (это гипотеза :) )
В вашем случае 6 — 6/6 = 0! + 1 + 3
В вашем случае 6 — 6/6 = 0! + 1 + 3
Всего 55252 счастливых билетов от 1 000 до 999 999
Вот я тут думал, что мне с MAC'ами и IP'ами из подсети моего провайдера делать.
Теперь знаю)
Теперь знаю)
А я просто пытаюсь собрать значение 100 из цифр билетика. Только перестановка запрещена, т.к. в некоторых случаях очень сильно облегчает задачу. А так, использую любые арифметические знаки.
Порой все легко, иногда очень сложно. Бывают случаи, когда невозможно (например, первые 95 билетов).
Другими словами, нужно расставить арифметические знаки так, чтобы при решении вышло 100.
Порой все легко, иногда очень сложно. Бывают случаи, когда невозможно (например, первые 95 билетов).
Другими словами, нужно расставить арифметические знаки так, чтобы при решении вышло 100.
Попробовал найти "в лоб" все несчастливые билеты. Оказалось несложно, компьютер считал где-то 5 секунд. Всего нашлось 874 комбинации.
Код на Питоне
opindex=["+","*","-","/"]
partemplates=["%s%s%s%s%s","(%s%s%s)%s%s","%s%s(%s%s%s)"]
def build(values,op1,op2,paren):
textvalues=[str(a) for a in values]
result=partemplates[paren] % (textvalues[0],opindex[op1],textvalues[1],opindex[op2],textvalues[2])
return result
tickets=[]
calcs=[]
def all_tickets():
for d1 in range(0,10):
for d2 in range(0,10):
for d3 in range(0,10):
calc_ticket((d1,d2,d3))
def calc_ticket(ticket):
calc=set()
for o1 in range(0,4):
for o2 in range(0,4):
for p in range(0,3):
form=build(ticket,o1,o2,p)
try:
value=int(eval(form))
calc.add(value)
except:
pass
tickets.append(ticket)
calcs.append(calc)
bad_tickets=[]
def find_bad_tickets():
for i1 in range(0,len(calcs)):
for i2 in range(0,len(calcs)):
if calcs[i1].isdisjoint(calcs[i2]):
bad_tickets.append((i1, i2))
all_tickets()
find_bad_tickets()
print(len(bad_tickets))
Я думал, я один этим занимаюсь,*(
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Занимательная задачка «Несчастливый билет»