Нахождение всех комбинаций расстановки n ферзей на доске n X n
end else begin
down;
end;
end;
end.
Расчёт вычислительной сложности.
Емкостная сложность:
В программе используется одномерный массив размерности n, поэтому объём
входа и объём выхода совпадают и равны n. Количество пременных равно
3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.
С(n)=n+4
Временная сложность:
Если рассматривать обработку каждого листа, без проверки на пути к
нему, то временная сложность T(n) = n0+n1+n2+n3+…+nn .
Но в случае, когда каждая вершина проверяется, временная сложность T(n) =
o(n0+n1+n2+n3+…+nn). И это тем вернее, чем больше n. Данный вывод получен
на основе приведённых ниже статистических данных:
|1 |2 |3 |4 |5 |6 |7 | |Общее кол-во листьев |2 |7 |40 |341 |3906 |55987
|960800 | |Кол-во вершин построенного дерева. |2 |3 |4 |17 |54 |153 |552 |
|Время построения(сек) |<0.01 |<0.01 |<0.01 |<0.01 |<0.01 |<0.01 |<0.01 | |
|8 |9 |10 |11 |12 |13 | |Общее кол-во листьев |[pic] |[pic] |[pic] |[pic]
|[pic] |[pic] | |Кол-во вершин построенного дерева. |2057 |8394 |35539
|166926 |856189 |4674890 | |Время построения(сек) |<0.01 |0.21 |1.20 |6.48
|37.12 |231.29 | |
Тестирование.
Построенная по описанному алгоритму программа при различных n выдаёт
следующие данные:
n=4
<1,2><2,4><3,1><4,3>
<1,3><2,1><3,4><4,2>
Т.е. количество расстановок равно 2. Ниже приведена таблица зависимости
от n количества решений (R).
n = |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |11 |12 |13 | |
|R= |1 |0 |0 |2 |10 |4 |40 |92 |352 |724 |2680 |14200 |73712|
Cписок литературы.
1) Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для
инженера. – М.: Энергоатомиздат, 1988.
2) Евстигнеев В.А. Применение теории графов в программировании. –
М.:Наука, 1984.
3) Основной алгоритм находился на BBS “Master of Univercity” в файле
shen.rar в файловой области “Bardak” (тел. 43-27-03; время работы 21.00
– 7.00; FTN адрес – 2:5090/58).
| |  скачать работу |
Нахождение всех комбинаций расстановки n ферзей на доске n X n |
