Programozás

[Kutyuleee]

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?

[Cpt Balu]

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)

[Kutyuleee]

Originally Posted by Cpt Balu

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)

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.

[Cpt Balu]

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

[Dus]

Originally Posted by Cpt Balu

(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.

[Cpt Balu]

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

[Cpt Balu]

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)

[Cpt Balu]

Originally Posted by Kutyuleee

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?

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

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:

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.

[csabi]

[Ati]

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.