ekorniminator Skrevet 8. mars 2007 Rapporter Del Skrevet 8. mars 2007 (endret) prøver å skrive et program som finner antall mulige veier i et rutete rørnett. men det er noe i koden som er feil. programmet avslutter aldri en av løkkene tror jeg. er ganske så ny med programmering, men ville prøve meg på å skrive et program som benytter brute-force til å løse et problem veien skal være så kort som mulig, og sluttpunktet vil alltid ligge til høyre og under startpunket. #include<iostream> #include<vector> #include<ios> #include<windows.h> using std::cout; using std::cin; using std::endl; using std::vector; int main() { int x,y; cin>>x>>y; //distanse vector<int> locked((x+1)*(y+1), 0);//vektor som inneholder informasjon om hvilke kryss som er "låst" int solutions = 0; //antall løsninger int exit = 0; while(exit==0){ int a = 0; //din x-posisjon int b = 0; //din y-posisjon int inc_x=0; //retning på din forrige bevegelse int last_turn; //siste sving du gjorde i y-retning while(a!=x && b!=y){ /*tester om neste kryss er "låst" eller om du er kommet til veis ende i x-retning. i så tilfelle går du i y-retning*/ if(locked[b*(x+1)+a+1]==1 || a==x){ if(inc_x==1) last_turn = b*(x+1)+a; inc_x=0; ++b; } //ellers beveger du deg i x else { ++a; inc_x = 1; } //låser opp igjen hjørner som ikke skal være låst lenger if(a!=x && b==y) for(vector<int>::size_type i = last_turn; i!=locked.size(); ++i) locked[i] = 0; //om dette er den siste muligheter if(a==0 && b==y) exit = 1; } //låser krysset du sist gjorde en y-sving i locked[last_turn] = 1; ++solutions; } cout<<solutions; Sleep(5000); return 0; } holder med hint om hva som er feil.. om ikke alt er helt på trynet da godt mulig jeg bruker en dårlig algoritme, så kom gjerne med forslag til bedre fremgangsmåter også edit*koden ser jo helt hy ut her kanskje best å kopiere den til et annet sted så linjene ikke blir delt.. Endret 8. mars 2007 av ekorniminator Lenke til kommentar
Zolo Skrevet 8. mars 2007 Rapporter Del Skrevet 8. mars 2007 Dersom du vil feilsøke på koden for å finne ut om den går inn i evig loop og liknende. Berre skriv ut noe til skjerm inne i løkkene f.eks tellevariabler. Så vil du fort finne ut hva som kan være feil. Lenke til kommentar
Zolo Skrevet 8. mars 2007 Rapporter Del Skrevet 8. mars 2007 En annen måte du kan få programmet til å gi fornuftige feilmeldinger med er "exceptions". det er ganske enkelt å lage. try{ // your code here if (something_that_should_never_happen happens) throw "whatever_you_call_this_exeption_string" } catch(const char* msg){ // catch your exception // recognise your exception string if you have more than one eception in your try block std::cout << "your readable error message"; // and error handling } Dette kan spare deg for mye i større program Lenke til kommentar
ekorniminator Skrevet 8. mars 2007 Forfatter Rapporter Del Skrevet 8. mars 2007 (endret) utrolig greit å bare skrive alle vesentlige variabler for hver loop tok meg 5 min å finne ut av det.. etter mange timer før i dag while(a!=x && b!=y) skulle selvfølgelig vært while(a!=x || b!=y).. men dette tok ganske lang tid. noen hete tips for å forkorte kjøretiden? bruker 2 sek ved 10 10.. og 5 min med 10 20. Endret 9. mars 2007 av ekorniminator Lenke til kommentar
Giddion Skrevet 9. mars 2007 Rapporter Del Skrevet 9. mars 2007 Du kan jo bytte ut dette //låser opp igjen hjørner som ikke skal være låst lenger if(a!=x && b==y) { for(vector<int>::size_type i = last_turn; i!=locked.size(); ++i) locked[i] = 0; } med dette //låser opp igjen hjørner som ikke skal være låst lenger if(a!=x && b==y) { vector<int>::size_type SizeofLocked = locked.size(); for(vector<int>::size_type i = last_turn; i!=SizeofVector; ++i) locked[i] = 0; } Det som kort sagt er gjort er at den lagrer locked.size() slik det ikke trenger å kjøre locked.size() vær eneste gang. Men jeg kan ikke skjønne at den koden din går så treigt med 10, 10 = 203ms med 10, 20 = 15609ms = 15,6 s Programmet er kjørt på en 1,6 ghz Intel M Du kjører vel ikke debug versionen? Debug: med 10, 10 = 3812 = 3,812s med 10, 20 = lang tid (>1 min) her er koden jeg kjører med en timer via GetTickCount #include<iostream> #include<vector> #include<ios> #include<windows.h> using std::cout; using std::cin; using std::endl; using std::vector; int main() { int x,y; cin>>x>>y; //distanse DWORD StartTime = GetTickCount(); vector<int> locked((x+1)*(y+1), 0);//vektor som inneholder informasjon om hvilke kryss som er "låst" int solutions = 0; //antall løsninger int exit = 0; while(exit==0) { int a = 0; //din x-posisjon int b = 0; //din y-posisjon int inc_x=0; //retning på din forrige bevegelse int last_turn = 0; //siste sving du gjorde i y-retning while(a!=x || b!=y) { /*tester om neste kryss er "låst" eller om du er kommet til veis ende i x-retning. i så tilfelle går du i y-retning*/ if(locked[b*(x+1)+a+1]==1 || a==x) { if(inc_x==1) last_turn = b*(x+1)+a; inc_x=0; ++b; } //ellers beveger du deg i x else { ++a; inc_x = 1; } //låser opp igjen hjørner som ikke skal være låst lenger if(a!=x && b==y) { vector<int>::size_type SizeofVector = locked.size(); for(vector<int>::size_type i = last_turn; i!=SizeofVector; ++i) locked[i] = 0; } //om dette er den siste muligheter if(a==0 && b==y) exit = 1; } //låser krysset du sist gjorde en y-sving i locked[last_turn] = 1; ++solutions; } cout<<solutions; DWORD EndTime = GetTickCount(); DWORD DeltaTime = EndTime - StartTime; cout<<"\nDelta time in ms\n"; cout<<DeltaTime; Sleep(5000); return 0; } Lenke til kommentar
ekorniminator Skrevet 9. mars 2007 Forfatter Rapporter Del Skrevet 9. mars 2007 festlig med klokke som tar tiden 10, 10 gir meg 1265ms.. kjører i Dec-c++, bruker "ctrl F10", run. kjører vel ikke en debug versjon da? kjører selv på intel pentium M 1,73 gHz Lenke til kommentar
Zolo Skrevet 9. mars 2007 Rapporter Del Skrevet 9. mars 2007 kjører vel ikke en debug versjon da? 8113240[/snapback] Når du skriv ut mye til skjerm så blir kjøretiden av programmet lengre.. Lenke til kommentar
ekorniminator Skrevet 9. mars 2007 Forfatter Rapporter Del Skrevet 9. mars 2007 åh det han mente.. nei, jeg har fjernet alt slikt! sikler virkelig etter tidene til Giddion. 5 min er alt for tregt! Lenke til kommentar
Giddion Skrevet 9. mars 2007 Rapporter Del Skrevet 9. mars 2007 åh det han mente.. nei, jeg har fjernet alt slikt! sikler virkelig etter tidene til Giddion. 5 min er alt for tregt! 8114008[/snapback] En debug version har ingenting om det skrives mye til skjerm eller ikke, men når du kompilerer om du da lager en debug version, jeg kjenner ikke Dec-c++ så jeg kan ikke si om du kjører debug eller ikke, men det virker slik med mindre du har fryktelig masse andre programmer du kjører. Sånn kort så har en debug version masse masse ekstra kode som sinker programmet, men også skjekker det meste av kjøringen for feil. Lenke til kommentar
ekorniminator Skrevet 9. mars 2007 Forfatter Rapporter Del Skrevet 9. mars 2007 (endret) hmm, jeg lukket bevisst alle andre programmer for å prøve å få best mulig tid.. mulig jeg kjører debug edit* ser slik ut, for om jeg velger debug eller vanlig run så kjører programmet til samme tid.. men hvordan slår jeg av dette da? jeg får samme tider om jeg kjører .exe-filen utenfor IDE også. Endret 9. mars 2007 av ekorniminator Lenke til kommentar
aC Skrevet 9. april 2007 Rapporter Del Skrevet 9. april 2007 (endret) Hahaha, stilig lite program, ble litt hekta på å få bra tid. kompilerte i VS 2005 med \0x full optimization og i gcc med samme option. og tiden ble da. (btw IA32 p4 3,3ghz) VS: 10 10 = 47 ms gcc: 10 10 = 47 ms VS: 10 20 = 10906 gcc: 10 20 = 9438 litt morsomt å se de forskjelige kompilerne bruke forskjelig tid, men det er kanskje alment kjent at gcc er raskere en ms kompiler. Jeg brukte Dev-c++ i windows hvor gcc da er en windows port fra mingw. Hadde vært litt morsomt om noen hadde skrevet det rett i asm, og om det ble noen forbedringer.. cpu info Endret 9. april 2007 av aC Lenke til kommentar
Iyon Skrevet 9. april 2007 Rapporter Del Skrevet 9. april 2007 Jeg har ikke satt meg skikkelig inn i problemet, men hadde det ikke passet bra med en dynamisk programmering-approach til dette problemet? Istedenfor ren brute force? Lenke til kommentar
ekorniminator Skrevet 9. april 2007 Forfatter Rapporter Del Skrevet 9. april 2007 Jeg har ikke satt meg skikkelig inn i problemet, men hadde det ikke passet bra med en dynamisk programmering-approach til dette problemet? Istedenfor ren brute force? Absolutt, har løst problemet med dynamisk programmering også. Vesentlig mye raskere! Men som den nooben jeg er har jeg godt av å prøve litt forskjellig Har forresten fått mye bedre kjøretider, problemet var at det ikke var haket av for optimal kompilering. Noe som ga svært store utslag på kjøretid. Lenke til kommentar
Anbefalte innlegg
Opprett en konto eller logg inn for å kommentere
Du må være et medlem for å kunne skrive en kommentar
Opprett konto
Det er enkelt å melde seg inn for å starte en ny konto!
Start en kontoLogg inn
Har du allerede en konto? Logg inn her.
Logg inn nå