Řešení hledání min – Delphi – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Řešení hledání min – Delphi – Fórum – Programujte.comŘešení hledání min – Delphi – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Martin
~ Anonymní uživatel
1377 příspěvků
18. 4. 2009   #1
-
0
-

Ahoj všem
Vymyslel jsem si menší blbost do školy v domnění že to bude jednoduché, ale trochu jsem to podcenil..

Programuju hledání min, které zároveň mají obsahovat jakéhosi řešitele. Představoval jsem si ho tak, že hracím poli vyberu některá políčka, a program mi spočítá, které z nich je bezpečné/určitě je na něm mina/pravděpodobnost, z jakou na něm je mina.
Jenže nevím, jak s pomocí čísel počtu min u okolních políček spočítat ony pravděpodobnosti, např.


a potřebuju spočítat pravděpodobnost u políček A,B,C,D,E.
Na wikipedii nějaký postup je - http://en.wikipedia.org/wiki/Minesweeper_(computer_game) , s rovnicema, netuším ale, jak to naprogramovat(jde to vůbec?).

Potřeboval bych nejaký jiný postup, ideálně aby mi spočítal ty pravděpodobnosti.
Diky za pomoc

Nahlásit jako SPAM
IP: 85.132.181.–
Reklama
Reklama
Martin
~ Anonymní uživatel
1377 příspěvků
18. 4. 2009   #2
-
0
-

Špatně jsem vložil obrázek, přikládám opravený..

Nahlásit jako SPAM
IP: 85.132.181.–
o-lox0
Super člen
19. 4. 2009   #3
-
0
-

Ten algoritmus mi vyšel na 15 řádek, vůbec si nelam hlavu s rovnicema, normálně to vše vyčísli (postupnou inkrementací) a nakonec vyděl, protože se nedočkáš nijak velkých čísel, musí to být vypočítané ve zlomkovém čase...

Ještě jsem to u sebe drobně doupravil - pro dlouhé úseky jsem se uchýlil k fintě, dělení po 6 čtverečcích, přišlo mi to pro dělení na 6 nejrychlejší. Před vlastním cyklem určujícím pravděpodobnost jsem udělal paměťové sejmutí všech 6ti políčkových skupin, ve vlastní smyčce se tak několikanásobně zrychlil běh. Teď to zvládá nenáročné úseky (rychlejší to mám pro řidší výskyt min) okolo 40 a dalo by se ještě optimalizovat.
Ukázkový zdroják klidně s tebou povyměnim :-))

Nahlásit jako SPAM
IP: 85.71.152.–
Martin
~ Anonymní uživatel
1377 příspěvků
19. 4. 2009   #4
-
0
-

Zapomněl jsem připsat, že jsem tak nějak spíš začátečník.... a právě jsem to moc nepobral :-D

Můžeš prosím přiložit ten zdroják? Z toho to snad poberu, diky moc.

Nahlásit jako SPAM
IP: 85.132.181.–
o-lox0
Super člen
19. 4. 2009   #5
-
0
-

Jakmile to bude šňůra třeba 80 svázaných políček,
tak stejně se ovšem výsledku nedočkáš. Pak bych sám rád našel odlišnej přístup.
Z hotového kódu nikdy nic pořádného nepobereš, převod do binární soustavy,
testování, nic víc na tom neni...

Doporučuji ti jestli to na tebe neni velké sousto zmohutnit skupiny na 8,10. 6 je
nakonec pro cache se mi zdá zbytečně málo.

Var

pole : array[1..58]of byte;
pole2 : array[1..12]of tpole;
delka : array[1..58]of byte;
vpoli:array[1..58] of integer;
maxima : array[1..58,1..58]of shortint;
{maxima jsou ty samotne cisla platne pro policka
mam je v jedne rade za sebou proto kazde maxima zasahuje do 3 / jedno cislo sikmonahoru,doprava,sikmodolu
}
pravd: array[1..58]of real;
zas : array[1..12]of t1;
pocet:integer;

{--------}
For i:=1 to n do
begin
For ii:=0 to 64 do begin
suma:=ii;
for j:=1 to delka[i] do begin pole2[i,j]:=0;
pole2[i,j]:=suma mod 2;
suma:=suma div 2;
end;

b:=0;
for j:=1 to n do begin
for a:=1 to delka[j] do pole[b+a]:=pole2[j,a];
b:=b+delka[j];
end;
test1:=true;
for j:=1 to l do begin
a:=1;
while (maxima[j,a]=-1)and(a<l) do inc(a);
suma:=0;
while maxima[j,a]<>-1 do
begin
suma:=suma+pole[a];
inc(a);
end;
If suma>maxima[j,a-1] then begin
{
TAHLE PODMINKA NENI VUBEC OPTIMALNI
U MAXIMA ktere je plne kryto v dane skupine je potreba testovat rovnost!
u okraju pak dejme tomu takhle
}
test1:=false; break; end;
suma:=0;
end;
If not test1 then continue;
zas[i].h[zas[i].uk]:=pole2[i];
inc(zas[i].uk);
end;
end;


To byla předpříprava

 Repeat

For ii:=1 to n do begin
pole2[ii]:=zas[ii].h[vpoli[ii]];
end;
i:=1;
while vpoli[i]>=zas[i].uk do begin
vpoli[i]:=0;
inc(i);
inc(vpoli[i]);
end;
If i>n then break;
inc(vpoli[1]);

i:=0;
for j:=1 to n do begin
for a:=1 to delka[j] do pole[i+a]:=pole2[j,a];
i:=i+delka[j];
end;

test1:=true;
for j:=1 to 25 do
begin
a:=1;
while (maxima[j,a]=-1)and(a<l) do inc(a);
suma:=0;
while maxima[j,a]<>-1 do
begin
suma:=suma+pole[a];
inc(a);
end;
If suma<>maxima[j,a-1] then begin test1:=false; break; end;
suma:=0;
end;
If not test1 then continue;
for j:=1 to l do
If pole[j]=1 then
pravd[j]:=pravd[j]+1;
inc(pocet);

until false;


Tohle bylo samotné řešení výsledky jsou vysledek:=pravd[a]/pocet:4:2;

Spíš to ale pochopíš z tohohle základního

 For i:=1 to 2 shl n do begin

suma:=i;
for j:=1 to n do begin pole[j]:=0;
pole[j]:=suma mod 2;
suma:=suma div 2;
end;
test1:=true;
for j:=1 to 3 do
begin
a:=1;
while maxima[j,a]=0 do inc(a);
suma:=0;
while maxima[j,a]<>0 do
begin
suma:=suma+pole[a];
inc(a);
end;
If suma<>maxima[j,a-1] then test1:=false;
end;
If not test1 then continue;
for j:=1 to n do
If pole[j]=1 then pravd[j]:=pravd[j]+1;
inc(pocet);

end;


Nahlásit jako SPAM
IP: 85.71.152.–
Martin
~ Anonymní uživatel
1377 příspěvků
19. 4. 2009   #6
-
0
-

Ale ať dělám co dělám, ani že zdrojáku se mne nedaří pochopit myšlenku. Nemám moc ve zvyku se takto ptát, nechci vypadat jak telátko s přístupem "udělej to za mně", to jsem ani nechtěl ;-)
Potřeboval bych to ale pochopit, mohl bys prosím trochu víc rozepsat myšlenku(nejspíš bych potřeboval spíš takovou verzi pro blbečky :-D), případně víc okomentovat kód?

Díky.

Nahlásit jako SPAM
IP: 85.132.181.–
o-lox0
Super člen
20. 4. 2009   #7
-
0
-

No to neni moc zábava, popisovat ti začátek, kterej budeš muset setsakra zrychlovat, protože je sám o sobě nepoužitelně pomalej.

mina: maxima:
1
*2
*2
1
1
*1
1
0

POCET:=0;

máš 8 políček-
00000000 - znamená žádná mina
00000001 - znamená mina na pozici na konci, a taky BINARNI 1
00000010 - znamená mina na pozici o jedno vlevo a taky BINARNE 2
11100000 - znamená 224 a 3 miny ty ovšem musíš testovat viz:

každý úsek jsem si uložil do pole maxima, to pole jsem psal je trojrozmerne, porovnas ho s polem 11100000
i:=1 to 3
suma:=suma+pole[index+i] // jakkoliv te napadne
suma=3>maxima[j] then MIMOPODMINKU NEPLATNE

Naopak kdyz suma=maxima[j]
nove pole floating point inkrementujes
0 -- 0 -- 0 -- 1 -- ..miny
z
0.0 0.0 0.0 0.0 ....atd
na
0.0 0.0 0.0 1.0 // pro minu na pozici 4

+ inkrementace POCET

vysledek [index]/pocet = HURA

Jestli neutahnes zaklad, vybodni se na to a vzdej to, vrat se k tomu nekdy se zkusenostmi pozdeji.

Nahlásit jako SPAM
IP: 85.71.152.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 14 hostů

Podobná vlákna

Hledání min (nul) — založil David2563

Firefox a min-height — založil Petr

Min or max v seznamu — založil Karel

Min a Max hodnota z čísel — založil Martin

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý