PDA

Prikaži potpunu verziju : Algoritamski zadacici


Teva
21.12.2012, 19:21
Naleteo sam na ovo

http://challenge.greplin.com/

I pade mi na pamet da otvorim temu ovde, koja bi se bavila prvenstveno tako nekim sličnim problemčićima i njihovim rešenjima :)

Lucic Nemanja
21.12.2012, 21:09
Prva stvar koja mi pada na pamet:
1) Pronadji dva identicna uzastopna karaktera
2) Zapamti poziciju u datoteci
3) Kreni sa dva pokazivaca (jednim napred, jednim nazad) i uporedjuj karaktere. Kad naidjes na razlicite uporedi sa duzinom prehodnog stringa i ako je veca zapamti novi string
4) Nastavi proveru od zapamcene pozicije

Nije bas najoptimalnije, ali mislim da je efikasno :D. Mrsko mi sad da kucam kod, mada mislim da svi mogu da pretpostave kako ce izgledati. A i kako je poenta u algoritmu zadrzacu se na ovome. Ako se nateram mozda i iskucam.
Ostali? :)

Ivan452
21.12.2012, 21:38
@Nemanja
Mislim da ti je u prvom koraku greska.
Jer u slucaju teksta:

"xzyanavolimilovanaxyz" ili u njihovom primeru " "I like racecars that go fast"

nemas dva ista uzastopna karaktera, a postoji trazeni substring.

Zanimljiv sajt, btw.
Mada tezina realizacije algoritama zavisi od programskog jezika.
U Javi se prvi problem resi za 2.5 minuta. Dok verujem u C-u bi trebalo malo vise vremena bez koriscenja dodatnih biblioteka.

Teva
21.12.2012, 22:09
Pa nije ti bitan jezik ako lepo zamisliš xD :) Ja sam radio u "nazovi" C++u xD
što mu dođe malo bezbolniji C, dok sam smislio trebalo mi nekih 15ak minuta, a otkuca se za 3 xD

Evo kako sam ja rešio.


#include<iostream>
#include<string.h>

using namespace std;

int main(){
string text = "Fourscoreandsevenyearsagoourfaathersbroughtforthon thiscontainentanewnationconceivedinzLibertyanddedi catedtothepropositionthatallmenarecreatedequalNoww eareengagedinagreahtcivilwartestingwhetherthatnapt ionoranynartionsoconceivedandsodedicatedcanlongend ureWeareqmetonagreatbattlefiemldoftzhatwarWehaveco metodedicpateaportionofthatfieldasafinalrestingpla ceforthosewhoheregavetheirlivesthatthatnationmight liveItisaltogetherfangandproperthatweshoulddothisB utinalargersensewecannotdedicatewecannotconsecrate wecannothallowthisgroundThebravelmenlivinganddeadw hostruggledherehaveconsecrateditfaraboveourpoorpon wertoaddordetractTgheworldadswfilllittlenotlenorlo ngrememberwhatwesayherebutitcanneverforgetwhatthey didhereItisforusthelivingrathertobededicatedhereto theulnfinishedworkwhichtheywhofoughtherehavethusfa rsonoblyadvancedItisratherforustobeherededicatedto thegreattdafskremainingbeforeusthatfromthesehonore ddeadwetakeincreaseddevotiontothatcauseforwhichthe ygavethelastpfullmeasureofdevotionthatweherehighly resolvet
hatthesedeadshallnothavediedinvainthatthisnationun sderGodshallhaveanewbirthoffreedomandthatgovernmen tofthepeoplebythepeopleforthepeopleshallnotperishf romtheearth";
string solution;
string candidate;
int start, end, length = text.length();
for(int i = 0;i < (2*length -1);i++){
start = i/2 - i%2;
end = i/2+1;
while(start > 0 && end < length && text[start] == text[end]){
start--;
end++;
}
candidate = text.substr(start+1,(end-start-1));
if(candidate.length() > solution.length())
solution = candidate;
}
cout << "Password for completing lvl1 is: " << solution << endl;
return 0;
}




Bilo bi ful kad bi se postavljalo još ovakvih zadačića sa sve diskusijom kako bi se rešilo.

Sun Tzu
22.12.2012, 0:19
Dok verujem u C-u bi trebalo malo vise vremena bez koriscenja dodatnih biblioteka.
Da nema onog jednog strlen, moglo bi i bez string.h.

#include<stdio.h>
#include<string.h>

int main()
{
const char *rec = "Fourscoreandsevenyearsagoourfaathersbroughtforthon thiscontainentanewnationconceivedinzLibertyanddedi catedtothepropositionthatallmenarecreatedequalNoww eareengagedinagreahtcivilwartestingwhetherthatnapt ionoranynartionsoconceivedandsodedicatedcanlongend ureWeareqmetonagreatbattlefiemldoftzhatwarWehaveco metodedicpateaportionofthatfieldasafinalrestingpla ceforthosewhoheregavetheirlivesthatthatnationmight liveItisaltogetherfangandproperthatweshoulddothisB utinalargersensewecannotdedicatewecannotconsecrate wecannothallowthisgroundThebravelmenlivinganddeadw hostruggledherehaveconsecrateditfaraboveourpoorpon wertoaddordetractTgheworldadswfilllittlenotlenorlo ngrememberwhatwesayherebutitcanneverforgetwhatthey didhereItisforusthelivingrathertobededicatedhereto theulnfinishedworkwhichtheywhofoughtherehavethusfa rsonoblyadvancedItisratherforustobeherededicatedto thegreattdafskremainingbeforeusthatfromthesehonore ddeadwetakeincreaseddevotiontothatcauseforwhichthe ygavethelastpfullmeasureofdevotionthatweherehighly resolvethatthesedeadshallnothavediedinvainthatthis nationunsderGodshallhaveanewbirthoffreedomandthatg overnmentofthepeoplebythepeopleforthepeopleshallno tperishfromtheearth";
char trenutni, za_poredjenje, pocetak, kraj;
int max = 1, offset, duzina = 0, mog_poz_pocetka, j, nadjeno = 0;
int poz_poc, poz_kraj, zadnje;

zadnje = strlen(rec) - 1;
poz_poc = 0;
poz_kraj = zadnje;
trenutni = rec[0];

while(trenutni != '\0') {
while(poz_poc != poz_kraj) {
za_poredjenje = rec[poz_kraj];
if( trenutni == za_poredjenje ) {
pocetak = trenutni;
kraj = za_poredjenje;
offset = 0;
while( (pocetak == kraj) && !nadjeno ) {
if( (poz_poc + offset) >= (poz_kraj - offset) ) {
duzina = poz_kraj - poz_poc;
if(duzina >= max) {
max = duzina;
mog_poz_pocetka = poz_poc;
}
nadjeno = 1;
}
else {
offset++;
pocetak = rec[poz_poc + offset];
kraj = rec[poz_kraj - offset];
}
}
}
nadjeno = 0;
poz_kraj--;
}
poz_kraj = zadnje;
poz_poc++;
trenutni = rec[poz_poc];
}

for (j = 0; j<= max; j++)
{
printf("%c", rec[mog_poz_pocetka + j]);
}
return 0;
}
Za svako slovo, krenuvši od početka, krene sa kraja reči i traži isto to. Ako ga nađe, gleda da li je između palindrom ručno, slovo po slovo. Na kraju samo ispiše tih max karaktera sa dobitne pozicije. :D

Ivan452
22.12.2012, 1:57
To je ono o cemu sam pricao.
U C-u zahteva malo malo vise egzibicija i razumevanja samog problema (barem za prvi zadatak).
Dok u Javi iskoristis substring funkciju klase String i uradis zadatak u 5 linija koda uradis zadatak.

Teva
22.12.2012, 10:28
Probaj sa klot javom da radiš zadatak xD (bez string klase xD )

EDIT: Opet sam malo guglao i pade mi napamet sledeće. Kako bi naterali naš kod za palindrom da se ispiše sam? :D

Ivan452
22.12.2012, 14:50
Kako mislis "da se ispise sam"?

Teva
22.12.2012, 22:55
Pa da ispiše svoj source kod :D

http://en.wikipedia.org/wiki/Quine_(computing)