antall veier i et rørnett

ekorniminator · 8. mars 2007

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 :blush:

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

Zolo · 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.

Zolo · 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

ekorniminator · 8. mars 2007

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

Giddion · 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;
}

ekorniminator · 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 :hmm:

Zolo · 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..

ekorniminator · 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! :thumbdown:

Giddion · 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.

ekorniminator · 9. mars 2007

hmm, jeg lukket bevisst alle andre programmer for å prøve å få best mulig tid.. mulig jeg kjører debug :hmm:

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

aC · 9. april 2007

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

Iyon · 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?

ekorniminator · 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.

Logg inn

antall veier i et rørnett

Anbefalte innlegg

ekorniminator

Lenke til kommentar

Videoannonse

Zolo

Lenke til kommentar

Zolo

Lenke til kommentar

ekorniminator

Lenke til kommentar

Giddion

Lenke til kommentar

ekorniminator

Lenke til kommentar

Zolo

Lenke til kommentar

ekorniminator

Lenke til kommentar

Giddion

Lenke til kommentar

ekorniminator

Lenke til kommentar

aC

Lenke til kommentar

Iyon

Lenke til kommentar

ekorniminator

Lenke til kommentar

Opprett en konto eller logg inn for å kommentere

Opprett konto

Logg inn

Hvem er aktive 0 medlemmer