Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 30.06.2003, 22:20   #1
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default кто рискнет ?

Так. люди. вы какие-то пассивные ,программеры :)

для начинающих предлагаю занять свое свободное время (послесессионное) следующим:

написание игры 'Life', которая умеет играть на бесконечном поле
и
написание алгоритма, который бы умел генерить
лабиринты (все линии под углами 90 градувос к друг другу, косых линий нет), которые проходимы из любой точки в другую.

для желающих потренировать мозги и размяться - вперед ;)
если есть вопросы - пишите сюда или в приват
Reply With Quote
Old 01.07.2003, 05:00   #2
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

Меня вот что волнует в первой задачке - я же могу сгенерить такую популяцию, которая разрастется до бесконечности - и никакого озу тебе не хватит...
Reply With Quote
Old 01.07.2003, 06:43   #3
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

Quote:
Originally posted by Agregat
Меня вот что волнует в первой задачке - я же могу сгенерить такую популяцию, которая разрастется до бесконечности - и никакого озу тебе не хватит...
а ты свапуй на диск, в файлы

а что, идейка некосмическая, можна пораскинуть у кого чем есть...

а каковы правила этой игры ?
Reply With Quote
Old 01.07.2003, 06:45   #4
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

Гарик, могу объяснить и на пальцах, но лучше пусть Гугл найдет тебе хорошие ссылки.
Автор игры - Конвей. Игра - жизнь.
Первая приличная ссылка вот
http://www.elvisti.kiev.ua/skl/conwey1/w_life_n.htm
Я делал ее еще на паскале на первом курсе и для ограниченного поля.
Reply With Quote
Old 10.07.2003, 19:50   #5
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally posted by Agregat
Гарик, могу объяснить и на пальцах, но лучше пусть Гугл найдет тебе хорошие ссылки.
Автор игры - Конвей. Игра - жизнь.
Первая приличная ссылка вот
http://www.elvisti.kiev.ua/skl/conwey1/w_life_n.htm
Я делал ее еще на паскале на первом курсе и для ограниченного поля.

как ты заметил - речь шла именно об неограниченном поле, но не о популяции. кстати огромная популяция - она скорее всего у тебя либо периодическая, либо повторяет саму себя с мааленькими изменениями - я думаю, что оно должно аатличненько так сжиматься ....
Reply With Quote
Old 11.07.2003, 05:16   #6
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

Гаспар, ты можешь доказать или привести ссылку на доказательство, но не существует неограниченно растущих популяций?
Reply With Quote
Old 11.07.2003, 09:31   #7
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally posted by Agregat
Гаспар, ты можешь доказать или привести ссылку на доказательство, но не существует неограниченно растущих популяций?
я говорил что то подобное ? попытайся перечитать мой пост еще раз

хотя . все равно . как я вижу программеры у нас более важными делами заняты
Reply With Quote
Old 11.07.2003, 10:14   #8
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

Я понял о чем ты.
Но все же если существуют такие популяции ("она скорее всего у тебя" - не совсем устраивает ) - то никакое сжатие тебе не поможет.
А делом на самом деле заняты другим...
Reply With Quote
Old 11.07.2003, 17:23   #9
Banned
 
DaNYer's Avatar
 
Join Date: 10 2002
Location: Brooklyn, New York
Age: 39
Posts: 3,760
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

menya zainteresovala eta zadachka. popodrobnee pls. mne nikogda ne prixodilos' s takim stalkivat'sya. kak doljen bil predstavlen labirint? kakaya texnika? matrica?
Reply With Quote
Old 11.07.2003, 21:12   #10
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally posted by DaNYer
menya zainteresovala eta zadachka. popodrobnee pls. mne nikogda ne prixodilos' s takim stalkivat'sya. kak doljen bil predstavlen labirint? kakaya texnika? matrica?
bez raznicy, kak tebe udobno , tak i predstawljaj ... nu . dlja konkretizacii skazhu -
labirint prjamougol'nyj, NxM kletok (podskazka - (2n+1 na 2m+1 kletok) wse stenki idut pod uglami 0,90,180,270 gradusow drug k drugu
esli predstawljaesh w wide matricy -
skazhem wse stenki pomechaesh 1 , wse pustye mesta 0 ... nado sozdat'/pridumat' algoritm, kotoryj pozwolit stroit' labirinty, iz ljuboj pustoj (0) tochki kotorogo w ljubuju druguju pustuju tochku mozhno projti...
Reply With Quote
Old 15.07.2003, 02:06   #11
инсценирующи
 
[ Xelgen ]'s Avatar
 
Join Date: 07 2002
Location: Fireplace of Ecotopia
Age: 31
Posts: 4,327
Downloads: 22
Uploads: 0
Reputation: 193 | 4
Default

Quote:
Originally posted by nm
кто рискнет?
ну я... рискну..

вообще то как выходить их лаюиринта имеющего выход, думаю все знают, модет здесь это как то задействовать...

кстати "проходимы из любой точки в другую" означает что во всем лабиринте один общий "коридор"?
Reply With Quote
Old 15.07.2003, 08:40   #12
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally posted by [ Xelgen ]
ну я... рискну..

вообще то как выходить их лаюиринта имеющего выход, думаю все знают, модет здесь это как то задействовать...

кстати "проходимы из любой точки в другую" означает что во всем лабиринте один общий "коридор"?

da
Reply With Quote
Old 21.07.2003, 09:41   #13
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

pro labirint ya dumayu - volnovoj algoritm daet reshenie na ura
Reply With Quote
Old 06.08.2003, 13:47   #14
Дошкольник
 
Join Date: 03 2003
Location: 2A
Age: 49
Posts: 104
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Life

Поле может быть бесконечным только в теории, а так в данном примере MinInt .. MaxInt (можно конечно поменять на int64).
Сразу говорю пример написан с руки (не оптимизирован и могут быть логические ошибки).

interface
uses Classes;

type
TItemState = (sEmpty, sStable, sNew, sDying);
TDirection = (dNone, dLeft, dLeftTop, dTop, dRightTop, dRight, dRightBottom, dBottom, dLeftBottom);

PItem = ^TItem;
TItem = record
X: integer;
Y: integer;
State: TItemState;
end;

TPopulation = class(TList)
private
procedure CalculateDirections(Direction: TDirection; var X, Y: integer);
function GetItemState(X, Y: integer; Direction: TDirection = dNone): TItemState;
procedure MarkNeighbours;
public
procedure AddItem(X, Y: integer);
procedure ClearPopulation;
procedure Run(Step: integer = 1);
end;

implementation

procedure TPopulation.CalculateDirections(Direction: TDirection; var X, Y: integer);
begin
case Direction of
dLeft: dec(X);
dLeftTop: begin
dec(X);
dec(Y);
end;
dTop: Dec(Y);
dRightTop: begin
inc(X);
dec(Y);
end;
dRight: inc(X);
dRightBottom: begin
inc(X);
inc(Y);
end;
dBottom: inc(Y);
dLeftBottom: begin
dec(X);
inc(Y);
end;
end;
end;

function TPopulation.GetItemState(X, Y: integer; Direction: TDirection = dNone): TItemState;
var
i: integer;
begin
result:= sEmpty;
CalculateDirections(Direction, X, Y);
for i:= 0 to Count - 1 do
if (PItem(Self[i])^.X = X) and (PItem(Self[i])^.Y = Y) then
begin
result:= PItem(Self[i])^.State;
break;
end;
end;

procedure TPopulation.MarkNeighbours;
var
i: integer;
Dir, Dir1: TDirection;
Item: PItem;
NewItem: PItem;
NeighboursCount: byte;
NeighboursCountForEmptyItem: byte;
X, Y: integer;
begin
i:= 0;
while i < Count do
begin
NeighboursCount:= 0;
Item:= PItem(Self[i]);
if Item^.State = sStable then
begin
for Dir:= dLeft to dLeftBottom do
case GetItemState(Item^.X, Item^.Y, Dir) of
sStable, sDying: inc(NeighboursCount);
sEmpty: begin
NeighboursCountForEmptyItem:= 0;
new(NewItem);
X:= Item^.X;
Y:= Item^.Y;
CalculateDirections(Dir, X, Y);
NewItem^.X:= X;
NewItem^.Y:= Y;
for Dir1:= dLeft to dLeftBottom do
case GetItemState(NewItem^.X, NewItem^.Y, Dir1) of
sStable, sDying: inc(NeighboursCountForEmptyItem);
end;
if NeighboursCountForEmptyItem = 3 then
begin
NewItem^.State:= sNew;
Self.Add(NewItem);
end else
dispose(NewItem);
end;
end;
if (NeighboursCount < 2) or (NeighboursCount > 3) then
Item^.State:= sDying;
end;
inc(i);
end;
end;

procedure TPopulation.Run(Step: integer = 1);
var
i, j: integer;
begin
for i:= 1 to Step do
begin
MarkNeighbours;
j:= 0;
while j < Count do
begin
case GetItemState(PItem(Self[j])^.X, PItem(Self[j])^.Y) of
sNew: begin
PItem(Self[j])^.State:= sStable;
inc(j);
end;
sDying: begin
Dispose(Self[j]);
Self.Delete(j);
end;
else inc(j);
end;
end;
Pack;
end;
end;

procedure TPopulation.AddItem(X, Y: integer);
var
P: PItem;
begin
new(P);
P^.X:= X;
P^.Y:= Y;
P^.State:= sStable;
Add(P);
end;

procedure TPopulation.ClearPopulation;
var
i: integer;
begin
for i:= 0 to Count - 1 do
Dispose(Self[i]);
Clear;
end;
Reply With Quote
Old 06.08.2003, 13:59   #15
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

А Pack это метод класс TList?
И что он представляет собой? Связанный список?
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 03:59.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.