Очередная пятничная задачка ;)

← →
MBo © (2002-12-06 10:10) [0]

Антипаскалевский треугольник
Все целые числа от 1 до n*(n+1)/2 разместить в треугольнике так,
чтобы число, стоящее ниже двух других равнялось их разности по модулю.
Например
для n=2 (один из вариантов)

3 2
1

(1=3-2)

для n=3(один из вариантов)

1 6 4
5 2
3

Построить такие треугольники для n=4 и при возможности n=5

← →
Наталия © (2002-12-06 10:32) [1]

8 10 1 6
2 9 5
7 4
3

← →
MBo © (2002-12-06 11:10) [2]

Отлично!
Всего 4 варианта, если не учитывать зеркальные.
Для n=5 моя прога пока (за час) проверила 0.2% вариантов ;))

← →
MBo © (2002-12-14 10:57) [3]

Непереборный код.
для n=5 вариант всего один (+зеркальный)
для 6,7,8 - нет

6 14 15 3 13 8 1 12 10 7 11 2 4 9 5 procedure TForm1.Button1Click(Sender: TObject); const MaxSize=5; type matr=array[1..MaxSize,1..MaxSize] of byte; bset=set of byte; var a:matr; NMax:byte; procedure PrintSet(a:matr); var i,j:byte; s:string; begin for i:=maxsize downto 1 do begin s:=StringOfChar(" ",2*(maxsize-i)); for j:=1 to i do s:=s+Format("%4d",[a[i,j]]); memo1.lines.add(s); end; memo1.lines.add(""); memo1.refresh; end; procedure FillNext(b:bset; level, npos:byte); var i:byte; begin if level>maxsize then begin PrintSet(a); Exit; end; if npos>level then begin FillNext(b,level+1,1); Exit; end; if npos=1 then begin for i:=1 to nmax do if not (i in b) then begin a[level,1]:=i; FillNext(b+[i],level,2); end; Exit; end; i:=a[level,npos-1]-a[level-1,npos-1]; if (i<=nmax) and (not (i in b)) then begin a[level,npos]:=i; FillNext(b+[i],level,npos+1); end; i:=a[level,npos-1]+a[level-1,npos-1]; if (i<=nmax) and (not (i in b)) then begin a[level,npos]:=i; FillNext(b+[i],level,npos+1); end; end; begin FillChar(a,Sizeof(a),0); nmax:=MaxSize*(MaxSize+1) div 2; FillNext([],1,1); end;

← →
Oleg_Gashev © (2002-12-14 13:31) [4]

Мне не понравилось
matr=array[1..MaxSize,1..MaxSize] of byte;

Ты не весь массив используешь. Может его лучше задать как одномерный массив указателей на массив byte.

← →
MBo © (2002-12-14 20:51) [5]

>Oleg_Gashev
Конечно, при оптимизации это разумно. Здесь я использовал простейший метод, при котором легко увидеть алгоритм, не отвлекаясь на несколько усложненную адресацию. Кроме того, не использовано удаление зеркальных отражений (реализуется легко, всего лишь по второй строчке матрицы).
Думаю, в данном случае нет смысла экономить память - алгоритм способен работать только для небольших n (запускал при n<10, выч. сложность O~(15^n)), поэтому я и байтовое множество смог использовать.

Впечатляет выч.сложность алгоритма генерации всех матриц и проверки на указанные условия - O((n*(n+1)/2)!) ;)))

Я немножко поспешил с ответом. Matr можно задать как одномерный массив длиной MaxSize*(MaxSize+1)/2. Соответственно придется немного изменить алгоритм.

Первая строка: индексы 1..MaxSize
Вторая: MaxSize+1.. 2*MaxSize-1

> MBo © (14.12.02 20:51)
>
> Впечатляет выч.сложность алгоритма генерации всех матриц
> и проверки на указанные условия - O((n*(n+1)/2)!) ;)))

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

>Igorek
Это я не про приведенный алгоритм написал, а про полный перебор возможных матриц.

В приведенном же вижу несколько путей ускорения - в ~2 раза - за счет отсечения зеркальных отражений (по второй строчке)
Еще немного - если учитывать, что макс. число может находиться только в последней строчке и т.п. эвристика. Но это все нерадикально.

Очередная пятничная задачка ;) Найти похожие ветки