Головна сторінка
Top.Mail.Ru Яндекс.Метрика
Форум: "пошарпану";
Поточний архів: 2002.12.23;
Завантажити: [xml.tar.bz2];

Вниз

Чергова завдання для розминки мізків;) Знайти схожі гілки


MBo   (2002-11-29 10:14) [0]

Квадраты в квадрате.
Целые числа от 1 до 9 разместить в клетках квадрат 3x3 так, чтобы в нем
можно было найти максимальное количество чисел, являющихся квадратами.
Где запись квадрата может идти слева направо, справа налево,
сверху вниз и снизу вверх.
То есть если есть квадрат 169, то есть и квадраты 1,9,16 и 961.

Наприклад:

+1 2 3 XNUMX
+4 5 6 XNUMX
+7 8 9 XNUMX

здесь 5 квадратов: 1,4,9,25 и 36

из fido.golovolomka



MBo   (2002-11-29 10:19) [1]

P.S. у меня получилось макс. 10 квадратов



Igorek   (2002-11-29 10:37) [2]

Максимум тільки повний перебір однозначно визначить. А вручну нецікаво. Треба програму писати. Правда варіантів купа, так що без оптимізації перебору - ніяк.



Виктор Щербаков   (2002-11-29 10:39) [3]

MBo ©
Как бы сделать, чтобы все варианты не перебирать?
Тут ведь симметрия сплошная!



Opuhshii   (2002-11-29 14:05) [4]

10 квадратов получилось, но имхо можно больше,..



MBo   (2002-11-29 15:03) [5]

> Віктор Щербаков
Не знаю, как не перебирать. Я вручную прикинул - вроде больше 10 не получилось. Сделал переборную программу, не оптимизировал, даже зеркальные и повернутые не отсеивал, т.е. 9! матриц пробежал. Около 10-15 сек. считает на П600.



Виктор Щербаков   (2002-11-29 16:00) [6]

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



MBo   (2002-11-29 16:24) [7]

>упорядочить множество квадратов
А принципе, эта задачу можно свести к такой:
1)
нумеруем клетки в таком порядке
а1 а2 а3
а8 а9 а4
а7 а6 а5
2)
теперь составляем такие последовательности из 8 из 9 чисел, чтобы среди них не было обратных друг к другу и закольцованных (т.е. сдвиг с переносом): если у нас есть 12345678, то 23456781,56781234 и т.п., и 87654321, 32187654 и т.п. отбрасываем.
3)
После этого расставляем полученные последовательности, начиная с a1 и с a2 по кругу, не занимая клетку a9, в которую ставим остающееся число. Таким образом получаем все несимметричные решения.
Здесь главное - пункт 2 мудро реализовать



Igorek   (2002-11-29 16:28) [8]

Можна з іншого боку підійти. Спочатку обчислити всі квадрати аж до 999. Потім заповнювати квадрат цими послідовностями. Схоже на складання кросворд (я коли то таку програму написав). Правда алгоритм перебору нетривіальний.



Виктор Щербаков   (2002-11-29 16:30) [9]

Igorek © (29.11.02 16: 28)
ИМХО, ты всё усложнил :)))



MBo   (2002-11-29 17:35) [10]

по пункту 2 (MBo 16:24) придумал пока такой метод -
чтобы не сравнивать, есть ли уже циклически сдвинутая последовательность (что нетрудно сделать с помощью логических операций сдвига и or c приведением 8-байтового массива, скажем, к Int64, но требует хранения уже полученных последовательностей), можно сделать так:
исключаем, скажем, наименьшее из 8 чисел, для остальных получаем все перестановки, после чего в начало или конец добавляем исключенное число. Таким образом получим 9*7! последовательностей. Остающаяся избыточность - обращенные последовательности.



Igorek   (2002-11-29 19:54) [11]


> Віктор Щербаков © (29.11.02 16: 30)
> Igorek © (29.11.02 16: 28)
> ИМХО, ты всё усложнил :)))

Ваш алгоритм хорош еще для матрицы 3х3. А как для 4х4 и больше?



MBo   (2002-12-02 18:35) [12]

Прошу прощения, в программе допустил ошибку, максимальное число квадратов после ее исправления выросло ;) до 11 штук

+9 4 3 XNUMX
+2 5 6 XNUMX
+7 8 1 XNUMX

1,4,9,16,25,36,49,81,256,361,729



сторінки: 1 вся гілка

Форум: "пошарпану";
Поточний архів: 2002.12.23;
Завантажити: [xml.tar.bz2];

Вгору





Пам'ять: 0.59 MB
Час: 0.036 c
4-75044
Космічні
2002-11-10 16:45
2002.12.23
Як прибрати консоль?


1-74708
demonastarot
2002-12-13 08:03
2002.12.23
RichEdit проблема з копіюванням-виділенням ...


8-74845
Юрій До
2002-09-06 02:01
2002.12.23
Відтворення аудіо файлів


7-75023
Daan_m
2002-10-17 14:08
2002.12.23
Як написати процес


1-74744
Tik
2002-12-14 17:26
2002.12.23
TreeView





африкаанс албанський арабська вірменин азербайджанець баскський білоруський болгарська каталонський Китайська (спрощене письмо) Китайський традиційний) хорватський чеська данську мову нідерландський Ukranian естонець Філіппінська фінську мову французький
галісійська грузинський німецький грецький гаїтянський креольський давньоєврейську хінді угорський ісландський індонезієць ірландський італійський японський корейський латиська литовець македонець малайський мальтійський норвежець
перс полірування португальська румунський російська сербський словацький словенський іспанська суахілі шведську мову тайський турецька український урду в'єтнамський валлійський ідиш бенгальський боснійський
кебуано есперанто гуджараті хауса хмонг ігбо яванський каннада кхмерская Лао латинь маорі маратхі монгольський непальська панджабі сомалійський тамільська телугу йоруба
зулуський
Англійська Французький Німецький Італійський Португальська Русский Іспанська