Hódító / Queosia forum

Hódító / Queosia forum (http://forum.hodito.hu/index.php)

- PC (hardver, szoftver, játékok stb.) (http://forum.hodito.hu/forumdisplay.php?f=28)

- - Programozás (http://forum.hodito.hu/showthread.php?t=4435)

egy forráskódot nekem is küldenél??? elsőre én is hasonló algoritmusban gondolkodtam csak nem volt időm még foglalkozni vele.:)

Még annyi a kérdés, hogy az eredeti feladatban használható-e rekurzió vagy nem?

Gondolom igen, csak erősen nem ajánlott :) Területvizsgálatnál egy rekurzió hamar elszabadulhat (pl. felezéses közelítéseknél ha nincs limit, akkor 2^n felé tart a lehetséges újrahívások száma, ami elég bizonytalan futási időt eredményez)

Quote:

Originally Posted by Cpt Balu (Post 294264)

ezzel tisztában vagyok, de annyira nem vészes, ebben az esetben. csak mert szerintem megirnám rekurziv backtrack-kel is. ugyis kell gyakorolnom majd vizsgára, meg azért is, mert van olyan tételem, hogy rekurzív fügvényt kell átirni simára, és vissza.

Az átírás gyakorlatilag annyi, hogy while ciklus helyett függvényt hívsz :)
rekurziót akkor érdemes használni, ha egyébként túl sok köztes eredményt és állapotot kellene tárolni, ezt a függvény hívása megoldja nekünk, de pont ez a gyengéje is, a hívás és visszatérés sokszor lényegesen több mint maga a programkód futási ideje, ekkor kell választani, egy kis plusz programozásért cserébe gyorsíthatunk a kódon.
Elkezdem szép lassan írni az oldalra a jelenlegi progi algoritmusát is, remélem érdekesnek találjátok majd a gondolatmenetet :)

Quote:

Originally Posted by Cpt Balu (Post 294252)

(ps: ha moderátoroknak kifogásuk van linkelés miatt, várnék javaslatot hogy tudnám megoldani a képes postokat, img tagek behozták a képeket oszt el is tüntették rögtön, gondolom tiltva van külső hivatkozás bbc-ben)

Elvileg nincs, és img tagek jól működnek. Legalábbis eddig jól működtek. Nem lehet, hogy inkább a külső linkelés van letiltva annál az oldalaknál, ahonnan behúztad a képet? Mert olyat szoktak. Bár képmegosztó oldalaknál nem, de pl. az ingyenes tárhelyszolgáltatók ezt csinálják, hogy ne használd a tárhelyüket "háttértárolónak" egy másik oldalhoz.

Erre nem is gondoltam, köszi... :)
A fura h előnézetnél egy pillanatra megjelentek a képek, aztán eltűntek belőle, ezért gondoltam h fórum motor csinálja.
Időközben befejeztem az algoritmus leírásának első lépését, a "profilozást" (talán valakinek ismerős lesz a módszer), feltettem az oldalamra, nemsokára megírom az utolsó lépést, ami saját szerzemény, és kicsit bonyolult, de megpróbálom érthetően :)

Update: mialatt írtam a cikket, észrevettem egy dolgot, amit beletettem a progiba :)
Az új eredmény (csak a kritikus rész):

99,200% 393 415 463
99,300% 402 423 444
99,400% 430 450 474
99,500% 444 462 471
99,600% 440 459 471
99,700% 432 442 456
99,800% 399 420 438

Egyértelmű a javulás, lám egyetlen integerrel mi mindent lehet tenni... :) (A becslés szerint a javulás mértéke a tábla méretével arányos)

Quote:

Originally Posted by Kutyuleee (Post 294263)

Mivel a megoldás maga egyszerűbb, mint a magyarázkodás :P ezért itt postolom az algoritmust C# kódját:

Code:

public static class Searcher

{

        public static int[,] Table;

        static int Width, Height;<-- Tábla méretei

        public static void SetTable(int W, int H)

        {Adott méretű tábla generálása}

        public static void Fill(double p)

        {Feltöltés random szám segítségével, Rand<p?1:0 alapján}

        public static void Search(ref int X, ref int Y, ref int W, ref int H)

        {A kereső függvényünk}

}

Eddig a bevezetés, hogy hogy is néz ki a tábla, tehát int tömb, 1 és 0, ebben fogunk keresgélni.
A következő függvény adja a megoldást, az eredmények
X,Y,W,H változókba kerülnek (híváskor W értéke -1, a többi lényegtelen), amit a hívás helyén tudunk felhasználni:

Code:

public static void Search(ref int X, ref int Y, ref int W, ref int H)

{

        int[,] Dists = new int[Width, Height];

        int[] Stack1 = new int[Width];

        int Stack1P = 0;

        for (int i = Width - 1; i > -1; i--)

        {

                for (int j = Height - 1; j > -1; j--)

                        if (Table[i, j] == 1)

                                Dists[i, j] = (i == Width - 1 || Table[i + 1, j] == 0) ? 1 : Dists[i + 1, j] + 1;

                        else

                                Dists[i, j] = 0;

                Stack1[i] = 0;

        }

        for (int i = 0; i < Width; i++)

                if (W == -1 || (Width - i) * Height > W * H)

                {

                        int C1 = 0;

                        int CF = 0;

                        while (C1 <= Height)

                        {

                                int N = C1 == Height ? 0 : Dists[i, C1];

                                if (N == 0)

                                        CF = C1 + 1;

                                while (N != Stack1P)

                                {

                                        if (N > Stack1P)

                                        {

                                                Stack1[Stack1P] = C1;

                                                Stack1P++;

                                        }

                                        else if (N < Stack1P)

                                        {

                                                Stack1P--;

                                                int newh = C1 - Stack1[Stack1P];

                                                int neww = Stack1P + 1;

                                                if (neww * newh > W * H)

                                                {

                                                        W = neww;

                                                        H = newh;

                                                        X = i;

                                                        Y = Stack1[Stack1P];

                                                }

                                                Stack1[Stack1P] = -1;

                                                if (Stack1[Stack1P] == CF)

                                                        Stack1P = N;

                                        }

                                }

                                C1++;

                        }

                }

}

Nem túl hosszú kód, de annál bonyolultabb értelmezni, kíváncsi vagyok ki jön rá mit is csinál pontosan :) Lehet ötletelgetni!
Segítség: az első for ciklus (for (int i = Width - 1; i > -1; i--)) törzsének végéig az oldalon leírtak szerint működik.

Más szerverről kell beilleszteni a képet. Valami olyanról, ami képként kezeli, és nem html oldalként, ami fölé muszáj fejlécet is tenni. Ott a Gugli fotóalbuma például, az korlátlan, ingyenes, gyors.