Имеется квадрат 3 на 3. В нем стоят числа от 1 до 9. Берутся произведения трех цифр в каждой строке и в каждом столбике и складываются. Какая минимальная сумма может быть сумма и при какой расстановке? К примеру:
ivana2000, прикольно, но мимо кассы. Поскольку в нашем случае минимум принципиально недостижим (единственная пятерка, неспособная входить во все произведения) - так что 428 нам тут, по большому счету нафиг не нужно - только как маркер, если вдруг у кого получится меньше, значит точно ошибся. :))
Некоторые идеи (вроде, когда-то уже писал). Если квадратная таблица n×n заполняется числами от 1 до n², то сумма 2n произведений, описанных в условии, не опустится ниже некоторого числа M₀. Равенство (минимум) достигается, если все произведения Pi будут равны между собой.
В данном случае n=3, M₀=428 (427.96).
Админ, Вам слово. \n\n
Поскольку мы наконец вроде выяснили, где зарыта собака, - светить мне "логику 436", или нет? Она так и провисла недоказанной, и с одной стороны, если я ее сейчас засвечу, то пропадет весь смысл моей контр-задачи... :( С другой стороны, может быть, кого-то из мэтров она, наоборот, вдохновит на то самое доказательство, до которого у меня так и не дошли руки? 8) \n\n
Решение за Вами.
8))) N.N а вот теперь Вы меня по-настоящему удивили! XD XD XD Я, конечно, понимаю, что алгоритм Нараяны еще и не такое слопает - но если уж Вы писали программу *для проверки себя*, - то неужели сложно было набить исходный массив автоматикой a[i]=i ??? С гарантией от ошибок? 8))) \n\n
И еще примечательно, что первый не представившийся тоже использовал две тройки? XD XD XD N.N, простите за нескромность, - с ошибкой у Вас выходило 396? ;)))
N.N 2013-02-25 19:27:27 пишет:
Извините я не так подставил числа, я 2 раза использовал 3. Сейчас перепроверю решение
N.N, ну что вам сказать... :))) Не знаю, что и кому Вы хотели доказать своим упрямством, поэтому лучше промолчу... XD В одном Вы несомненно меня обыграли: Вы таки заставили меня написать программу. XD XD XD \n\n
Около трех часов мне потребовалось на ее написание - под рукой был только Визуальный Васик от Экселя, а после четверти века общения с разными, но все же исключительно Си-подобными языками, вспоминать Васик начиная от азов синтаксиса было сложновато... XD XD XD Итог: абсолютно неоптимально составленная программа (лишь бы вообще завелась :))), перебрала *все* 9! вариантов за примерно 5 минут. Еще и тратя при этом совершенно лишнее время на красивое булькание цифирками по экрану. :))) \n\n
И что бы Вы думали? ;))) Она утверждает, что таки да 436 - минимум из всех вообразимых возможных. :Р Так что если бы не Ваши странные личностные качества, это же самое время я мог бы потратить на попытки аналитического доказательства давно полученной эмпирическим путем логики. Теперь не буду - смысла нет уже. :(( \n\n
Буде у кого-нибудь из тех, кому я доверяю, :Р закрадутся сомнения в моей программе, готов ее предоставить в виде Эксель файла со всеми потрохами. Вы же, N.N, если хотите ;))))))) и дальше утверждать, что я неправ - приведите контрпример. :Р И, возможно, я смогу указать Вам на Вашу ошибку. :Р \n\n
Поскольку, как уже было замечено раньше, решение не единственно, то итоговое решение станцуем от Татьяниного, как от максимально близкого и в дань уважения. :) \n\n
5 8 2\n
6 1 9\n
3 7 4\n
Сумма 436
:) N.N не хочу я писать программу - своих хватает... :))) Но таки выходит, я не ошибся с выводами, и "чистого" аналитического решения у Вас таки нет, иначе не было бы необходимости проверять его программой. Значит у вас тоже нечто эмпирически обоснованное, как и моя "логика 436", только подкрепленное "железным доказательством". 8))) Ну тогда ответьте наконец на вопрос - 436 - минимум? Если да, то я успокоюсь и выложу найденную логику. Если нет, то буду думать и копаться дальше.
Админ:
N.N 2013-02-19 09:36:28 пишет:
KoKos, я сказал, что всего 9! вариантов расстановки, я не говорил, что некоторые дадут одинаковую сумму. И если хотите, то пишите программу( я себя так проверял)
N.N я не понял - это Вы мне отвечали, или это просто "замечание в пространство"? 8))) Если мне, то даже при нерабочей "логике убегания" 4*5*6 нигде получиться не может, так что "контрпример" бессмысленен. ;) Насчет количества комбинаций Вы тоже сильно погорячились, ибо даже "на глаз", - каждые 36 разных "линейных" перестановок, будучи вписанными в квадрат, дадут идентичную сумму в данных условиях. lg(36) это примерно 1.5 - то бишь Вы ошиблись на полтора порядка. 8))) Всего-то около десяти тысяч выходит потенциально различных, и при современных вычислительных мощностях Вы и кофе выпить не успеете, пока лобовой машинный подбор будет искать результат. ;))) А значит, Вы в своей собственной задаче "плаваете" :) ничуть не лучше нас, остальных. ;))) \n\n
Поскольку мои вопросы Вы старательно игнорируете, то я пока залягу на дно и подожду, пока не зачтут чье-нибудь решение. А тогда уже буду - то ли думать, то ли ругаться, - по обстоятельствам... XD
N.N 2013-02-16 15:05:47 пишет:
Подбором не решить. Всего 9! комбинаций. И кстати, 4*5*6>8*9*1
:) Хм... Админ, меньше 436? \n\n
Поясню свое любопытство - некоторую, хоть и недоказанную, а просто эмпирически полученную "логику 436" я таки нашел. Естественно, она подходит и для меньших квадратов. :))) Испытательный же прогон на квадрате 4х4 показал, что результат построения по четкому алгоритму =17178 , что на четыре лучше, чем результат построения "на глаз" *по той же самой* логике =17182 . \n\n
Так вот, пытаться ли придумать теперь для нее хоть какое-нибудь доказательство? Или она тоже неверна и не стоит впустую тратить время? 8)
:) На ответе "шесть" буду настаивать, :))) но чем-то меня эта задачка все же зацепила... Может быть, детство вспомнил, и одну из первых своих программ, которая никогда *не проигрывала* :) в "крестики-нолики"? XD Что-то уж очень смутно похожее тут рисуется, но все равно логики расстановки чисел не вижу, что называется, "в упор". 8/ \n\n
Если "цветок лотоса" Татьяны попытаться допилить моим "напильником убегания" (в очевидных проколах), то после первой перестановки получим 440, а после второй - 436. Это будет "рекорд", конечно, на данный момент, но меня он таки не устраивает. XD XD XD \n\n
Автор, признавайтесь :))) - существует ли в принципе "серьезное" решение, 8) отличное от простого перебора вариантов? Которое обобщается на квадраты большего размера, например, - при желании? ;)
Татьяна, простите. Где-то лопухнулся в подсчетах... 8( Таки да, выходит у Вас 448. \n\n
Я, конечно, еще поковыряюсь - почему не работает "логика убегания", но вот две анонимные тройки навели меня на интересную мысль... XD XD XD Ну ооочень интересную. ;) Еще раз перечитал условие, и таки не нашел в нем *требования*, чтобы "числа от 1 до 9" были *разными*. ;))) Значит, ответ: 6. Расписывать квадратик из девяти единиц надо? XD XD XD
Админ: так и ждал, когда придеретесь :) Не фиг, числа должны быть использованы все, задача не детская. :)