@EvGenius142417 окт 2016 в 15:13

Занимательная задачка «Несчастливый билет»

3 мин

18K

Java * Занимательные задачкиМатематика *

Из песочницы

+17

Комментарии 31

@AndreyRubankov 17 окт 2016 в 15:32

> И чтобы развлечь себя до конца поездки, я изобрел концепт «Несчастливого билета».

Черт! А я книгу в телефоне читаю, чтобы скоротать время :-(

@SLASH_CyberPunk 17 окт 2016 в 15:33

По вашей логике:
9-8/3 = 6
Отбрасывать хорошо — округлять интереснее…

@EvGenius1424 17 окт 2016 в 15:47

Может и интересно, но как-то нечестно. В глубине души я буду знать, что эти числа не равны. Зато я не запрещаю использовать нецелые числа в процессе вычисления. e.g. 2/8*4

@AndrewN 17 окт 2016 в 17:56

Смысл есть в этом? Ведь можно переставить и не целых промежуточных уже не будет

@koldyr 17 окт 2016 в 15:45

Расширте до игры Ландау.

@SLASH_CyberPunk 17 окт 2016 в 16:04

Жаль не могу вам поставить плюс, но спасибо за подсказку отличной игры! ^_^

@impwx 17 окт 2016 в 15:48

Жалко, что в приведенном решении перебор вариантов идет вручную. Самый сок задачи был бы в том, чтобы именно алгоритмически перебрать все возможные комбинации знаков и скобок.

P.S. Не нашел комбинации a * (b - c).

@EvGenius1424 17 окт 2016 в 15:54

Спасибо. Добавил, но на результат не повлияло. Буду рад, если кто-нибудь откликнется и опубликует собственный вариант решения.

@SLASH_CyberPunk 17 окт 2016 в 16:01

Деление лучше рассматривать в виде целой части и остатка от деления, это и алгоритм и момент из комментариев выше

@koldyr 17 окт 2016 в 16:16

Перестановка и обратная польская запись позволяют перебрать все варианты, правда с избытком из-за коммутативности сложения и умножения.

@UA3MQJ 17 окт 2016 в 23:56

Вот я попробовал решить задачу перебора комбинаций операций.

@Imp5 17 окт 2016 в 15:53

Я играл ещё с факториалами, корнями и степенями.

@phvoryh 17 окт 2016 в 17:01

Есть известная вариация: расставляя знаки арифметических действий и скобки, получить в результате 100. Знаки само собой не обязательно расставлять между всеми цифрами, то есть для билета 777777 допустимым решением является (777-77)/7. Решения есть для значительной доли билетов (если мне не изменяет память, по опыту выходило где-то треть или половина), но зачастую очень хитрые.

@LynXzp 17 окт 2016 в 19:02

У меня получилось раз 10… из 10. Может повезло. Но использовал все (если сравнить с игрой Ландау то далеко не все).

@phvoryh 17 окт 2016 в 21:11

Закодил перебор. Если нигде не ошибся, то счастливыми являются 906735 билетов. Так что результат 10 из 10 кажется не сильно удивительным. Но, если честно, я поражён, что у вас так легко получилось. Порой я убивал всю поездку, чтобы найти сотню. Поэтому попробовал специально поискать сложные билеты (сам билет в заголовке спойлера, ответ внутри):

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.

@TheGodfather 18 окт 2016 в 06:26

У меня тоже получается почти в 100% случаев, когда часто ездил на автобусе, специально собирал билетики, для которых не получилось в уме составить. За год поездок штук 10 таких билетов накопилось, из них для 7 или 8 решения и вправду не существует (проверял самописной программкой)

@ainu 18 окт 2016 в 10:42

422400. Годами думал, не решил

@LynXzp 18 окт 2016 в 14:25

4^(-log2(2))*400

@ainu 18 окт 2016 в 14:49

Ну логарифм тоже не очень то вписывается, как и знак степени. Так то у меня была мысль:
(4^ — (2/2)) * 400
Для яваскрипта:
(4** — (2/2)) * 400
Но это выходит за рамки + — / * ( )

@LynXzp 18 окт 2016 в 15:08

Но если решений без степени и логарифма нет (phvoryh подтвердил), то почему бы не воспользоваться.

@phvoryh 18 окт 2016 в 15:18

Или факториал:
4!*2*2+4+0+0

@phvoryh 18 окт 2016 в 14:42

Перебор подтверждает, что решений нет.

@senya_z 17 окт 2016 в 20:22

Предложенный алгоритм обхода можно слегка улучшить. Первое, что бросается в глаза — много ненужных операций с листом тикетов — почти каждый кандидат добавляется в лист, и почти каждый потом из листа убирается. Немного переписав цикл, можно оставить только добавление, которое будет происходить после внутреннего 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. Прошу прощение за корявые отступы. Не могу использовать тэги, а пробелы и табы почему-то игнорируются.

@EvGenius1424 18 окт 2016 в 06:17

Спасибо. Время выполнения уменьшилось с 2000 ms до 300 ms)

@senya_z 17 окт 2016 в 20:34

Еще как вариант (если много свободной памяти) можно заранее посчитать мэп обратных зависимостей (в то же время, когда прямые считаются) — от арифметического результата к списку триад. По этим данным легко быстро построить лист билетов, не удовлетворяющим условию задачи. Можно для этого создать массив из миллиона булов, в который писать тру, на каждую такую найденную комбинацию. В конце пройти по массиву, выбрав те индексы, где значение false.

@eversyt 18 окт 2016 в 04:11

Я в детстве еще факториал себе разрешал. И тогда несчастливых билетов не остается (это гипотеза :) )
В вашем случае 6 — 6/6 = 0! + 1 + 3

@bender_rodriges_m 18 окт 2016 в 04:11

Всего 55252 счастливых билетов от 1 000 до 999 999

@abyrkov 18 окт 2016 в 04:11

Вот я тут думал, что мне с MAC'ами и IP'ами из подсети моего провайдера делать.
Теперь знаю)

@meft 18 окт 2016 в 06:10

А я просто пытаюсь собрать значение 100 из цифр билетика. Только перестановка запрещена, т.к. в некоторых случаях очень сильно облегчает задачу. А так, использую любые арифметические знаки.
Порой все легко, иногда очень сложно. Бывают случаи, когда невозможно (например, первые 95 билетов).
Другими словами, нужно расставить арифметические знаки так, чтобы при решении вышло 100.

@Barafu 18 окт 2016 в 08:51

Попробовал найти "в лоб" все несчастливые билеты. Оказалось несложно, компьютер считал где-то 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))

@Saderty2011 19 окт 2016 в 04:48

Я думал, я один этим занимаюсь,*(

Зарегистрируйтесь на Хабре, чтобы оставить комментарий