Van egy szabadon választható programozási "feladványunk", a legjobb pályázók 200.000 Ft-ot vihetnek haza! Ha felsőoktatási intézményben tanulsz, szeretsz programozni, innovatív vagy és maximalista, akkor ez a pályázat neked lett kitalálva.
Idén első alkalommal került meghirdetésre az Invitel InnoApps pályázata, melyben azokat a fiatalokat keressük, akik saját applikációt/alkalmazást fejlesztettek bármilyen témában. Például nevezhetsz Android, iPhone alkalmazásokkal, játékokkal; PC, Apple Macintosh szoftver, applikáció, vagy webes fejlesztéssel, Facebook alkalmazásokkal.
Gyere és pályázz, hogy megnyerd a fődíjat, kategóriánként 200.000 forintot és 1 éves Net&Go előfizetést.
Indulhatsz minden olyan innovatív fejlesztéssel, amely akár üzlethez, munkához, tanuláshoz, akár a szórakozáshoz köthető. A lényeg: kizárólag megvalósított, működő alkalmazásokkal, szoftverekkel, webes fejlesztésekkel jelentkezhetsz, tervekkel nem!
Két kategóriában pályázhatsz:
I. Szórakozz! - minden olyan alkalmazás, amely a szórakoztatással, szórakozással függhet össze, megvalósítás formájától, annak hasznosságától függetlenül.
II. Ne szórakozz! - minden olyan alkalmazás, ami tanulással, munkával, tájékozódással, információs összeköttetéssel, bármilyen hasznosnak ítélt dologgal kapcsolatos, megvalósítási formájától függetlenül.
Sziasztok!
segitségre lenne szükségem seretném ha segitene valaki hogy hol találok samsung s 100 hoz java játékokat a Wapon , weben . aki ebben tud segiteni kérem írjon nekem egy mailt a ZSUSZIKA@FREEMAIL.hu ra
Ahh sejtettem, hogy Dijsktra-val is meg lehet oldani. Mindegy, a szándék az volt, hogy mátrixhatványozással kelljen számolni. Van valakinek erre egy jó feladata?
Encsé
Ja, az én megoldásom theta(n^3) műveletigényű, ahol n a gráf csúcsainak száma. Jó, mondjuk ez elég becsapós, mert ha pontosabb akarnék lenni, akkor theta((l+1)*n^3)-öt kéne mondani, ahol l a leghosszabb út hossza, és még lenne másodfokú tényező is, de persze mindez belefér a theta(n^3)-be is. :)
Encsé
Itt van még egy. Ez saját feladat, nem tudom milyen gyors a legjobb megoldás. Szóval: határozzuk meg egy gráfban az egymástól páratlan távolságra levő csúcsokat. Praktikusan az eredmény is legyen egy gráf. Két pont egymástól páratlan távolságra van, ha az őket összekötő legrövidebb út hossza páratlan. (pl. a szomszédos pontok, meg azok akik között 2 csúcs van, stb.)
Jó munkát!
Encsé
Valoban ugyanaz, de igy tenyleg sokkal szebb. Igazabol, amikor ResetGomb kerdesere valaszoltam mar nekem is leesett a tantusz, hogy szimetrikus 'ind1' es 'ind2' viselkedese, es egy ciklus is eleg.
A 'kisebb' es a 'nagyobb' valtozok kulonbsege a belso ciklusmag egy lefutasa utan mindenkeppen csokken eggyel (vagy a kisebb no, vagy a nagyobb csokken azaltal, hogy a kulso ciklus lep.). Igy maximum n lepes alatt osszeernek.
// Igazat ad vissza, ha talalt.
BOOL keres(int* v, int n, int szumma, int& ind1, int& ind2)
{
int kisebb = 0;
int nagyobb = n-1;
while(kisebb < nagyobb)
{
int s = -1;
while((s < szumma)&&(kisebb{
s = v[kisebb] + v[nagyobb];
kisebb++;
}
kisebb--;
if(s == szumma)
{
ind1 = kisebb;
ind2 = nagyobb;
return true;
}
nagyobb--;
}
return false;
}
// Igazat ad vissza, ha talalt.
BOOL keres(int* v, int n, int szumma, int ind1&, int& ind2)
{
int kisebb = 0;
int nagyobb = n-1;
while(kisebb < nagyobb)
{
int s = -1;
while(s < szumma)
{
s = v[kisebb] + v[nagyobb];
kisebb++;
}
kisebb--;
if(s == szumma)
{
ind1 = kisebb;
ind2 = nagyobb;
return true;
}
nagyobb--;
}
return false;
}
Magyarazat: a trivialis megoldas az osszes parositas megnezese lenne. Ezt tesszuk, a nagyobbik indexet elinditjuk fentrol, de a kisebbre mar nem nezunk meg olyan ertekeket, amelyek mar egy nagyob 'nagyobb'-al osszedadva is kiseb osszeget adtak mint 'szumma'...
Nem probaltam ki, remelem nem rontottam el.
Sziasztok!
Kihalt ez a fórum. Kár érte. Van egy kis fejtörőm. Nem nehéz, de nekem tetszik. Állítólag valahol valaki egy állásinterjún találkozott vele.
Tehát: egy v vektor 1-től n-ig indexelve természetes számokat tartalmaz monoton növekvő sorrendben. Előre adott egy k természetes szám. Keresendő olyan i és j index, hogy v[i]+v[j]=k. Mindezt theta(n) időben, azaz n-nel arányosan.
Jó munkát!
Encsé
Szerintem elsőrendű rezolúciós kalkulussal megoldható, csak azt nagyon nehéz programozni (viszont ha egyszer sikerül, akkor már egész jól fogsz tudni automatikusan tételeket bizonyítani).
Vannak mindenféle erre kihegyezett programnyelvek (talán pl. Prolog, bár annyira még nem másztam bele a dolgokba és azt hiszem, hogy az inkább szabályalapú következtetésre való.)
Ez persze nem sok minden, de ha tényleg érdekel a dolog, akkor keress rá a rezolúcióra, elég nagy irodalma van, biztos találsz hozzá neten dolgokat.
Hellosztok.
Feladat: http://www.lba.hu/kulonos/einstein.php ; aminek megoldasa neten megtalalhato. De nem a feladat a lenyeg, meg amugy is regi..., hanem az, hogy programozas szemszogebol hogyan lehetne megoldani a feladatot??? En hiaba tortem a fejem rajta, nemigen jottem ra, bar nem vagyok hivatasos programozo+matematikus:). Tehat ha tudtok, segitsetek letszives! Koszonom elore is.
Igen, valami ilyesmit lehet írni, bár talán nem pont ezt. Ismétlődő betűnél nem az előző helyen levő D érték kell, hanem az attól eggyel jobbra eső helyen levő - talán. De mindenképpen jó az elv. És abban egyet értünk asszem, hogy elsőre bonyolultabbnak tűnik a dolog.
Encsé
Tényleg szép, mondtam, hogy van rá képlet :-)
De nem egyszerűbb a következő forma?
D(v,-1)=-1, D(v,0)=0, D(v,i+1)=2*D(v,i)-D(v,prev(v,i)),
ahol prev(v,i) az i. betű előző előfordulásának indexe v-ben vagy -1, ha nincs ilyen, azaz prev(i)=max(max(j, j<i és v(i)=v(j)), -1)
És akkor az embert ne üsse meg a guta, hogy hülyeségeket írt a TDK dolgozatában. Legalább a formalizmus meg a bizonyítás jónak tűnik: ott még a kezdeti last[]={0,0,0,0} helyett végtelennel volt inicializálva a dolog (és így akkor az ifben is végtelennel volt vizsgálva), csak a kódban "egyszerűsítettem" a hülye eszemmel.
Köszönöm az észrevételt, pasa_!
Encsé
Elso nekifutasra azt mondanam, hogy az 'aa' szora az algoritmus 3-at ad, mig a helyes eredmeny 2.
Az if-ben inkabb azt kene nezni, hogy szerepelt-e mar a betu a string hatul levo reszeben, akkor mintha jo eredmeny jonne ki.
A last[] erre azert nem jo, mert 0 ertek irodik bele egyes esetekben.
exist[] = {0,0,0,0}
A ciuklusban meg
if exist[ord(v[i])] = 0 then
result <- 2 * result + 1 , exist[ord(v[i])] = 1
else
result <- 2 * result - last[ ord(v[i]) ]
illetve, ahogy latom csak az utolso betunel van gebaszt a last[]-ban, igy az eredeti algo ugy is javithato, ha az if-et kiegeszitjuk azzal, hogy
AND (i = n-1 OR v[i] <> v[n-1] )
És akkor most már talán jó is lesz. (Remélem.)
Tegyük fel, hogy a szó n hosszúságú és 4 különböző betű van benne. (Ez nyilván nem jelent lényegi megszorítást, viszont így egyszerű az algoritmus.)
Legyen ord fv. bijektív megfeleltetés a szó betűi és a {0,1,2,3} halmaz között.
Legyen a szó a v tömbben tárolva.
last[] <- {0,0,0,0}
result <- 0
for i = n-1 downto 0 do
begin
s <- result
if last[ ord(v[i]) ] = 0 then
result <- 2 * result + 1
else
result <- 2 * result - last[ ord(v[i]) ]
last[ ord(v[i]) ] <- s
end;
Magyarázat (????) Megpróbálom elmagyarázni (nem lesz könnyű). Legyen először a szó abcd. Futtassuk le erre az algoritmust! Ugye a szó végéről kezdjük, és előre haladunk. A result értékek sorban: 0, 1, 3, 7, 15. Leírom úgy is, hogy az éppen vizsgált betű alá írom a resultot:
| a | b | c | d | a ciklus előtt|
--------+---+---+---+---+---------------+
result: | 15| 7 | 3 | 1 | 0 |
. Ebből látható, hogy result mindig a már vizsgált postfix D-komplexitását tartalmazza a ciklusmag végén. (Azt már megbeszéltük, hogy ebben az esetben ez 2^postfixhossz - 1.) Persze ezen nem nagyon csodálkozunk, mert mi történik? Mondjuk, hogy ott tartunk, hogy a c-t már vizsgáltuk, most jön a b, és a result 3, mert az utolsó két betűből háromféle részsorozatot lehet alkotni, azaz:
| a | b | c | d | a ciklus előtt|
--------+---+---+---+---+---------------+
result: | | | 3 | 1 | 0 |
. Ha hozzávesszük a b-t a vizsgálódáshoz, akkor most hány részsorozatunk lesz? Megmarad az eddigi 3. Ezek elé betehetünk egy-egy 'b'-t, így újabb 3 részsorozatot kapunk és végül van egy olyan részsorozat, hogy 'b'. Tehát az új result érték: 2*result+1=7.
| a | b | c | d | a ciklus előtt|
--------+---+---+---+---+---------------+
result: | | 7 | 3 | 1 | 0 |
. A probléma akkor kezdődik, ha vannak egyforma betűk a sorozatban. Mondjuk dbabc esete
| d | b | a | b | c |a ciklus előtt|
--------+---+---+---+---+---+--------------+
result: | | | 7 | 3 | 1 | 0 |
. eddig minden rendben, de most egy olyan betű jön (b), amivel már találkoztunk. Hány részsorozatunk lesz az utolsó 4 betűből? Megmarad az eddigi 7, hozzáteszünk mindegyikhez előlről egy-egy b-t, ez újabb 7. Számoltunk-e valamit kétszer? Igen: a 'bc'-t, mert az eddigi 7 részsorozatban a 'c' és 'bc' is szerepel, így 'c'-t előlről kiegészítve b-vel 'bc'-t már kétszer számoljuk. Ebből adódik (és ez az, amit nehéz látni), hogy le kell vonnunk a b utolsó előfordulásától jobbra levő result részeredményt (azaz 1-t jelen esetben), ugyanis pontosan ennyi részsorozat elé írhatjuk bármelyik b-t, így ennyit számolunk kétszer.
| d | b | a | b | c |a ciklus előtt|
--------+---+---+---+---+---+--------------+
result: | | 13| 7 | 3 | 1 | 0 |
. és a vége:
| d | b | a | b | c |a ciklus előtt|
--------+---+---+---+---+---+--------------+
result: | 27| 13| 7 | 3 | 1 | 0 |
. Hát ennyi. Nehéz megérteni, tudom. Fórumon elmagyarázni még ennél is nehezebb. Viszont abban remélem egyet értünk, hogy az algoritmus rövid és piszokgyors. Korántsem exponenciális! Kár, hogy nem gondolkodott rajta igazán senki.
Akkor fussunk neki még1x, na nem mintha sikerülne, csak úgy:
Bocsánat.
Tegyük fel, hogy a szó n hosszúságú és 4 különböző betű van benne. (Ez nyilván nem jelent lényegi megszorítást, viszont így egyszerű az algoritmus.)
Legyen ord fv. bijektív megfeleltetés a szó betűi és a {0,1,2,3} halmaz között.
Legyen a szó a v tömbben tárolva.
last[] <- {0,0,0,0}
result <- 0
for i = n-1 downto 0 do
begin
s <- result
if last[ ord(v[i]) ] = 0 then
result <- 2 * result + 1
else
result <- 2 * result - last[ ord(v[i]) ]
last[ ord(v[i]) ] <- s
end;
Magyarázat (????) Megpróbálom elmagyarázni (nem lesz könnyű). Legyen először a szó abcd. Futtassuk le erre az algoritmust! Ugye a szó végéről kezdjük, és előre haladunk. A result értékek sorban: 0, 1, 3, 7, 15. Leírom úgy is, hogy az éppen vizsgált betű alá írom a resultot:
| a | b | c | d | a ciklus előtt|
--------+---+---+---+---+---------------+
result: | 15| 7 | 3 | 1 | 0 |
Ebből látható, hogy result mindig a már vizsgált postfix D-komplexitását tartalmazza a ciklusmag végén. (Azt már megbeszéltük, hogy ebben az esetben ez 2^postfixhossz - 1.) Persze ezen nem nagyon csodálkozunk, mert mi történik? Mondjuk, hogy ott tartunk, hogy a c-t már vizsgáltuk, most jön a b, és a result 3, mert az utolsó két betűből háromféle részsorozatot lehet alkotni, azaz:
| a | b | c | d | a ciklus előtt|
--------+---+---+---+---+---------------+
result: | | | 3 | 1 | 0 |
Ha hozzávesszük a b-t a vizsgálódáshoz, akkor most hány részsorozatunk lesz? Megmarad az eddigi 3. Ezek elé betehetünk egy-egy 'b'-t, így újabb 3 részsorozatot kapunk és végül van egy olyan részsorozat, hogy 'b'. Tehát az új result érték: 2*result+1=7.
| a | b | c | d | a ciklus előtt|
--------+---+---+---+---+---------------+
result: | | 7 | 3 | 1 | 0 |
A probléma akkor kezdődik, ha vannak egyforma betűk a sorozatban. Mondjuk dbabc esete
| d | b | a | b | c |a ciklus előtt|
--------+---+---+---+---+---+--------------+
result: | | | 7 | 3 | 1 | 0 |
eddig minden rendben, de most egy olyan betű jön (b), amivel már találkoztunk. Hány részsorozatunk lesz az utolsó 4 betűből? Megmarad az eddigi 7, hozzáteszünk mindegyikhez előlről egy-egy b-t, ez újabb 7. Számoltunk-e valamit kétszer? Igen: a 'bc'-t, mert az eddigi 7 részsorozatban a 'c' és 'bc' is szerepel, így 'c'-t előlről kiegészítve b-vel 'bc'-t már kétszer számoljuk. Ebből adódik (és ez az, amit nehéz látni), hogy le kell vonnunk a b utolsó előfordulásától jobbra levő result részeredményt (azaz 1-t jelen esetben), ugyanis pontosan ennyi részsorozat elé írhatjuk bármelyik b-t, így ennyit számolunk kétszer.
| d | b | a | b | c |a ciklus előtt|
--------+---+---+---+---+---+--------------+
result: | | 13| 7 | 3 | 1 | 0 |
és a vége:
| d | b | a | b | c |a ciklus előtt|
--------+---+---+---+---+---+--------------+
result: | 27| 13| 7 | 3 | 1 | 0 |
Hát ennyi. Nehéz megérteni, tudom. Fórumon elmagyarázni még ennél is nehezebb. Viszont abban remélem egyet értünk, hogy az algoritmus rövid és piszokgyors. Korántsem exponenciális! Kár, hogy nem gondolkodott rajta igazán senki.
Bocsánat.
Tegyük fel, hogy a szó n hosszúságú és 4 különböző betű van benne. (Ez nyilván nem jelent lényegi megszorítást, viszont így egyszerű az algoritmus.)
Legyen ord fv. bijektív megfeleltetés a szó betűi és a {0,1,2,3} halmaz között.
Legyen a szó a v tömbben tárolva.
last[] <- {0,0,0,0}
result <- 0
for i = n-1 downto 0 do
begin
s <- result
if last[ ord(v[i]) ] = 0 then
result <- 2 * result + 1
else
result <- 2 * result - last[ ord(v[i]) ]
last[ ord(v[i]) ] <- s
end;
Magyarázat (????) Megpróbálom elmagyarázni (nem lesz könnyű). Legyen először a szó abcd. Futtassuk le erre az algoritmust! Ugye a szó végéről kezdjük, és előre haladunk. A result értékek sorban: 0, 1, 3, 7, 15. Leírom úgy is, hogy az éppen vizsgált betű alá írom a resultot:
| a | b | c | d | a ciklus előtt|
--------+---+---+---+---+---------------+
result: | 15| 7 | 3 | 1 | 0 |
Ebből látható, hogy result mindig a már vizsgált postfix D-komplexitását tartalmazza a ciklusmag végén. (Azt már megbeszéltük, hogy ebben az esetben ez 2^postfixhossz - 1.) Persze ezen nem nagyon csodálkozunk, mert mi történik? Mondjuk, hogy ott tartunk, hogy a c-t már vizsgáltuk, most jön a b, és a result 3, mert az utolsó két betűből háromféle részsorozatot lehet alkotni, azaz:
| a | b | c | d | a ciklus előtt|
--------+---+---+---+---+---------------+
result: | | | 3 | 1 | 0 |
Ha hozzávesszük a b-t a vizsgálódáshoz, akkor most hány részsorozatunk lesz? Megmarad az eddigi 3. Ezek elé betehetünk egy-egy 'b'-t, így újabb 3 részsorozatot kapunk és végül van egy olyan részsorozat, hogy 'b'. Tehát az új result érték: 2*result+1=7.
| a | b | c | d | a ciklus előtt|
--------+---+---+---+---+---------------+
result: | | 7 | 3 | 1 | 0 |
A probléma akkor kezdődik, ha vannak egyforma betűk a sorozatban. Mondjuk dbabc esete
| d | b | a | b | c |a ciklus előtt|
--------+---+---+---+---+---+--------------+
result: | | | 7 | 3 | 1 | 0 |
eddig minden rendben, de most egy olyan betű jön (b), amivel már találkoztunk. Hány részsorozatunk lesz az utolsó 4 betűből? Megmarad az eddigi 7, hozzáteszünk mindegyikhez előlről egy-egy b-t, ez újabb 7. Számoltunk-e valamit kétszer? Igen: a 'bc'-t, mert az eddigi 7 részsorozatban a 'c' és 'bc' is szerepel, így 'c'-t előlről kiegészítve b-vel 'bc'-t már kétszer számoljuk. Ebből adódik (és ez az, amit nehéz látni), hogy le kell vonnunk a b utolsó előfordulásától jobbra levő result részeredményt (azaz 1-t jelen esetben), ugyanis pontosan ennyi részsorozat elé írhatjuk bármelyik b-t, így ennyit számolunk kétszer.
| d | b | a | b | c |a ciklus előtt|
--------+---+---+---+---+---+--------------+
result: | | 13| 7 | 3 | 1 | 0 |
és a vége:
| d | b | a | b | c |a ciklus előtt|
--------+---+---+---+---+---+--------------+
result: | 27| 13| 7 | 3 | 1 | 0 |
Hát ennyi. Nehéz megérteni, tudom. Fórumon elmagyarázni még ennél is nehezebb. Viszont abban remélem egyet értünk, hogy az algoritmus rövid és piszokgyors. Korántsem exponenciális! Kár, hogy nem gondolkodott rajta igazán senki.
