В «Занимательной арифметике» известного популяризатора наук Якова Исидоровича Перельмана в конце первой главы я нашел пример следующих «Арифметических курьезов»:
100 = 1+2+3+4+5+6+7+8*9
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123-45-67+89
Первое из этих решений я нашел еще в начальной школе на олимпиаде по математике, и теперь подумав, что, может быть, та победа повлияла на мое будущее становление, я решил воздать должное этой задаче и найти все возможные решения, написав соответствующий скрипт на Python.
Пусть задача поставлена так: есть строка цифр 123456789 (пусть я и правда не очень интересуюсь нулем), между которыми можно в любых местах поставить 4 арифметических операции (+, -, *, /) или не ставить ничего (то есть ставить пустую строку, тогда образуются двух- и более -значные числа) так, чтобы общее выражение давало в результате 100, как в примерах из книги выше. Ничего другого нельзя, никаких скобок, никаких перестановок, никаких дублей, никаких выкидываний.
Я не учился программированию, и реализовал задачу, как придумал. Поэтому у меня есть вопрос: «Как это можно было сделать лучше?».
А придумал я так: для того чтобы перебрать все возможные варианты вставки символов промежутков (а их пять: либо пустая строка, либо +, -, *, /), я представлял их как варианты числа по основанию 5, дополненные слева нулями. Длина такого числа восемь символов, поскольку цифр девять, и между ними тогда имеется восемь промежутков. Нули соответствуют пустым строкам, все остальные — арифметическим операциям. Вот что получилось:
Для 100 нашлось 101 такое решение, причем некоторые из них довольно забавные, особенно с дробями:
123+45-67+8-9 = 100
123+4-5+67-89 = 100
123+4*5-6*7+8-9 = 100
123-45-67+89 = 100
123-4-5-6-7+8-9 = 100
12+34+5*6+7+8+9 = 100
12+34-5+6*7+8+9 = 100
12+34-5-6+7*8+9 = 100
12+34-5-6-7+8*9 = 100
12+3+4+5-6-7+89 = 100
12+3+4-56/7+89 = 100
12+3-4+5+67+8+9 = 100
12+3*45+6*7-89 = 100
12+3*4+5+6+7*8+9 = 100
12+3*4+5+6-7+8*9 = 100
12+3*4-5-6+78+9 = 100
12-3+4*5+6+7*8+9 = 100
12-3+4*5+6-7+8*9 = 100
12-3-4+5-6+7+89 = 100
12-3-4+5*6+7*8+9 = 100
12-3-4+5*6-7+8*9 = 100
12*3-4+5-6+78-9 = 100
12*3-4-5-6+7+8*9 = 100
12*3-4*5+67+8+9 = 100
12/3+4*5-6-7+89 = 100
12/3+4*5*6-7-8-9 = 100
12/3+4*5*6*7/8-9 = 100
12/3/4+5*6+78-9 = 100
1+234-56-7-8*9 = 100
1+234*5*6/78+9 = 100
1+234*5/6-7-89 = 100
1+23-4+56+7+8+9 = 100
1+23-4+56/7+8*9 = 100
1+23-4+5+6+78-9 = 100
1+23-4-5+6+7+8*9 = 100
1+23*4+56/7+8-9 = 100
1+23*4+5-6+7-8+9 = 100
1+23*4-5+6+7+8-9 = 100
1+2+34-5+67-8+9 = 100
1+2+34*5+6-7-8*9 = 100
1+2+3+4+5+6+7+8*9 = 100
1+2+3-45+67+8*9 = 100
1+2+3-4+5+6+78+9 = 100
1+2+3-4*5+6*7+8*9 = 100
1+2+3*4-5-6+7+89 = 100
1+2+3*4*56/7-8+9 = 100
1+2+3*4*5/6+78+9 = 100
1+2-3*4+5*6+7+8*9 = 100
1+2-3*4-5+6*7+8*9 = 100
1+2*34-56+78+9 = 100
1+2*3+4+5+67+8+9 = 100
1+2*3+4*5-6+7+8*9 = 100
1+2*3-4+56/7+89 = 100
1+2*3-4-5+6+7+89 = 100
1+2*3*4*5/6+7+8*9 = 100
1-23+4*5+6+7+89 = 100
1-23-4+5*6+7+89 = 100
1-23-4-5+6*7+89 = 100
1-2+3+45+6+7*8-9 = 100
1-2+3*4+5+67+8+9 = 100
1-2+3*4*5+6*7+8-9 = 100
1-2+3*4*5-6+7*8-9 = 100
1-2-34+56+7+8*9 = 100
1-2-3+45+6*7+8+9 = 100
1-2-3+45-6+7*8+9 = 100
1-2-3+45-6-7+8*9 = 100
1-2-3+4*56/7+8*9 = 100
1-2-3+4*5+67+8+9 = 100
1-2*3+4*5+6+7+8*9 = 100
1-2*3-4+5*6+7+8*9 = 100
1-2*3-4-5+6*7+8*9 = 100
1*234+5-67-8*9 = 100
1*23+4+56/7*8+9 = 100
1*23+4+5+67-8+9 = 100
1*23-4+5-6-7+89 = 100
1*23-4-56/7+89 = 100
1*23*4-56/7/8+9 = 100
1*2+34+56+7-8+9 = 100
1*2+34+5+6*7+8+9 = 100
1*2+34+5-6+7*8+9 = 100
1*2+34+5-6-7+8*9 = 100
1*2+34-56/7+8*9 = 100
1*2+3+45+67-8-9 = 100
1*2+3+4*5+6+78-9 = 100
1*2+3-4+5*6+78-9 = 100
1*2+3*4+5-6+78+9 = 100
1*2-3+4+56/7+89 = 100
1*2-3+4-5+6+7+89 = 100
1*2-3+4*5-6+78+9 = 100
1*2*34+56-7-8-9 = 100
1*2*3+4+5+6+7+8*9 = 100
1*2*3-45+67+8*9 = 100
1*2*3-4+5+6+78+9 = 100
1*2*3-4*5+6*7+8*9 = 100
1*2*3*4+5+6+7*8+9 = 100
1*2*3*4+5+6-7+8*9 = 100
1*2*3*4-5-6+78+9 = 100
1*2/3+4*5/6+7+89 = 100
1/2*34-5+6-7+89 = 100
1/2*3/4*56+7+8*9 = 100
1/2/3*456+7+8+9 = 100
Потом я решил просмотреть полную зависимость числа возможных решений таких разложений от всех возможных сумм, в том числе и нецелых. Для этого цикл стал функцией, работающей на заполнение словаря:
Списки зависимости ylist=f(xlist) рисуются с помощью matplotlib. Зависимость имеет пик в нуле со 167 решениями:
Левая ветвь не симметрична правой, потому что перед вариантом 1*2*3*4*5*6*7*8*9 по условию задачи минус мы поставить не можем. Чем ближе к нулю, тем чаще встречаются действительные числа, которые можно представить несколькими возможными способами.
Отдельное рассмотрение для решений в области [-1.1, 1.1]: наибольшее число решений приходится, собственно, на ноль, потом на целые числа -1, 1, потом на полуцелые -0.5, 0.5.
Проверено, что любое из целых чисел от 0 до 100 может быть выражено таким способом:
Может быть, эта задача понравится и просто, чтобы задать кому-то, например собственному ребенку или приятелю, на скорость счета и умение обращаться с числами, как когда-то мне она была задана в начальной школе и нужно было найти одно решение, хотя, как я теперь вижу, их было намного больше. А можете попробовать сами в уме или на бумаге найти хотя бы одно из 167 решений для нуля.
UPD: Не подумайте, что все эти графики это что-то серьезное. Здесь нет ничего серьезного, кроме постановки задачи, кода и предложения питонистам попробовать написать что-то более быстрое.
UPD2: Отличный вариант улучшения кода был написан в комментарии hellman
100 = 1+2+3+4+5+6+7+8*9
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123-45-67+89
Первое из этих решений я нашел еще в начальной школе на олимпиаде по математике, и теперь подумав, что, может быть, та победа повлияла на мое будущее становление, я решил воздать должное этой задаче и найти все возможные решения, написав соответствующий скрипт на Python.
Пусть задача поставлена так: есть строка цифр 123456789 (пусть я и правда не очень интересуюсь нулем), между которыми можно в любых местах поставить 4 арифметических операции (+, -, *, /) или не ставить ничего (то есть ставить пустую строку, тогда образуются двух- и более -значные числа) так, чтобы общее выражение давало в результате 100, как в примерах из книги выше. Ничего другого нельзя, никаких скобок, никаких перестановок, никаких дублей, никаких выкидываний.
Я не учился программированию, и реализовал задачу, как придумал. Поэтому у меня есть вопрос: «Как это можно было сделать лучше?».
А придумал я так: для того чтобы перебрать все возможные варианты вставки символов промежутков (а их пять: либо пустая строка, либо +, -, *, /), я представлял их как варианты числа по основанию 5, дополненные слева нулями. Длина такого числа восемь символов, поскольку цифр девять, и между ними тогда имеется восемь промежутков. Нули соответствуют пустым строкам, все остальные — арифметическим операциям. Вот что получилось:
Copy Source | Copy HTML<br/>from __future__ import division # for 2.x version<br/> <br/>s = '123456789'<br/>d = {'0':'', '1':'+', '2':'-', '3':'*', '4':'/'}<br/>sum_num = 100<br/>count = 0<br/> <br/>def to_new_base(n, new_base):<br/> s = []<br/> if n == 0:<br/> s.append('0')<br/> while n:<br/> s.append(str(n % new_base))<br/> n = n // new_base<br/> num = '{0:0>8}'.format(''.join(s[::-1]))<br/> return num<br/> <br/> <br/>for n in xrange(int('44444444', 5)):<br/> num = to_new_base(n, 5)<br/> expr = ''<br/> for i, j in zip(s, num):<br/> expr += i + d[j]<br/> expr += '9'<br/> if eval(expr) == sum_num:<br/> print('{0} = {1}'.format(expr, sum_num))<br/> count += 1<br/> <br/> <br/>print 'So, {0} expressions for {1}'.format(count, sum_num) <br/>Для 100 нашлось 101 такое решение, причем некоторые из них довольно забавные, особенно с дробями:
123+45-67+8-9 = 100
123+4-5+67-89 = 100
123+4*5-6*7+8-9 = 100
123-45-67+89 = 100
123-4-5-6-7+8-9 = 100
12+34+5*6+7+8+9 = 100
12+34-5+6*7+8+9 = 100
12+34-5-6+7*8+9 = 100
12+34-5-6-7+8*9 = 100
12+3+4+5-6-7+89 = 100
12+3+4-56/7+89 = 100
12+3-4+5+67+8+9 = 100
12+3*45+6*7-89 = 100
12+3*4+5+6+7*8+9 = 100
12+3*4+5+6-7+8*9 = 100
12+3*4-5-6+78+9 = 100
12-3+4*5+6+7*8+9 = 100
12-3+4*5+6-7+8*9 = 100
12-3-4+5-6+7+89 = 100
12-3-4+5*6+7*8+9 = 100
12-3-4+5*6-7+8*9 = 100
12*3-4+5-6+78-9 = 100
12*3-4-5-6+7+8*9 = 100
12*3-4*5+67+8+9 = 100
12/3+4*5-6-7+89 = 100
12/3+4*5*6-7-8-9 = 100
12/3+4*5*6*7/8-9 = 100
12/3/4+5*6+78-9 = 100
1+234-56-7-8*9 = 100
1+234*5*6/78+9 = 100
1+234*5/6-7-89 = 100
1+23-4+56+7+8+9 = 100
1+23-4+56/7+8*9 = 100
1+23-4+5+6+78-9 = 100
1+23-4-5+6+7+8*9 = 100
1+23*4+56/7+8-9 = 100
1+23*4+5-6+7-8+9 = 100
1+23*4-5+6+7+8-9 = 100
1+2+34-5+67-8+9 = 100
1+2+34*5+6-7-8*9 = 100
1+2+3+4+5+6+7+8*9 = 100
1+2+3-45+67+8*9 = 100
1+2+3-4+5+6+78+9 = 100
1+2+3-4*5+6*7+8*9 = 100
1+2+3*4-5-6+7+89 = 100
1+2+3*4*56/7-8+9 = 100
1+2+3*4*5/6+78+9 = 100
1+2-3*4+5*6+7+8*9 = 100
1+2-3*4-5+6*7+8*9 = 100
1+2*34-56+78+9 = 100
1+2*3+4+5+67+8+9 = 100
1+2*3+4*5-6+7+8*9 = 100
1+2*3-4+56/7+89 = 100
1+2*3-4-5+6+7+89 = 100
1+2*3*4*5/6+7+8*9 = 100
1-23+4*5+6+7+89 = 100
1-23-4+5*6+7+89 = 100
1-23-4-5+6*7+89 = 100
1-2+3+45+6+7*8-9 = 100
1-2+3*4+5+67+8+9 = 100
1-2+3*4*5+6*7+8-9 = 100
1-2+3*4*5-6+7*8-9 = 100
1-2-34+56+7+8*9 = 100
1-2-3+45+6*7+8+9 = 100
1-2-3+45-6+7*8+9 = 100
1-2-3+45-6-7+8*9 = 100
1-2-3+4*56/7+8*9 = 100
1-2-3+4*5+67+8+9 = 100
1-2*3+4*5+6+7+8*9 = 100
1-2*3-4+5*6+7+8*9 = 100
1-2*3-4-5+6*7+8*9 = 100
1*234+5-67-8*9 = 100
1*23+4+56/7*8+9 = 100
1*23+4+5+67-8+9 = 100
1*23-4+5-6-7+89 = 100
1*23-4-56/7+89 = 100
1*23*4-56/7/8+9 = 100
1*2+34+56+7-8+9 = 100
1*2+34+5+6*7+8+9 = 100
1*2+34+5-6+7*8+9 = 100
1*2+34+5-6-7+8*9 = 100
1*2+34-56/7+8*9 = 100
1*2+3+45+67-8-9 = 100
1*2+3+4*5+6+78-9 = 100
1*2+3-4+5*6+78-9 = 100
1*2+3*4+5-6+78+9 = 100
1*2-3+4+56/7+89 = 100
1*2-3+4-5+6+7+89 = 100
1*2-3+4*5-6+78+9 = 100
1*2*34+56-7-8-9 = 100
1*2*3+4+5+6+7+8*9 = 100
1*2*3-45+67+8*9 = 100
1*2*3-4+5+6+78+9 = 100
1*2*3-4*5+6*7+8*9 = 100
1*2*3*4+5+6+7*8+9 = 100
1*2*3*4+5+6-7+8*9 = 100
1*2*3*4-5-6+78+9 = 100
1*2/3+4*5/6+7+89 = 100
1/2*34-5+6-7+89 = 100
1/2*3/4*56+7+8*9 = 100
1/2/3*456+7+8+9 = 100
Потом я решил просмотреть полную зависимость числа возможных решений таких разложений от всех возможных сумм, в том числе и нецелых. Для этого цикл стал функцией, работающей на заполнение словаря:
Copy Source | Copy HTML<br/>figure = {}<br/>xlist = []<br/>ylist = []<br/> <br/>def func():<br/> for n in range(int('44444444', 5)):<br/> num = to_new_base(n, 5)<br/> expr = ''<br/> for i, j in zip(line, num):<br/> expr += i + d[j]<br/> expr += '9'<br/> num_sum = eval(expr)<br/> if num_sum in figure:<br/> figure[num_sum] += 1<br/> else:<br/> figure[num_sum] = 1<br/> <br/> for key in sorted(figure):<br/> xlist.append(key)<br/> ylist.append(figure[key]) <br/>Списки зависимости ylist=f(xlist) рисуются с помощью matplotlib. Зависимость имеет пик в нуле со 167 решениями:
Левая ветвь не симметрична правой, потому что перед вариантом 1*2*3*4*5*6*7*8*9 по условию задачи минус мы поставить не можем. Чем ближе к нулю, тем чаще встречаются действительные числа, которые можно представить несколькими возможными способами.
Отдельное рассмотрение для решений в области [-1.1, 1.1]: наибольшее число решений приходится, собственно, на ноль, потом на целые числа -1, 1, потом на полуцелые -0.5, 0.5.
Проверено, что любое из целых чисел от 0 до 100 может быть выражено таким способом:
Может быть, эта задача понравится и просто, чтобы задать кому-то, например собственному ребенку или приятелю, на скорость счета и умение обращаться с числами, как когда-то мне она была задана в начальной школе и нужно было найти одно решение, хотя, как я теперь вижу, их было намного больше. А можете попробовать сами в уме или на бумаге найти хотя бы одно из 167 решений для нуля.
UPD: Не подумайте, что все эти графики это что-то серьезное. Здесь нет ничего серьезного, кроме постановки задачи, кода и предложения питонистам попробовать написать что-то более быстрое.
UPD2: Отличный вариант улучшения кода был написан в комментарии hellman
