C++ tenho dificuldade em criar um programa

21 de setembro de 2020

Consideremos um problema comum encontrado por fabricantes de placas eletrônicas e projetistas de computadores. Eles empregam furadeiras a laser para a fabricação de dezenas de milhares de milhares de buracos em suas placas. Para minimizar o custo, os projetistas de computadores não querem que os buracos se comportem como “turistas acidentais”. Pelo contrário, o problema é encontrar a “excursão” mais curta entre os buracos, que visite a posição de cada um deles exatamente uma vez.

A proposta do projeto é resolver o problema citado acima, desenvolvendo um código a partir de coordenadas de pontos de furação em uma máquina. Considere que no instante 0, a máquina está posicionada na posição (0,0) no plano, e ao terminar a furação, essa máquina deverá voltar à posição inicial. Resolva de maneira a garantir o resultado ótimo.

Entrada: A entrada é composta por um valor N (0 < N ≤10), que indica a quantidade de pontos de furação. Logo após, seguem N linhas, cada uma com uma coordenada (X,Y), que indica onde deverá ser furado.

Saída: A saída é composta por um valor de ponto flutuante com 2 casas decimais que representa a distância que a furadeira irá percorrer. Após isso, segue a sequência de pontos que deverá ser executada para percorrer a menor distância.

aguem me ajuda a fazer? em c++

Flávio Pedroza · 21 de setembro de 2020

Eu faria assim:

você tem que pegar os pontos e ordená-los a partir da distância da origem (os mais pertos primeiro e mais distantes por último). A distância você calcula com Pitágoras (c^2 = a^2 + b^2). Ex.:

(1, 4) (2, 3) (1, 2) - coordenadas
 4,12   3,16   2,24 - distância da origem

O mais eficiente é você furar os pontos mais próximos e deixar os mais distantes por último. Então:, ordenados os "furos"

(1, 2) (2, 3) (1, 4)
Neste examplo, a broca ira percorrer a distância horizontal (eixo x) de 1+1+1=3 e na vertical (eixo y) 2+1+1=4 - total 5.
Mais a distância para voltar a origem (0,0) = 5 + 4,12 = 9,12

Caso não tivesse ordendando os ponto a distância seria:
(1, 4) (2, 3) (1, 2) 
x: 1 + 1 + 1 = 3
y: 4 + 1 + 1 = 7
7,62 + 2,24 = 9,86

Depois é só você calcular a distância percorrida, lembrado que deve adicionar a distância que a broca percorrer para volta a origem.

21 de setembro de 2020

@Flávio Pedroza o problema é fazer o codigo que n to sabendo

using namespace std;

int main()
{
//inicialização

   int n; //indica a quantidade de pontos de furação
   float furos [0][0]; //seguem N linhas, cada uma com uma coordenada (X,Y), que indica onde deverá ser furado
   float soma;

//entradas

cout << "Entre com a quantidade de pontos de furação" << endl;
cin >> n;

   for(int i = 0; i < 2; i++)
       for(int j = 0; j < 2; j++)
       {
           cin >> furos[i][j];
       }
isso q fiz ate agora porque n sei como q faz

Flávio Pedroza · 22 de setembro de 2020

using namespace std;

int main()
{
    //inicialização

    int n; //indica a quantidade de pontos de furação
    float soma = 0;

    //entradas

    cout << "Entre com a quantidade de pontos de furação" << endl;
    cin >> n;
	float furos [n][n]; //seguem N linhas, cada uma com uma coordenada (X,Y), que indica onde deverá ser furado

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            cin >> furos[i][j];
        }
	//...
}

22 de setembro de 2020

@Flávio Pedroza vou ir tentando aqui

22 de setembro de 2020

@Flávio Pedroza

using namespace std;

int main()
{
//inicialização

   int n; //indica a quantidade de pontos de furação
   float aux = 0;
   float a,b,c;
   float furos [n][n]; //seguem N linhas, cada uma com uma coordenada (X,Y), que indica onde deverá ser furado

//entradas

cout << "Entre com a quantidade de pontos de furação" << endl;
cin >> n;

   for(int i = 0; i < n; i++)
       for(int j = 0; j < n; j++)
       {
           cout << "Entre com as coordenadas dos furos" << endl;
           cin >> furos[i][j];
       }

//começando nos pontos (0,0)

   for(int i = 0; i < 0; i++)
       for(int j = 0; j < 0; j++)
       {
           cout << fixed << setprecision(2) << furos[i][j] << endl;
       }

//inciando as contas

   for(int i = 0; i < n; i++)
       for(int j = 0; j < n; j++)
       {
           c^2=b^2+c^2;
           //aux = sqrt(pow(i-i,2)+pow(j-j,2));
       }

return 0;
}

nao estou entendo esta a conta,como vou fazer para começar no início e fazer as contas e voltar no inicio novamente, vou mandar o que tem q entrar e sair

entrada

4

1.0 1.0

1.0 2.0

2.0 1.0

2.0 2.0

saida

6.65

0.00 0.00

1.00 1.00

1.00 2.00

2.00 2.00

2.00 1.00

0.00 0.00

Flávio Pedroza · 22 de setembro de 2020

Pelas saídas que você mostrou, o algoritmo utilizado utiliza outra lógica.

Ele utilizar a ordenação pelo ponto mais próximo do anterior. No caso:

0 0 - ponto inicial
1 1 - ponto mais próximo do inicial (0 0)
1 2 - esté é o ponto mais próximo do anterior ( 1 1)
2 2 - este é o ponto mais próximo do anterior (1 2)
2 1 - este é o ponto mais próximo do anterior (2 1)

Distância percorrida:
de 0 0 para 1 1 - 1,41
de 1 1 para 1 2 - 1
de 1 2 para 2 2 - 1
de 2 2 para 2 1 - 1
de 2 1 para 0 0 - 2,24
total = 6,65

Algumas correções no seu código:

#include <iostream>
#include <iomanip> 
using namespace std;

int main()
{
    //inicialização

    int n; //indica a quantidade de pontos de furação
    float aux = 0;
    float a,b,c;
  

    //entradas

    cout << "Entre com a quantidade de pontos de furação" << endl;
    cin >> n;
    float furos [n][2]; //seguem N linhas, cada uma com uma coordenada (X,Y), que indica onde deverá ser furado

    for(int i = 0; i < n; i++)
	{
        cout << "Entre com as coordenadas do furo "<< i << " X e Y" << endl;
        for(int j = 0; j < 2; j++)
        {
            
            cin >> furos[i][j];
        }
	}
    //começando nos pontos (0,0)

    for(int i = 0; i <n; i++)
        {
            cout << fixed << setprecision(2) << furos[i][0] << " " << furos[i][1] << endl;
        }

    //inciando as contas
    
    return 0;
}

23 de setembro de 2020

@Flávio Pedroza ok vou tentando novamente

adicionado 16 minutos depois

@Flávio Pedroza mais o que ja fiz esta certo?ou tem coisa errada como você corrigiu,como na maquina começar no 0,0 e dps começa ou pontos!

23 de setembro de 2020

17 horas atrás, Flávio Pedroza disse:

0 0 - ponto inicial 1 1 - ponto mais próximo do inicial (0 0) 1 2 - esté é o ponto mais próximo do anterior ( 1 1) 2 2 - este é o ponto mais próximo do anterior (1 2) 2 1 - este é o ponto mais próximo do anterior (2 1) Distância percorrida: de 0 0 para 1 1 - 1,41 de 1 1 para 1 2 - 1 de 1 2 para 2 2 - 1 de 2 2 para 2 1 - 1 de 2 1 para 0 0 - 2,24 total = 6,65

me diga como q vou fazer esta conta no algoritmos q n to conseguindo enxergar

arfneto · 25 de setembro de 2020

Em 21/09/2020 às 13:41, Flávio Pedroza disse:

O mais eficiente é você furar os pontos mais próximos e deixar os mais distantes por último. Então:, ordenados os "furos"

Outro dia furei uma placa que era assim

Pense nesse caso: são 8 furos e você pode furar no sentido horário ou anti-horário e o percurso vai ser de 8cm.

Agora se você classificar os pontos para furar os mais próximos da origem vai andar muito mais... 2 e 2 são os mais distantes por exemplo. As maiores distâncias estão nas diagonais e fica fácil de ver no desenho, já que todas as outras são 1.

A distância entre (2,0) e (0,2) é de 2.83, a mesma que entre (2,2) e (0,0)
A distância entre (1,0) e (0,1) é 1.41, a mesma que entre (1,2) e (2,1)

Só esses percursos vão somar 8.48 e ainda faltariam 2 pontos

Uma planilha sempre ajuda Veja as contas, graças ao Planilhas do Google

Bem mais que os 8cm do percurso normal. Isso considerando que dentre os pontos equidistantes da origem você escolha o mais próximo, porque se furar por exemplo A G B F C E D H na diagonal vai andar 14.96.

Em 21/09/2020 às 13:41, Flávio Pedroza disse:
Eu faria assim:

você tem que pegar os pontos e ordená-los a partir da distância da origem (os mais pertos primeiro e mais distantes por último). A distância você calcula com Pitágoras (c^2 = a^2 + b^2). Ex.:
(1, 4) (2, 3) (1, 2) - coordenadas
 4,12   3,16   2,24 - distância da origem

A distância para o segundo ponto está errada. Seriam aprox. 3,61

Sequenciar os furos na ordem de distância da origem não é a melhor opção, e ainda assim teria que classificar os pontos equidistantes pela distância em relação à broca no momento do furo, como no exemplo

25 de setembro de 2020

@arfneto vou ir tentando aqui, você usaria q método? busca exaltava, método guloso, pd?

arfneto · 25 de setembro de 2020

2 horas atrás, keven2312 disse:

busca exaltava, método guloso, pd?

Que significa?

26 de setembro de 2020

@arfneto programação dinâmica:trata de uma metodologia de construção de algoritmos que resolvam problemas originais do sistema, de forma que otimize e faça uso da análise combinatória, afim de prevenir queda de performance e recálculos desnecessários para atender subsistemas que possam sobrepujar o sistema original, gerando novos subproblemas.

busca exaltiva: percorremos todo o espaço de possíveis soluções em busca da solução do problema. Tipicamente uma solução por busca exaustiva é composta de duas funções: uma que gera todas as possíveis soluções e outra que verifica se a solução gerada é a solução que atende ao problema. Um dos problemas com a busca exaustiva é que pode existir um número muito grande de soluções a serem verificadas.

metodo guloso:é uma técnica de algoritmos para resolver problemas de otimização, sempre realizando a escolha que parece ser a melhor no momento; fazendo uma escolha ótima local, na esperança de que esta escolha leve até a solução ótima global.Vantagens: Algoritmos simples e de fácil implementação.

arfneto · 27 de setembro de 2020

8 horas atrás, keven2312 disse:

exaltiva

Imagino que pretendia escrever exaustiva.

Grato pela explicação das abreviaturas. Talvez seja uma nomenclatura exagerada, mas entendo que possa ser descrito assim.

No popular acho que se poderia dizer:

no jeito. "pd'
na força. "exaustiva"
o melhor que podemos fazer até a hora de entregar. "método guloso"

Outros poderiam dizer

método analítico, usando matemática. Não sei se programação dinâmica é um bom termo.
análise combinatória: considera as permutações, tabela os possíveis resultados e lista os melhores percursos
métodos heurísticos, como o método de Monte Carlo: usam aproximações para o problema e param quando acabar o tempo, o dinheiro ou os dois.

Tenho formação em matemática, mas considerando que:

estamos escrevendo em C++, que talvez seja a melhor linguagem que existe para modelar coisas
o número máximo de furos é bem modesto: 10

Eu iria pelo simples: tabelar os resultados e ver o que dá

Um percurso é uma série de pontos e suas distâncias são conhecidas, como @Flávio Pedroza e Pitágoras já diziam

Então uma classe Ponto ajudaria

#pragma once
#include <iostream>
#include <math.h>
using namespace std;
class Ponto
{
public:
	float x;
	float y;

public:
	Ponto() : x(0.), y(0.) {};
	Ponto(float a, float b) : x(a), y(b) {};

	float distanciaDaOrigem() { return sqrt(x * x + y * y); };
	friend float operator>>(const Ponto&, const Ponto&);
};

float operator>>(const Ponto& A, const Ponto& B)
{
	return sqrt(
		(A.x - B.x) * (A.x - B.x) +
		(A.y - B.y) * (A.y - B.y)
	);
};

Dado um ponto A e um ponto B:

A.distanciaDaOrigem()
B.distanciaDaOrigem()
A>>B

Definem a distância de A e B da origem e a distância entre A e B. Bem conveniente.

E uma classe Percurso

class Percurso
{
public:
	string			arquivo;
	vector<Ponto>	melhor_sequencia;
	vector<Ponto>	pontos;
	float			menor_percurso{};

public:
	Percurso() : arquivo(""), melhor_sequencia({}), pontos({}) {};
	Percurso(string arquivo);

	float	comprimento(vector<int>&);
	friend	ostream& operator<<(ostream&, const vector<Ponto>&);
};

Define um Percurso como um conjunto de Ponto, lido a partir do arquivo "arquivo" fornecido na linha de comando

comprimento() devolve o simples: o deslocamento total da broca incluindo a ida e volta da origem e a passagem por todos os furos. As contas são as mesmas que estão embutidas na planilha que eu postei no tópico #10 antes, basta você preencher os pontos e o programa refaz os cálculos. E se está aparentemente ok pode passar direto para a função em C++, em algo assim:

float		Percurso::comprimento(vector<int>& idx)
{
	// calcula o deslocamento total do broca, indo
	// da origem ate cada ponto na ordem do vetor 
	// de indices e voltando ate a origem ao final
	if (pontos.size() == 0) return 0.; // sem furos sem distancia
	float total = 0;
	float segmento = 0;
	Ponto A{ 0.,0. }; // comeca na origem
	// soma os segmentos
	for_each(idx.begin(), idx.end(), [&](int ix)
		{	total += A>>(pontos[ix]);
			A = pontos[ix];
		});
	// e volta para a origem
	total += A.distanciaDaOrigem();
	return total;
};	// comprimento()

Algo assim para os seus 4 pontos por exemplo mostraria

Esperados 4 pontos
Lidos 4 pontos
Entrada: 'entrada.txt'

Total de 4 pontos

Percurso: (Ponto) (Dist Origem) (+Segmento) (=Subtotal)

(0.00,0.00)
(2.00,2.00) (2.83) (+2.83) (=2.83)
(2.00,1.00) (2.24) (+1.00) (=3.83)
(1.00,1.00) (1.41) (+1.00) (=4.83)
(1.00,2.00) (2.24) (+1.00) (=5.83)
(0.00,0.00) (2.24) (+2.24) (=8.06)

Total do percurso = 8.06


[inicio] Total do percurso acima: 8.06


Total de 4 pontos

Percurso: (Ponto) (Dist Origem) (+Segmento) (=Subtotal)

(0.00,0.00)
(1.00,1.00) (1.41) (+1.41) (=1.41)
(2.00,1.00) (2.24) (+1.00) (=2.41)
(1.00,2.00) (2.24) (+1.41) (=3.83)
(2.00,2.00) (2.83) (+1.00) (=4.83)
(0.00,0.00) (2.83) (+2.83) (=7.66)

Total do percurso = 7.66


[classificado por distancia da origem] Total do percurso acima: 7.66



==> Percurso com deslocamento MINIMO: 6.65mm


Total de 4 pontos

Percurso: (Ponto) (Dist Origem) (+Segmento) (=Subtotal)

(0.00,0.00)
(2.00,1.00) (2.24) (+2.24) (=2.24)
(2.00,2.00) (2.83) (+1.00) (=3.24)
(1.00,2.00) (2.24) (+1.00) (=4.24)
(1.00,1.00) (1.41) (+1.00) (=5.24)
(0.00,0.00) (1.41) (+1.41) (=6.65)

Total do percurso = 6.65

Escrevi um protótipo e usei seus dados

Veja main() como pode ser simples:

    percurso.menor_percurso = 10e20f;
    float este_percurso = 0.f;
    
    // computa as distancias para todos os possiveis percursos
    int testes = 0;
    do
    {
        testes += 1;
        este_percurso = percurso.comprimento(idx);
        if (este_percurso < percurso.menor_percurso)
        {   
            percurso.menor_percurso = este_percurso;
            percurso.melhor_sequencia.clear();
            for_each( idx.begin(), idx.end(),
                [&](int ix) { percurso.melhor_sequencia.push_back(percurso.pontos[ix]); }
            );  // for_each()
        };  // if()

    } while (std::next_permutation(idx.begin(), idx.end()));

Afinal C++ calcula sozinho as permutações, usando STL. Classificar os pontos é trivial, se quiser tentar o que eu disse no tópico #10 que não funciona.

    // classificando os pontos por distancia da origem
    sort(percurso.pontos.begin(), percurso.pontos.end(),
        [](Ponto a, Ponto b) { return a.distanciaDaOrigem() < b.distanciaDaOrigem(); });
    cout << percurso.pontos;

O resultado aparece na listagem acima também em

[classificado por distancia da origem] Total do percurso acima: 7.66

esse cout é o que mostra essa parte

Total de 4 pontos

Percurso: (Ponto) (Dist Origem) (+Segmento) (=Subtotal)

(0.00,0.00)
(1.00,1.00) (1.41) (+1.41) (=1.41)
(2.00,1.00) (2.24) (+1.00) (=2.41)
(1.00,2.00) (2.24) (+1.41) (=3.83)
(2.00,2.00) (2.83) (+1.00) (=4.83)
(0.00,0.00) (2.83) (+2.83) (=7.66)

Total do percurso = 7.66

Bem cômodo

O resultado para o conjunto do desenho em azul no tópico #10

Esperados 7 pontos
Lidos 7 pontos
Entrada: 'quadrado.txt'

Total de 7 pontos

Percurso: (Ponto) (Dist Origem) (+Segmento) (=Subtotal)

(0.00,0.00)
(1.00,0.00) (1.00) (+1.00) (=1.00)
(2.00,0.00) (2.00) (+1.00) (=2.00)
(2.00,1.00) (2.24) (+1.00) (=3.00)
(2.00,2.00) (2.83) (+1.00) (=4.00)
(1.00,2.00) (2.24) (+1.00) (=5.00)
(0.00,2.00) (2.00) (+1.00) (=6.00)
(0.00,1.00) (1.00) (+1.00) (=7.00)
(0.00,0.00) (1.00) (+1.00) (=8.00)

Total do percurso = 8.00


[inicio] Total do percurso acima: 8.00


Total de 7 pontos

Percurso: (Ponto) (Dist Origem) (+Segmento) (=Subtotal)

(0.00,0.00)
(1.00,0.00) (1.00) (+1.00) (=1.00)
(0.00,1.00) (1.00) (+1.41) (=2.41)
(2.00,0.00) (2.00) (+2.24) (=4.65)
(0.00,2.00) (2.00) (+2.83) (=7.48)
(2.00,1.00) (2.24) (+2.24) (=9.71)
(1.00,2.00) (2.24) (+1.41) (=11.13)
(2.00,2.00) (2.83) (+1.00) (=12.13)
(0.00,0.00) (2.83) (+2.83) (=14.96)

Total do percurso = 14.96


[classificado por distancia da origem] Total do percurso acima: 14.96



==> Percurso com deslocamento MINIMO: 8.00mm


Total de 7 pontos

Percurso: (Ponto) (Dist Origem) (+Segmento) (=Subtotal)

(0.00,0.00)
(1.00,0.00) (1.00) (+1.00) (=1.00)
(2.00,0.00) (2.00) (+1.00) (=2.00)
(2.00,1.00) (2.24) (+1.00) (=3.00)
(2.00,2.00) (2.83) (+1.00) (=4.00)
(1.00,2.00) (2.24) (+1.00) (=5.00)
(0.00,2.00) (2.00) (+1.00) (=6.00)
(0.00,1.00) (1.00) (+1.00) (=7.00)
(0.00,0.00) (1.00) (+1.00) (=8.00)

Total do percurso = 8.00

Sem discussões religiosas aqui:

não testei quase nada
só rodei em Windows
só compilei com o compilador da Microsoft

O programa pode ser mais simples, mas eu não fui capaz de escrever como eu queria, no tempo que eu tinha. Acho que usei o "método guloso" para escrever. Se eu tiver uma ideia melhor reescrevo main(). Aquele loop do{}while() não está bom

Uma nota

Essa coisa de

Esperados 4 pontos
Lidos 4 pontos
Entrada: 'entrada.txt'

é porque eu não queria desconsiderar o enunciado, mas não queria um loop para ler os 4 pontos, Então preferi ler o número de pontos e depois ler os pontos que estiverem no arquivo, ainda que diferentes do esperado.

4
2.0 2.0
2.0 1.0
1.0 1.0
1.0 2.0

Esse era o arquivo mas podia editar e colocar mais ou menos pontos para testar. De todo modo o nome do arquivo pode ir na linha de comando mesmo:

    furos pontos.txt

leria o arquivo pontos.txt no diretório corrente.

28 de setembro de 2020

@arfneto sinceramente eu me perco porque conheço mais c++,ai tenho q ficar procurando o que significa o que você digitou kk

arfneto · 28 de setembro de 2020

1 hora atrás, keven2312 disse:

sinceramente eu me perco porque conheço mais c++,ai tenho q ficar procurando o que significa o que você digitou kk

Mas o que por exemplo? Eu postei código em C++ e essas coisas do seu enunciado Você fala daquela nomenclatura alternativa?

E aqui é um forum público então um ligar natural para você perguntar sobre algo que eu digitei num forum público deve ser aqui mesmo, assim o mesmo eu mesmo pode ler e tentar escrever de outro jeito, a invés de você "ficar procurando"

De volta ao programa

Acho que entendi o que faltava para um jeito mais simples de escrever o tal cálculo do menor percurso. Acho que eu não sei um jeito de iterar sobre as possíveis permutações e não pelo mapa de pontos que vai furar. . . Talvez tenha algo, mas não sei. Desisti.

No entanto uma classe Permuta resolve!

class Permuta
{
public:
	bool        _Final{};
	unsigned    _TP;
	unsigned    _Pos{};
	vector<int> _Sequencia{};

public:
	class       Iterator;
	Iterator	begin();
	Iterator	end();

	Permuta&    get(unsigned);
	bool        proxima();
	void        reinicia();
	unsigned    size();

public:
	Permuta(int N);
	~Permuta(){};

private:
};	// Permuta{}

Só 3 variáveis:

o vetor com a permutação dos pontos
um contador de permutações
um bool dizendo se acabou

Só 2 métodos:

reinicia() reinicia a sequência de permutações
proxima() devolve no vetor a próxima permutação, sem repetir claro

Lembrando do ensino fundamental, o total de combinações de N elementos é o fatorial de N. E essa é a quarta variável, só para simplificar. Podia não ter.

Exemplo para 4 pontos

Pos:  1 Final: 0 [ 0 2 1 ]
Pos:  2 Final: 0 [ 1 0 2 ]
Pos:  3 Final: 0 [ 1 2 0 ]
Pos:  4 Final: 0 [ 2 0 1 ]
Pos:  5 Final: 0 [ 2 1 0 ]
Pos:  6 Final: 1 [ 0 1 2 ]

E aí se pode colocar isso naquele código estranho de main() e ficar com algo assim

    // tabela todos os percursos possiveis
    Permuta P(percurso.pontos.size()); // prepara as permutacoes
    percurso.menor_percurso = 10e20f;
    cmp.percurso = &percurso;
    cmp.este_percurso = 0.f;
    for_each(P.begin(), P.end(), cmp );

Onde P é da classe que eu listei acima e calcula as permutações. Então usando P pode calcular os percursos todos e selecionar o menor em uma linha, e sem aquele do{}while() que tinha antes:

    // computa as distancias para todos os possiveis percursos
    int testes = 0;
    do
    {
        testes += 1;
        este_percurso = percurso.comprimento(idx);
        if (este_percurso < percurso.menor_percurso)
        {   
            percurso.menor_percurso = este_percurso;
            percurso.melhor_sequencia.clear();
            for_each( idx.begin(), idx.end(),
                [&](int ix) { percurso.melhor_sequencia.push_back(percurso.pontos[ix]); }
            );  // for_each()
        };  // if()

    } while (std::next_permutation(idx.begin(), idx.end()));

e a função cmp fica com esse código que era o loop antes. Ao final do loop o vetor melhor_sequencia tem a ordem dos pontos que usa o menor percurso possível da broca, e menor_percurso tem o total a percorrer.

O código do cálculo no outro post está completo eu acho.

Gabriel Fraguas · 29 de setembro de 2020

seguinte eu fiz pelo metodo de busca gulosa mas no caso das entradas serem o meu programa deu resposta errada segue o codigo:

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main(){

int n;

double posicao[10][10];

double partida[5][5];

double tamtotal = 0;

int cordenadas[55];

double auxx, auxy;

int menorponto = 0;

partida[0][0] = 0;
partida[0][1] = 0;


// Inserção
// numero de furos

cin >> n;

for(int i = 0; i < n; i++){
for(int j = 0; j < 2; j++)
cin >> posicao[i][j];
}

//Calculos
for(int i=0; i<n; i++){
double menorhip = 999;
for(int j=i; j<n; j++){
double fracaox = posicao[j][0];
double fracaoy = posicao[j][1];
double catetox = pow((fracaox - partida[0][0]), 2);
double catetoy = pow((fracaoy - partida[0][1]), 2);
double hipotenusa = sqrt(catetox + catetoy);

if(hipotenusa < menorhip){
menorhip = hipotenusa;
menorponto = j;
}
}

tamtotal = tamtotal + menorhip;
partida[0][0] = posicao[menorponto][0];
partida[0][1] = posicao[menorponto][1];
cordenadas[i] = menorponto;
auxx = posicao[i][0];
auxy = posicao[i][1];
posicao[i][0] = posicao[menorponto][0];
posicao[i][1] = posicao[menorponto][1];
posicao[menorponto][0] = auxx;
posicao[menorponto][1] = auxy;
}

double fracaox = 0;
double fracaoy = 0;
double catetox = pow((fracaox - posicao[menorponto][0]), 2);
double catetoy = pow((fracaoy - posicao[menorponto][1]), 2);
double hipotenusa = sqrt(catetox + catetoy);
tamtotal = tamtotal + hipotenusa;

cout << tamtotal << endl;

cout << "0.00 0.00" << endl;

for(int i=0; i<n; i++){
cout << posicao[i][0] << " " << posicao[i][1] << endl;
}

cout << "0.00 0.00" << endl;

return 0;
};

se você conhece o problema do caxeiro viajante acredito que consiga fazer algo melhor em cima dele

arfneto · 30 de setembro de 2020

Em 29/09/2020 às 15:02, Gabriel Fraguas disse:

seguinte eu fiz pelo metodo de busca gulosa mas no caso das entradas serem o meu programa deu resposta errada

Para este arquivo

6
3.12    5.3
1.4     2
0       4.4
-2.2    -2
1.7     7.13
-0.25   4.9

Compare com esses números

Esperados 6 pontos
Lidos 6 pontos
Entrada: 'seis.txt'

Total de 6 pontos

Percurso:
(Ponto) (Dist Origem)   (+Segmento)     (=Subtotal)

(0.00,0.00)
(3.12,5.30)     (6.15)  (+6.15) (=6.15)
(1.40,2.00)     (2.44)  (+3.72) (=9.87)
(0.00,4.40)     (4.40)  (+2.78) (=12.65)
(-2.20,-2.00)   (2.97)  (+6.77) (=19.42)
(1.70,7.13)     (7.33)  (+9.93) (=29.35)
(-0.25,4.90)    (4.91)  (+2.96) (=32.31)
(0.00,0.00)     (4.91)  (+4.91) (=37.21)

Total do percurso = 37.21


[inicio] Total do percurso acima: 37.21


Total de 6 pontos

Percurso:
(Ponto) (Dist Origem)   (+Segmento)     (=Subtotal)

(0.00,0.00)
(1.40,2.00)     (2.44)  (+2.44) (=2.44)
(-2.20,-2.00)   (2.97)  (+5.38) (=7.82)
(0.00,4.40)     (4.40)  (+6.77) (=14.59)
(-0.25,4.90)    (4.91)  (+0.56) (=15.15)
(3.12,5.30)     (6.15)  (+3.39) (=18.54)
(1.70,7.13)     (7.33)  (+2.32) (=20.86)
(0.00,0.00)     (7.33)  (+7.33) (=28.19)

Total do percurso = 28.19


[classificado por distancia da origem] Total do percurso acima: 28.19



==> Percurso com deslocamento MINIMO: 21.74mm


Total de 6 pontos

Percurso:
(Ponto) (Dist Origem)   (+Segmento)     (=Subtotal)

(0.00,0.00)
(1.40,2.00)     (2.44)  (+2.44) (=2.44)
(3.12,5.30)     (6.15)  (+3.72) (=6.16)
(1.70,7.13)     (7.33)  (+2.32) (=8.48)
(-0.25,4.90)    (4.91)  (+2.96) (=11.44)
(0.00,4.40)     (4.40)  (+0.56) (=12.00)
(-2.20,-2.00)   (2.97)  (+6.77) (=18.77)
(0.00,0.00)     (2.97)  (+2.97) (=21.74)

Total do percurso = 21.74

O primeiro grupo tem os pontos na ordem do arquivo
O segundo tem os pontos classificados pela distância da origem conforme sugestão de @Flávio Pedroza
O terceiro tem um possível menor percurso para o conjunto.

Em 29/09/2020 às 15:02, Gabriel Fraguas disse:

se você conhece o problema do caxeiro viajante acredito que consiga fazer algo melhor em cima dele

Tenho dúvida de que para esse número pequeno de pontos e escrevendo em C++ valha a pena não usar a força bruta e usar o método analítico e computar os valores todos. Não leva nem 1s para 6 pontos eu acho. Mais alguns segundos para 12. C++ calcula as permutações, classifica os pontos e roda as permutações para os conjuntos, em 1 linha ou duas, como no código que eu postei.

Poste seu algoritmo ou referência para essa solução