Подсчет количества полимино n-ого порядка. На главную
Полимино n-ого
порядка называется связная фигурка, составленная из n клеточек.
Одинаковыми являются полимино, которые можно получить друг из друга путем
перемещения, поворота и отражения. Дырявым полимино назовем фигурку, в которой
есть хотя бы одна дырка – область из клеточек, не принадлежащих фигурке, из
которой нет перехода наружу по свободным от фигурки клеточкам. Вот примеры:
Сначала
идут два одинаковых полимино 5-го порядка (пентамино). Они образованы друг из
друга поворотом и отражением. Затем – дырявое полимино
наименьшего порядка – 7-го. Затем – недырявое полимино 20-го порядка. Затем – дырявое полимино 17-го
порядка.
Задача заключается в подсчете количества различных фигурок полимино
заданного порядка. Мною написана программа на С++,
состоящая из 143 строк (3,6 КБ), решающая эту задачу и записывающая результаты
в файл. Вот результаты:
AMD AM2
3800+ память 800МГц:
N= 1 P= 1
H= 0 time=0
N= 2 P= 1
H= 0 time=0
N= 3 P= 2
H= 0 time=0
N= 4 P= 5
H= 0 time=0
N= 5 P=12
H= 0 time=0
N= 6 P=35
H= 0 time=0
N= 7 P=107
H= 1 time=0
N= 8 P=363
H= 6 time=0
N= 9 P=1248
H=37 time=0
N=10 P=4460
H=195 time=0.016
N=11
P=16094 H=979 time=0.015
N=12
P=58937 H=4663 time=0.062
N=13
P=217117 H=21474 time=0.219
N=14
P=805475 H=96496 time=0.812
N=15
P=3001127 H=425449 time=3.063
N=16
P=11230003 H=1849252 time=11.579
N=17
P=42161529 H=7946380 time=44.015
N=18
P=158781106 H=33840946 time=168.23
N=19
P=599563893 H=143060339 time=643.83
N=20
P=2269506062 H=601165888 time=2469.8
Где:
N – порядок полимино,
P – количество полимино этого порядка,
H – количество дырявых полимино этого порядка,
time – время подсчета в секундах.
Если кто-то знает что-то об аналогичных результатах или заинтересовался этими, то напишите в гостевую книгу или пошлите мне письмо.