Třídění čísel – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Třídění čísel – C / C++ – Fórum – Programujte.comTřídění čísel – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Kaja
~ Anonymní uživatel
22 příspěvků
14. 10. 2012   #1
-
0
-

Ahoj, snažím se setřídit velké množství čísel seškrtáváním tak abych našel nejvyšší číslo a od něj čísla na obě strany klesaly(rostoucí čísla - nejvyšší číslo - klesající čísla). Nejlepší postup co mě napadl je zredukovat duplikáty (všechna stejná čísla nahradit jedním - 1, 2, 2, 2, 3, 5 = 1, 2, 3, 5), potom najít nejvyšší číslo "zprava" (1, 8, 2, 3, 4, 8, 5, 6, 8, 1)  a od něj to porovnávat doprava i doleva menší než (1 < 8 < 2 < 3 < 4 < 8 < 5 < 6 < 8 >1) - 2 "vyškrtnutí". Nemáte lepší postup?(nejde mi o rychlost ale o co nejmíň vyřazených čísel)

Díky

Nahlásit jako SPAM
IP: 89.190.52.–
Reklama
Reklama
ingiraxo+15
Grafoman
14. 10. 2012   #2
-
0
-

takze vlastne uprostred pole bude nejvyssi cislo a pak na kazdou stranu se budou snizovat?

v první řadě to bude nejspíš potřeba setřidit od nejmensiho po nejvetsi... potom do novýho pole to začít tridit.. pokud budou nejaky cisla 2x nebo vickrat, tak je vzdy hodit bud napravo nebo vlevo od stredu

šlo by to i s prohazováním cisel v tom samim poli, ale myslim ze s pomocnym polem to je snazsi

Nahlásit jako SPAM
IP: 213.168.183.–
Moje aplikace: http://ophite.cz
Tutoriály na: C#
vitamin+8
Grafoman
14. 10. 2012   #3
-
0
-

Nestacilo by zotriedit cisla pomocou std::sort(c++) alebo qsort(c)  a potom vypisovat kazde cislo s parnym indexom ako keby bolo nalavo od maxima a kazde cislo s neparnym indexom ako napravo(pripadne opacne)?

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Kaja
~ Anonymní uživatel
22 příspěvků
15. 10. 2012   #4
-
0
-

Jde mi o to seřadit to tím vyřazováním (vyřazuju čísla dokud to není tak jak má - stoupá - vrchol - klesá). Příklad - 1 8 2 3 4 8 6 - 1 2 3 4 8 6 (škrtnu 8) - chci vyškrtnout co nejmíň čísel tak aby to splňovalo ty podmínky.

Nahlásit jako SPAM
IP: 89.190.52.–
vitamin+8
Grafoman
15. 10. 2012   #5
-
0
-

Takze ty nechces aby sa prvky pola presuvali, cize nechces zoradit pole.

Teraz som si to naprogramoval a nie je to tak jednoduche ako to na prvy pohlad vyzera. Hlavne ta podmienka:

vyškrtnout co nejmíň čísel

Na co to vlastne potrebujes?

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
liborb
~ Redaktor
+18
Guru
16. 10. 2012   #6
-
0
-

Nejspíš se můžeš snažit sebevíc, ale vždycky najdeš jenom heuristiku, co funguje na nějaká konkrétní data, ale nikoliv obecně. Pokud ti nejde o rychlost, ale správnost, tak použit prohledávání stavového prostoru, tj. postupně vyřazuj jednotlivé kombinace čísel a zkoušej, jestli je posloupnost po vyřazení již setříděná a pamatuj si ten nejlepší pokus.

Nahlásit jako SPAM
IP: 188.75.135.–
vitamin+8
Grafoman
16. 10. 2012   #7
-
0
-

Ja som to spravyl nasledovne:

Vyradil som vsetky rovnake prvky stojace pri sebe a odpametal si vsetky maxima (nie hodnoty, ale iteratory na maximalne prvky)

Pre kazde maximum som spravyl pole intov ktore bolo rovnako velke ako pole dat.

Kazde pole bolo rozdelene na lavu a pravu cast od vrchola (maxima).

Prvok v novom poli reprezentuje "vahu" prvka s rovnakym indexom v povodnom(datovom) poli.

Kazdy integer(vaha) v novom poli obsahuje pocet cisel ktore treba vyradit z pola dat tak aby sa mohlo ponechat cislo z rovnakym indexom v poli dat.

Potom odstranit prvok z pola ktory ma najvecsiu vahu ( z lavej aj pravej casti zvlst). Odstranenie prvka vyzera tak ze sa mu nastavy vaha na -1 a v dalsich cykloch sa bude prvok ignorovat. 

Znovu sa prepocitaju vsetky vahy a opakuje sa to dovtedy kym na lavej aj pravej strane su prvky s vahou vecsou ako 0.

Teraz nove pole obsahuj vahy s hodnotami 0  a  -1, prvy z datoveho pola s vahou -1 su vyradene a prvky s vahou 0 sa mozu pouzit.

Samozrejme je to spravene pre vsetky vrcholy(maxima), uz si staci vybrat kombinaciu ktora je najdlhsia.

Trochu spraseny kod   :

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <limits>
using namespace std;

typedef int num_t;
typedef int weight_t;

class Tops{
		vector<vector<num_t>::iterator>	data;
	public:
		num_t value()const{return *data.front();}
		void reset(vector<num_t>::iterator x){data.clear();data.push_back(x);}
		void add(vector<num_t>::iterator x){data.push_back(x);}
		size_t size()const{return data.size();}
		vector<num_t>::iterator operator [](size_t i)const{return data[i];}
		vector<vector<num_t>::iterator>::iterator begin(){return data.begin();}
		vector<vector<num_t>::iterator>::iterator end(){return data.end();}
		Tops(vector<num_t>::iterator x){data.push_back(x);}
};
class Weights{
		const vector<num_t>& data;
		vector<num_t>::const_iterator	top;	//vrchol
		vector<weight_t>::iterator	wtop;	//vrchol(vaha)
		vector<weight_t> weights;			//vahy
		vector<weight_t>::iterator max_left, max_right;	//maxima
		size_t	a_size;		//pocet aktyvnych prvkov
	public:
		size_t size()const{
			return a_size;
			}
		
		Weights(const vector<num_t>& data, vector<num_t>::const_iterator top):data(data), top(top), weights(data.size(), 0), a_size(data.size()){
			auto d = data.begin();		//aktualny prvok v data
			auto w = weights.begin();	//aktualna vaha
			
			//lava cast od vrcholu:
			max_left = w;
			for(; d != top; ++d, ++w){
				auto x = data.begin();
				if(*d == *top){
					 *w = numeric_limits<int>::max();
					 max_left = w;
					 continue;
				 }	
				
				for( ; x != d; ++x)if(*x >= *d)++(*w);//lava cast od testovaneho prvku
				for(++x; x != top; ++x)if(*x <= *d)++(*w);//prava cast od testovaneho prvku
				
				if(*w > *max_left)max_left = w;
			}
			
			//prava cast od vrcholu:
			wtop = w;
			++d;	//vrchol sa ignoruje
			++w;	//vrchol sa ignoruje
			max_right = w;
			for(auto d_begin = d; d != data.end(); ++d, ++w){
				auto x = d_begin;
				if(*d == *top){
					 *w = numeric_limits<int>::max();
					 max_right = w;
					 continue;
				 }
				
				for( ; x != d; ++x)if(*x <= *d)++(*w);//lava cast od testovaneho prvku
				for(++x; x != data.end(); ++x)if(*x >= *d)++(*w);//prava cast od testovaneho prvku
				
				if(*w > *max_right)max_right = w;
				
			}
			//reduce(data);
		}
		
		size_t reduce(){
			vector<num_t>::const_iterator d;		//aktualny prvok v data
			vector<int>::iterator w;		//aktualna vaha
			
			//lava cast od vrcholu
			while(*max_left > 0){
				d = data.begin();		//aktualny prvok v data
				w = weights.begin();	//aktualna vaha
			
				(*max_left) = (-1);		//oznaci prvok ako zmazany
				--a_size;				//znizi pocet aktivnych prvkov
				max_left = w;			//nastavy maximum ako prvy prvok
				
				for(; d != top; ++d, ++w){
					if(*w < 0)continue;		//preskoci zmazane prvky
					if(*d != *top)*w = 0;	//vynuluje vahu
					else{
						 *w = numeric_limits<int>::max();
						 max_left = w;
						 continue;
					 }	
					
					auto x = data.begin();
					auto y = weights.begin();
					
					//prepocita vahy:
					for( ; x != d; ++x, ++y)if(*x >= *d && *y >= 0 )++(*w);//lava cast od testovaneho prvku
					for(++x, ++y; x != top; ++x, ++y)if(*x <= *d && *y >= 0)++(*w);//prava cast od testovaneho prvku
					
					if(*w > *max_left)max_left = w;
				}
			}
			
			while(*max_right > 0){
				d = (top  + 1);	//vrchol sa ignoruje
				w = (wtop + 1);	//vrchol sa ignoruje
		
				(*max_right) = (-1);
				--a_size;
				max_right = w;
				
				auto x_begin = d;
				auto y_begin = w;
								
				for(; d != data.end(); ++d, ++w){	
					if(*w < 0)continue;
					if(*d != *top)*w = 0;
					else{
						 *w = numeric_limits<int>::max();
						 max_right = w;
						 continue;
					 }	

					auto x = x_begin;
					auto y = y_begin;
					
					for( ; x != d; ++x, ++y)if(*x <= *d && *y >= 0 )++(*w);//lava cast od testovaneho prvku
					for(++x, ++y; x != data.end(); ++x, ++y)if(*x >= *d && *y >= 0 )++(*w);//prava cast od testovaneho prvku
					
					if(*w > *max_right)max_right = w;
					
				}
			}
			return a_size;
		}
		void print()const{
			for(auto a : weights){
				if(a == -1)cout << setw (4)<< "   -  ";
				else if(a == numeric_limits<int>::max())cout << setw (4)<< "   M  ";
				else cout << setw (4) << a << ", ";
			}
			cout << endl;
		}
		void print(const vector<num_t>& data)const{
			auto d = data.begin();
			auto w = weights.begin();
			for(;d!= data.end(); ++d, ++w)
				if(*w == 0)cout << setw (4) << *d << "  ";
		}
		
		Weights(const Weights& x) = delete;
		Weights(Weights&& x) = default;
	
};

int main(){
	vector<num_t>	data = { 1, 8, 2, 2, 2, 3, 4, 8, 8, 6};
	
	auto i = data.begin(); 
	for(auto d = data.begin();d != data.end();++i){

		*i = *d;
		while(d != data.end() && *d == *i)++d;
		
	}
	data.erase(i, data.end());
	
	Tops max(data.begin());
	for(auto d = data.begin() + 1;d != data.end();++d){
		if(max.value() < *d)max.reset(d);
		else if(max.value() == *d)max.add(d);
		
	}
	
	cout << "input : ";
	for(auto x : data)cout << setw (4) << x << "  ";
	
	vector<Weights>	weights;
	for(auto& top : max)
		weights.emplace_back(data, top);
	
	cout << "\n-----------------------------\n";
	for(auto& w : weights){
		
		cout << "      : ";w.print();
		w.reduce();
		cout << "      : ";w.print();
		cout << "output: ";w.print(data);
		
		cout << "\n-----------------------------\n";
	}
		
}

edit: opraveny kod

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 77 hostů

Podobná vlákna

Třídění — založil Frantisek

Třídění struktury — založil BarBorka

Třídění řádků v C — založil lukas011

Trideni jmen — založil Lukáš

Trideni hudby — založil Halbax

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý