PDA

Visualizza la versione completa : [C++] Cambio dell'ordine degli elementi di un vettore


Feanor_00
20-07-2009, 12:51
Salve, premetto che non so se il titolo è corretto ma sono un neofita sia del forum che della programmazione... Quindi abbiate pietà di me :D

Detto ciò mi trovo per un esame a dover scrivere un algoritmo di forza bruta che risolva il TSP (http://it.wikipedia.org/wiki/Problema_del_commesso_viaggiatore) con pochi elementi, meno di 10 probabilmente, quindi parto dalla considerazione (e lo stesso spero farà il professore) che non mi serva un algoritmo particolarmente ottimizzato... Mi basta fondamentalmente che funzioni :mame:

Detto ciò ho iniziato a scrivere il mio programma e l'ho impostato in modo che mi crei due vettori in cui confluiscono i dati che metto in input (un vettore per le x e uno per le y dato che tratto i nodi come punti di un piano cartesiano) e che poi mi calcoli la distanza tra i vari "nodi" percorrendo i vettori dalla posizione 0 alla n (in cui n sta per il numero dei nodi).

Il mio problema dunque consiste nel creare "qualcosa" :mame: che scambi/modifichi gli elementi all'interno dei due vettori per creare tutte le combinazioni necessarie (n! O_O) ad essere calcolate con la funziona di cui parlavo sopra... Cercado un po' in rete ho trovato il comando "swap" che forse potrebbe essermi utile ma non riesco a capirne la sintassi (ne se sia quello che mi serve effettivamente T_T)

Help!!!!
E grazie per l'aiuto :)

Stoicenko
20-07-2009, 15:27
i vettori come sono dichiarati o definiti? un po' di codice sarebbe utile

Feanor_00
20-07-2009, 18:54
Hem ^^' temo di non conoscere la differenza...

Stoicenko
21-07-2009, 09:16
:dhò: :dhò:

Hai scritto almeno qualche linea di codice? questi vettori sono degli array o vector della stl?
In ogni caso sono vettori o array di cosa?

Senza sapere ciò come possiamo rispondere?

oregon
21-07-2009, 09:24
Originariamente inviato da Feanor_00
... ho iniziato a scrivere il mio programma e l'ho impostato in modo che mi crei due vettori ...

Mostra questo codice ...

Feanor_00
21-07-2009, 12:27
Si scusate



#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>

using namespace std;

int a;
vector <int> Vx,Vy;
vector <float> Vsomma;

float distanza(int x1, int x2, int y1, int y2);


main()

{
int x;
int y;
float somma;
float d;

cout << "Inserisci il numero di punti \n";
cin >> a;
cout << "Il numero é " << a << endl;

cout << "inserisci le cordinate (x,y) dei nodi: \n";

somma = 0;



for (int i=0; i<a; i++)
{
cin >> x;
cin >> y;
Vx.push_back(x);
Vy.push_back(y);
}

for (int h=0; h<a-1; h++)

{
cout << Vx[h] << Vx[h+1] << Vy[h] << Vy[h+1] << endl; //controllo delle variabili in entrata
d=distanza(Vx[h],Vx[h+1],Vy[h],Vy[h+1]);
cout<< d << endl;
somma=(d+somma);
cout << "somma del punto " << h+1;
cout << " + " << h+2 << " = ";
cout << somma << endl;

}
}

float distanza(int x1, int x2, int y1, int y2)
{

float dis;

// cout << x1 << x2 << y1 << y2 << endl; //controllo delle variabili in entrata
dis=sqrt(pow((x2-x1),2)+pow((y2-y1),2));
// cout << x1 << x2 << y1 << y2 << endl; //controllo delle variabili in uscita nella funzione
// cout << dis << endl;
// cout << " x2-x1 "<< x2-x1 << endl; //controllo dei binomi in uscita nella funzione
// cout << " y2-y1 "<< y2-y1 << endl; //controllo dei binomi in uscita nella funzione

return dis;
}



Non sono riuscito a metterlo in maniera meno confusionaria... Ieri ho passato la giornata a cercare anache delle alternative... Ma il mio problema rimane che non riesco a spostare gli elementi all'interno dei vector...

Feanor_00
21-07-2009, 14:44
Attualmente ho fatto (forse) un piccolo passo avanti...



#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>

using namespace std;

int a;
vector <int> Vx,Vy;
vector <float> Vsomma;

float distanza(int x1, int x2, int y1, int y2);


main()

{
int x;
int y;
float somma;
float d;

cout << "Inserisci il numero di punti \n";
cin >> a;
cout << "Il numero é " << a << endl;

cout << "inserisci le cordinate (x,y) dei nodi: \n";

somma = 0;



for (int i=0; i<a; i++)
{
cin >> x;
cin >> y;
Vx.push_back(x);
Vy.push_back(y);
}
for (int g=0; g<a; g++)
{
for (int b=0; b<a; b++)
{
for (int h=0; h<a; h++)
{
cout << Vx[h] << endl;; //controllo delle variabili in entrata
/* d=distanza(Vx[h],Vx[h+1],Vy[h],Vy[h+1]);
cout<< d << endl; //output a schermo della distanza tra i vari nodi
somma=(d+somma);
cout << "somma del punto " << h+1; //output che fornisce l'indicazione sul numero della somma che stiamo svolgendo
cout << " + " << h+2 << " = ";
cout << somma << endl; //somme parsiali della distanza al passo h
*/
}
cout << "-----------" << endl;
int o = Vx[b+1];
int p = Vy[b+1];
Vx[b] = Vx[b+2];
Vy[b] = Vy[b+2];
Vx[b+2] = o;
Vy[b+2] = p;
}

int m = Vx[g];
int n = Vy[g];
Vx[g] = Vx[g+1];
Vy[g] = Vy[g+1];
Vx[g+1] = m;
Vy[g+1] = n;

}

}

float distanza(int x1, int x2, int y1, int y2)
{

float dis;

// cout << x1 << x2 << y1 << y2 << endl; //controllo delle variabili in entrata
dis=sqrt(pow((x2-x1),2)+pow((y2-y1),2));
// cout << x1 << x2 << y1 << y2 << endl; //controllo delle variabili in uscita nella funzione
// cout << dis << endl;
// cout << " x2-x1 "<< x2-x1 << endl; //controllo dei binomi in uscita nella funzione
// cout << " y2-y1 "<< y2-y1 << endl; //controllo dei binomi in uscita nella funzione

return dis;
}



Il problema così facendo è che oltre a dover finire di sistemare il ciclo ne serve uno in più per ogni nodo che si aggiunge... :(

Feanor_00
22-07-2009, 11:31
Nessuno saprebbe darmi una mano? :(

Feanor_00
23-07-2009, 15:33
Come non detto ho dovuto abbandonare quella soluzione e anche tutte quelle che seguenti... Il mio rpoblema attualmente rimane quello di calcolare le differenti combinazioni di numeri naturali... Ad esempio dando in input 4 numeri:

a b c d;

mi servirebbe un rpogramma che mi dia in output:

a b c d
a b d c
a c b d
a c d b
a d b c
a d c b

b a c d
b a d c
b c a d
b c d a
b d a c
b d c a

c b a d
c a d c
c a b d
c a d b
c d b a
c d a b

d b c a
d b a c
d c b a
d c a b
d a b c
d a c b


Cioé se i numeri a b c d in input sono 4 mi servono le 4! possibili combinazioni... Nessuno ha idea di come potrei implementare un idea simile? Sarò almeno al 6 o al 7 tentativo ma ogni volta mi scontro con un muro... :(

Stoicenko
23-07-2009, 15:41
prova a seguire il regolamento postando il codice nei tag code così capiamo meglio.. in più non capisco dove tu trovi difficolta.. sulle combinazioni?

Loading