МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН
Есикский казахско-турецкий лицей-интернат им. А.Малькеева
Тема: «Алгоритм порядка комбинаций»
Направление: Информационные технологии.
Секция: Информатика
Руководитель: Боранбай Асылбек
Учитель информатики казахско-турецкого
лицей-интерната г.Есик
Выполнили: Нурбеков Тимур, Ораз Динислам
Научный руководитель: Камалова Г.Б.
Доктор педагогических наук,
Профессор кафедры «Информатики, математики
и информатизации образования»
Казахского национального педегогического
университета имени Абая
Есик, 2012
Содержание
Абстракт……………………………………………………………………………..3
Введение………………………………………………………………………………4
Анализ………………………………………………………………………………...5
§ 1………………………………………………………….………………….………7
§ 2………………………………………………………………………….…………..9
Пример 1………………………………………………………………………...…..10
§ 3 ……………………………………………………………………………………11
Шаг 1………………………………………………………………………………...12
Шаг2…………………………………………………………………………………13
Актуальность………………………………………………………………………14
Прикладное применение…………………………………………………………...15
Заключение.………………………………………………………………………...16
Литература..…………………………………………….…………………………17
Абстракт
В эти дни, многие проблемы компьютерных программ связаны с распорядком групп чисел. Если компьютеру было задано найти комбинации, которые работали бы, то он подбирал бы различные комбинации одну за другой. Этот компьютерный метод может занять очень много времени, если дана большая комбинация. Используя компьютерные алгоритмы, которые вносят комбинации в указатель, можно заставить компьютер пропускать числа, которые как мы знаем, не будут работать. Цельнашей научной работы состоит в том, чтобы найти алгоритм, который внесет числа в указатель. В этой работе создается метод, который используется для того, чтобы найти комбинационное число.
Abstract
These days, many problems of computer programs are connected with the schedule of groups of numbers. If to a computer has been set to find a combination of numbers which would work it would select various combinations one by one. This computer method can take a lot of time if the big combination is given. Using computer algorithms, mathematical function which brings combinational numbers to the index and can force computer to pass numbers which as we know will not work. Purpose consists in finding mathematical function which will bring numbers to the index. In this project function which carries out this problem is created. This method is used to find combinational number.
‘
Введение
Комбинаторный анализ изучает комбинаторные объекты: перестановки, сочетания, размещения, графы, сети и т.д.
В большинстве случаев решаются такие задачи:
1) Перечисление комбинаторных объектов определенного вида.
2) Подсчет количества комбинаторных объектов определенного вида.
Для перечисления комбинаторных объектов, они упорядочиваются некоторым образом А1 А2 А3..... и т.д.
Как правило алгоритм перечисления с первого объекта А1, а затем используя свойства А1, строится объект А2. После используя свойства А2 строится объект А3 и т.д.
Таким образом, чтобы построить объект Аk нужно строить последовательно объекты А1 А2 А3.... А(k-1), что требует большого объема вычислений.
В нашей работе предлагается метод, значительно сокращающий построения произвольного объекта Аk, на примере перестановок из элементов.
Перестановкой n-ой степени называется взаимное расположение чисел 1,2,3.....n
Существует несколько алгоритмов перечисления перестановок n-ой степени. Один из них заключается в следующем: перестановки упорядочиваются в лексикографическом порядке. Пусть заданны перестановки
А= i1 i2 i3...in, В= j1 j2 j3.... jn. Считается, что А < В,
если i1 < j1.
Если же i1 = j1, сравниваются i2 и j2. В этом случае, если i2 < j2.
Если же i2 = j2, сравниваются i3 и j3. В этом случае А < В, если i3 < j3 и т. д.
Алгоритм перечисления при таком порядке следующий. Самым первым считается перестановка 1,2,3,..., n, где числа расположены в возрастающем порядке, а последним – перестановка n, (n-1),..., 2, 1, где числа расположены в убывающем порядке.
В этом алгоритме все перестановки перечисляются в возрастающем порядке.
Например:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Цель настоящей работы состоит в том, чтобы найти алгоритм, позволяющий найти перестановку с заданным номером К в их лексикографическом упорядочении, не перечисляя предыдущих, что значительно сокращает вычисления. И обратно, по заданной перестановке определить её порядковый номер.
Анализ
Вопрос о том, сколькими способами можно расположить числа
1 2 3 4
Ответ 4! = 24. Есть 24 комбинации уже известные математикам. Что бы найти перестановку по ее порядковому номеру в лексикографическом упорядовачении, а также для нахождения порядкового номера заданной перестановки нам потребуется понятие комбинационного числа.
Для этого посмотрим, как работают системы счисления. В десятичной системе счисления единицы (цифры в самой правой позиции) меняются каждый шаг. Десятки(цифры на второй позиции справа) меняются каждый десятый шаг и так далее.
В шестнадцатиричной системе счисления единицы меняются каждый шаг. Десятки меняются каждый шестнадцатый шаг, а сотни – через 256 шагов и т.д.
Десятичная система работает следующим образом:
3 Место единиц меняется каждый шаг.
.. Место десятков меняется каждый десятый шаг.
..
..
Шестнадцатиричной система основана на основании 16:
1
..
A
B В шестнадцатиричной системе единицы
C меняют место каждый 16-ый шаг.
D
E
F
Одно сходство в этих двух системах - то, когда перечисляются все единицы,то меняется цифра состоящая в позиции десятков, когда меняются все цифры десятков,то меняются все цифры сотен и т.д... Есть ли способ выяснить сходство между десятичными числами и перестановками? Если перечислять перестановки в лексикографическом порядке,
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
...
...
то можно видеть, что в первой позициии (отсчет справа) числа изменяются каждый шаг (длина шага равна 0!=1 – число перестановок степени 0), во второй позиции также изменяются каждый шаг (длина шага равна 1!=1 – число перестановок степени 1), в третьей позиции каждый второй шаг (длина шага равна 2!=2 – число перестановок степени 2), а в четвертой позиции числа меняются через шесть шагов (длина шага равна 2!=6 – число перестановок степени 3) и т.д. Есть сходство с десятичной и шестнадцатиричной системой, но есть и различие. Попытаемся найти условие изменения чисел в каждой позиции.
- В десятичной системе отношения следующие: × 1 × 10 × 100 × 1000
- В шестнадцатиричной системе отношения следующие: × 1 × 16 × 256
- Настоящая система в комбинационном порядке такова: × 1 × 1 × 2 × 6 × 24 × 120 и т.д.
- Видно, что шаги изменения чисел равны факториалам: 0!, 1!, 2!, 3!,...
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
ПОРЯДОК
4! = 24 3! = 6 2! = 2 1! = 1 0! = 1
| 0. | |||||||||||||||||||
| 1. | |||||||||||||||||||
| 2. | |||||||||||||||||||
| 3. | |||||||||||||||||||
| 4. | |||||||||||||||||||
| 5. | |||||||||||||||||||
| 6. | |||||||||||||||||||
| 7. | |||||||||||||||||||
| 8. | |||||||||||||||||||
| 9. | |||||||||||||||||||
| 10. | |||||||||||||||||||
| 11. |
Как можно построить комбинационное число по порядковому номеру перестановки?
§ 1. Как можно построить комбинационное число по порядковому номеру перестановки?
Например, определим какая перестановка имеет порядковый номер 117?
Для этого:
1) 117 разделим на 24 (ближайший факториал, меньший или равный 117), получим частное 4 и остаток 21.
Так как частное – 4, то 5-ый элемент меняется 4 раза.
2) Полученный остаток 21 разделим на 6 (следующий меньший факториал), получим частное 3 и остаток 3.
3) Остаток 3 разделим на 2, получим частное 1 и остаток 1.
4) Остаток 1 разделим на 1, получим частное 1 и остаток 0.
5) Остаток 0 разделим на 1, получим частное 0 и остаток 0.
