Форум: "Потрепаться";
Текущий архив: 2003.01.02;
Скачать: [xml.tar.bz2];
Вниз
Очередная пятничная задачка ;) Найти похожие ветки
← →
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)!) ;)))
← →
Oleg_Gashev (2002-12-14 21:31) [6]Я немножко поспешил с ответом. Matr можно задать как одномерный массив длиной MaxSize*(MaxSize+1)/2. Соответственно придется немного изменить алгоритм.
Первая строка: индексы 1..MaxSize
Вторая: MaxSize+1.. 2*MaxSize-1
← →
Igorek (2002-12-15 11:17) [7]
> MBo © (14.12.02 20:51)
>
> Впечатляет выч.сложность алгоритма генерации всех матриц
> и проверки на указанные условия - O((n*(n+1)/2)!) ;)))
Надо как-то оптимизировать. Использовать метод ветвей и границ возможно. Прикинул немного - надо большие и сложные графы разворачивать для быстроты поиска, только памяти много будет жрать.
← →
MBo (2002-12-15 13:08) [8]>Igorek
Это я не про приведенный алгоритм написал, а про полный перебор возможных матриц.
В приведенном же вижу несколько путей ускорения - в ~2 раза - за счет отсечения зеркальных отражений (по второй строчке)
Еще немного - если учитывать, что макс. число может находиться только в последней строчке и т.п. эвристика. Но это все нерадикально.
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2003.01.02;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.006 c
