Gå til innhold

antall veier i et rørnett


Anbefalte innlegg

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

 

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 :p kanskje best å kopiere den til et annet sted så linjene ikke blir delt..

Endret av ekorniminator
Lenke til kommentar
Videoannonse
Annonse

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

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

 

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 av ekorniminator
Lenke til kommentar

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
åh :p det han mente.. nei, jeg har fjernet alt slikt! sikler virkelig etter tidene til Giddion. 5 min er alt for tregt! :thumbdown:

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

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 av ekorniminator
Lenke til kommentar
  • 5 uker senere...

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 av aC
Lenke til kommentar
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 :p

 

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

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 konto

Logg inn

Har du allerede en konto? Logg inn her.

Logg inn nå
  • Hvem er aktive   0 medlemmer

    • Ingen innloggede medlemmer aktive
×
×
  • Opprett ny...