Задача на рекурсию., Надо составить таблицу где будут все цифры в диапазоне от 1 до N и где Опции

[DarkWishmaster]

Привет.
Вообщем дано число N. Надо выяснить если возможно поставить все числа в диапазоне от 1 lдо N в массив из L линий так что-бы сума чисел из каждой линии будет одинаковой. (место той или иной цифры в массиве не важно, главное что бы не повторялись)
Например N:=8 , L=4
1 8 9 (для этого примера у меня всё работает, и для всех где N=2*L;
2 7 9 Я как понимаю что тут надо Бэктрэкинг использовать или другую рекурсию, но как это сделать
3 6 9 я не знаю.
4 5 9 {в первых колонках цифры, в третий сума}

for i:=1 to N do                                                              
         S:=S+i;                                                              
              if S mod L<>0 then Q:=false     {тут выяснем суму которую надо посчитать,                                
                 else Q:=true;                               например если если N=8 то сума будет 9}                 
            S:=S div L;                                                       
if Q=True then     begin                                                      
   for i:=1 to L do begin                                                     
   k:=0;   Sa:=0; M:=N+1-i;                                                   
   while Sa<>S do begin                                                       
     Sa:=Sa+M;                                                               {а тут бред... числа всё равно повторяются}
            inc(k);                                                           
           if Sa>S then begin Sa:=Sa-M; dec(m); dec(k)                        
            end else begin a[i,k]:=M; dec(m); end;                            
            h:=k;                                                             
      end;                                                                    
    end;                                                                      
   end;                                                                       
for i:=1 to L do begin                                                        
 a[i,k+1]:=S;                                                                 
 for j:=1 to  k+1 do begin                                                    
  write(a[i,j],' '); end;                      

Сообщение отредактировано: DarkWishmaster - 7.02.2011 12:43

[TarasBer]

Ну идеи такие.
Понятно, что групп должно быть не более, чем (N+1) div 2, иначе в хотя бы двух группах будет только 1 число и сумма будет разная.
Сумма чисел в каждой группе равна M := N*(N+1) div 2 div L (да, оно должно делиться, иначе создание сумм невозможно).
Далее, если M < 2*N , то делаем так:

В 1ю группу запихиваем два числа: N и M-N. Во вторую - N-1 и M-N+1. И так далее, пока не дойдём до набора M div 2 +1, M div 2 (если M - нечётное) или до набора из одного числа M div 2.
Теперь максимальное число стало M div 2 - 1, сумма чисел в группах по-прежнему должна равняться M.

Если же M>=2*N, то делаем так:

Во все группы (от 1 до L-ой) запихиваем поочерёдно числа по убыванию. Потом ещё раз делаем то же, но от Lй до 1й.
Тогда во все группы будет положена одинаковая сумма 2*(N-L)+1. В 1й группе будут 2 числа - N и N-2*L+1, а в
Lй группе - N-L+1 и N-L.

То есть максимальное число стало N-2*L, а сумма стала M-(N-2*L+1).

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

> for i:=1 to N do
> S:=S+i;

А формулу суммы чисел от 1 до N не знаем? S := N*(N+1) div 2;

> if S mod L<>0 then Q:=false {тут выяснем суму которую надо посчитать,
> else Q:=true;

Q := (S mod L = 0); не?

> if Q=True then begin

if ((((Q=True)=True)=True)=True) then begin...

Пиши просто if Q then begin

[DarkWishmaster]

TarasBer,
Спасибо за подсказки, надеюсь получиться у меня.