Comments 114
Я вас поздравляю, вы придумали свой вариант игры 24
Что-то поискав, не смог найти такой игры. Может быть, вы ее опишите?
www.24game.com/ вот она.
Условия игры — даны 4 произвольных цифры
Цель игры — с помощью всяких арифметических операция получить из них число 24
Например: даны 1,2,3,4 24 = 1 * 2 * 3 * 4
Условия игры — даны 4 произвольных цифры
Цель игры — с помощью всяких арифметических операция получить из них число 24
Например: даны 1,2,3,4 24 = 1 * 2 * 3 * 4
Спасибо.
честно говоря не знал про 24, меня отец в детстве научил из 6 цифр на автобусном билете получать 100…
а я упростил игру до пока едет машина в поле зрения — успеть получить число 10 из цифр номера…
а я упростил игру до пока едет машина в поле зрения — успеть получить число 10 из цифр номера…
UFO just landed and posted this here
я тоже билетики считаю :)
аналогично, только придумал сам эту игру, а так как поездки были длинные, то искал решения для 100, 99 и 101 (по возрастанию трудности)
так как 99 — нечетное число, то решений меньше
101 — простое число
так как 99 — нечетное число, то решений меньше
101 — простое число
этим занимайтесь, пожалуйста, только на пассажирском сидении…
Самое интересное, что помню из таких задачек — получить 24 из 1,3,4,6. (можно использовать +-*/ и скобки).
А переставлять можно? Если да — 6/(1-3/4). Если нет — пока не получается.
Правильно.
Мы в такое иногда тоже играем, но операций побольше — есть степень, корень, факториал и десятичные дроби (конечные и периодические). Обычно задача — получить текущий год из минимального числа одинаковых цифр.
Например, (.(2)-.2)^(-2)-sqrt(2/.(2))/.2 = 2010
Например, (.(2)-.2)^(-2)-sqrt(2/.(2))/.2 = 2010
«та победа повлияла на мое будущее становление»
Развеселили.
Да это то все понятно давно. Практической пользы увы никакой. Если смотреть в сторону сжатия информации — то опять-таки нужно хранить последовательность операций, числа (однозначное-двухзначное) и тд. Получается что на выходе будет информации еще больше чем было. А больше я не знаю зачем оно все это нужно. Да и вообще, 123456789 последовательность встречается крайне редко.
Конечно. Ведь я и не искал никакой пользы для сжатия информации. Я искал лишь удовлетворение личного математического (или пусть даже арифметического) любопытства, коего и достиг, о котором и написал. По крайней мере три вопроса, которые я хотел решить таким образом и решил:
1) Сколько решений найдется для наиболее известной задачи числа ста?
2) Действительно ли предполагаемый 0 должен обладать наибольшим числом вариаций?
3) Действительно ли можно все целые числа до 100 так представить?
Мне просто это было интересно. Может быть, этим может когда-то заинтересоваться кто-то еще, возможно даже для какого-то неожиданного практического применения, поэтому я описал свои действия.
1) Сколько решений найдется для наиболее известной задачи числа ста?
2) Действительно ли предполагаемый 0 должен обладать наибольшим числом вариаций?
3) Действительно ли можно все целые числа до 100 так представить?
Мне просто это было интересно. Может быть, этим может когда-то заинтересоваться кто-то еще, возможно даже для какого-то неожиданного практического применения, поэтому я описал свои действия.
Чаще всего в паролях
А слабо найти первое число в натуральном ряду, которое не может быть вычислено таким способом? :)
Может быть вариация: ставить перед 1 минус или нет.
Может быть вариация: ставить перед 1 минус или нет.
Сколько времени занимает расчёт одного числа (например, 100)?
Написал сейчас на JS (т.к. Пайтон не установлен и не знаю), полный расчёт по 1 числу в Хроме (проц e2180) занял 67 секунд (390625 циклов с таким же eval() ).
Потенциальные ошибки вашего алгоритма: не проверяется деление на 0 (но тут его, «к счастью», нет), и не проверяется в строчке «if eval(expr) == sum_num:» эпсилон-окружение результата — от округления могло получиться что-то типа 100.000001 или 99.99999987. Но с числом 100 это тоже, видимо, обошлось, у меня тоже ответ 101.
Написал сейчас на JS (т.к. Пайтон не установлен и не знаю), полный расчёт по 1 числу в Хроме (проц e2180) занял 67 секунд (390625 циклов с таким же eval() ).
Потенциальные ошибки вашего алгоритма: не проверяется деление на 0 (но тут его, «к счастью», нет), и не проверяется в строчке «if eval(expr) == sum_num:» эпсилон-окружение результата — от округления могло получиться что-то типа 100.000001 или 99.99999987. Но с числом 100 это тоже, видимо, обошлось, у меня тоже ответ 101.
Да, деление на ноль и бессмысленно проверять, потому что единственная операция, которая могла его обеспечить при таком порядке чисел, это скобки. С ошибками дело обстоит так:
Получить случай эпсилон-разницы с большей точностью для данной последовательности мне хотя бы интуитивно кажется невозможным. Но и судя по просмотренным результатам для той же сотни, все дроби оказываются верны, и этим, скажем, наиболее забавны :).
Обработка занимает 55 секунд.
>>> 100 == 100.0
True
>>> 100 == 100.00000000000001
False
>>> 100 == 99.9999999999999
False
Получить случай эпсилон-разницы с большей точностью для данной последовательности мне хотя бы интуитивно кажется невозможным. Но и судя по просмотренным результатам для той же сотни, все дроби оказываются верны, и этим, скажем, наиболее забавны :).
Обработка занимает 55 секунд.
На каком процессоре? Получается, что на слабеньком e2180 Javascript в Хроме считает практически с той же скоростью.
Celeron D 336.
Этот раза в 3 слабее, но при вычислениях с P-кодами разница будет не столь заметна.
Я не очень программист, мне непонятно что это.
Ну Пайтон же и JS компилируются в P-код (закодированные операторы), которые потом исполняется через быструю интерпретацию (в Хроме уже вроде JIT-компиляция). Поэтому в исполнении больше логики, чем расчётов, поэтому вычислительная мощность процессора используется не так сильно, чем если бы это был компилированный код. Можно предполагать, что разница будет не в 3 раза, а меньше, но всё равно Пайтон считает раза в 2-3 быстрее, чем браузер.
И ещё, самая главная ошибка. У многих, если не у всех, языков приоритет деления ненормальный: равный с умножением. У людей деление слабее умножения. Для проверки, посчитайте, сколько будет alert( 10*10 / 5*5 ); в языке и у людей. У людей — 4 (потому что 10 * 10 / (5 * 5) ), в JS, например, 100, потому что считается (10*10/5)*5. Поскольку задача — из мира людей, то предполагается, что считаем выражение по-людски. Значит, нам придётся расставлять скобки.
Я никогда не слышал о приоритете умножения над делением в мире людей. Вы просто группируете скобками операции: (10*10)/(5*5) вместо 10*10/5*5, а скобки в задаче не предполагаются.
Вы думаете, что это «по-человечески», поскольку сравниваете значок слэша со знаком дроби, а не знаком деления (в виде двоеточия или знака обелюса ÷), который как раз более свойственен миру людской арифметики. Так что никакой ошибки в этом нет.
Вы думаете, что это «по-человечески», поскольку сравниваете значок слэша со знаком дроби, а не знаком деления (в виде двоеточия или знака обелюса ÷), который как раз более свойственен миру людской арифметики. Так что никакой ошибки в этом нет.
Ну, конечно, как автор поставит задачу, так и будет. :) Но в том и дело, что операция деления пошла с алгоритмических языков, а раньше всегда применяли деление-двоеточие с более слабым приоритетом. Достаточно посмотреть, как пишут формулы в научных статьях. Для проверки, открыл «Гидродинамику» Ландау-Лифшица, и вижу там, например, m2/mr3. Тут фокус в отсутствии знака "*" на месте умножения, но почему мы должны думать иначе? Если мишем цифры, то приходится ставить умножение-точку, но при этом не вводим скобок из-за появившихся точек: 2·3/4·5, это значит 2·3/(4·5).
(Нет, всё же, поставьте тему в другой блог, не пожалеете, придут нормальные читатели :) (хотя да, 8 марта), она будет на главной. И рассудят с приоритетами операций.)
(Нет, всё же, поставьте тему в другой блог, не пожалеете, придут нормальные читатели :) (хотя да, 8 марта), она будет на главной. И рассудят с приоритетами операций.)
Я и говорю, что вы понимаете здесь под знаком /, которым я обозначаю деление, также как * означает точку умножения. Неужели, если бы вы писали 2·3÷4·5, то вам бы так же хотелось получить то же самое? Или если считать на калькуляторе, и вводить последовательно знаки умножения деления, то есть какая-то разница?
Я правда в том первом варианте, что вы предложили посчитал также 10·10:5·5 и получил 100, потому что нет скобок и нет приоритета, также как нет приоритета у сложения или вычитания.
И я уже переместил :)
Я правда в том первом варианте, что вы предложили посчитал также 10·10:5·5 и получил 100, потому что нет скобок и нет приоритета, также как нет приоритета у сложения или вычитания.
И я уже переместил :)
Первый раз слышу про «человеческий» приоритет, честно. Ваша формула на «моём человеческом» читается как 10 умножить на 10 разделить на 5 умножить на 5 и никак иначе = 100, причем последние две операции сразу сокращаются как взаимоисключающие. Возможно у меня какой то другой мозг, ближе к роботам уже :)
Вот, у меня в голове чипы сработали точно также.
Совершенно верно, это следствие знания программирования :). И калькуляторы — то же самое. Не думал даже, что о нормальном порядке деления настолько забудут.
(Сейчас допиливаю алгоритм расставления скобок. Интересно будет посмотреть, что получится. Но это точно уже не будет ответ 101.)
(Сейчас допиливаю алгоритм расставления скобок. Интересно будет посмотреть, что получится. Но это точно уже не будет ответ 101.)
Если вводить скобки, то и не забудьте про вариацию с минусом перед 1, или если уж быть совсем полными (или что там еще возможно), то можно и забыть даже про -1, а просто добавить еще к цифрам вначале 0.
И был бы очень рад увидеть сами варианты для такого скобочного решения, так что жду!
И был бы очень рад увидеть сами варианты для такого скобочного решения, так что жду!
Готово. Для числа 100 получился ответ 99, а считало на e2180 — 66 секунд.
Код:
Код:
… Какой-то сбой.
Код:
Скобок получилось немного, что-то ушло, что-то добавилось.
Распечатка: paste.org/pastebin/view/29878
Если надо посчитать без скобок, в цикле for(var i =0; i <=8; i++){} оставляют только s += s0.charAt(i) + a[x0[i]]; и убирают if(wasLeftPar) s+= ')';
Код:
//поиск решений задачи: из 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+= ')';
Не понимаю, почему со скобками получается меньше решений, если это наоборот добавляет возможности получить 100 и почему они не начинают группировать операции сложения и вычитания.
Нет, что-то добавляется, а что-то исчезает. Случайные флуктуации.
Добавил проверку с минусом впереди.
Ответов стало 150, а считалось 138 секунд.
Доп. код — это 3 строчки:
Добавил проверку с минусом впереди.
Ответов стало 150, а считалось 138 секунд.
Доп. код — это 3 строчки:
eval(s.replace(/=/,'=-'));
if(sum > 99.999 && sum < 100.001)
console.log(++nn, n, s.replace(/=/,'=-'), sum);
Это как это «что-то исчезает»?! Множество ответов задачи со скобками, очевидно, полностью включает все ответы без скобок.
Ответы без скобок — это то же, что ответы с другим порядком скобок. Ушедшие решения легко найти. Они обязательно содержат /\/\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 годах, да и сейчас не исключены.
Вот они, ушедшие 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 годах, да и сейчас не исключены.
Re: посмотрите в книги по математике и физике;
посмотрите в учебнике по математике за 1-2 класс :)
Есть стандартная школьная запись деления с помощью символа "÷", и выражение a·b÷c·d выполняется в порядке ((a·b)÷c)·d
Книжная запись — ab/cd — это однострочный вариант записи дроби, когда в числителе a·b, а в знаменателе c·d. И порядок выполнения операций тут характерный для дроби (a·b)÷(c·d)
Что касается программирования, то тут все достаточно просто: символом "*" в языках программирования обозначается математическая операция "·"(умножение), а символом "/" математическая операция "÷"(деление), но никак не запись дроби.
посмотрите в учебнике по математике за 1-2 класс :)
Есть стандартная школьная запись деления с помощью символа "÷", и выражение a·b÷c·d выполняется в порядке ((a·b)÷c)·d
Книжная запись — ab/cd — это однострочный вариант записи дроби, когда в числителе a·b, а в знаменателе c·d. И порядок выполнения операций тут характерный для дроби (a·b)÷(c·d)
Что касается программирования, то тут все достаточно просто: символом "*" в языках программирования обозначается математическая операция "·"(умножение), а символом "/" математическая операция "÷"(деление), но никак не запись дроби.
Верно.
Значит, вопрос стоит, как сформулировать задачу: как запись дроби в строке или как операцию деления в математике? И тот, и тот подход имеет право на существование, потому что 345/67 = не что иное, как дробь, а 345/67*89 — строчная запись решения математической формулы, в которой не поставить знак умножения мы не можем. Поэтому автор поискал решение с вычислительной операцией деления (как в алг.языках и в учебнике за 2-й класс), а я привёл аналогичное решение с операцией, аналогичной строчной записи деления (в формулах).
Значит, вопрос стоит, как сформулировать задачу: как запись дроби в строке или как операцию деления в математике? И тот, и тот подход имеет право на существование, потому что 345/67 = не что иное, как дробь, а 345/67*89 — строчная запись решения математической формулы, в которой не поставить знак умножения мы не можем. Поэтому автор поискал решение с вычислительной операцией деления (как в алг.языках и в учебнике за 2-й класс), а я привёл аналогичное решение с операцией, аналогичной строчной записи деления (в формулах).
А при чем здесь знание программирования? умножение и деление — коммутативные операции, т.е. без введения скобок их операнды можно переставлять произвольным образом -> 10*10/5*5 == 10/5*10*5 == 10*5*10/5. То, что вы в этой формуле приделали скобки — так это вы другую формулу просто получили, очень так по человечески :)
Это не с программированием связано, а с математикой. В математике A∙B:C∙D = ((A∙B):C)∙D. И нам так объясняли ещё в школе. С программированием учителя ни разу связаны не были. Так что мимо.
В учебнике математики 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))
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))
Я бы перефразировал ваше утверждение:
в научных статьях при строчной записи через "/" и при отсутствующем знаке умножения порядок умножения другой, но это не отменяет того факта, что в учебнике математики 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)
в научных статьях при строчной записи через "/" и при отсутствующем знаке умножения порядок умножения другой, но это не отменяет того факта, что в учебнике математики 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)
+ переместите статью, пожалуйста из персональных блогов в открытый всему миру блог (она доказала свою ценность рейтингом). В Персональных её не увидят неавторизованные (это весь интернет) и сейчас посетит в 6 раз меньше народа, чем в блоге «Алгоритмы» или «Ненормальное программирование».
Просто я не думаю, что он относится как-то к этим блогам, для первого он не соответствует уровню блога, для второго в нем нет ничего ненормального и brainfuck-овского, как в последнее время там водится. Когда думал разместить просто в занимательных задачах, то тут же был заминусован, скорее всего за то, что там непривычно сразу видеть какой-то ответ :)
Но в итоге (действительно, чтобы больше людей, кому понадобится) прочитало, опубликовал в Алгоритмах. Надеюсь, с предыдущими комментариями будет понятнее как она здесь оказалась.
>А можете попробовать сами в уме или на бумаге найти хотя бы одно из 167 решений для нуля.
Комментарии ещё не читал (может в них уже дали подобный ответ), но решение нашёл буквально за несколько секунд:
1*2-3-4+5+6-7-8+9 == 0
Комментарии ещё не читал (может в них уже дали подобный ответ), но решение нашёл буквально за несколько секунд:
1*2-3-4+5+6-7-8+9 == 0
>>> 1*2-3-4+5+6-7-8+9 == 0
True
Excellent! Правда, из всевозможных целых найти для него решение проще всех. А других решительных ответов что-то невидно.
True
Excellent! Правда, из всевозможных целых найти для него решение проще всех. А других решительных ответов что-то невидно.
У Вас пытливый ум, но он занимается бесполезными вещами :)
Кстати, для этого задания можно придумать еще кое-что более «извращенное»: рассмотреть вероятностную модель случайного блуждания по ряду вещественных чисел.
1) Стартует случайное блуждание в точке 0.
2) Возможные траектории определяются цифрами, числами, состоящими из этих цифр и возможных операций над ними.
3) Оценивать нужно вероятность остановки траектории в числе равном тому, что у вас в правой части.
Математических выкладок, чувствую, будет немеряно, но теорию построить можно :)
1) Стартует случайное блуждание в точке 0.
2) Возможные траектории определяются цифрами, числами, состоящими из этих цифр и возможных операций над ними.
3) Оценивать нужно вероятность остановки траектории в числе равном тому, что у вас в правой части.
Математических выкладок, чувствую, будет немеряно, но теорию построить можно :)
Не подумайте, что я это всерьез каким-то боком. Довольно шутливый тон задан теми же картинками и общим содержанием статьи. Это не более чем очередное развлечение, направленное на развитие устного счета, подстрекаемого завлекательной постановкой задачи :)
Я понимаю, я просто это к тому, что можно было потратить время с бОльшей пользой.
Насчет улучшения навыков устного счета могу порекомендовать неплохую книженцию: Считайте в уме как компьютер, Билла Хэндли
Насчет улучшения навыков устного счета могу порекомендовать неплохую книженцию: Считайте в уме как компьютер, Билла Хэндли
Да, знаю эту книгу. Но и в ней говорится, что если вы хорошо знаете таблицу умножения или проделывали много раз подобные операции, то вы можете пользоваться ей там, где удобно, указанным «улучшенным» способам подсчета это не повредит.
А в длине и долготе большой шутки можно увидеть и почувствовать какой-то новый обертон, о котором никогда не знал. Не думаю, что все надо стараться делать с «с бОльшей пользой» и что кто-то может объективно определить, дало это в итоге бОльшую или меньшую пользу, и тем более, насколько это важно.
А в длине и долготе большой шутки можно увидеть и почувствовать какой-то новый обертон, о котором никогда не знал. Не думаю, что все надо стараться делать с «с бОльшей пользой» и что кто-то может объективно определить, дало это в итоге бОльшую или меньшую пользу, и тем более, насколько это важно.
Арифметика вообще необъятна, но это же не причина постоянно складывать или вычитать числа.
Польза примера в разминке для мозга, ни больше ни меньше, это моё субъективное мнение.
Вот если бы рассмотреть случайное блуждание (которое я описал выше), то можно было бы строго объяснить суть вещей — почему всё так, как получается на практике.
Польза примера в разминке для мозга, ни больше ни меньше, это моё субъективное мнение.
Вот если бы рассмотреть случайное блуждание (которое я описал выше), то можно было бы строго объяснить суть вещей — почему всё так, как получается на практике.
UFO just landed and posted this here
Для каких чисел? И зачем вам это?
UFO just landed and posted this here
Какой вам нужен формат:
или
выражение, число
или
число, сколько_раз_это_число_повторяется
UFO just landed and posted this here
И правда. Только строчек очень много, так что:
narod.ru/disk/7015094001/make_a_hundred.zip.html
narod.ru/disk/7015094001/make_a_hundred.zip.html
Задачка-то уже не нова, на самом деле, вот нашел такое решение: 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).
Также в интернете, действительно, предлагают использовать преобразование чисел в другую систему счисления, с основанием равным числу элементов в массиве (например, тут — http://www.codinghorror.com/blog/2010/02/the-nonprogramming-programmer.html в самом низу страницы для трех операций переводится в систему по основанию 3).
Я рад, что результат моего решения подтвердилось уже 2 раза. А перебор реализовал через преобразование основания чисел, потому что просто не придумал другого более простого способа необходимого перебора.
Кстати, хотел добавить: вывод кусками подтормаживает. Если сохранять все в массив, а вывести его потом, то можно сэкономить 0,5 секунды, что уже неплохо.
Накидал по-быстрому на 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
Вот второй вариант подоспел, более вменяемый. Тут подход такой — формируется массив всех возможных строк, затем сравнивается выражение с искомым. В процессе выяснился один нюанс. Изначально массивы декларировались как $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
> Я не учился программированию, и реализовал задачу, как придумал. Поэтому у меня есть вопрос: «Как это можно было сделать лучше?».
Ну я бы как минимум использовал числа а не строки для предстваления чисел и заменил бы eval на свитч (последовательность elif -ов). Размер кода немного увеличился бы, но работать должен быстрее. Если заставлю себя, то попробую подправить…
Ну я бы как минимум использовал числа а не строки для предстваления чисел и заменил бы eval на свитч (последовательность elif -ов). Размер кода немного увеличился бы, но работать должен быстрее. Если заставлю себя, то попробую подправить…
Я конечно все понимаю, но зачем простые задачи по типу этой превращать в что-то чрезвычайное, люди разучились «знать» такие алгоритмы, тонкости их, давайте каждый сделает много графиков и напишет фибоначи на brainfuck (хотя это интересная задумка). И пуская меня минусуют, этот топик не заслуживает и бублика.
А здесь и нет ничего чрезвычайного, во многих местах текста и комментариев подкинуты намеки на шуточность этого тона. И в Алгоритмы этот текст попал (а мог попасть и в Ненормальное программирование) лишь по просьбе того, чтобы она оказалось более доступной людям. Лежала она себе спокойно в Персональных блогах, и никого не раздражала.
Все, кроме описания задачи, кода и предложения улучшить его, здесь шутка.
Все, кроме описания задачи, кода и предложения улучшить его, здесь шутка.
Можете ещё степени добавить)
А ещё квадратные корни и логарифмы =) Тогда вообще абсолютно любое натуральное число можно будет тремя двойками представить :-)
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 = 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-23^4+5+6^7+8-9
12^3/4-5-6*7*8+9
:-P
12^3/4-5-6*7*8+9
:-P
В своё время Дирак и Ландау играли в такую игру (Лев Давыдович показал её Дираку, вернее, показал традицию надеяться на «счастливый билет», а Дирак решил её усложнить, чтобы каждый билет стал «счастливым»), надо было путём арифметики приравнять комбинации первых трёх чисел и последующих в автобусных (трамвайных, тролейбесных) билетах. Тривиальный случай, это всем известный «счастливый билейт». Позже Дирак написал универсальную функцию приравнивания. К сожалению эту функцию не помню. Но всегда получая на руки билет пытаюсь играть в эту игру и скоротать время поездки.
Помнится, еще на первом курсе писал очень схожую реализацию этого на паскале, только без умножения и деления. То есть для данного числа найти его разложение в ряд *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(""));
но тогда задача далась мне с огромным трудом.
Честно говоря, не понял вот эту штуку: s = [1,2,0,2,0,1,0,0,0]; // Двоичное представление числа от 0 до 2432-1
Поясните, если не затруднит.
Поясните, если не затруднит.
Эм. Малость ошибся. Не двоичное, а троичное.
Это для того, чтобы обойти все возможные варианты подстановки * в строку *1*2*3*4*5*6*7*8*9
Поскольку
(0..2432-1)10 = (000000000..222222222)3, то
— циклически обхожу числа 0..2432-1;
— каждое перевожу в троичную систему;
— каждую цифру полученного троичного числа сопоставляю соответствующеу значению *: 0 — ничего, 1 — «минус», 2 — «плюс».
Получаю готовую строку, которая выполняется eval'ом.
Это для того, чтобы обойти все возможные варианты подстановки * в строку *1*2*3*4*5*6*7*8*9
Поскольку
(0..2432-1)10 = (000000000..222222222)3, то
— циклически обхожу числа 0..2432-1;
— каждое перевожу в троичную систему;
— каждую цифру полученного троичного числа сопоставляю соответствующеу значению *: 0 — ничего, 1 — «минус», 2 — «плюс».
Получаю готовую строку, которая выполняется eval'ом.
Да, мне тоже не понятно двоичное представление с двойкой.
С минусом 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
-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
Довольно распространенный случай скобок: калькулятор с неправильным приоритетом операций (практически все «обычные» калькуляторы + калькулятор 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
Без минуса впереди 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
UFO just landed and posted this here
Наконец дописал вариант для Java. Можно глянуть тут — dumpz.org/39029/.
Пытался решить рекурсией, никак не получается… Проблема в том, что надо помимо значения как-то сохранить путь, которым оно было получено.
Пытался решить рекурсией, никак не получается… Проблема в том, что надо помимо значения как-то сохранить путь, которым оно было получено.
На эрланге. Самой затратной по времени является часть 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]).
Немного переработал :) Пытался сделать покороче, вышло и побыстрее чуток (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>
Sign up to leave a comment.
Как сделать из 123456789 число 100 или 0