помогите с массивами!!!

[VILLIREX]

здравствуйте помогите пожалуйста решить задачу
Задано 121 натуральное число - 1,2,3, . . ., 121. Составить программу, которая располагает эти числа в 11 групп так, что одновременно будут выполняться следующие условия:
1) каждая группа содержит точно 11 чисел;
2) каждое число принадлежит только одной группе;
3) сумма чисел в каждой отдельной группе одинакова для всех групп.

[Serge_Bliznykov]

Прежде всего - не уверен, что решение вообще существует ;-) Хотя возможно, что и существует...

исходя из заданных условия (сумма всех чисел от 1 до 121 = 7381. Делим на 11 (т.к. 11 групп) получается, что сумма в каждой группе должна быть ровно 671.
и, судя по тому что все числа различны и все без исключения должны войти в группы, то решение (если оно есть) - единственное!

Заводим массив на 121 элемент (индекс массива - это число), а значение массива = номеру группы, в которую данное число входит.
Дальше - перебором находим 11 элементов массива, сумма которых строго равна 671 (вот в этом переборе и заключена основная сложность задачи!)
всем найденным элементам проставляем номер группы.
Наращиваем номер группы на единицу и перебираем оставшиеся элементы массива (которые ещё не входят ни в одну группу).

[eoln]

Почесал голову и попробовал провести мат анализ.
1) Предположим что чисел не 121, а 11, тогда получим такое
01 02 03 04 05 06 07 08 09 10 11

2) Теперь добавим диапазон 12-33, получим
01 02 03 04 05 06 07 08 09 10 11
22 21 20 19 18 17 16 15 14 13 12
23 24 25 26 27 28 29 30 31 32 33
Вторые и третьи элементы каждого из столбцов дают в сумме одинаковое число, но первый элемент каждого столбца портит дело. Единственная возможная операция (имеющая цель изменить сумму чисел в столбцах) - обмен числами между разными столбцами. Так как расхождение суммы столбца от нормы = i div 2 + 1, где i - номер столбца, то при обмене на внутри одной строки произойдёт следующее:
S1 := S1 - i div 2 + 1 + j div 2 + 1 (*)
S2 := S2 + i div 2 + 1 - j div 2 + 1 (**)
где S2 = S1 - (j - i)
где S1, S2 - суммы i-того и j-того столбцов. Всё сделато в предположении j>i, иначе просто переименуем переменные. Вычислив выражения, видим, что варианты сумм столбцов неизменились.

3) При обмене элементов столбцов принадлежащих разным строкам просто к суммам будет прибавляться/отниматься константа

4) Далее добавляем диапазон 34-55 и повторяем рассуждения (мат индукция).
Получаем вывод - для подобной задачи с нечётным количеством строк решения нет.
Хотя я мог где-то ошибиться...

[puporev]

Решение есть, т.к. это упрощенный вариант магического квадрата ( в нем суммы равны не только по строкам, но и по столбцам и главной и побочной диагонали), а квадраты со стороной 3, 5, 7 точно существуют, когда-то решал, правда для 11 не решал. Помню что решение трудное, но полностью сейчас не помню.
Сейчас прочитал в Википедии, что такие квадраты существуют для всех n>=1, кроме n=2.
Вот принципы построения магического квадрата, должно пригодиться.

Построение магических квадратов
Правила построения магических квадратов делятся на три категории в зависимости от того, каков порядок квадрата: нечетен, равен удвоенному нечетному числу или равен учетверенному нечетному числу. Общий метод построения всех квадратов неизвестен, хотя широко применяются различные схемы.[12] Найти все магические квадраты порядка n удается только для , поэтому представляют большой интерес частные процедуры построения магических квадратов при n > 4. Проще всего конструкция для магического квадрата нечетного порядка. Нужно в клетку с координатами (i,j) поставить число 1 + ((i − j + (n − 1) / 2)mod n)n + (( − i − j + (n + 1) / 2)mod n).

Ещё проще построение выполнить следующим образом. Берётся матрица n x n . Внутри её строится ступенчатый ромб. В нём ячейки слева вверх по диагоналям заполняются последовательным рядом нечётных чисел. Определяется значение центральной ячейки C. Тогда в углах магического квадрата значения будут такими: верхняя правая ячейка C-1 ; нижня левая ячейка C+1 ; нижняя правая ячейка C-n ; верхняя левая ячейка C+n. Заполнение пустых ячеек в ступенчатых угловых треугольниках ведётся с соблюдением простых правил: 1)по строкам числа слева направо увеличиваются с шагом n + 1; 2) по столбцам сверху вниз числа увеличиваются с шагом n-1.

[Serge_Bliznykov]

я тоже глянул статейку на Википедии...
puporev, Вы абсолютно правы - это реальный способ решения задачи!! если вечерком будет полчасика - обязательно решу! (если смогу ;-)) )

Нужно в клетку с координатами (i,j) поставить число 1 + ((i − j + (n − 1) / 2)mod n)n + (( − i − j + (n + 1) / 2)mod n).

а вот почему эта формула у меня не заработала ;(
для N=3 какой квадрат у Вас получается по этомй формуле? или даже проще - задачка для устного счёта до 4-х: если в эту формулу подставить i=1 (первая строка) j=3 (третий столбец) и N=3 — чему будет равняться значение выражения??

[eoln]

Я всегда был плохим математиком
Вот выявил последовательность размещения чисел - каждый i-тый элемент группы может заполняться по порядку 1, 2, 3, ... n, а следующая группа начинается заполняться так n+1+k, n+2+k, ... n+(n-k), n+1,... n+k, где k - номер группы минус один. Тогда получим исходный код

const
  n = 11;

var
  mas: array[1..n, 1..n] of integer;
  i, j, jj, st, sum: integer;

begin
  st := 0; // номер группы
  for i := 1 to n do
  begin
    inc(st);
    for j := 1 to n do
    begin
      jj := j + st;//это позиция с которой начинаем заполнять
// группу
      if jj > n then jj := jj - n;//позиция от начала группы до того
//места откуда мы начинали заполнять эту группу
      mas[i, jj] := (i - 1) * n + j //собственно заполнение
    end
  end;
  //далее вывод на экран с подсчётом суммы 
//(проверка для наглядности чтобы калькулятором не считать)
  for i := 1 to n do
  begin
    sum := 0;
    for j := 1 to n do begin
      write(mas[j, i]:5);
      sum := sum + mas[j, i]
    end;
    writeln('   = ', sum:5);
  end;
  readln
end.

[puporev]

Я решение от Eoln не видел, у меня интернета не было, решил по другому, правда менее изящно. На всякий случай выложу.

uses crt;
const n=11;
var i,j:byte;
    sum:word;
    a:array[1..n,1..n]of word;
begin
clrscr;
//в первую строку записываем арифметичемкую прогрессию от 1 до n^2 
//с шагом (n^2-1)/(n-1)=(n+1)
for j:=1 to n do a[1,j]:=(n+1)*(j-1)+1;
//во второй строке увеличиваем все числа на 1, последнее уменьшаем на (n-1)
for j:=1 to n-1 do a[2,j]:=a[1,j]+1; a[2,n]:=a[1,n]-(n-1);
//начиная с третьей строки увеличиваем все на 1, те, что должны повториться,на 2, 
//последнее уменьшаем на n
for i:=3 to n do
     for j:=1 to n do
      begin
         if j=n-i+2 then a[I,j]:=a[i-1,j]+2
         else if j=n then a[I,j]:=a[i-1,j]-n
         else a[I,j]:=a[i-1,j]+1;
     end;
for i:=1 to n do
   begin
     sum:=0;
     for j:=1 to n do
      begin
        write(a[i, j]:5);
        sum:=sum+a[i,j];
      end;
    writeln(sum:7);
  end;
readln
end.

Порядок чисел естественно другой.

[VILLIREX]

Serge_Bliznykov ,eoln ,puporev спасибо большое всё работает.Классс!!!!

[Sasha_Smirnov]

Если у вас установлен Паскаль, выложите этот квадрат — интересно же!

[puporev]

Вот оба варианта. Но это не магический квадрат, это решение данной по условию задачи.