3 leilākais skaitlis

[Ownmen]

Sveiki,

galīgi nestrādā galva un nevaru izdomāt kā nesakārtojot masīvu atrast 3. lielāko skaitli.

 

piemērs:

doti skaitļi 0, 3, 9, 2, 12, 8, 1

nepieciešams atgriezt ciparu 8.

doma ir iekļaut ciklu ciklā un salīdzināt katru skaitli ar katru, bet īsti neprotu to realizēt.

Ceru uz palīdzību :)

 

for(int i=0; i<n; i++)
   	{
       	for(int j=0; j<n; j++)
       	if (masivs[i] > masivs[j]) max=masivs[i];
   	}
   	cout << max << endl;

 

šis atgriež tikai lielāko vērtību...

Edited November 7, 2011 by Ownmen

[zintis8789]

Tikai viena problēma: Šis ir PHP forums.

[daGrevis]

Tāpēc grūti palīdzēt biedram, ka C++?

[zintis8789]

Pašlaik mēģinu kko samontēt c++, bet šī sadaļa ir PHP -> iesācējiem.

[codez]

Kādas problēmas, izmanto priority queue

#include <iostream>
#include <queue>
using namespace std;
int main()
{
int a[]={1,5,8,2,4,6,3,7};
priority_queue<int> q(a,a+8);
q.pop();
q.pop();
cout << q.top(); // 6
}

[Ownmen]

atvainojos, par c++, bet valodas jau ir ļoti līdzīgas

[codez]

var arī set:

#include <iostream>
#include <set>

using namespace std;
int main()
{
int a[]={1,5,8,2,4,6,3,7};
set<int> s(a,a+8);
cout << *++++s.rbegin(); //6
}

[daGrevis]

var arī kaut kā super-forši ar rekursiju, bet es nerakstīšu kā...

[Mr.Key]

Codez varianti ir pilnīgi nederīgi, jo uzdevuma nosacījumos ir teikts, ka nedrīkst veikt skaitļu virknes sakārtošanu. Protams, tas viņš to domāja kā joku.

 

Kas attiecas uz algoritmu, protams, tu iesi pāri visiem skaitļiem un veiksi salīdzināšanu. Iztēlojies, ka tu esi fizkultūras skolotājs un tev starp rajona sporta spēļu dalībniekiem jāatrod 3 garākais skolēns. Visi skolēni nāk rindā pa vienam cauri vārtiņiem... Primitīvā variantā pieturi 3 garākos skolēnus un salīdzini ar katru ienākošo - ja tas ir garāks par vienu no tiem, tas nomaina līdz šim atrasto īsāko, kad visi izgājuši cauri, 3. garākais ir attiecīgi īsākais no tiem 3. Sarežģītāks gadījums ir tad, ja jāatrod x lielākais/mazākais tālu no robežvērtības un/vai negribas "turēt pie vārtiņiem" visus x "skolēnus". :) (pieņemsim, starp miljards skaitļiem jāatrod 13467878. lielākais)

 

p.s. l-IE-lākais, nevis l-EI-lākais

Edited November 8, 2011 by Mr.Key

[codez]

Nu jā, ar vārdu "sakārtot", parasti saprot sakārtot augošā vai dilstošā secībā, kamēr priority_queue sakārto balsanētā binārajā kokā, bet set-s sakārto bst.

Ja tomēr to grib saukt par sakārtošanu, tad arī algoritms, kur atdala 3 elementus no pārējiem ir zināma elementu sakārtošana 2 daļās.

 

Bet nu labi, ja bez kārtošanas, tad divreiz atrodam max elementu un izdzēšam un trešoreiz izvadam max elementu:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int m[]={1,5,8,2,4,6,3,7};
vector<int> v(m,m+8);
v.erase(max_element(v.begin(),v.end()));
v.erase(max_element(v.begin(),v.end()));
cout << *max_element(v.begin(),v.end());
}

[Mr.Key]

codez, tagad iedomājies, ka jāatrod trešais lielākais baits, kas izmantots failā. Tas var būt gan 1, gan 44, gan 253, whatever. Fails ir 1 TB.

 

Nu? Vektors, sets, queue?

Edited November 8, 2011 by Mr.Key

[daGrevis]

Man lūdzu atrast 264264264 baitu. :D

[briedis]

Hmm, mans risinājums būtu šāds:

 

http://codepad.viper-7.com/TduOJt

 

tas pats queue, tikai limitēts līdz X elementiem, kur atrodu vietu, kur iespraust atrasto elementu un tad nobīda visus mazākos. Iespējams, ka to nobīdīšanu varētu kaut kā low-level-īgāk atrisināt un būtu efektīvāka..

[codez]

codez, tagad iedomājies, ka jāatrod trešais lielākais baits, kas izmantots failā. Tas var būt gan 1, gan 44, gan 253, whatever. Fails ir 1 TB.

 

Nu? Vektors, sets, queue?

ejam cauri, skaitam katras vērtības skaitu, cik reizes 255, cik 254, kopā 256 baitu masīvs - tipa mathsort.

 

#include <iostream>
using namespace std;
int c[256];
int main()
{
int k=3;
int m[]={1,5,8,2,4,6,3,7};
for(int i=0;i<=8;i++){
   	c[m[i]]++;
}
for(int i=255; i>=0; i--){
   	if(c[i]<k) {
       	k-=c[i];
   	} else {
       	cout << i;
       	break;
   	}
}
}

 

 

Vēl viens variants ir uztaisit min priority queue un glabāt tur visu laiku trīs elementus, tad no masīva likt vienu klāt un noņemt no tiem minimālo, tādā veidā priority queue visu laiku saturē līdz tam esošos 3 lielākos elementus. Pēc cikla vienkārši atkal paņemam mazāko, kurš būs 3. mazākais. Šis algoritms principā var apstrādāt ļoti lielus datu daudzumus un strādā arī ļoti ātri un dažās vietās nomainot 3 pret K var atrast arī n-to lielāko elementu, pie tam laikā O(N log2(K));

 

#include <iostream>
#include <queue>
using namespace std;
int c[256];
int main()
{
int m[]={1,5,8,2,4,6,3,7};
priority_queue<int,vector<int>, greater<int> > q(m,m+3);
for(int i=3;i<8;i++){
   	q.push(m[i]);
   	q.pop();
}
cout << q.top();
}

 

P.S. Bet nu jūs jau sapratāt, ka mans mērķis ir piedāvāt risinājumu, kuru ar lielu varbūtību nesapratīs pats pasniedzējs.

Edited November 8, 2011 by codez

[Gints Plivna]

Man lūdzu atrast 264264264 baitu. :D

Es parasti šāda veida problēmas risinu ielādējot datus DB un tālāk jau kā parasti SQLs rullē :)

 

Tiesa gan cik sapratu, šeit tas laikam neietu cauri. No otras puses Oracle ir rakstīta iekš C, tā kā zināma līdzība ar sākotnējo uzdevuma uzstādījumu ir :)

 

Gints Plivna

http://datubazes.wordpress.com