Помощь - Поиск - Пользователи - Календарь
Полная версия: Задача на рекурсию.
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
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;
TarasBer
Ты вывел все цифры числа 12345678.
А по условию надо вывести все цифры числа 8 (то есть одну-единственную цифру).
Что на самом деле написано в условии?
DarkWishmaster
Цитата(TarasBer @ 7.02.2011 11:31) *

Ты вывел все цифры числа 12345678.
А по условию надо вывести все цифры числа 8 (то есть одну-единственную цифру).
Что на самом деле написано в условии?


Ну так так и надо, вывести все числа в диапазоне от 1 до N в L линий так что-бы сума в каждой линии было одинаковой;
Например N=64
L:=8
1 4 6 3..... сума
2 32 13 ..... сума
и так 8 линий, но чтобы числа не повторялись в масиве.
Что написано в условии точно написать не могу, так как оно было на другом языке.
Всё, исправил первый пост, я там неправильно написал, извините.
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,
Спасибо за подсказки, надеюсь получиться у меня.
TarasBer
> Спасибо за подсказки, надеюсь получиться у меня.

http://tsya.ru/
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.