7 марта 2011 в 18:41

Как сделать из 123456789 число 100 или 0

В «Занимательной арифметике» известного популяризатора наук Якова Исидоровича Перельмана в конце первой главы я нашел пример следующих «Арифметических курьезов»:

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
from __future__ import division # for 2.x version
 
s = '123456789'
d = {'0':'', '1':'+', '2':'-', '3':'*', '4':'/'}
sum_num = 100
count =  0
 
def to_new_base(n, new_base):
    s = []
    if n ==  0:
        s.append('0')
    while n:
        s.append(str(n % new_base))
        n = n // new_base
    num = '{0:0>8}'.format(''.join(s[::-1]))
    return num
 
 
for n in xrange(int('44444444', 5)):
    num = to_new_base(n, 5)
    expr = ''
    for i, j in zip(s, num):
        expr += i + d[j]
    expr += '9'
    if eval(expr) == sum_num:
        print('{0} = {1}'.format(expr, sum_num))
        count += 1
 
 
print 'So, {0} expressions for {1}'.format(count, sum_num)


Для 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
figure = {}
xlist = []
ylist = []
 
def func():
    for n in range(int('44444444', 5)):
        num = to_new_base(n, 5)
        expr = ''
        for i, j in zip(line, num):
            expr += i + d[j]
        expr += '9'
        num_sum = eval(expr)
        if num_sum in figure:
            figure[num_sum] += 1
        else:
            figure[num_sum] = 1
 
    for key in sorted(figure):
        xlist.append(key)
        ylist.append(figure[key])


Списки зависимости 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
+154
16369
69
LeoMat 40,1

Комментарии (112)

+3
ArtemSmirnov, #
Я вас поздравляю, вы придумали свой вариант игры 24
+6
LeoMat, #
Что-то поискав, не смог найти такой игры. Может быть, вы ее опишите?
+3
ArtemSmirnov, #
www.24game.com/ вот она.
Условия игры — даны 4 произвольных цифры
Цель игры — с помощью всяких арифметических операция получить из них число 24
Например: даны 1,2,3,4 24 = 1 * 2 * 3 * 4
+1
LeoMat, #
Спасибо.
+9
smind, #
честно говоря не знал про 24, меня отец в детстве научил из 6 цифр на автобусном билете получать 100…
а я упростил игру до пока едет машина в поле зрения — успеть получить число 10 из цифр номера…
+4
RReverser, #
Подготовка спецагентов прям)
+2
psman, #
я тоже билетики считаю :)
+18
Aracon, #
image
0
LeoMat, #
Отлично.
+2
Mrrl, #
(38+3i)*(38-3i). А в действительных числах — простое.
0
TedBeer, #
аналогично, только придумал сам эту игру, а так как поездки были длинные, то искал решения для 100, 99 и 101 (по возрастанию трудности)
так как 99 — нечетное число, то решений меньше
101 — простое число
+3
mihmig, #
этим занимайтесь, пожалуйста, только на пассажирском сидении…
+3
hellman, #
Самое интересное, что помню из таких задачек — получить 24 из 1,3,4,6. (можно использовать +-*/ и скобки).
0
Mrrl, #
А переставлять можно? Если да — 6/(1-3/4). Если нет — пока не получается.
0
hellman, #
Правильно.
0
Mrrl, #
Мы в такое иногда тоже играем, но операций побольше — есть степень, корень, факториал и десятичные дроби (конечные и периодические). Обычно задача — получить текущий год из минимального числа одинаковых цифр.
Например, (.(2)-.2)^(-2)-sqrt(2/.(2))/.2 = 2010
0
hellman, #
Я просто на braingames.ru раньше зависал, запомнилось. Вот еще задачка (оттуда же), я ее так и не осилил:
Как с помощью трех цифр «2» и знаков математических операций записать число 2007? Округлять числа нельзя.
Тут можно использовать еще алгебраические функции (подробности на странице).
0
Mrrl, #
Не помню, кто ее придумал. Не то Паули, не то Винер. В общем, что-то середины прошлого века…
0
Norty, #
«та победа повлияла на мое будущее становление»

+17
LeoMat, #
Я вполне уверен в этом, так как тогда я первый раз победил в каком-то интеллектуальном соревновании в большой группе людей, и я стал меньше волноваться по поводу своих способностей и больше пользоваться ими.
+7
easyman, #
Это психологическое
+3
ckopn, #
Развеселили.
0
tronix286, #
Да это то все понятно давно. Практической пользы увы никакой. Если смотреть в сторону сжатия информации — то опять-таки нужно хранить последовательность операций, числа (однозначное-двухзначное) и тд. Получается что на выходе будет информации еще больше чем было. А больше я не знаю зачем оно все это нужно. Да и вообще, 123456789 последовательность встречается крайне редко.
+4
LeoMat, #
Конечно. Ведь я и не искал никакой пользы для сжатия информации. Я искал лишь удовлетворение личного математического (или пусть даже арифметического) любопытства, коего и достиг, о котором и написал. По крайней мере три вопроса, которые я хотел решить таким образом и решил:

1) Сколько решений найдется для наиболее известной задачи числа ста?
2) Действительно ли предполагаемый 0 должен обладать наибольшим числом вариаций?
3) Действительно ли можно все целые числа до 100 так представить?

Мне просто это было интересно. Может быть, этим может когда-то заинтересоваться кто-то еще, возможно даже для какого-то неожиданного практического применения, поэтому я описал свои действия.
0
yeroo, #
Чаще всего в паролях
+2
spmbt, #
А слабо найти первое число в натуральном ряду, которое не может быть вычислено таким способом? :)

Может быть вариация: ставить перед 1 минус или нет.
0
LeoMat, #
Хорошо, подумаю.
+2
LeoMat, #
Получается, что 910.

А далее 990, 1000, 1002, 1004, 1062…

Забавно что 100 представить можно 101 способом, а 1000 ни одним.
+2
LeoMat, #
При том, что у предшествующего числа даже 7 вариантов реализоваться:

123-4-5+6+789 = 909
12+3*45*6+78+9 = 909
12*3*4*5/6+789 = 909
1+234+5+678-9 = 909
1+2+3*45*6+7+89 = 909
1+2-3+4*5*6+789 = 909
1/2*3*45*6+7*8*9 = 909
0
spmbt, #
Сколько времени занимает расчёт одного числа (например, 100)?

Написал сейчас на JS (т.к. Пайтон не установлен и не знаю), полный расчёт по 1 числу в Хроме (проц e2180) занял 67 секунд (390625 циклов с таким же eval() ).

Потенциальные ошибки вашего алгоритма: не проверяется деление на 0 (но тут его, «к счастью», нет), и не проверяется в строчке «if eval(expr) == sum_num:» эпсилон-окружение результата — от округления могло получиться что-то типа 100.000001 или 99.99999987. Но с числом 100 это тоже, видимо, обошлось, у меня тоже ответ 101.
0
LeoMat, #
Да, деление на ноль и бессмысленно проверять, потому что единственная операция, которая могла его обеспечить при таком порядке чисел, это скобки. С ошибками дело обстоит так:

>>> 100 == 100.0
True
>>> 100 == 100.00000000000001
False
>>> 100 == 99.9999999999999
False


Получить случай эпсилон-разницы с большей точностью для данной последовательности мне хотя бы интуитивно кажется невозможным. Но и судя по просмотренным результатам для той же сотни, все дроби оказываются верны, и этим, скажем, наиболее забавны :).

Обработка занимает 55 секунд.
0
spmbt, #
На каком процессоре? Получается, что на слабеньком e2180 Javascript в Хроме считает практически с той же скоростью.
0
LeoMat, #
Celeron D 336.
0
spmbt, #
Этот раза в 3 слабее, но при вычислениях с P-кодами разница будет не столь заметна.
0
LeoMat, #
Я не очень программист, мне непонятно что это.
+1
spmbt, #
Ну Пайтон же и JS компилируются в P-код (закодированные операторы), которые потом исполняется через быструю интерпретацию (в Хроме уже вроде JIT-компиляция). Поэтому в исполнении больше логики, чем расчётов, поэтому вычислительная мощность процессора используется не так сильно, чем если бы это был компилированный код. Можно предполагать, что разница будет не в 3 раза, а меньше, но всё равно Пайтон считает раза в 2-3 быстрее, чем браузер.
–12
spmbt, #
И ещё, самая главная ошибка. У многих, если не у всех, языков приоритет деления ненормальный: равный с умножением. У людей деление слабее умножения. Для проверки, посчитайте, сколько будет alert( 10*10 / 5*5 ); в языке и у людей. У людей — 4 (потому что 10 * 10 / (5 * 5) ), в JS, например, 100, потому что считается (10*10/5)*5. Поскольку задача — из мира людей, то предполагается, что считаем выражение по-людски. Значит, нам придётся расставлять скобки.
+19
LeoMat, #
Я никогда не слышал о приоритете умножения над делением в мире людей. Вы просто группируете скобками операции: (10*10)/(5*5) вместо 10*10/5*5, а скобки в задаче не предполагаются.

Вы думаете, что это «по-человечески», поскольку сравниваете значок слэша со знаком дроби, а не знаком деления (в виде двоеточия или знака обелюса ÷), который как раз более свойственен миру людской арифметики. Так что никакой ошибки в этом нет.
–5
spmbt, #
Ну, конечно, как автор поставит задачу, так и будет. :) Но в том и дело, что операция деления пошла с алгоритмических языков, а раньше всегда применяли деление-двоеточие с более слабым приоритетом. Достаточно посмотреть, как пишут формулы в научных статьях. Для проверки, открыл «Гидродинамику» Ландау-Лифшица, и вижу там, например, m2/mr3. Тут фокус в отсутствии знака "*" на месте умножения, но почему мы должны думать иначе? Если мишем цифры, то приходится ставить умножение-точку, но при этом не вводим скобок из-за появившихся точек: 2·3/4·5, это значит 2·3/(4·5).

(Нет, всё же, поставьте тему в другой блог, не пожалеете, придут нормальные читатели :) (хотя да, 8 марта), она будет на главной. И рассудят с приоритетами операций.)
+2
LeoMat, #
Я и говорю, что вы понимаете здесь под знаком /, которым я обозначаю деление, также как * означает точку умножения. Неужели, если бы вы писали 2·3÷4·5, то вам бы так же хотелось получить то же самое? Или если считать на калькуляторе, и вводить последовательно знаки умножения деления, то есть какая-то разница?

Я правда в том первом варианте, что вы предложили посчитал также 10·10:5·5 и получил 100, потому что нет скобок и нет приоритета, также как нет приоритета у сложения или вычитания.

И я уже переместил :)
+3
maxshopen, #
Первый раз слышу про «человеческий» приоритет, честно. Ваша формула на «моём человеческом» читается как 10 умножить на 10 разделить на 5 умножить на 5 и никак иначе = 100, причем последние две операции сразу сокращаются как взаимоисключающие. Возможно у меня какой то другой мозг, ближе к роботам уже :)

+1
LeoMat, #
Вот, у меня в голове чипы сработали точно также.
–2
spmbt, #
Совершенно верно, это следствие знания программирования :). И калькуляторы — то же самое. Не думал даже, что о нормальном порядке деления настолько забудут.

(Сейчас допиливаю алгоритм расставления скобок. Интересно будет посмотреть, что получится. Но это точно уже не будет ответ 101.)
0
LeoMat, #
Если вводить скобки, то и не забудьте про вариацию с минусом перед 1, или если уж быть совсем полными (или что там еще возможно), то можно и забыть даже про -1, а просто добавить еще к цифрам вначале 0.

И был бы очень рад увидеть сами варианты для такого скобочного решения, так что жду!
0
spmbt, #
Готово. Для числа 100 получился ответ 99, а считало на e2180 — 66 секунд.
Код:
0
spmbt, #
… Какой-то сбой.
Код:
//поиск решений задачи: из 123456789 получить target = 100

if(!window.console){ //для IE и отключенного Firebug
	console = {log: function(X){
			if(arguments.length <=1)
				alert(X);
		},
		time: function(){
			dat=(new Date()).getTime();
		},
		tmeEnd: function(){
			alert((new Date()).getTime() - dat);
		}
	}
}
console.time('a'); //данные
s0 = '123456789';
x0 = [0,0,0,0,0,0,0,0, 4];
a = ['+','-','/','*',''];
var target = 100;

plus1 = function(x, i){ //5-ричный счётчик
	if(i==null) i=0;
	if(++x[i] >= 5){
		x[i] =0;
		if(++i >=8) return i;
		return plus1(x, i);
	}else return i;
}
window.sum =0; //поиск решений
var n=1, nn=0, leftPar, rightPar, wasLeftPar, wasDivide;
do{
	s='sum=';
	wasLeftPar = wasDivide =false;
	
	for(var i =0; i <=8; i++){
		if(x0[i]==3 && wasDivide){ //исправление приоритета деления
			wasLeftPar = true;
			var j = s.lastIndexOf('/') +1;
			s = s.substr(0, j) +'('+ s.substr(j) + s0.charAt(i) + a[x0[i]];
		}else if(wasLeftPar && x0[i] <3){
			wasLeftPar = false;
			s += s0.charAt(i) + ')' + a[x0[i]];
		}else
			s += s0.charAt(i) + a[x0[i]];
		if(x0[i]==2)
			wasDivide = true;
		else if(x0[i] !=4)
			wasDivide = false;
	}
	if(wasLeftPar) s+= ')';

	eval(s);
	
	if(sum > 99.999 && sum < 100.001)
		console.log(++nn, n, s, sum);
	if(plus1(x0) ==8) break;
}while(++n <1000000);
console.log(n);
console.timeEnd('a');

Скобок получилось немного, что-то ушло, что-то добавилось.
Распечатка: paste.org/pastebin/view/29878
Если надо посчитать без скобок, в цикле for(var i =0; i <=8; i++){} оставляют только s += s0.charAt(i) + a[x0[i]]; и убирают if(wasLeftPar) s+= ')';
+1
LeoMat, #
Не понимаю, почему со скобками получается меньше решений, если это наоборот добавляет возможности получить 100 и почему они не начинают группировать операции сложения и вычитания.
–2
spmbt, #
Нет, что-то добавляется, а что-то исчезает. Случайные флуктуации.

Добавил проверку с минусом впереди.
Ответов стало 150, а считалось 138 секунд.

Доп. код — это 3 строчки:
	eval(s.replace(/=/,'=-'));
	if(sum > 99.999 && sum < 100.001)
		console.log(++nn, n, s.replace(/=/,'=-'), sum);

+6
matiouchkine, #
Это как это «что-то исчезает»?! Множество ответов задачи со скобками, очевидно, полностью включает все ответы без скобок.
0
spmbt, #
Ответы без скобок — это то же, что ответы с другим порядком скобок. Ушедшие решения легко найти. Они обязательно содержат /\/\d+\*/ (другими словами, знак деления, за которым цифры и знак умножения)

Вот они, ушедшие 4 ответа из списка автора:
73: 1*23+4+56/7*8+9 = 100
99: 1/2*34-5+6-7+89 = 100
100: 1/2*3/4*56+7+8*9 = 100
101: 1/2/3*456+7+8+9 = 100
Зто означало, например, ((1/2)/3)*456+7+8+9 = 100. По моим правилам в моём списке это записывалось в виде 1/2/(3*456)+7+8+9 = 24.000365 и из списка выбывало.

А вот пришедшие (другой порядок следования из моего списка)
24: «sum=1*23*4-56/(7*8)+9» 100
51: «sum=12/(3*4)+5*6+78-9» 100

Итого, получаем 99 решений.

Кто-то трое понизили мне карму за высказывание, что решение задачи ошибочно. Ещё раз, неверящие и особенно, минусующие:
1) посмотрите в книги по математике и физике;
2) убедитесь, что знак умножения в строчной записи вида a2/mr3 имеет приоритет умножения перед делением.
И это соблюдается до сих пор. Равный приоритет умножения и деления — следствие правил языков программирования и к правилам человеческой записи выражений отношения не имеет. В Фортране ещё часты были ошибки от забывания этого правила в 60-70 годах, да и сейчас не исключены.
0
general, #
Re: посмотрите в книги по математике и физике;
посмотрите в учебнике по математике за 1-2 класс :)

Есть стандартная школьная запись деления с помощью символа "÷", и выражение a·b÷c·d выполняется в порядке ((a·b)÷c)·d

Книжная запись — ab/cd — это однострочный вариант записи дроби, когда в числителе a·b, а в знаменателе c·d. И порядок выполнения операций тут характерный для дроби (a·b)÷(c·d)

Что касается программирования, то тут все достаточно просто: символом "*" в языках программирования обозначается математическая операция "·"(умножение), а символом "/" математическая операция "÷"(деление), но никак не запись дроби.
0
spmbt, #
Верно.
Значит, вопрос стоит, как сформулировать задачу: как запись дроби в строке или как операцию деления в математике? И тот, и тот подход имеет право на существование, потому что 345/67 = не что иное, как дробь, а 345/67*89 — строчная запись решения математической формулы, в которой не поставить знак умножения мы не можем. Поэтому автор поискал решение с вычислительной операцией деления (как в алг.языках и в учебнике за 2-й класс), а я привёл аналогичное решение с операцией, аналогичной строчной записи деления (в формулах).
+2
maxshopen, #
А при чем здесь знание программирования? умножение и деление — коммутативные операции, т.е. без введения скобок их операнды можно переставлять произвольным образом -> 10*10/5*5 == 10/5*10*5 == 10*5*10/5. То, что вы в этой формуле приделали скобки — так это вы другую формулу просто получили, очень так по человечески :)
0
maxshopen, #
упс, про коммутативность я сморозил конечно, деление не коммунитативная операция. Но суть я думаю понятна, в каком порядке делить и умножать, если нет скобок — не имеет значения. В школе вроде так объясняли
+2
NickLion, #
Это не с программированием связано, а с математикой. В математике A∙B:C∙D = ((A∙B):C)∙D. И нам так объясняли ещё в школе. С программированием учителя ни разу связаны не были. Так что мимо.
0
spmbt, #
В учебнике математики 2-го класса, действительно, учат так:
s60.radikal.ru/i167/1103/83/218cec616733.png
(Петерсон.) Используют знак ":" (двоеточие).
Но это же не отменяет факта, что в научных статьях при строчной записи через "/" и при отсутствующем знаке умножения порядок умножений другой? И, насколько помню, всегда, в алгебре при преобразовании сложных выражений соблюдалось (в школе тоже) правило приоритета умножения перед делением. Например 2ab/3(x+y) означало 2ab/(3(x+y)). А если запишем для наглядности 2ab/3·(x+y), это будет уже (2ab/3)·(x+y)? Нет, насколько помню, в школе писали и считали по первому случаю, 2ab/(3·(x+y))
0
general, #
Я бы перефразировал ваше утверждение:
в научных статьях при строчной записи через "/" и при отсутствующем знаке умножения порядок умножения другой, но это не отменяет того факта, что в учебнике математики 2-го класса A∙B:C∙D = ((A∙B):C)∙D.

Количество людей прочитавших одну научную статью по математике или физике будет около 1% населения. А количество прочитавших учебник математики за второй класс — близко к 100%.

Есть стандартная(школьная) запись деления с помощью символа "÷", и выражение a·b÷c·d выполняется в порядке ((a·b)÷c)·d

Книжная запись — ab/cd — это однострочный вариант записи дроби, когда в числителе a·b, а в знаменателе c·d. И порядок выполнения операций тут характерный для дроби (a·b)÷(c·d)
+3
spmbt, #
+ переместите статью, пожалуйста из персональных блогов в открытый всему миру блог (она доказала свою ценность рейтингом). В Персональных её не увидят неавторизованные (это весь интернет) и сейчас посетит в 6 раз меньше народа, чем в блоге «Алгоритмы» или «Ненормальное программирование».
0
LeoMat, #
Просто я не думаю, что он относится как-то к этим блогам, для первого он не соответствует уровню блога, для второго в нем нет ничего ненормального и brainfuck-овского, как в последнее время там водится. Когда думал разместить просто в занимательных задачах, то тут же был заминусован, скорее всего за то, что там непривычно сразу видеть какой-то ответ :)
0
LeoMat, #
Но в итоге (действительно, чтобы больше людей, кому понадобится) прочитало, опубликовал в Алгоритмах. Надеюсь, с предыдущими комментариями будет понятнее как она здесь оказалась.
+1
Mezomish, #
>А можете попробовать сами в уме или на бумаге найти хотя бы одно из 167 решений для нуля.

Комментарии ещё не читал (может в них уже дали подобный ответ), но решение нашёл буквально за несколько секунд:

1*2-3-4+5+6-7-8+9 == 0
0
LeoMat, #
>>> 1*2-3-4+5+6-7-8+9 == 0
True

Excellent! Правда, из всевозможных целых найти для него решение проще всех. А других решительных ответов что-то невидно.
0
spmbt, #
Ещё подумал секунд 30, и получил:
1*2*3*4 — 5*6 +7+8-9
Использовав подсказки отсюда: игру «24» и то, что 5*6=30, 7+8=15, и 9.
0
LeoMat, #
1+2+3+4-56/7/8-9
Помня эту десятку из четырех и о способе получения единицы дробью.
–2
Tibr, #
У Вас пытливый ум, но он занимается бесполезными вещами :)
0
Tibr, #
Кстати, для этого задания можно придумать еще кое-что более «извращенное»: рассмотреть вероятностную модель случайного блуждания по ряду вещественных чисел.

1) Стартует случайное блуждание в точке 0.
2) Возможные траектории определяются цифрами, числами, состоящими из этих цифр и возможных операций над ними.
3) Оценивать нужно вероятность остановки траектории в числе равном тому, что у вас в правой части.

Математических выкладок, чувствую, будет немеряно, но теорию построить можно :)
+1
LeoMat, #
Не подумайте, что я это всерьез каким-то боком. Довольно шутливый тон задан теми же картинками и общим содержанием статьи. Это не более чем очередное развлечение, направленное на развитие устного счета, подстрекаемого завлекательной постановкой задачи :)
+1
Tibr, #
Я понимаю, я просто это к тому, что можно было потратить время с бОльшей пользой.
Насчет улучшения навыков устного счета могу порекомендовать неплохую книженцию: Считайте в уме как компьютер, Билла Хэндли
0
LeoMat, #
Да, знаю эту книгу. Но и в ней говорится, что если вы хорошо знаете таблицу умножения или проделывали много раз подобные операции, то вы можете пользоваться ей там, где удобно, указанным «улучшенным» способам подсчета это не повредит.

А в длине и долготе большой шутки можно увидеть и почувствовать какой-то новый обертон, о котором никогда не знал. Не думаю, что все надо стараться делать с «с бОльшей пользой» и что кто-то может объективно определить, дало это в итоге бОльшую или меньшую пользу, и тем более, насколько это важно.
0
Tibr, #
Арифметика вообще необъятна, но это же не причина постоянно складывать или вычитать числа.
Польза примера в разминке для мозга, ни больше ни меньше, это моё субъективное мнение.

Вот если бы рассмотреть случайное блуждание (которое я описал выше), то можно было бы строго объяснить суть вещей — почему всё так, как получается на практике.
0
LeoMat, #
Или превратит шутку в паранойю.
0
Doktor_Gradus, #
Например, как ответить на вопрос — почему для числа 100 существует 101 решение, для числа 909 — 7 решений, а для 910 — ни одного? И почему именно столько?
НЛО прилетело и опубликовало эту надпись здесь
0
LeoMat, #
Для каких чисел? И зачем вам это?
НЛО прилетело и опубликовало эту надпись здесь
0
LeoMat, #
Какой вам нужен формат:
выражение, число
или
число, сколько_раз_это_число_повторяется
НЛО прилетело и опубликовало эту надпись здесь
0
LeoMat, #
И правда. Только строчек очень много, так что:
narod.ru/disk/7015094001/make_a_hundred.zip.html
+1
guyfawkes, #
Задачка-то уже не нова, на самом деле, вот нашел такое решение: http://lesliesteward.com/2010/02/little-program-to-use-integer-math-to.php. В быстром переводе на яваскрипт решение у меня нашло для числа 100 все то же 101 решение, а время выполнения под win 7 x64, quad 2,4, 8gb ddr2, chrome 9.0 — 7606 мс.
Также в интернете, действительно, предлагают использовать преобразование чисел в другую систему счисления, с основанием равным числу элементов в массиве (например, тут — http://www.codinghorror.com/blog/2010/02/the-nonprogramming-programmer.html в самом низу страницы для трех операций переводится в систему по основанию 3).
0
LeoMat, #
Я рад, что результат моего решения подтвердилось уже 2 раза. А перебор реализовал через преобразование основания чисел, потому что просто не придумал другого более простого способа необходимого перебора.
0
guyfawkes, #
Кстати, хотел добавить: вывод кусками подтормаживает. Если сохранять все в массив, а вывести его потом, то можно сэкономить 0,5 секунды, что уже неплохо.
0
LeoMat, #
Но так за результатом следить интереснее.
0
Doktor_Gradus, #
Если бы имело это практическое значение… А так, ну полсекунды, ну и что.
0
guyfawkes, #
Тут уже что в топике, что ниже, что выше вашего комментария говорится, что топик не несет практической нагрузки. Just for fun, просто эксперименты.
+2
Speedimon, #
Накидал по-быстрому на Powershell, немного дикий вариант без рекурсии правда получился, зато компактно, с подсветкой кода правильной не знаю как быть, подскажите если кто знает, кстати. В первых двух строках можно менять операции и исходный ряд чисел если вдруг понадобится.

$nums="123456789"; $levels=$nums.length-1;
$op="","+","*","/","-";$ops=$op.count
$found=0
$powers=@()
($levels-1)..0 | %{$powers += [Math]::Pow($ops,$_)}
0..[Math]::Pow($ops,$levels) | %{
    $i=$_;$str=""
    0..($levels-1) | %{
        $str+=$nums[$_]
        $str+=$op[([Math]::floor($i/$powers[($_)]))]; $i=$i % $powers[($_)]
        }
    $str+=$nums[$levels]
    if ([double](Invoke-Expression $str) -eq 100) {$str;++$found}
    }
write "Found solutions:" $found
0
Speedimon, #
Вот второй вариант подоспел, более вменяемый. Тут подход такой — формируется массив всех возможных строк, затем сравнивается выражение с искомым. В процессе выяснился один нюанс. Изначально массивы декларировались как $a=@(), и для добавления в массив использовалось $a=+. Работало это все дико медленно. Декларирование массива как объект типа System.Collections.ArrayList увеличило скорость обработки в разы (хотя тоже вроде динамический массив задаем). Замена добавления в массив на метод Add() также увеличила еще раз скорость в разы. В результате этот вариант работает раз в 5-10 (субъективно, не засекал) только из-за синтаксиса касающегося массивов.

$nums="123456789"; $levels=$nums.length-1;
$ops="","+","*","/","-"
$a = $b = $results = New-Object System.Collections.ArrayList
$a = $nums[$levels]
($levels-1)..0 | %{
    $b.Clear()
    foreach ($op in $ops) { write $_
        $add=$nums[$_] + $op
        foreach ($obj in $a) {
            $b.Add($add + $obj)|out-null
            }
        }
    $a=$b
    }
foreach ($result in $b) {
    if ([double](Invoke-Expression $result) -eq 100) {$results+=$result}
    }
$results
write "Found solutions:" $results.count
0
seriyPS, #
> Я не учился программированию, и реализовал задачу, как придумал. Поэтому у меня есть вопрос: «Как это можно было сделать лучше?».

Ну я бы как минимум использовал числа а не строки для предстваления чисел и заменил бы eval на свитч (последовательность elif -ов). Размер кода немного увеличился бы, но работать должен быстрее. Если заставлю себя, то попробую подправить…
0
seriyPS, #
Хотя не, что-то ваш код заметно упростить у меня не получается без значительных изменений.
+1
LeoMat, #
А жаль, я чувствую, что все можно сделать проще и быстрее.
–2
mr47, #
Я конечно все понимаю, но зачем простые задачи по типу этой превращать в что-то чрезвычайное, люди разучились «знать» такие алгоритмы, тонкости их, давайте каждый сделает много графиков и напишет фибоначи на brainfuck (хотя это интересная задумка). И пуская меня минусуют, этот топик не заслуживает и бублика.
+1
LeoMat, #
А здесь и нет ничего чрезвычайного, во многих местах текста и комментариев подкинуты намеки на шуточность этого тона. И в Алгоритмы этот текст попал (а мог попасть и в Ненормальное программирование) лишь по просьбе того, чтобы она оказалось более доступной людям. Лежала она себе спокойно в Персональных блогах, и никого не раздражала.

Все, кроме описания задачи, кода и предложения улучшить его, здесь шутка.
+1
mr47, #
Это было в 4 утра поэтому вы попали под сонную голову и горячую руку.
0
hx0, #
Можете ещё степени добавить)
+2
lany, #
А ещё квадратные корни и логарифмы =) Тогда вообще абсолютно любое натуральное число можно будет тремя двойками представить :-)
1 = log_2 (log_2(sqrt(2)))
2 = log_2 (log_2(sqrt(sqrt(2))))
3 = log_2 (log_2(sqrt(sqrt(sqrt(2)))))
4 = log_2 (log_2(sqrt(sqrt(sqrt(sqrt(2))))))
+1
lany, #
Минусики в начале забыл :-)
+1
LeoMat, #
Задача была поставлена, что операции можно ставить только между символами. Это множество можно расширить еще проще включив вначале символ нуля, тогда добавляются и 0-1..., 0*1.
0
Vayun, #
1-23^4+5+6^7+8-9

12^3/4-5-6*7*8+9

:-P
+1
Stepler, #
В своё время Дирак и Ландау играли в такую игру (Лев Давыдович показал её Дираку, вернее, показал традицию надеяться на «счастливый билет», а Дирак решил её усложнить, чтобы каждый билет стал «счастливым»), надо было путём арифметики приравнять комбинации первых трёх чисел и последующих в автобусных (трамвайных, тролейбесных) билетах. Тривиальный случай, это всем известный «счастливый билейт». Позже Дирак написал универсальную функцию приравнивания. К сожалению эту функцию не помню. Но всегда получая на руки билет пытаюсь играть в эту игру и скоротать время поездки.
0
sielover, #
Помнится, еще на первом курсе писал очень схожую реализацию этого на паскале, только без умножения и деления. То есть для данного числа найти его разложение в ряд *1*2*3*4*5*6*7*8*9, где вместо * может стоять плюс, минус либо ничего. Сейчас такое на JS пишется на одном дыхании, вроде:

s = [1,2,0,2,0,1,0,0,0]; // Двоичное представление числа от 0 до 243<sup>2</sup>-1
v = [1,2,3,4,5,6,7,8,9];
g = [];
for (i=0;i<9;i++){
  if(s[i]==1);
    g.push("-");
  else
 if (s[i] ==2)
    g.push("+");
 g.push(v[i]);
}
result = eval(g.join("")); 

но тогда задача далась мне с огромным трудом.
0
guyfawkes, #
Честно говоря, не понял вот эту штуку: s = [1,2,0,2,0,1,0,0,0]; // Двоичное представление числа от 0 до 2432-1
Поясните, если не затруднит.
0
sielover, #
Эм. Малость ошибся. Не двоичное, а троичное.
Это для того, чтобы обойти все возможные варианты подстановки * в строку *1*2*3*4*5*6*7*8*9
Поскольку
(0..2432-1)10 = (000000000..222222222)3, то
— циклически обхожу числа 0..2432-1;
— каждое перевожу в троичную систему;
— каждую цифру полученного троичного числа сопоставляю соответствующеу значению *: 0 — ничего, 1 — «минус», 2 — «плюс».
Получаю готовую строку, которая выполняется eval'ом.
0
guyfawkes, #
Ясно, спасибо. Тоже подумал, что скорее всего троичное, но решил дождаться вашего ответа.
0
monkegoist, #
Да, мне тоже не понятно двоичное представление с двойкой.
0
Vayun, #
С минусом 61 решение
-123-4+5*6*7+8+9
-123+45*6-7*8+9
<...cut...>
-1/2-3+45/6+7+89
-1/2*34+5*6+78+9
0
Vayun, #
Довольно распространенный случай скобок: калькулятор с неправильным приоритетом операций (практически все «обычные» калькуляторы + калькулятор windows в простом режиме)

Без минуса впереди 68 решений, с минусом 35

Примеры:
(((((((1)/2)-3)*4)/5)+6)+7)+89
(((((((1)+2)+3)-4)+5)/6)*78)+9

(((((-1)+23)*4)/56)*7)+89
((((((((-1)*2)/3)-4)*5)/6)+7)+8)*9

Некоторые решения совпадают с решениями с нормальным приоритетом:
((((((1)/2)/3)*456)+7)+8)+9
0
Robotex, #
Интересное исследование :) Уже опубликовали?
0
monkegoist, #
Наконец дописал вариант для Java. Можно глянуть тут — dumpz.org/39029/.

Пытался решить рекурсией, никак не получается… Проблема в том, что надо помимо значения как-то сохранить путь, которым оно было получено.
0
LiveStalker, #
На эрланге. Самой затратной по времени является часть eval, где собранное эрланговское выражение (например: 123-45-67+89.) вычисляется. А генерация размещений с повторениями и генерация строк для вычисления происходит достаточно быстро.
-module(test).
-export([find/0]).

perms(L, 0, N) ->
	L;
perms(L, K, N) ->
	perms([ [X|Lx] || X <- N, Lx <- L], K-1, N).

make_str(Nums, [], Res) ->
	Res;
make_str(Nums, [H_op|T_op], Res) ->
	S = lists:concat(lists:zipwith(
                   fun(X, Y) -> lists:concat([X,Y]) end, 
                   Nums, H_op)),
	make_str(Nums, T_op, [S|Res]).

eval([], Count) ->
	Count;
eval([H_exp|T_exp], Count) ->
	{ok, Tokens, _} = erl_scan:string(H_exp),
	{ok, [Form]} = erl_parse:parse_exprs(Tokens),
	{value, Res, _} = erl_eval:expr(Form, []),
	if
		Res == 100 ->
			io:format("~p = ~p~n", [H_exp, Res]),
			eval(T_exp, Count+1);
		true ->
			eval(T_exp, Count)
	end.

find() ->
	statistics(wall_clock),
	Nums = [1,2,3,4,5,6,7,8,9],
	Op = ['', '-', '+', '*', '/'],
	Ops = perms([['.']], 8, Op),
	Expr = make_str(Nums, Ops, []),
	io:format("Count: ~p~n", [eval(Expr, 0)]),
	{_, Time} = statistics(wall_clock),
        io:format("Time=~p~n" , [Time / 1000]).	
+2
hellman, #
Немного переработал :) Пытался сделать покороче, вышло и побыстрее чуток (15 сек против 21)
#!/usr/bin/env python
#-*- coding:utf-8 -*-

from __future__ import division
from itertools import product

sum_num = 100
count =  0

digits = '123456789'
signs = '', '+', '-', '*', '/'
atoms = [map(lambda x: d + x, signs) for d in digits[:8]]

for indexes in product(range(5), repeat=8):
    expr = "".join( [ atoms[i][indexes[i]] for i in range(8) ] )
    expr += '9'
    if eval(expr) == sum_num:
        print('{0} = {1}'.format(expr, sum_num))
        count += 1
 
print 'So, {0} expressions for {1}'.format(count, sum_num)</code>
0
LeoMat, #
Спасибо, отличное решение! product() как раз то, что мне было нужно и о чем я не знал.
0
hellman, #
А еще у вас range(int('44444444', 5)) не сделает последнюю итерацию ;) Ну это так, к слову.
0
LeoMat, #
Да, я знаю, как и любой range, просто изначально думал только про 100 :)

Только зарегистрированные пользователи могут оставлять комментарии.
Войдите, пожалуйста.