Ir para o conteúdo
H12.10

Criar uma rede de energia

Mensagens Recomendadas

H12.10

Estou a fazer um programa com o objectivo de criar uma rede de energia, o enunciado do trabalho é o seguinte:

Pretende-se desenvolver um programa de computador para optimizar uma rede eléctrica para

um conjunto de N povoações. A rede é composta por uma central de geração de energia

eléctrica que será instalada nas imediações de uma das povoações e diversas linhas de

transmissão de energia que interligam as cidades.

Cada povoação é caracterizada por um par de coordenadas (x, y) correspondendo à sua

longitude e latitude e um valor de potência correspondendo ao seu consumo médio de energia.

Cada linha de transmissão interliga duas povoações e possui um determinado limite de potência

que não deve ser excedido.

O programa deve executar as seguintes tarefas:

1 – Ler um ficheiro de texto contendo a lista de povoações, com o seguinte formato:

a) A primeira linha contém o número de povoações

:) As linhas seguintes contêm as coordenadas x e y e a potência média consumida.

Exemplo do ficheiro:

4

100 250 4000

130 250 3000

50 100 5000

400 080 4000

2 – Deve permitir ao utilizador escolher a povoação onde fica a central

3 – Deve permitir ao utilizador definir o limite de potência das linhas de transmissão.

4 – Optimizar a ligação entre as povoações, obedecendo às seguintes regras:

a) As povoações podem ser ligadas directamente à central ou indirectamente, a uma

cidade que já esteja ligada

:D Cada povoação está ligada à central por apenas um único caminho (não há

circulações).

c) Quando se ligam povoações indirectamente, a carga sobre as linhas de transmissão

que abastecem várias povoações deve ser somada e nunca pode exceder o limite

definido pelo utilizador.

d) O programa deve minimizar o comprimento das linhas de transmissão, ligando cada

cidade à cidade mais próxima que já está ligada, desde que não exceda o limite carga

das linhas de transmissão.

5 – Mostrar no ecrã uma representação gráfica das povoações (circulo) e das linhas de

transmissão.

Em cada cidade deve ser exibido o seu número (de acordo com o ficheiro) e em cada linha deve

ser mostrado a potência que essa linha vai suportar, através de um circulo com esse valor a

meio da linha.

Para tal, criei os seguintes header files:

#pragma once
#include <windows.h> // Win32API Header File
#include "Ponto.h"
#define WHITE RGB (255,255,255)
#define RED RGB (255,0,0)
#define LIME RGB (206,255,0)
#define BLUE RGB (0,0,255)
class Linha
{
private:
HWND janelaId; // Identificador da janela da consola onde se vai
// desenhar a linha
Ponto pi, pf; // pi - Ponto inicial da linha
// pf - Ponto final da linha
public:
Linha(); // Construtor de defeito
Linha(Ponto p1, Ponto p2, HWND janId);
void desenhar(); // Desenha graficamente uma linha com as coordenadas dos pontos pi e pf na janela da consola
float obterComprimento(); // Comprimento da linha
};

#pragma once
#include<stdio.h>
#include<math.h>

class Ponto{
private:
int x, y;

public:
Ponto(int xi=0,int yi=0){x=xi,y=yi;}//construtor por omissão




void atribuirXY(int novo_x, int novo_y){x=novo_x,y=novo_y;} // novas coordenadas
void escreverXY(){printf ("O vector tem as seguintes coordenadas [x=%d,y=%d]",x,y);} //escreve no monitor as coordenadas

float distancia(Ponto p2){return sqrt(pow(float(x)-p2.x,2)+pow(float(y)-p2.y,2));} // calcula a distancia a um ponto p2

int obterX(){return x;} // devolve a coordenada x
int obterY(){return y;} // devolve a coordenada y
};

#pragma once
#include <windows.h> // Win32API Header File
#include "Ponto.h"
class Povoacao{
private:
HWND janelaId; // Identificador da janela da consola onde se vai desenhar o circulo
int nPov;
int npov;
Ponto coordenada_pov; // coordenadas do centro
int raio; // raio no gráfico
int valor;// número da povoação
int potencia;//potência de cada povoação
public:
Povoacao(); // construtor por omissão
Povoacao(Ponto coord_pov, int pot, int v, int r, HWND janId); //construtor para atribuição
int obterPotencia(){return potencia;}//obetm a potencia do povoação
void desenhar(); // Desenha graficamente a povoação
Ponto obtercentro(){return coordenada_pov;}
};

E os seguintes Cpp files:

#include "Linha.h"
Linha::Linha()
{
pi = Ponto(0, 0);
pf = Ponto(0, 0);
janelaId = NULL;
}
Linha::Linha(Ponto p1, Ponto p2, HWND janId)
{
pi = p1;
pf = p2;
janelaId = janId;
}
void Linha::desenhar()
{
if (janelaId != NULL)
{
HPEN hOPen;
// penstyle, width, color
HPEN hNPen = CreatePen(PS_SOLID, 2, WHITE);
HDC DrawHDC = GetDC(janelaId);
hOPen = (HPEN)SelectObject(DrawHDC, hNPen);
// starting point of line
MoveToEx(DrawHDC, pi.obterX(), pi.obterY(), NULL);
// ending point of line
LineTo(DrawHDC, pf.obterX(), pf.obterY());
DeleteObject(SelectObject(DrawHDC, hOPen));
ReleaseDC(janelaId, DrawHDC);
}
}

float Linha::obterComprimento()
{
return sqrt(pow(float (pf.obterX()) - pf.obterX(),2)+pow(float (pi.obterY()) - pf.obterY(),2));
}

#define _USE_MATH_DEFINES
#include <math.h>
#include "Povoacao.h"
#include "Ponto.h"


Povoacao::Povoacao()
{
   coordenada_pov = Ponto(0,0);
   raio = 0;
   valor = 0;
   potencia = 0;
}


Povoacao::Povoacao(Ponto coord_pov, int pot, int v, int r, HWND janId)
{
coordenada_pov = coord_pov;
    janelaId=janId;
potencia = pot;
raio=r;
valor=v;
}


void Povoacao::desenhar()
{
if (janelaId != NULL)
{
HDC DrawHDC = GetDC(janelaId);
// penstyle, width, color
HPEN hNPen = CreatePen(PS_SOLID, 2, RGB(255, 255, 255));
HPEN hOPen = (HPEN)SelectObject(DrawHDC, hNPen);
HBRUSH hOldBrush;
HBRUSH hNewBrush;
hNewBrush = CreateSolidBrush(RGB(255, 255, 255));
hOldBrush = (HBRUSH)SelectObject(DrawHDC, hNewBrush);
Ellipse(DrawHDC, coordenada_pov.obterX()-raio, coordenada_pov.obterY()+raio,
coordenada_pov.obterX()+raio, coordenada_pov.obterY()-raio);
char str[80];
sprintf_s (str, "%d", valor);
SetBkMode(DrawHDC, TRANSPARENT);
SetTextColor(DrawHDC, RGB(0, 0, 0));
SetTextAlign(DrawHDC, TA_CENTER | TA_BOTTOM | TA_BASELINE);
TextOut(DrawHDC, coordenada_pov.obterX(), coordenada_pov.obterY(), str, strlen(str));
DeleteObject(SelectObject(DrawHDC, hOPen));
DeleteObject(SelectObject(DrawHDC, hOldBrush));
ReleaseDC(janelaId, DrawHDC);
}
}

Com o ficheirom main (ainda incompleto):

#include <windows.h> // Win32API Header File
#include <stdio.h>
#include <stdlib.h>
#include "ponto.h"
#include "Povoacao.h"
#include "Linha.h"
HWND GetConsoleWndHandle (void);
void main(){
HWND hConWnd;
hConWnd = GetConsoleWndHandle();



int npov;
FILE *pfile;
char nome_ficheiro[]="C:\\Documents and Settings\\PC\\Ambiente de trabalho\\Ficha5\\Povoacoes.txt";
pfile = fopen (nome_ficheiro,"r");
if(pfile==NULL)
	printf("Erro ao abrir o ficheiro para leitura\n");
else
{
	int x,y, pot;
	fscanf(pfile, "%d", &npov);
	Povoacao *povoacao = new Povoacao[npov];
	printf("As coordenadas e respectivas potencias sao:\n\n");
	for(int i=0;i<npov;++i){
		fscanf(pfile,"%d %d %d\n",&x,&y,&pot);
		printf("\tPovoacao %d - %d,%d com potencia de %d\n",i+1, x,y,pot);
		povoacao[i] = Povoacao(Ponto (x,y),pot,i+1,20, hConWnd);
	}

	//Potencia da povoacao
	int pot_max;
	printf("Indique a potencia maxima admitida nas linhas\t");
	scanf("%d", &pot_max);



	//Povoacao ligada
	int central;
        printf ("\nIndique o numero da povoacao que pretende para central:\t");
	scanf  ("%d", &central);


	//Calcular as distancias
	float d;
	float distmin=1000000; 
	for (int i=0;i<npov;i++)
	{
		d = ((povoacao [central-1]).obtercentro()).distancia((povoacao [i]).obtercentro());
		printf ("Distancia da central (localizada em %d) a povoacao %d => %f\n", central,i+1, d);
		if (d!=0 && d<distmin) distmin=d;
	}printf("%f\n", distmin);
	for (int i=0;i<npov;i++)
	{
		d = ((povoacao [central-1]).obtercentro()).distancia((povoacao [i]).obtercentro());
					if (d == distmin){ 
			Linha L(povoacao [central-1].obtercentro(),povoacao [i].obtercentro(),hConWnd);
			L.desenhar();}
	}

	for (int j=0;j<npov;j++){
	for (int i=0;i<npov;i++)
	{
		d = ((povoacao [j]).obtercentro()).distancia((povoacao [i]).obtercentro());
		if (d!=0 && d<distmin) distmin=d;
	}
	for (int i=0;i<npov;i++)
	{
		d = ((povoacao [j]).obtercentro()).distancia((povoacao [i]).obtercentro());
					if (d == distmin){ 
			Linha L(povoacao [j].obtercentro(),povoacao [i].obtercentro(),hConWnd);
			L.desenhar();}
	}
	}





    // Desenhar
	for(int i=0;i<npov;++i)
	{
		povoacao[i].desenhar();
	} 
}



}



HWND GetConsoleWndHandle(void)
{
HWND hConWnd;
OSVERSIONINFO os;
char szTempTitle[64], szClassName[128], szOriginalTitle[1024];
os.dwOSVersionInfoSize = sizeof( OSVERSIONINFO );
GetVersionEx( &os );
// may not work on WIN9x
if ( os.dwPlatformId == VER_PLATFORM_WIN32s ) return 0;
GetConsoleTitle( szOriginalTitle, sizeof( szOriginalTitle ) );
sprintf( szTempTitle,"%u - %u", GetTickCount(), GetCurrentProcessId() );
SetConsoleTitle( szTempTitle );
Sleep( 40 );
// handle for NT
hConWnd = FindWindow( NULL, szTempTitle );
SetConsoleTitle( szOriginalTitle );
// may not work on WIN9x
if ( os.dwPlatformId == VER_PLATFORM_WIN32_WINDOWS )
{
hConWnd = GetWindow( hConWnd, GW_CHILD );
if ( hConWnd == NULL ) return 0;
GetClassName( hConWnd, szClassName, sizeof ( szClassName ) );
while ( strcmp( szClassName, "ttyGrab" ) != 0 )
{
hConWnd = GetNextWindow( hConWnd, GW_HWNDNEXT );
if ( hConWnd == NULL ) return 0;
GetClassName( hConWnd, szClassName, sizeof( szClassName ) );
}
}
return hConWnd;
}

A minha dúvida está no momento de criar as ligações entre as Povoações, como dá para reparar tentei fazer isso no ficheiro main, mas não tenho tido sucesso, gostaria que alguém me pudesse dar uma mão ou uma ideia.

Notoriamente continuarei a tentar, mas ainda não sou um às nisto e as vezes faltam-me ideias, tenho de entregar esse trabalhar até a noite de réveillon :)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Começas por ver, a partir da povoação que tem a central, as distâncias para cada uma das outras cidades e colocas numa lista ordenada por distância (crescente). As estruturas que estarão nessa lista deverão ter ambas as povoações: a de origem (que inicialmente será a da central para todas as estruturas que estarão na lista) e a de destino. Deverá ter também a distância que foi calculada entre essas cidades e a potência actual que está a ser servida a essa cidade de origem (que para qualquer uma das iniciais será zero).

Dessa lista vais tirar a povoação que está mais próxima (a primeira, visto que estão ordenadas), verificas se é possível adicionar a potência de destino de forma a não passar o limite e, em caso positivo, crias essa ligação e, a partir dessa cidade de destino, crias todas as distâncias para as outras cidades não ligadas, com a soma da potência (provavelmente vais necessitar de uma outra estrutura para registar as cidades ligadas) e colocas ordenadamente na lista.

Assim estás sempre a tirar a povoação mais próxima, que é a que irá utilizar menos cabo. E, como fazes a verificação da potência total, nunca corres o risco de a ultrapassar.

E, com isto, desejo um bom trabalho :)


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
H12.10

Boa noite

Eu já tentei de várias maneiras registar as cidades ligadas, como disseste, mas não vejo com fazê-lo

A verdade é que encalhei nessa fase do programa, a fase das ligações.

Identificar se uma povoação está ligada ou não , como ligar a seguinte povoação, evitar que existam duas ligações a mesma povoação vinda de duas povoações distintas, por ai a fora, é um dilema que tenho a 4 dias.

É incrível que tenha conseguido fazer isto tudo e tenha encalhado aqui, mas acredito que a programar toda a gente já tenha tido um momento desses, curtia que alguém me desse mesmo uma mão nesse aspeto... o Resto a tolerância da linha isso é fácil de tratar depois disto estar resolvido...

KTachyon, muito obrigado pelas dicas, mas eu tenho isso tudo em mente, o problema mesmo é executar :S

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Tens a lista de povoações que identificas por um id crescente, a partir de zero, por exemplo. Com isto crias um array:

char ligada[N_POVOACOES] = { 0 };

ligada[POVOACAO_CENTRAL] = 1;

// ...
// quando vais tentar ligar duas povoações
if (!ligada[id_povoacao_destino]) {
    // ligas a povoação
    ligada[id_povoacao_destino] = 1;
}

Se fizeres como disse, com uma fila ordenada por distâncias em que vais inserindo as novas cidades já ligadas como ponto de origem e as não ligadas como ponto de destino a essa lista, ordenada por distâncias, à medida que vais tirando as estruturas dessa lista, tens sempre a menor distância para uma ligação, onde tens apenas que verificar se a de destino já está ligada (tal como o código anterior), e se a soma das potências desde a central não ultrapassa o limite.

A estrutura podia ser, por exemplo uma struct do tipo:

struct ligacao {
    povoacao* origem;
    povoacao* destino;
    int potencia_acumulada;
    int distancia;
}

Mas também podes (e se calhar será uma melhor opção) criar uma classe com este objectivo.

Basicamente não adicionei nenhum elemento que não tivesse já indicado no post anterior, mas acredito que assim já seja mais legível. Podes ter dúvidas na implementação, mas esta solução funciona. Só tens que tirar dúvidas em relação a determinados aspectos relacionados com a implementação, mas penso que os dados que aqui estou a dar já são suficientes para desenvolveres a solução optimizada, pedida no ponto 4 do teu trabalho.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
H12.10

KTachyon, obrigado pelas dicas  :D, ainda não me consegui safar, mas amanhã dou mais umas voltas nisto.

Isto anda-me mesmo a tirar o sono, sei que para muito pessoal aqui isto é uma piada, mas para mim, isto é o cabo dos trabalhos  :D

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Se fores fazendo por passos e testando, chegas à solução. Por exemplo, vais precisar de, por exemplo, uma lista ordenada. Crias uma lista com conteúdo simples e crias os métodos para a ordenar. Verificas e corriges até estar tudo OK. Depois crias as ligações e alteras a lista e o método para utilizar as ligações e ordenar as ligações na lista, respectivamente. Por aí em diante... não é preciso implementares tudo de uma vez. Uns prints de vez em quando ajudam a desenvolver o trabalho com relativa facilidade.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
H12.10

Não estou mesmo a atinar com isto, tentei criar uma classe para fazer as ligações mas são só erros atrás de erros...

Começo a achar que não tenho mesmo conhecimento suficiente para fazer isto :S

Isto é que é morrer na praia... Passo o dia nisto e não mexe nem um bocado

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Mostra la o código e os erros que o pessoal já te diz o que estás a fazer mal :D

Também se aprende assim.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
H12.10

Eu já enviei código, na primeira mensagem.

Não mudei nada porque esse foi o ultimo código que, embora precário, é o que menos erros me dá.

Eu queria mesmo era umas luzes, mas tipo holofotes, porque estou mesmo sem sangue  :D

Já estou nisto a duas semanas e só vim aqui porque já não tinha outra chance... Podia pedir umas dicas o meu prof, mas ambos estamos de férias e não consigo contacta-lo...

Estou a ver que não vou conseguir fazer isto  :D

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Mas o que nós queremos é que tu nos apresentes a tua tentativa de implementar a solução (como a que já indiquei) e que digas que erros ocorrem, para que tos possamos corrigir.

É óbvio que se não alterares o código para implementar a funcionalidade que te dá a solução para esse problema, nunca vais avançar no projecto.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
H12.10

Natal feito, kilos engoradados e já voltei a casa para trabalhar... Consiguei dar um avanço a isto, mas preciso de uma pequena dica em relação à seguinte parte do algoritmo:

//Ligação Central povoação mais proxima
	for (int i=0;i<npov;i++)
	{
		d = ((povoacao [central-1]).obtercentro()).distancia((povoacao [i]).obtercentro());
					if (d == distmin){ 
			Linha L(povoacao [central-1].obtercentro(),povoacao [i].obtercentro(),hConWnd);
			L.desenhar();
			ligada[i] = 1;}
	}


	//Ligações prosteriores, Povoacao a povoacao.
	// ainda sem verificacao de potencia :S
	for (int j=0;j<npov;j++)
	{
	distmin =100000;
	for (int i=0;i<npov;i++)
	{
		d = ((povoacao [j]).obtercentro()).distancia((povoacao [i]).obtercentro());
		if (d!=0 && d<distmin) distmin=d; 
	}printf("%f\n", distmin);
	for (int i=0;i<npov;i++)
	{
		d = ((povoacao [j]).obtercentro()).distancia((povoacao [i]).obtercentro());
		if (ligada[i] == -1 && d == distmin)
			{
				Linha L(povoacao [j].obtercentro(),povoacao [i].obtercentro(),hConWnd);
				L.desenhar();
				ligada[i] = 1;
			}

	}
	}

A minha duvida reside em conseguir fazer o algoritmo saltar as ligações já feitas e conseguir verificar qual é a cidade mais próxima sem ligação, para posteriormente fazer a ligação... O que me acontece é que ele acha a ligação mais próxima, mas se já se encontra ligada, não faz ligação alguma e segue para a cidade vizinha para iniciar o processo de verificação da mais próxima...

Em relação a potencia máxima, não sei ainda como fazer, mas creio que posso fazer um While e adicionar um somador, para ele fazer as ligações apenas quando esse somador não ultrapassar o limita máximo de ligações... mas primeiro gostaria de resolver o problema das ligações :thumbsup:

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Epah... parece-me que nem sequer tentaste perceber a sugestão que te dei. Sabes que, se fizeres uma lista ordenada por distâncias, consegues obter sempre as menores distâncias e passas o processo de verificação de potência para um segundo plano...

1. Só podes ligar cidades sem corrente a cidades com central ou ligadas à central. Caso contrário nunca sabes a potência máxima que vai surgir das ligações que estás a adicionar.

2. Cidades já ligadas não precisam de ser novamente ligadas, daí a minha sugestão de teres uma lista que verifica o estado de ligação de cada uma das cidades.

3. A ordem de ligação por distância ascendente entre cada cidade ligada com cada cidade não ligada é o percurso mais curto da corrente, daí a minha sugestão de utilizares uma lista ordenada por distâncias onde vais adicionando as distâncias entre cidades que vão sendo ligadas e cidades que não foram ainda ligadas.

A partir do momento em que consegues criar todas as ligações mais curtas entre as cidades a partir de cidades já ligadas, aí já podes começar a pensar nos limites de banda, que não são mais que adicionares mais uma variável aos objectos da lista que te indicam o somatório das potências necessárias.

Aquilo que estás a fazer é, pegar numa povoação, e verificar a distância mínima entre essa e outra. Isso não te vai garantir que, a partir dessa cidade não existem outras cidades que estejam mais próximas dessa e que sejam cobertas pela potência máxima da linha. Logo, à partida, o teu algoritmo vai mal.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
H12.10

Não, não é que não tentei a tua solução, simplesmente não sei implementar isso, estou completamente a nora :S

Eu compreendi o que me pediste, tanto que criei isto no ficheiro main:

// Verificador de ligação
	int ligada[500]; 
	for(int i = 0; i < npov; i++)
	{	
	ligada[i] = -1;
	}

Mas, quando me pedes para criar uma lista que ordene as distancias, não sei como fazer isso...

Tenho duas dúvidas:

1 - Crio um array de distancias e mando ordenar!?

2 - Como é que eu sei, depois de ordenado o array, o índice a que tenho de ligar a povoação!?

Não é que tenho ignorado os teus concelhos, mas não sei mesmo como fazê-los, eu até percebo as ideas, mas implementar, está complicado.

Eu só tenho duas cadeiras de programação no curso e a primeira fiz a 4 anos, isto para mim é do mais difícil que há, assumo.

Eu bem podia fazer como muita malta faz e pagar a um gajo qualquer para fazer isto, mas assim não se aprende nada.

Epah peço desculpa se achaste que estou a ser teimoso, mas estou mesmo agarrado com isto e não estou em posição de teimar nada lol

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

No que toca à lista ordenada, tens imensas opções, mas penso que a mais eficaz para este trabalho seria uma lista ligada, em que verificarias elemento a elemento a distância e farias a inserção de elementos já na posição correcta. Desta forma evitas utilizar arrays, que têm alguns problemas de flexibilidade.

Tens a definição e exemplos de listas ligadas em:

http://en.wikipedia.org/wiki/Linked_list (mais teoria/fácil compreensão)

http://pt.wikipedia.org/wiki/Lista_ligada (com bastante código)

Depois de perceberes bem o que é uma lista ligara (e de teres a base implementada, incluindo um método que faz a inserção no meio da lista), o teu algoritmo será baseado em criar estruturas que representem a uma ligação entre duas cidades, a de origem que já tem energia, e a destino que não têm. O processo seria qualquer coisa como:

Cidades: A, B, C, D

Hc (central)
H* (com energia)

Distâncias
A,B = 10
A,C = 7
A,D = 3
B,C = 4
B,D = 5
C,D = 2

Listas:
Por ligar: B, C, D
(A, D, 3) -> (A, C, 7) -> (A, B, 10)

Retiras o primeiro elemento da lista... D já está ligado? Não. Então liga.
Inseres na lista todas as ligações derivadas de D que não estão ainda ligadas:

Listas:
Por ligar: B, C
(D, C, 2) -> (D, B, 5) -> (A, C, 7) -> (A, B, 10)

Retiras o primeiro elemento da lista... C já está ligado? Não. Então liga.
Inseres na lista todas as ligações derivadas de C que não estão ainda ligadas:

Listas:
Por ligar: B
(C, B, 4) -> (D, B, 5) -> (A, C, 7) -> (A, B, 10)

Retiras o primeiro elemento da lista... B já está ligado? Não. Então liga.
Inseres na lista todas as ligações derivadas de B que não estão ainda ligadas:

Listas:
Por ligar: nenhuma
(D, B, 5) -> (A, C, 7) -> (A, B, 10)

Neste momento, visto que não há mais cidades por ligar, podes parar o processo por aqui.

Depois só tens que inserir a potência total utilizada aos elementos da lista e fazer a verificação se a potência é ultrapassada. É também importante verificares se existem mais elementos na lista (verificar se o ponteiro para o próximo nó é nulo), para evitar casos em que não consegues mesmo ligar uma determinada cidade (caso a potência necessária seja superior ao limite indicado pelo utilizador). Mas isto já são pormenores, quando chegares a este ponto já terás 95% do trabalho feito.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
zarantan

Boa noite, tambem estou a realizar este programa(e também já fiz a anterior,cadeira de programação, a cerca de 3 anos)

Acabei por usar uma nova classe a classe linhadetransmissao, estou agora e com dificuldades a tentar ordenar as distancias

    //Povoacao ligada
                int central;
        printf ("\nIndique o numero da povoacao que pretende para central:\t");
                scanf  ("%d", &central);
                //Calcular as distancias
				float d;
				int dist[100]; 
                for (int i=0;i<npov;i++)
                {
                        d = ((povoacao [central-1]).obtercentro()).distancia((povoacao [i]).obtercentro());
                        printf ("Distancia da central (localizada em %d) a povoacao %d => %f\n", central,i+1, d);
					Ponto p=povoacao [central-1].obtercentro();
					Ponto pf=povoacao [i].obtercentro();
					Linha L(p,pf,hConWnd);
					linhatransmissao *lintrans = new linhatransmissao[npov];
					lintrans[i]=linhatransmissao(L,povoacao [i].obterPotencia(),d);

					dist[i]=lintrans[i].obterdistancia();
                }


			Quick(dist , 0, npov);

			} 
     }

}
void Quick(int vetor[100], int inicio, int fim)
{
    
   int pivo, aux, i, j, meio;
    
   i = inicio;
   j = fim;
    
   meio = (int) ((i + j) / 2);
   pivo = vetor[meio];
    
   do{
      while (vetor[i] < pivo) i = i + 1;
      while (vetor[j] > pivo) j = j - 1;
       
      if(i <= j){
         aux = vetor[i];
         vetor[i] = vetor[j];
         vetor[j] = aux;
         i = i + 1;
         j = j - 1;
      }
   }while(j > i);
    
   if(inicio < j) Quick(vetor, inicio, j);
   if(i < fim) Quick(vetor, i, fim);   

}

Nao sei se este código quick(quick sort) esta a fazer aquilo que necessito pois penso que só estou a ordenar as distancias sem saber a qual cidade pertence, penso eu.Sera que a solução é por aqui?Precisava de uma ajuda!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Estás a fazer isto dentro do ciclo for:

linhatransmissao *lintrans = new linhatransmissao[npov];
lintrans[i]=linhatransmissao(L,povoacao [i].obterPotencia(),d);

A mim parece-me que estás a alocar um npov espaços para linhas de transmissão em memória, para só utilizares o espaço de um elemento durante todo o ciclo.

Depois, ordenares distâncias sem teres nada associado não te serve de nada. O que podes fazer é:

struct line {
    pov* origem;
    pov* destino;
    int distancia;
}

E ordenas as estruturas com o método. Também podes fazer uma classe em vez de utilizares uma struct.

Finalmente, existem (npov-1)*(npov-2) linhas possíveis e (npov-1) ligações finais. Não sei exactamente o que pretendes fazer com esse ciclo, mas não me parece que sirva para criar e ordenar todas as distâncias, apenas as distâncias à central. Vocês estão a limitar o algoritmo à central, para depois terem que replicar todo o processo para 2, 3, 4, (...) povoações que entretanto vão sendo ligadas.

Aquilo que vocês sabem é que têm que limitar a procura de ligações a cidades que já estejam ligadas.

Ciclicamente, o que vocês podem fazer é, com nested loops (um for dentro de outro for) é verificar se a cidade/povoação está ligada. Caso afirmativo, correm o segundo ciclo para achar as distâncias mínimas. Mas, se fizerem isto vão ter que ter outra estrutura que mantenha todas as rotas que todas as ligações têm, caso contrário não conseguem limitar a potência das linhas. Outro problema que vão ter é que, quando encontrarem uma distância mínima que ultrapasse o limite de potência, têm que arranjar uma forma de impedir que a próxima pesquisa por distâncias mais curtas volte a apanhar essa ligação (porque é mais curta).

Da forma como eu vos estou a solucionar o problema, vocês só têm que se preocupar em colocar as linhas uma vez por cidade ligada, por ordem, e nunca mais têm que se preocupar se se repetem ou não. Toda a informação necessária para limitar a potência pode ser colocada nos mesmos objectos que representam as distâncias entre cidades. Mas nada disto implica que necessitem de um algoritmo de ordenamento. Com a estrutura correcta (como já disse, listas ligadas), vocês não necessitam de ordenar. Basta inserirem na posição correcta.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
zarantan

Nao tenho a certeza se percebi tudo o que disseste mas surgiu-me uma ideia eu ja criei a classe linha transmissão, com as informações desta classe posso depois ligar as povoações mais próxima e depois verificar se as restantes povoações serão ligadas a central ou a outra povoacao!

#include "linha.h"
#include "Ponto.h"
class linhatransmissao
{
private:
Linha l;
int potenciamaxima;
int distancia;
public:
linhatransmissao(void);
linhatransmissao(Linha line,int Pmax,int dist);
int obterdistancia(){return distancia;}
~linhatransmissao(void);
};

mas o meu problema agora e nao saber usar o quick sort numa classe, ou seja, eu como guardei a informaçao toda nesta classe queria agora ordenar isto por potencias

lintrans[i]=linhatransmissao(L,povoacao [i].obterPotencia(),d);

penso que aqui estou a guardar todas as informações que preciso! L--> da me a linha e d--> esta me a dar a distancia a central!

Agora queria era ordenar lintras por distancia(d), não sei e fazer este passo!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Tal como tens um array de vectores, tens um array de objectos. Fazes exactamente a mesma coisa, mas em vez de comparares os valores comparas as variáves que estão dentro dos objectos. Ou melhor: fazes uma função que te devolva a comparação entre dois objectos. Ou ainda: fazes o operator overload para esse objecto, para poderes aplicar a comparação directamente entre esses dois objectos. :thumbsup:


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
zarantan

Isso que disseste ultrapassa em muito os meus conhecimentos, mas o que vou tentar e calcular todas as distancias entre as povoacoes e a central e entre todas as povoações.E depois por um metodo, que ainda nao sei, ligar as que estao mais perto e tentar ligar depois as mais distantes.! :wallbash:

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
H12.10

zarantan

Eu também tenho essa tua duvida e estou a tentar fazer o que pretendes

Criar uma lista com as distancias, ordena-la e depois ligar a mais próxima a centras e as sucessivas as que já se encontram ligadas.

Também tenho dificuldade em perceber e implementar as solução que o KTachyon tem, com grande disponibilidade, fornecido.

Mas a verdade é que somos muito verdes nisto e seria óptimo termos soluções mais simples, não é!!? loool

KTachyon

Eu estive a pensar, depois de falhar todas alternativas que me deste (por falta de talento nisto), se poderíamos um criar array de duas dimensões e depois ordenar apenas as distancias. Posteriormente iríamos ler esse array e saber o que índice pertence a distancia mais próxima... Sabendo esse índice poderíamos utiliza-lo para efectuar as ligações que pretendíamos.

Também poderíamos por ai criar um "while" que iria procurar distancia a distancia (recolhendo o índice reconhecedor da cidade), enquanto a potencia das cidades ligadas não excedesse o limite pretendido. Para isso obteríamos a potencia da cidade ligada a cada ligação efectuada e fazíamos um somador que seria verificado, caso excedesse o valor de potencia, a nova central a ligar voltaria a ligara a central e começava uma nova linha.

Esta solução é praticável!!? Eu gostaria de saber, mas mesmo assim, não sei se tenho bases de programação suficientes para conseguir trazer essa ideia à luz do dia  :down:

Eu estive o dia todo a tentar perceber o conceito das listas ligadas e não deu em nada...

Eu só quero acabar este trabalho e nunca mais olhar para isto, não é mesmo a minha praia LOL

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

int comparaDistancias(Objecto o1, Objecto o2) {
    return o1.getDistancia() - o2.getDistancia();
}

Retorna positivo se a distância de o1 for maior que a de o2, negativo se a de o2 for maior que a de o1 e zero se forem iguais. Não estou a perceber a vossa dúvida.

Vocês têm que fazer isto com classes e objectos, correcto? Eu vou mostrar-vos uma solução feita em C puro, sem grandes estruturação, feito nalguns minutos:

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

typedef struct city {
    int coordX;
    int coordY;
    int power;
} city;

typedef struct conn {
    int origin;
    int destin;
    float distance;
    int power;
} connection;

typedef struct dlnode* dlist;
typedef struct dlnode {
    connection* conn;
    dlist prev;
    dlist next;
} dlist_node;

// verifica se já todas as cidades foram ligadas
char all_connected(char states[], int npov) {
char x = 1;
int i;

for (i = 0; i < npov; i++) x *= states[i];

return x;
}

float distance(city* origin, city* destin) {
return sqrt(pow(origin->coordX - destin->coordX, 2) + pow(origin->coordY - destin->coordY, 2));
}

// adiciona conn à lista ordenada por distãncia ascendente
void add_ascending(dlist sentinel, connection* conn) {
dlist r = (dlist) malloc (sizeof (dlist_node));

dlist s = sentinel->next;

while (s != sentinel && s->conn->distance < conn->distance) s = s->next;

s = s->prev;

r->conn = conn;
    r->prev = s;
    r->next = s->next;
r->prev->next = r;
    r->next->prev = r;
}

void actualiza_potencias(dlist sentinel, int origem, int potencia_adicional) {
dlist s = sentinel->next;

while (s != sentinel) {
	if (s->conn->origin == origem) {
	   s->conn->power += potencia_adicional;
	   
	   printf("\tConnection %d->%d updated - distancia %f, com potencia de %d\n", (s->conn->origin)+1, (s->conn->destin)+1, s->conn->distance, s->conn->power);
	}

	s = s->next;
}
}

int main ()
{
    FILE *pfile;
    pfile = fopen ("povs.txt","r");
    int npov;
    
    if (pfile == NULL)
        printf("Erro ao abrir o ficheiro para leitura\n");
    else {
        fscanf(pfile, "%d", &npov);
        city* cities = malloc(sizeof(city) * npov);
        printf("As coordenadas e respectivas potencias sao:\n\n");
        
        int i;
        
        for(i = 0; i < npov; i++){
            fscanf(pfile,"%d %d %d\n",&(cities[i].coordX),&(cities[i].coordY),&(cities[i].power));
            printf("\tPovoacao %d - %d,%d com potencia de %d\n",i+1, cities[i].coordX,cities[i].coordY,cities[i].power);
        }
        
        int pot_max;
        printf("Indique a potencia maxima admitida nas linhas\t");
        scanf("%d", &pot_max);
        
        int central;
        printf ("\nIndique o numero da povoacao que pretende para central:\t");
        scanf  ("%d", &central);
        
        central--;
        
        char connected[npov];
        memset(connected, 0, npov*sizeof(char));
        
        connected[central] = 1;
        
        // criar lista inicial (central -> outras cidades):
        dlist sentinel = malloc(sizeof(dlist_node)); // Nó sentinela (se sentinel->next = sentinel, a lista está vazia)
        sentinel->next = sentinel;
        sentinel->prev = sentinel;
        sentinel->conn = NULL;
        
        for (i = 0; i < npov; i++) {
            if (i != central) {
            	connection* line = malloc(sizeof(connection));
            	line->origin = central;
            	line->destin = i;
            	line->distance = distance(&(cities[central]), &(cities[i]));
            	line->power = cities[i].power;
            	
            	printf("\tConnection %d->%d added - distancia %f, com potencia de %d\n", central+1, i+1, line->distance, line->power);
            	add_ascending(sentinel, line);
            }
        }
        
        // processo de selecção de ligações
        while (sentinel->next != sentinel && !all_connected(connected, npov)) {
        	// tira o primeiro nó da lista:
        	connection* conn = sentinel->next->conn;
        	
        	if (sentinel->next == sentinel->prev)
        		sentinel->prev = sentinel;
        	sentinel->next = sentinel->next->next;
        	sentinel->next->prev = sentinel;
        	
        	// Se não ultrapassar a potência e o destino ainda não estiver ligado, liga:
        	if (conn->power <= pot_max && !connected[conn->destin]) {
        		printf("Connection found: %d->%d\n", (conn->origin)+1, (conn->destin)+1);
        		
        		// marca como ligada:
        		connected[conn->destin] = 1;
        		
        		// adiciona ligações com cidades não ligadas à lista:
        		for (i = 0; i < npov; i++) {
				if (!connected[i]) {
					connection* line = malloc(sizeof(connection));
					line->origin = conn->destin;
					line->destin = i;
					line->distance = distance(&(cities[conn->destin]), &(cities[i]));
					line->power = cities[i].power + conn->power;

					printf("\tConnection %d->%d added - distancia %f, com potencia de %d\n", (line->origin)+1, (line->destin)+1, line->distance, line->power);
					add_ascending(sentinel, line);
				}
			}

			// actualiza potência de origem
			if (conn->origin != central)
				actualiza_potencias(sentinel, conn->origin, cities[conn->destin].power);
        	}
        }
    }
    
    return 0;
}

Resultados:

As coordenadas e respectivas potencias sao:

Povoacao 1 - 100,250 com potencia de 4000
Povoacao 2 - 130,250 com potencia de 3000
Povoacao 3 - 50,100 com potencia de 5000
Povoacao 4 - 400,80 com potencia de 4000
Indique a potencia maxima admitida nas linhas	5000

Indique o numero da povoacao que pretende para central:	1
Connection 1->2 added - distancia 30.000000, com potencia de 3000
Connection 1->3 added - distancia 158.113876, com potencia de 5000
Connection 1->4 added - distancia 344.818787, com potencia de 4000
Connection found: 1->2
Connection 2->3 added - distancia 170.000000, com potencia de 8000
Connection 2->4 added - distancia 319.061127, com potencia de 7000
Connection found: 1->3
Connection 3->4 added - distancia 350.570953, com potencia de 9000
Connection found: 1->4

As coordenadas e respectivas potencias sao:

Povoacao 1 - 100,250 com potencia de 4000
Povoacao 2 - 130,250 com potencia de 3000
Povoacao 3 - 50,100 com potencia de 5000
Povoacao 4 - 400,80 com potencia de 4000
Indique a potencia maxima admitida nas linhas	8000

Indique o numero da povoacao que pretende para central:	3
Connection 3->1 added - distancia 158.113876, com potencia de 4000
Connection 3->2 added - distancia 170.000000, com potencia de 3000
Connection 3->4 added - distancia 350.570953, com potencia de 4000
Connection found: 3->1
Connection 1->2 added - distancia 30.000000, com potencia de 7000
Connection 1->4 added - distancia 344.818787, com potencia de 8000
Connection found: 1->2
Connection 2->4 added - distancia 319.061127, com potencia de 11000
Connection 1->4 updated - distancia 344.818787, com potencia de 11000
Connection found: 3->4


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
zarantan

Tu es do gênero Deus! Eu estou a uma semana a tentar fazer o que fizeste em alguns minutos!Penso que isto e mesmo demais para mim porque agora não consigo entender o teu código, nao ha maneira de usando os headers files(.h) resolver o problema como estava a tentar?!tentando o normal copy-paste aparece sempre erros no malloc tentei substituir por new mas continua a dar erro! 

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.