Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 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.57 MB
Время: 0.023 c
1-1808
Мефодий
2002-12-18 10:51
2003.01.02
Проблема очистки страницы в QuickReport


1-1795
Фил
2002-12-18 00:08
2003.01.02
Атрибуты файла


14-1916
F1
2002-12-15 13:27
2003.01.02
Точка в полигоне!!!


4-1935
.nuke
2002-11-16 14:07
2003.01.02
grayscale


4-1930
Odd_1
2002-11-16 13:25
2003.01.02
mouse





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский