Не атакующие друг друга слоны, угроза всех полей

@Judie dkkd · Регистрация: 17.09.2022

Студворк — интернет-сервис помощи студентам

Всем здравствуйте, столкнулся с такой проблемой, что непонимаю условия задачи, может кто-то поймет, что здесь происходит? Сама задачу звучит так:
Не атакующие друг друга слоны, угроза всех полей
Найти все способы расстановки минимального числа не атакующих друг друга слонов на
шахматной доске размером n х n так, чтобы они держали под угрозой все поля доски.
Исследовать асимптотическую временную сложность решения задачи в зависимости от n.
Подсказка: число фигур = n; для n = 8, число фигур = 8, число расстановок = 5184.

Не понимаю, почем в подсказке фигуры, хотя n - это размерность доски. Может у кого-то есть идеи решения данной задачи? сколько слонов должно быть, 4?

@TheCalligrapher · 23.06.2024, 17:18

Сообщение от Judie dkkd

64 - это количество комбинаций в 1 ряду, если менять между собой этих слонов. Вот первая уникальная комбинация, где каждым цветом указан единственный слон - https://kappa.lol/1wsi-. Далее, мы ищем еще 1 комбинацию, можем поменять местами 2 слона между собой - это и будет еще уникальная комбинация - уже нашли 2 таких комбинаций - https://kappa.lol/TQi81. чтобы не сидеть и не менять местами вот так каждую, можно умножить 8 на 8 = 64.

Еще раз, в который раз, повторяю все тот же вопрос: при чем здесь "умножить 8 на 8"? Почему вы решили, что количество таки комбинаций равно "умножить 8 на 8"?

@gunslinger · 23.06.2024, 23:15

Ну и на основе

a(4*n) = (n+1)^2*((2*n)!)^2
a(4*n+1) = (1/3)*(n+2)*(1+4*n+6*n^2)*((2*n)!)^2
a(4*n+2) = 4*(n+1)^4*((2*n)!)^2
a(4*n+3) = (1/3)*(3+17*n+22*n^2+6*n^3)*(2*n)!*(2*n+2)!

такой код получается

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
using namespace std;
 
#define ull unsigned long long
 
ull fact (unsigned n)
{
  ull res = 1;
  for (unsigned i = 1; i <= n; i++)
    res *= i;
  return res;
}
 
ull count (unsigned n)
{
  if (n < 2)
    return n;
 
  unsigned k = n / 4;
  ull tmp;
 
  switch (n % 4)
  {
    case 0:
      tmp = (k + 1) * fact(2 * k);
      return tmp * tmp;
    case 1:
      tmp = fact(2 * k);
      return tmp * tmp * (k + 2) * (1 + 4 * k + 6 * k * k) / 3;
    case 2:
      tmp = (k + 1) * (k + 1);
      tmp *= fact(2 * k);
      return 4 * tmp * tmp;
    default:  // 3
      tmp = fact(2 * k);
      return tmp * tmp * (2 * k + 1) * (2 * k + 2) * (3 + 17 * k + 22 * k * k + 6 * k * k * k) / 3;
  }
}
 
int main()
{
  unsigned n = 24, i;
  for (i = 1; i <= n; i++)
    cout << "n = " << i << "\tcount = " << count(i) << "\n";
  system("pause");
}

Добавлено через 23 минуты
Есть еще "прямая" (общая) формула, но тут "рябит в глазах" от скобок.

MATHEMATICA
Table[If[n==1, 1, 1/768*(2*(3*n^3+23*n^2+17*n+21)*(((n-1)/2)!)^2*(1-(-1)^n+2*Sin[(Pi*n)/2])-2*(3*n^3+17*n^2-47*n+3)*((n-3)/2)!*((n+1)/2)!*((-1)^n+2*Sin[(Pi*n)/2]-1)+3*(n+2)^4*((n/2-1)!)^2*((-1)^n-2*Cos[(Pi*n)/2]+1)+12*(n+4)^2*((n/2)!)^2*((-1)^n+2*Cos[(Pi*n)/2]+1))], {n, 2, 25}] (* Vaclav Kotesovec, Apr 26 2012 *)

TheCalligrapher, может он сам не понял, что написал.

Добавлено через 2 часа 49 минут
Код для последней формулы:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
 
#define ull unsigned long long
#define Pi 3.1415926535897932384626433832795
 
ull fact (unsigned n)
{
  ull res = 1;
  for (unsigned i = 1; i <= n; i++)
    res *= i;
  return res;
}
 
int func (unsigned n)
{
  return (n % 2) ? -1 : 1;
}
 
ull count (unsigned n)
{
  if (n < 2)
    return n;
  ull tmp = (n + 2) * (n + 2);
  return (2 * (3 * n * n * n + 23 * n * n + 17 * n + 21) * fact((n - 1) / 2) *
          fact((n - 1) / 2) * (1 - func(n) + 2 * (int)sin(Pi * n / 2)) -
          2 * (3 * n * n * n + 17 * n * n - 47 * n + 3) * fact(int(n - 3) / 2) *
          fact((n + 1) / 2) * (func(n) + 2 * (int)sin(Pi * n / 2) - 1) +
          3 * tmp * tmp * fact(n / 2 - 1) * fact(n / 2 - 1) * (func(n) - 2 * (int)cos(Pi * n / 2) + 1) +
          12 * (n + 4) * (n + 4) * fact(n / 2) * fact(n / 2) * (func(n) + 2 * (int)cos(Pi * n / 2) + 1)) / 768;
}
 
int main()
{
  unsigned n = 21, i;
  for (i = 1; i <= n; i++)
    cout << "n = " << i << "\tcount = " << count(i) << "\n";
  system("pause");
}

Добавлено через 15 минут
P. S.: как мне кажется, код №2 (через switch) выглядит наиболее "лаконичным" (если это слово тут подходит).

Добавлено через 2 часа 15 минут
Подправил ("причесал") функцию из кода №2:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ull count (unsigned n)
{
  if (n < 2)
    return n;
 
  const int num = 4;
  unsigned rem = n % num, k[num] = {n / num, k[0] + 1, 2 * k[0], 3 * k[0]},
           arr[num] = {
                        1,
                        (k[1] + 1) * (k[2] * (k[3] + 2) + 1) / 3,
                        4,
                        (k[1] + k[0]) * (k[2] * (k[2] * (11 + k[3]) + 17) + 6) * k[1] / 3
                      };
  ull tmp = fact(k[2]);
 
  if (rem % 2 == 0)
  {
    tmp *= k[1];
    if (rem == 2)
      tmp *= k[1];
  }
 
  return tmp * tmp * arr[rem];
}

@Judie dkkd · 24.06.2024, 15:33 **[ТС]**

Сообщение от TheCalligrapher

Еще раз, в который раз, повторяю все тот же вопрос: при чем здесь "умножить 8 на 8"? Почему вы решили, что количество таки комбинаций равно "умножить 8 на 8"?

ок, возможно правильно факториал 8, но если спользовать факториал 8, то будет 40320 комбинаций, слишком много, перепутал я значит

Добавлено через 17 секунд
чат гпт не смог решить эту задачу

Добавлено через 22 секунды
такие долгие ответы от мне, потому что анти дудос защита не пускает меня на сайт

Новые блоги и статьи Все статьи Все блоги /
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@Judie dkkd 0 / 0 / 0 Регистрация: 17.09.2022 Сообщений: 46

	Не атакующие друг друга слоны, угроза всех полей 22.06.2024, 12:30. Показов 3001. Ответов 42 Метки нет (Все метки) Всем здравствуйте, столкнулся с такой проблемой, что непонимаю условия задачи, может кто-то поймет, что здесь происходит? Сама задачу звучит так: Не атакующие друг друга слоны, угроза всех полей Найти все способы расстановки минимального числа не атакующих друг друга слонов на шахматной доске размером n х n так, чтобы они держали под угрозой все поля доски. Исследовать асимптотическую временную сложность решения задачи в зависимости от n. Подсказка: число фигур = n; для n = 8, число фигур = 8, число расстановок = 5184. Не понимаю, почем в подсказке фигуры, хотя n - это размерность доски. Может у кого-то есть идеи решения данной задачи? сколько слонов должно быть, 4? 0