2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1 ... 4, 5, 6, 7, 8, 9, 10, 11  След.
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение03.07.2015, 03:00 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #1032948 писал(а):
Пример

даны два точных ортогональных покрытия массива, цепочки нормализованы:

Код:
23 719 743 1013 1223 1901 1913 2081 2633
29 479 659 1103 1493 1949 2069 2129 2339
59 191 281 389 1109 2459 2549 2591 2621
509 683 911 1151 1433 1439 1559 2153 2411
11 113 179 449 1361 2273 2543 2609 2711
311 569 1163 1283 1289 1571 1811 2039 2213
101 131 173 263 1613 2333 2441 2531 2663
383 593 653 773 1229 1619 2063 2243 2693
89 641 809 821 1499 1709 1979 2003 2699

29 59 101 683 1811 1913 2243 2699 2711
89 389 593 659 1571 2081 2153 2273 2441
113 773 1013 1283 1433 1493 1613 1979 2549
179 311 653 719 1499 1559 2339 2459 2531
131 509 821 1103 1361 1619 1901 2213 2591
191 263 383 1163 1223 2003 2069 2411 2543
173 743 1109 1229 1289 1439 1709 1949 2609
281 449 569 641 1151 2063 2129 2333 2633
11 23 479 809 911 2039 2621 2663 2693

Вводим покрытия в программу и мгновенно получаем следующий ассоциативный квадрат:

Код:
1913 2081 1013 719 1901 1223 743 2633 23
29 659 1493 2339 1103 2069 1949 2129 479
59 389 2549 2459 2591 191 1109 281 2621
683 2153 1433 1559 509 2411 1439 1151 911
2711 2273 113 179 1361 2543 2609 449 11
1811 1571 1283 311 2213 1163 1289 569 2039
101 2441 1613 2531 131 263 173 2333 2663
2243 593 773 653 1619 383 1229 2063 2693
2699 89 1979 1499 821 2003 1709 641 809

$K=2722$, $S=12249$

Интересно: первое и второе покрытия равноправны.
Введём в программу в качестве первого покрытия второе, а в качестве второго первое. Программа построит такой ассоциативный квадрат:

Код:
1913 29 59 683 2711 1811 101 2243 2699
2081 659 389 2153 2273 1571 2441 593 89
1013 1493 2549 1433 113 1283 1613 773 1979
719 2339 2459 1559 179 311 2531 653 1499
1901 1103 2591 509 1361 2213 131 1619 821
1223 2069 191 2411 2543 1163 263 383 2003
743 1949 1109 1439 2609 1289 173 1229 1709
2633 2129 281 1151 449 569 2333 2063 641
23 479 2621 911 11 2039 2663 2693 809

$K=2722$, $S=12249$

Всё правильно: строки стали столбцами, а столбцы - строками. Всё чётко работает.

Итак, пусть теперь мы имеем комплект из 4-х точных попарно ортогональных покрытий заданного массива из 81 чисел такой, что идеальный квадрат из этого комплекта составляется.
Понятно, что мы можем образовать из покрытий комплекта 6 пар точных ортогональных покрытий. Каждая пара должна дать нам ассоциативный квадрат.
Вопрос: обязательно ли хотя бы один из этих ассоциативных квадратов превратится в идеальный с помощью преобразований - перестановки симметричных строк/столбцов (алгоритм, предложенный whitefox) :?:
Это надо проверить.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение03.07.2015, 04:26 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Предъявляю шесть ассоциативных квадратов, построенных из шести пар ортогональных точных покрытий массива, образованных из покрытий комплекта из 4-х точных попарно ортогональных покрытий:

(Оффтоп)

Код:
Первая пара (1,2):

11 2621 2531 1499 1949 479 389 2459 311
2129 449 59 1979 179 2633 2693 569 1559
1901 641 1709 2609 1433 1493 719 131 1613
173 2069 683 1571 383 2201 659 2699 1811
2441 1439 839 509 1361 2213 1883 1283 281
911 23 2063 521 2339 1151 2039 653 2549
1109 2591 2003 1229 1289 113 1013 2081 821
1163 2153 29 89 2543 743 2663 2273 593
2411 263 2333 2243 773 1223 191 101 2711

Вторая пара (1,3):

11 1949 1499 389 2531 2621 2459 311 479
179 1559 2129 59 449 1979 2693 2633 569
1493 131 1613 2609 1901 1433 641 719 1709
1811 2201 383 2069 1571 173 683 2699 659
1283 1883 2213 2441 1361 281 509 839 1439
2063 23 2039 2549 1151 653 2339 521 911
1013 2003 2081 1289 821 113 1109 2591 1229
2153 89 29 743 2273 2663 593 1163 2543
2243 2411 263 101 191 2333 1223 773 2711

Третья пара (1,4):

11 2459 2621 1499 389 311 479 2531 1949
1979 2633 59 449 569 179 1559 2693 2129
1709 1433 131 719 1613 2609 1901 1493 641
2069 1811 659 683 2201 173 383 2699 1571
1883 2441 2213 1283 1361 1439 509 281 839
1151 23 2339 2549 521 2039 2063 911 653
2081 1229 821 113 1109 2003 2591 1289 1013
593 29 1163 2543 2153 2273 2663 89 743
773 191 2243 2411 2333 1223 101 263 2711

Четвёртая пара (2,3):

11 2411 2129 2441 1901 173 1109 1163 911
2153 23 263 2069 449 2621 641 2591 1439
2063 2003 29 59 2531 2333 683 839 1709
2243 89 1499 2609 1571 1979 509 521 1229
179 1949 383 1289 1361 1433 2339 773 2543
1493 2201 2213 743 1151 113 1223 2633 479
1013 1883 2039 389 191 2663 2693 719 659
1283 131 2081 101 2273 653 2459 2699 569
1811 1559 1613 2549 821 281 593 311 2711

Пятая пара (2,4):

11 2441 1163 2411 1109 173 1901 911 2129
2069 23 2621 449 2153 1439 2591 263 641
1709 29 59 683 2333 2003 2063 2531 839
1979 1229 2243 1499 521 2609 509 89 1571
773 1433 2339 2543 1361 179 383 1289 1949
1151 2633 2213 113 2201 1223 479 1493 743
1883 191 659 719 389 2039 2663 2693 1013
2081 2459 131 1283 569 2273 101 2699 653
593 1811 821 2549 1613 311 1559 281 2711

Шестая пара (3,4):

11 1811 2243 1283 2153 179 2063 1493 1013
1883 23 131 2411 2201 2003 1559 89 1949
2081 29 2213 1499 1613 2039 383 263 2129
2069 2441 59 2549 389 2609 101 1289 743
1151 191 821 449 1361 2273 1901 2531 1571
1979 1433 2621 113 2333 173 2663 281 653
593 2459 2339 683 1109 1223 509 2693 641
773 2633 1163 719 521 311 2591 2699 839
1709 1229 659 2543 569 1439 479 911 2711

whitefox
вы сосем напрасно откланялись :wink:
Самое время показать ваш алгоритм в действии: проверить предъявленные шесть ассоциативных квадратов и предъявить идеальный квадрат, который обязан получиться хотя бы из одного ассоциативного квадрата, если ваш алгоритм работает правильно.

Замечу, что у меня пока нет процедуры построения идеального квадрата из комплекта 4-х точных попарно ортогональных покрытий массива. Я только хочу такую процедуру сделать, но ещё не знаю как.
Ну вот и давайте опробуем вашу процедуру, примитивно разбив комплект на шесть пар точных ортогональных покрытий и проверив каждую пару, точнее - каждый ассоциативный квадрат, полученный из каждой пары покрытий.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение03.07.2015, 09:18 
Заслуженный участник
Аватара пользователя


19/12/10
1546
На самом деле, достаточно проверить только три пары ортогональных покрытий. Так как идеальный квадрат нечётного порядка инвариантен относительно замены "линий" "диагоналями". Это верно для пандиагонального квадрата (доказано Россером), очевидно, верно и для ассоциативного.

Этого вполне достаточно для того, чтобы убедится в невозможности построения идеального квадрата из данного комплекта точных покрытий. Но остаётся ещё возможность получить идеальный квадрат в котором одна пара покрытий совпадает с одной из не проверенных пар, а вторая не принадлежит нашему комплекту. Так что лучше, всё-таки, проверить все шесть пар.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение03.07.2015, 10:37 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #1033109 писал(а):
Так что лучше, всё-таки, проверить все шесть пар.

Процедуру проверки можете написать?

Сейчас очень мило пообщалась с одним из товарищей, писавших процедуру проверки ассоциативного квадрата 10-го порядка. Он долго не мог понять, о какой программе речь, а когда понял, сообщил, что эта программа у него не сохранилась.

Несколько лет назад я писала такую процедуру шутя, применяла её для классических квадратов.
Сейчас элементарно туплю :oops:
Но... придётся напрячь свои извилины, насколько их можно напрячь. Процедура-то простейшая!

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение03.07.2015, 18:18 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
О-о-о! Вспомнила, что другой товарищ прислал в сообщении ссылку на код программы.
Программа делает перестановку всех симметричных строк/столбцов в ассоциативном квадрате 10-го порядка с последующей проверкой полученных вариантов квадрата на пандиагональность.
Кажется, это Паскаль (?) И, насколько понимаю, программа написана для любого порядка квадрата N.

(Оффтоп)

Код:
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <set>
#include <stack>

typedef std::vector<int> Vec;
typedef std::set<Vec> Set;
typedef std::stack<Vec> Stack;

int N;
int S;
Set set;
Stack stack;
Vec best;
int best_n = 0;

void print_best(std::ostream &stream)
{
  stream << best_n << std::endl;
  for (int i = 0; i < N; ++i)
  {
    for (int j = 0; j < N; ++j)
    {
      stream << best[i * N + j] << " ";
    }
    stream << std::endl;
  }
}

void check(const Vec &square)
{
  int num = 0;
  for (int i = 0; i < N; ++i)
  {
    int sum1 = 0;
    int sum2 = 0;
    for (int j = 0; j < N; ++j)
    {
      int x = j + i;
      if (x >= N)
      {
        x-= N;
      }
      sum1 += square[j * N + x];
      sum2 += square[(N - j - 1) * N + x];
    }
    if (sum1 == S)
    {
      ++num;
    }
    if (sum2 == S)
    {
      ++num;
    }
  }
  if (num > best_n)
  {
    best = square;
    best_n = num;
  }
}

void insert(const Vec &vec)
{
  for (int i = N / 2; i < N; ++i)
  {
    if (vec[i] == 0) return;
  }
  if (set.insert(vec).second)
  {
    stack.push(vec);
  }
}

void swap(Vec vec, int i, int j)
{
  int t = vec[i];
  vec[i] = vec[j];
  vec[j] = t;
  if (j != N - i - 1)
  {
    i = N - i - 1;
    j = N - j - 1;
    t = vec[i];
    vec[i] = vec[j];
    vec[j] = t;
  }
  insert(vec);
}

void process(const Vec &vec)
{
  for (int i = 0; i < N / 2; ++i)
    for (int j = i + 1; j < N; ++j)
      swap(vec, i, j);
}

int main(int argc, char *argv[])
{
  const char *in_name;
  if (argc >= 2)
    in_name = argv[1];
  else
    in_name = "in.txt";

  const char *out_name;
  if (argc >= 3)
    out_name = argv[2];
  else
    out_name = "out.txt";

  std::ifstream in(in_name);
  std::ofstream out(out_name);
  Vec square;
  int v;
  while (in >> v)
  {
    square.push_back(v);
  }
  N = sqrt(square.size());

  S = 0;
  for (int i = 0; i < N; ++i)
  {
    S += square[i];
  }

  Vec vec(N);
  for (int i = 0; i < N; ++i)
  {
    vec[i] = i;
  }
  insert(vec);
  while (!stack.empty())
  {
    vec = stack.top();
    stack.pop();
    process(vec);
  }

  std::vector<Vec> vecs;
  for (Vec vec : set)
  {
    vecs.push_back(vec);
  }

  int Z = vecs.size();
  std::cout << "N=" << N << ", S=" << S << ", Z=" << Z << std::endl;

  Vec test(N * N);
  int count = 0;
  int total = Z * Z;
  for (int r = 0; r < Z; r++)
    for (int c = 0; c < Z; c++)
    {
      for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
          test[i * N + j] = square[vecs[r][i] * N + vecs[c][j]];
      check(test);
      if (++count % 100000 == 0)
      {
        std::cout << count << " / " << total << " (" << count * 100 / total << "%), best: " << best_n << std::endl;
      }
    }

  print_best(std::cout);
  print_best(out);

  return 0;
}

Там же есть и исполняемая программа.
Если я всё правильно поняла, то программа сейчас мигом проверит все мои ассоциативные квадраты 9-го порядка :-)
и предъявит идеальный квадрат.
Ушла проверять.

-- Пт июл 03, 2015 19:34:25 --

Результат проверки первого ассоциативного квадрата:

Код:
6
479 2459 11 2531 1499 311 2621 389 1949
1433 1709 131 1901 1493 641 2609 719 1613
683 2069 173 2201 1571 383 2699 659 1811
743 2273 29 2543 1163 89 2663 593 2153
1283 1883 281 2213 1361 509 2441 839 1439
569 2129 59 2633 1559 179 2693 449 1979
911 2063 23 2339 1151 521 2549 653 2039
1109 2003 113 2081 1229 821 2591 1013 1289
773 2333 101 2411 1223 191 2711 263 2243

Всего 6 правильных диагоналей! До идеального квадрата очень далеко.

Сильно подозреваю, что и остальные 5 ассоциативных квадратов дадут примерно такой же результат.
Но... не буду забегать вперёд. Проверю.

-- Пт июл 03, 2015 19:43:13 --

Ох, не то пока. Я ввела в качестве исходного квадрата не квадрат, а первое точное покрытие.
Снова ушла проверять первый ассоциативный квадрат :? может, сейчас лучше получится.

-- Пт июл 03, 2015 19:55:36 --

Да! Ура!
Вот он - идеальный квадрат, полученный из первого же ассоциативного квадрата:

Код:
18
2531 2621 1499 11 1949 311 479 2459 389
59 449 1979 2129 179 1559 2633 569 2693
683 2069 1571 173 383 1811 2201 2699 659
1709 641 2609 1901 1433 1613 1493 131 719
839 1439 509 2441 1361 281 2213 1283 1883
2003 2591 1229 1109 1289 821 113 2081 1013
2063 23 521 911 2339 2549 1151 653 2039
29 2153 89 1163 2543 593 743 2273 2663
2333 263 2243 2411 773 2711 1223 101 191

$K=2722$, $S=12249$

Progger
ау
большое спасибо за программу. Вот и пригодилась :D
Только... почему-то очень много вариантов программа проверяет и работает у меня минут 5.
Ну ладно, главное - работает.

А сейчас возьму известный минимальный ассоциативный квадрат с магической константой $S=12249$ и проверю его. Очень интересно, что он даст!

-- Пт июл 03, 2015 20:13:13 --

Ввела в программу известный минимальный ассоциативный квадрат 9-го порядка из различных простых чисел:

Код:
1283 311 1811 2213 1571 569 2039 1163 1289
773 653 2243 1619 2063 593 2693 383 1229
1979 1499 2699 641 821 89 809 2003 1709
1613 2531 101 131 2333 2441 2663 263 173
113 179 2711 449 1361 2273 11 2543 2609
2549 2459 59 281 389 2591 2621 191 1109
1013 719 1913 2633 1901 2081 23 1223 743
1493 2339 29 2129 659 1103 479 2069 1949
1433 1559 683 2153 1151 509 911 2411 1439

$K=2722$, $S=12249$

Результат проверки этого квадрата:

Код:
6
1619 773 2243 653 2063 383 2693 1229 593
2213 1283 1811 311 1571 1163 2039 1289 569
131 1613 101 2531 2333 263 2663 173 2441
641 1979 2699 1499 821 2003 809 1709 89
449 113 2711 179 1361 2543 11 2609 2273
2633 1013 1913 719 1901 1223 23 743 2081
281 2549 59 2459 389 191 2621 1109 2591
2153 1433 683 1559 1151 2411 911 1439 509
2129 1493 29 2339 659 2069 479 1949 1103

Максимум 6 правильных диагоналей.

Итак, теперь перед нами два пути к решению поставленной задачи (поиск минимального идеального квадрата 9-го порядка из различных простых чисел) методом точных ортогональных покрытий:

а) проверять все пары ортогональных покрытий массива на предмет построения из них идеального квадрата
(путь очень длинный, может растянуться на много недель и даже месяцев);
б) искать комплекты из 4-х точных попарно ортогональных покрытий массива и тоже проверять на предмет построения идеального квадрата; процедура проверки теперь есть
(ещё не знаю, как искать такие комплекты; пока не удалось ни одного комплекта найти).

Если будет доказано, что ни одного такого комплекта не существует, это будет равносильно доказательству несуществования искомого минимального квадрата.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение03.07.2015, 19:52 
Заслуженный участник


20/08/14
11068
Россия, Москва
Nataly-Mak в сообщении #1033219 писал(а):
Кажется, это Паскаль (?)
Нет, это С++.
Хотя программа довольно прозрачная, почти ничего специфического именно из С++ вроде и не использовано, за парой исключений переписать на паскаль или даже бейсик можно фактически 1-в-1.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение03.07.2015, 19:56 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Я тоже написал программу, реализующую алгоритм, приведённый мной ранее.
Идеальные квадраты нашлись для первого и шестого ассоциативного квадрата:

(Оффтоп)

Код:
1901  641  719 1493 1433 2609 1709  131 1613
2129  449 2693 2633  179 1979   59  569 1559
2411  263  191 1223  773 2243 2333  101 2711
911   23 2039 1151 2339  521 2063  653 2549
2441 1439 1883 2213 1361  509  839 1283  281
173 2069  659 2201  383 1571  683 2699 1811
  11 2621  389  479 1949 1499 2531 2459  311
1163 2153 2663  743 2543   89   29 2273  593
1109 2591 1013  113 1289 1229 2003 2081  821

2213 2039  263 2129 1613 2081   29 1499  383
659 1439  911 2711  569 1709 1229 2543  479
2621  173  281  653 2333 1979 1433  113 2663
1163  311 2699  839  521  773 2633  719 2591
821 2273 2531 1571 1361 1151  191  449 1901
131 2003   89 1949 2201 1883   23 2411 1559
  59 2609 1289  743  389 2069 2441 2549  101
2243  179 1493 1013 2153   11 1811 1283 2063
2339 1223 2693  641 1109  593 2459  683  509

Время работы программы 1 милисекунда.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение03.07.2015, 21:01 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #1033239 писал(а):
Время работы программы 1 милисекунда.

Ого!
А не поделитесь программой? :wink:
При такой скорости можно и пары ортогональных покрытий попроверять. Хотя... по-моему, проверять пары - голый номер.

Вот сейчас выполнила эксперимент.
Первое точное покрытие нашла случайной генерацией:

Код:
809  659  1499  569  509  2333  1571  2591  1709
29  311  2711  2243  1979  101  2663  1103  1109
1901  2633  773  2081  1289  23  2129  191  1229
1811  2039  179  263  281  2609  449  2549  2069
1439  383  1163  719  1361  1283  2339  1559  2003
653  173  2273  113  2441  2459  2543  683  911
1493  2531  593  2699  1433  641  1949  89  821
1613  1619  59  2621  743  479  11  2411  2693
1013  131  1151  389  2213  2153  1223  2063  1913

Второе точное покрытие ортогональное данному нашла по программе:

Код:
11 23 29 2333 2441 2213 821 2039 2339
131 2129 2531 2621 179 2663 173 659 1163
89 1913 2069 1709 911 1283 2243 1289 743
449 113 1619 1949 311 1571 2081 2153 2003
263 1109 1223 1229 1361 1493 1499 1613 2459
2273 2609 1103 773 2411 1151 641 569 719
2633 809 653 1013 1811 1439 479 1433 1979
2591 593 191 101 2543 59 2549 2063 1559
2711 2699 2693 389 281 509 1901 683 383

Своей процедурой строю из этих двух точных ортогональных покрытий ассоциативный квадрат (это всегда обеспечено на 100%):

Код:
2333 659 1709 1571 1499 569 809 2591 509
29 2663 2243 311 1109 1103 1979 101 2711
23 2129 1289 2081 1229 773 2633 191 1901
2039 179 2069 449 263 2609 1811 2549 281
2339 1163 1283 2003 1361 719 1439 1559 383
2441 173 911 113 2459 2273 653 2543 683
821 2531 89 1949 1493 641 1433 593 2699
11 2621 743 1619 1613 2411 479 59 2693
2213 131 1913 2153 1223 1151 1013 2063 389

Ввожу этот ассоциативный квадрат в программу Progger, результат проверки:

Код:
4
2333 1709 1571 2591 1499 659 569 809 509
29 2243 311 101 1109 2663 1103 1979 2711
23 1289 2081 191 1229 2129 773 2633 1901
2039 2069 449 2549 263 179 2609 1811 281
2339 1283 2003 1559 1361 1163 719 1439 383
2441 911 113 2543 2459 173 2273 653 683
821 89 1949 593 1493 2531 641 1433 2699
11 743 1619 59 1613 2621 2411 479 2693
2213 1913 2153 2063 1223 131 1151 1013 389

Максимум 4 правильные диагонали. Очень плохо!

И у меня такая гипотеза: в 90% (или даже намного больше) для пар точных ортогональных покрытий результат будет такой же.
Нужно искать комплекты из 4-х точных попарно ортогональных покрытий. Только они дают шанс найти идеальный квадрат.

-- Пт июл 03, 2015 22:16:05 --

whitefox в сообщении #1033239 писал(а):
Идеальные квадраты нашлись для первого и шестого ассоциативного квадрата:

Да, любопытно, что не все ассоциативные квадраты дают идеальный квадрат.
Сейчас проверила второй ассоциативный квадрат, результат проверки:

Код:
10
1949 11 1499 2621 2531 389 2459 479 311
1559 179 2129 1979 449 59 2693 569 2633
2201 1811 383 173 1571 2069 683 659 2699
131 1493 1613 1433 1901 2609 641 1709 719
1883 1283 2213 281 1361 2441 509 1439 839
2003 1013 2081 113 821 1289 1109 1229 2591
23 2063 2039 653 1151 2549 2339 911 521
89 2153 29 2663 2273 743 593 2543 1163
2411 2243 263 2333 191 101 1223 2711 773

Максимум 10 правильных диагоналей (должно быть 18).

Кстати, время работы программы Progger сильно зависит оттого, есть решение или нет. Когда идеальный квадрат строится, он строится в первую же секунду (и тут программу надо останавливать!).
А вот когда решения нет и программа выполняет полный перебор, тогда это минут 5.

-- Пт июл 03, 2015 22:45:51 --

Проверила оставшиеся 4 квадрата. Решение нашлось для 6-го квадрата.

(Оффтоп)

Код:
Третий
10
11 1499 2621 2531 389 2459 479 311 1949
1979 449 59 2693 569 2633 1559 179 2129
2069 683 659 2699 2201 1811 383 173 1571
1709 719 131 1493 1613 1433 1901 2609 641
1883 1283 2213 281 1361 2441 509 1439 839
2081 113 821 1289 1109 1229 2591 2003 1013
1151 2549 2339 911 521 23 2063 2039 653
593 2543 1163 89 2153 29 2663 2273 743
773 2411 2243 263 2333 191 101 1223 2711

четвёртый
10
173 11 1163 1109 1901 2129 2411 911 2441
2621 2153 2591 641 449 263 23 1439 2069
2663 1013 719 2693 191 2039 1883 659 389
113 1493 2633 1223 1151 2213 2201 479 743
1433 179 773 2339 1361 383 1949 2543 1289
1979 2243 521 509 1571 1499 89 1229 2609
2333 2063 839 683 2531 29 2003 1709 59
653 1283 2699 2459 2273 2081 131 569 101
281 1811 311 593 821 1613 1559 2711 2549

Пятый
10
2441 173 11 1163 1109 1901 2129 2411 911
23 1439 2069 2621 2153 2591 641 449 263
191 2039 1883 659 389 2663 1013 719 2693
2633 1223 1151 2213 2201 479 743 113 1493
1433 179 773 2339 1361 383 1949 2543 1289
1229 2609 1979 2243 521 509 1571 1499 89
29 2003 1709 59 2333 2063 839 683 2531
2459 2273 2081 131 569 101 653 1283 2699
1811 311 593 821 1613 1559 2711 2549 281

Шестой
18
1883 2411 131 89 2201 23 1559 2003 1949
11 1283 2243 1493 2153 1811 2063 179 1013
2081 1499 2213 263 1613 29 383 2039 2129
1979 113 2621 281 2333 1433 2663 173 653
1151 449 821 2531 1361 191 1901 2273 1571
2069 2549 59 1289 389 2441 101 2609 743
593 683 2339 2693 1109 2459 509 1223 641
1709 2543 659 911 569 1229 479 1439 2711
773 719 1163 2699 521 2633 2591 311 839

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение04.07.2015, 00:37 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
К этой паре точных ортогональных покрытий, которую посчастливилось очень быстро найти, попыталась найти третье точное покрытие ортогональное каждому из двух.

Код:
809  659  1499  569  509  2333  1571  2591  1709
29  311  2711  2243  1979  101  2663  1103  1109
1901  2633  773  2081  1289  23  2129  191  1229
1811  2039  179  263  281  2609  449  2549  2069
1439  383  1163  719  1361  1283  2339  1559  2003
653  173  2273  113  2441  2459  2543  683  911
1493  2531  593  2699  1433  641  1949  89  821
1613  1619  59  2621  743  479  11  2411  2693
1013  131  1151  389  2213  2153  1223  2063  1913

11 23 29 2333 2441 2213 821 2039 2339
131 2129 2531 2621 179 2663 173 659 1163
89 1913 2069 1709 911 1283 2243 1289 743
449 113 1619 1949 311 1571 2081 2153 2003
263 1109 1223 1229 1361 1493 1499 1613 2459
2273 2609 1103 773 2411 1151 641 569 719
2633 809 653 1013 1811 1439 479 1433 1979
2591 593 191 101 2543 59 2549 2063 1559
2711 2699 2693 389 281 509 1901 683 383

Не тут-то было! Три часа кручу программу и... нет третьего покрытия. Три пары цепочек находит программа быстро, а на четвёртой паре облом.
Окно программы

Изображение

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение04.07.2015, 05:59 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #1033294 писал(а):
К этой паре точных ортогональных покрытий, которую посчастливилось очень быстро найти...

А никакого счастья и не было :D
Сейчас ввела в программу поиска второго ортогонального покрытия то же самое первое покрытие и убрала выход по первому решению.
За десять секунд нашлёпалось штук 50 вторых покрытий ортогональных заданному.
Таким образом, поиск пар точных ортогональных покрытий не проблема, их будет вагон и маленькая тележка.
Из каждой пары строим ассоциативный квадрат (процедура построения выполняется долю секунды); каждый ассоциативный квадрат проверяем на получение идеального квадрата (по программе whitefox на проверку одной пары нужна миллисекунда).
Ну и... реально ли на этом пути найти идеальный квадрат :?:

-- Сб июл 04, 2015 07:25:12 --

Ловить жар-птицу за хвост :wink:
Схема возможна такая:
1. первое точное покрытие массива находим случайной генерацией;
2. к первому покрытию находим только одно ортогональное второе;
3. из двух точных ортогональных покрытий строим ассоциативный квадрат;
4. проверяем ассоциативный квадрат на предмет получения из него идеального квадрата;
если идеальный квадрат не получен, возврат на пункт 1.

Готова попробовать.

whitefox
вы даёте свою программу проверки ассоциативного квадрата?

Вообще, по-хорошему, надо бы весь цикл объединить в одну программу.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение04.07.2015, 09:02 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #1033318 писал(а):
вы даёте свою программу проверки ассоциативного квадрата?

Ту программу уже переделал под массовую обработку. Но что-то не заладилось, нужно отладить.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение04.07.2015, 09:30 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А, ну тогда я буду ждать, когда вы отладите.
Спасибо.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение04.07.2015, 21:16 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Итак, сделала под программу whitefox генератор ассоциативных квадратов.
Сгенерировала 4 порции по 5000 штук и проверила. 5000 квадратов программа проверяет за 22,763 сек. Класс!
Мой генератор ассоциативных квадратов, к сожалению, работает не так быстро, 5000 штук генерируются примерно 20 минут.

Ну и результат вполне ожидаемый: ни один из 20000 ассоциативных квадратов в идеальный не превратился.
В общем, вероятность попасть на тот ассоциативный квадрат, который превратится в идеальный, очень близка к нулю.
Более того, она, может быть, даже и равна нулю - если решения не существует.
Сильно подозреваю, что это так и есть. Однако... это надо доказать.
Один из возможных способов доказательства - доказать, что не существует ни одного комплекта из 4-х точных попарно ортогональных покрытий массива. Но и это доказать не так просто.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение05.07.2015, 01:11 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Эксперимент

Вот из этого массива простых чисел

Код:
5 23 41 59 83 101 113 149 173 191 269 293 311 353 359 443 461 479 491 503 509 521 563 569 761 773 821 839 863
929 971 1031 1091 1181 1193 1283 1289 1301
1319 1409  1451 1493 1583 1601 1613 1619 1709 1721 1811 1871 1931 1973 2039 2063 2081 2129 2141 2333 2339 2381 2393
2399 2411 2423 2441 2459 2543 2549 2591 2609 2633 2711 2729 2753 2789 2801 2819 2843 2861 2879 2897

составляется идеальный квадрат 9-го порядка с магической константой $S=13059$.

Генерирую случайным образом первое точное покрытие массива:

Код:
173 509 2897 2819 2081 1931 563 23 2063 
479 1301 1613 2861 311 1811 1409 2753 521 
443 503 2633 359 2549 2141 2789 1583 59 
1709 2711 1721 461 1283 491 1871 2039 773
101 929 293 2333 1451 2801 1973 2609 569 
2129 863 1031 2411 1619 2441 1181 191 1193
2843 1319 113 761 353 2543 269 2399 2459
2381 149 1493 1091 2591 41 1289 1601 2423
839 2879 2339 971 821 83 5 2393 2729

Далее по этому покрытию генерирую 5000 ассоциативных квадратов.
Проверяю их по программе, ни одного идеального квадрата не получено!
Пристраиваю в хвост массива (5001-ым квадратом) известный идеальный квадрат, программа его возвращает:

Код:
Sun Jul 05 00:53:47 2015

2843 149 1973 2039 971 1031 2141 293 1619
2063 563 1811 113 2549 1601 2633 1721 5
2393 503 1613 2381 1193 41 2411 101 2423
173 2711 2879 773 1583 1493 461 443 2543
569 83 821 311 1451 2591 2081 2819 2333
359 2459 2441 1409 1319 2129 23 191 2729
479 2801 491 2861 1709 521 1289 2399 509
2897 1181 269 1301 353 2789 1091 2339 839
1283 2609 761 1871 1931 863 929 2753 59

Даже в случае, когда идеальный квадрат из чисел заданного массива составляется, найти его данным способом (через ассоциативные квадраты) очень проблематично.

Осталось получить из этого идеального квадрата комплект из 4-х точных попарно ортогональных покрытий, из этих покрытий образовать 6 пар ортогональных покрытий, построить из пар покрытий 6 ассоциативных квадратов и ещё раз протестировать получение идеального квадрата из этих ассоциативных квадратов.
Завтра уже выполню этот эксперимент.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение05.07.2015, 09:39 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Эксперимент

Комплект из 4-х точных попарно ортогональных покрытий, получен из известного решения с магической константой $S=13059$, все цепочки нормализовала:

Код:
#1
149 293 971 1031 1619 1973 2039 2141 2843
5 113 563 1601 1721 1811 2063 2549 2633
41 101 503 1193 1613 2381 2393 2411 2423
173 443 461 773 1493 1583 2543 2711 2879
83 311 569 821 1451 2081 2333 2591 2819
23 191 359 1319 1409 2129 2441 2459 2729
479 491 509 521 1289 1709 2399 2801 2861
269 353 839 1091 1181 1301 2339 2789 2897
59 761 863 929 1283 1871 1931 2609 2753

#2
173 359 479 569 1283 2063 2393 2843 2897
83 149 503 563 1181 2459 2609 2711 2801
269 491 761 821 1613 1811 1973 2441 2879
113 311 773 1301 1409 1871 2039 2381 2861
353 971 1193 1319 1451 1583 1709 1931 2549
41 521 863 1031 1493 1601 2129 2591 2789
23 461 929 1091 1289 2081 2141 2411 2633
101 191 293 443 1721 2339 2399 2753 2819
5 59 509 839 1619 2333 2423 2543 2729

#3
23 149 839 1283 1583 1811 2381 2399 2591
113 191 509 1193 1493 1973 2081 2609 2897
41 461 479 761 1181 2039 2549 2729 2819
269 359 443 971 1601 1871 2333 2411 2801
59 563 773 1289 1451 1613 2129 2339 2843
101 491 569 1031 1301 1931 2459 2543 2633
83 173 353 863 1721 2141 2423 2441 2861
5 293 821 929 1409 1709 2393 2711 2789
311 503 521 1091 1319 1619 2063 2753 2879

#4
41 59 293 311 1583 2441 2633 2801 2897
479 773 821 839 1193 1601 2141 2459 2753
83 359 509 929 1031 2339 2381 2549 2879
113 569 863 971 1091 1613 2399 2711 2729
491 1181 1283 1409 1451 1493 1619 1721 2411
173 191 503 1289 1811 1931 2039 2333 2789
23 353 521 563 1871 1973 2393 2543 2819
149 443 761 1301 1709 2063 2081 2129 2423
5 101 269 461 1319 2591 2609 2843 2861

Шесть ассоциативных квадратов, построенных из шести пар точных ортогональных покрытий, образованных из данных 4-х попарно ортогональных покрытий:

(Оффтоп)

Код:
2843  149  1973  2039  971  1031  2141  293  1619
2063  563  1811  113  2549  1601  2633  1721  5
2393  503  1613  2381  1193  41  2411  101  2423
173  2711  2879  773  1583  1493  461  443  2543
569  83  821  311  1451  2591  2081  2819  2333
359  2459  2441  1409  1319  2129  23  191  2729
479  2801  491  2861  1709  521  1289  2399  509
2897  1181  269  1301  353  2789  1091  2339  839
1283  2609  761  1871  1931  863  929  2753  59

149  1973  2039  971  2843  1031  2141  293  1619
1811  113  2549  1601  563  2633  1721  5  2063
2381  1193  41  2411  1613  101  2423  2393  503
1583  1493  461  443  773  2543  173  2711  2879
2591  2081  2819  2333  1451  569  83  821  311
23  191  2729  359  2129  2459  2441  1409  1319
2399  509  479  2801  1289  491  2861  1709  521
839  2897  1181  269  2339  1301  353  2789  1091
1283  2609  761  1871  59  1931  863  929  2753

293  2141  1031  971  1619  2039  1973  149  2843
2633  1601  2549  113  1721  1811  563  2063  5
41  1193  2381  1613  2411  503  2393  2423  101
1583  773  2879  2711  1493  173  2543  443  461
311  821  83  569  1451  2333  2819  2081  2591
2441  2459  359  2729  1409  191  23  2129  1319
2801  479  509  2399  491  1289  521  1709  2861
2897  839  2339  1091  1181  2789  353  1301  269
59  2753  929  863  1283  1931  1871  761  2609

1283  2897  479  359  2843  569  173  2393  2063
149  2609  1181  2801  563  2459  83  2711  503
1811  1973  761  269  1613  491  2441  821  2879
2381  113  2039  1871  773  1301  2861  1409  311
1583  1193  2549  971  1451  1931  353  1709  1319
2591  1493  41  1601  2129  1031  863  2789  521
23  2081  461  2411  1289  2633  2141  929  1091
2399  191  2819  443  2339  101  1721  293  2753
839  509  2729  2333  59  2543  2423  5  1619

2897  479  359  569  1283  173  2393  2063  2843
2801  2459  83  2711  1181  503  563  149  2609
2441  821  2879  1613  491  1811  1973  761  269
311  773  2381  113  1409  2039  1871  1301  2861
1583  1193  2549  971  1451  1931  353  1709  1319
41  1601  1031  863  1493  2789  521  2129  2591
2633  2141  929  1091  2411  1289  23  2081  461
293  2753  2339  2399  1721  191  2819  443  101
59  839  509  2729  1619  2333  2543  2423  5

1583  839  2381  2399  1283  1811  23  149  2591
2897  1193  509  113  1493  191  1973  2081  2609
41  479  2549  2729  1181  2039  2819  761  461
2801  1601  359  971  2411  2333  1871  443  269
59  773  2339  1613  1451  1289  563  2129  2843
2633  2459  1031  569  491  1931  2543  1301  101
2441  2141  83  863  1721  173  353  2423  2861
293  821  929  2711  1409  2789  2393  1709  5
311  2753  2879  1091  1619  503  521  2063  1319

Ввожу эти ассоциативные квадраты в программу whitefox. Программа выдаёт два идеальных квадрата:

Код:
Sun Jul 05 09:21:55 2015

2843 149 1973 2039 971 1031 2141 293 1619
2063 563 1811 113 2549 1601 2633 1721 5
2393 503 1613 2381 1193 41 2411 101 2423
173 2711 2879 773 1583 1493 461 443 2543
569 83 821 311 1451 2591 2081 2819 2333
359 2459 2441 1409 1319 2129 23 191 2729
479 2801 491 2861 1709 521 1289 2399 509
2897 1181 269 1301 353 2789 1091 2339 839
1283 2609 761 1871 1931 863 929 2753 59

971 359 1601 2801 2411 269 443 1871 2333
2729 2549 479 41 1181 461 761 2819 2039
113 509 1193 2897 1493 2609 2081 1973 191
2399 2381 839 1583 1283 2591 149 23 1811
1613 2339 773 59 1451 2843 2129 563 1289
1091 2879 2753 311 1619 1319 2063 521 503
2711 929 821 293 1409 5 1709 2393 2789
863 83 2141 2441 1721 2861 2423 353 173
569 1031 2459 2633 491 101 1301 2543 1931

Первый совпадает с исходным известным решением, а второй эквивалентен ему с точность до преобразования "линии - диагонали" по Россеру.
И опять квадраты построились из первого и шестого ассоциативных квадратов.

Кто готов помочь в поиске комплекта из 4-х точных попарно ортогональных покрытий для минимального идеального квадрата 9-го порядка из различных простых чисел?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 153 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8, 9, 10, 11  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group