Понимание и умение применять
принцип математической индукции
является хорошим критерием логической зрелости
А. Н. Колмогоров

Урок 9. О ПРИМЕНЕНИИ КОМБИНАТОРИКИ И КОМБИНАТОРНОГО АНАЛИЗА В СИСТЕМЕ “ВЕКТОР

Теоретические положения

Комбинаторика и комбинаторный анализ есть распределение (чаще всего наилучшим способом) элементов по группам в соответствии с некоторыми заранее подготовленными условиями. Числовые комбинаторные задачи с древних времен применялись, например, в магических квадратах.

Основными задачами комбинаторики являются задачи на "существование" и "перечисление". Решение задач на "существование" состоит в том, чтобы ответить, существует ли некоторое заданное множество элементов или нет. Ответом является пример возможности построения такого множества или доказательства невозможности построения такого множества. Если множество существует, возникает задача перечислить множества данного типа.

Методы решения задача комбинаторики фактически сводятся к двум вычислительным операциям: перечислить и сравнить. Многие формулы комбинаторики доказываются с помощью принципа математической индукции: утверждение справедливо для всякого натурального n, если 1) оно справедливо для n=1, 2) из справедливости утверждения для какого-либо произвольного n=k следует его справедливость для n=k+1. .
 
Древний китайский логический квадрат  Ло Шу - один из примеров составления комбинаций. Требуется в квадрате 3 х 3 так расставить 9 цифр, чтобы суммы трех цифр в любом ряду по горизонтали, вертикали или диагонали были равны между собой. Квадрат Ло Шу является единственным решением этой задачи, не считая решений, получающихся из него при поворотах и отражениях.

Для решения задачи на ПК можно предложить различные варианты. Самый простой - перебрать всевозможные случаи, т.е. из девяти цифр выбрать так девять цифр, чтобы они не совпадали и при сложении по горизонтали, вертикали, горизонталям сумма чисел была постоянной. Выбор чисел можно осуществлять по методу выбора чисел с помощью генератора случайных чисел. Когда выпадет по всем ячейкам необходимое сочетание, то выход. В общем работа ПК будет долгой (на ПК типа Pentium требуется не менее 3 часов ее работы), поэтому желательно совмещать просто перебор с аналитическим подходом. Действительно, задачу Ло Шу можно значительно упростить. Значения центральной ячейки можно вычислить через уравнения выражающие пересечения вертикали, горизонтали и диагоналей. Сумма их будет равна 60, а центральная ячейка 5.  Вычисления остальных ячеек можно свести к их вычислению через две из них заданных. Таким образом, задача сводится к перебору цифр только в двух ячейках. Это можно осуществить или с помощью выбора цифр по методу случайных чисел, или перебора их через двойной цикл.

Другой пример - магический шестиугольник, имеющий 5 вертикальных рядов и 10 диагоналей, с 19 ячейками. Требуется расставить цифры от одного до 19 так, чтобы по всем рядам сумма чисел была постоянной. Магическая постоянная (МП) определяется сложением всех чисел от одного до 19 (в данном случае она равна 190), делением ее на пять (число допустимых рядов в одном направлении) и равна 38 (190/5=38).
Например, для магического квадрата Шу МП равна 15 - делением суммы от одного до девяти, равной 45, на число рядов (три). Порядок МК определяется числом элементов на стороне квадрата или шестиугольника. Так, для всех шестиугольников существует один магический шестиугольник, на поиски которого Адамс потратил 45 лет.

Аналитечески задачу можно свести к вычислению 12 ячеек по 7 задаваемым тем или другим способами. Вычисления также как и для квадрата Ло Шу можно осуществлять по методу случайных чисел или с помощью вложенных циклов - перебора возможных сочетаний.

Упражнения

 n/n   Название упражнений и обращение к тексту МК   Рисунок 
1 9.1. Используя выбор чисел по методу случайных чисел решить уравнение: 2*n1+4*n2=28, если известно, что n1, n2 изменяются в диапазоне от 1 до 6. 
Решение дано в МК cum.mac 
Контрольные вопросы
 
 
2 9.2. По методу случайных и некоторых  упращений решить древнекитайский квадрат Ло Шу. 
Решение в МК maglohu.mac 
Контрольные вопросы
Рис.8.2.3 
 
3 9.3. Используя циклы перебора двух переменных (остальные вычисляются через них), организовать вычисления квадрата Ло Шу. 
Решение в МК lohu.mac и lohu1.mac 
Контрольные вопросы
 
 
Самостоятельно
4 9.4. Найтие магические постоянные правильного шестиугольника и написать МК расчета его составляющих Рис.7.4.1 
Рис.7.4.1 


cum.mac  решение уравнения 2*n1+4*n2=28  при 0 < n1,n2 < 6
n > 50 ? exit    $ один цикл 50 ходов
tnn: n101=1 n102=7  $ выбор случайного числа от
n1=n191
tnn
n2=n191
n1 <> n2 ? goto met
n10=2*n1+4*n2
n10 <> 28 ? exit
$met
s=n*5
s1=n1
otrezok : p101=p99 p102=s,s1+30. $ график ЦФ n1 от хода n
p99=p102
s2=n2
otrezok: p101=p98 p102=s,s2+80. $ ЦФ n2 от n
p98=p102
cum: n=n+1
$ получили  первое решение n1 = 2, n2 =6   при n = 5
$ 2*2+4*6=28
$ второе при n1=4, n2= 5
$ 2*4+4*5=28
 

Контрольные вопросы

1. В каком случае программа cum.mac оканчивает свою работу?
2. В каком диапазоне происходит изменение абсциссы ЦФ? Ординаты ЦФ?
3. В каком параметре отыскивается максимум ЦФ?
4. В какой переменной формируется ЦФ?
5. Что нужно сделать в МК, чтобы определить размеры посылки при ее максимальном объеме?



 

maglohu.mac
$  msg$off
n > 10 ? exit    $  ? - оператор если (ставится после условия)
$ Вычисляем  n5 из соотношений
$ print$on
$ (n1+n5+n9)+(n3+n5+n7)+(n4+n5+n6)+(n2+n5+n8)=60
$ n1+n9+n3+n7+n4+n6+n2+n5+n8+3*n5=60
$ 3*n5=60-45
n5=15/3
tnn: n101=1 n102=10  $ случайное число от 1 до 9
n1=n191
tnn: n101=1 n102=10  $  случайное число от 1 до 9
n4=n191
n99=n1+n4
(n99 > 14) & (n1 > n4) ? n4=15-n1
(n99 > 14) & (n4 > n1) ? n1=15-n4
 n9=15-n1-n5
 n7=15-n1-n4
 n3=15-n7-n5
 n2=15-n1-n3
 n6=15-n4-n5
 n8=15-n2-n5
n9 < 1 ! n7 <1 ! n3<1 ! n2<1! n6<1 ! n8 < 1  ? goto met

n91=n1+n2+n3
n92=n4+n5+n6
n93=n7+n8+n9
n71=n1+n4+n7
n72=n2+n5+n8
n73=n3+n6+n9
n81=n1+n5+n9
n82=n3+n5+n7

n1<>n2!n1<>n3!n1<>n4!n1<>n5!n1<>n6!n1<>n7!n1<>8!n1<>n9?goto met
n2<>n3!n2<>n4!n2<>n5!n2<>n6!n2<>n7!n2<>n8!n2<>n9?goto met
n3<>n4!n3<>n5!n3<>n6!n3<>n7!n3<>n8!n3<>n9?goto met
n4<>n5!n4<>n6!n4<>n7!n4<>n8!n4<>n9?goto met
n5<>n6!n5<>n7!n5<>n8!n5<>n9?goto met
n6<>n7!n6<>n8!n7<>n9?goto met
n7<>n8!n7<>n9?goto met
n8<>n9 ? goto met
n91<>15&n92<>15&n93<>15&n71<>15&n72<>15&n73<>15&n81<>15&n82<>15?exit
$met
 s91=n91
 s=n*3
otrezok: p101=p91 p102=s,s91+25.
 p91=p102
s92=n92
otrezok: p101=p92 p102=s,s92+75.
 p92=p102
 s93=n93
otrezok: p101=p93 p102=s,s93+100.
 p93=p102
maglohu:n=n+1



lohu.mac
n1 > 9 ? exit    $  ? - оператор если (ставится после условия)
$ Вычисляем  n5 из соотношений
$ (n1+n5+n9)+(n3+n5+n7)+(n4+n5+n6)+(n2+n5+n8)=60
$ n1+n9+n3+n7+n4+n6+n2+n5+n8+3*n5=60
$ 3*n5=60-45
n5=15/3
lohu1: n4=1
n1<>n2!n1<>n3!n1<>n4!n1<>n5!n1<>n6!n1<>n7!n1<>8!n1<>n9?goto met
n2<>n3!n2<>n4!n2<>n5!n2<>n6!n2<>n7!n2<>n8!n2<>n9?goto met
n3<>n4!n3<>n5!n3<>n6!n3<>n7!n3<>n8!n3<>n9?goto met
n4<>n5!n4<>n6!n4<>n7!n4<>n8!n4<>n9?goto met
n5<>n6!n5<>n7!n5<>n8!n5<>n9?goto met
n6<>n7!n6<>n8!n7<>n9?goto met
n7<>n8!n7<>n9?goto met
n8<>n9 ? goto met
n91<>15&n92<>15&n93<>15&n71<>15&n72<>15&n73<>15&n81<>15&n82<>15?exit
$met
lohu1: n1=n1+1

lohu1.mac
n4 > 9  ? exit
n9=15-n1-n5
n7=15-n1-n4
n3=15-n7-n5
n2=15-n1-n3
n6=15-n4-n5
n8=15-n2-n5
n9 < 1 ! n7 <1 ! n3<1 ! n2<1! n6<1 ! n8 < 1  ? goto met
n91=n1+n2+n3
n92=n4+n5+n6
n93=n7+n8+n9
n71=n1+n4+n7
n72=n2+n5+n8
n73=n3+n6+n9
n81=n1+n5+n9
n82=n3+n5+n7
n1<>n2!n1<>n3!n1<>n4!n1<>n5!n1<>n6!n1<>n7!n1<>8!n1<>n9?goto met
n2<>n3!n2<>n4!n2<>n5!n2<>n6!n2<>n7!n2<>n8!n2<>n9?goto met
n3<>n4!n3<>n5!n3<>n6!n3<>n7!n3<>n8!n3<>n9?goto met
n4<>n5!n4<>n6!n4<>n7!n4<>n8!n4<>n9?goto met
n5<>n6!n5<>n7!n5<>n8!n5<>n9?goto met
n6<>n7!n6<>n8!n7<>n9?goto met
n7<>n8!n7<>n9?goto met
n8<>n9 ? goto met
n91<>15&n92<>15&n93<>15&n71<>15&n72<>15&n73<>15&n81<>15&n82<>15?exit
$met
lohu1: n4=n4+1


Контрольные вопросы

1. Что означает команда: n8 <> n9 ? goto met ?
2. Что означает команда: n7 <> n8 ! n7 <> n9 ? goto met ?
3. С каким шагом работает МК?
4. При каком условие прекращается работа МК lohu1.mac?