Jump to content
php.lv forumi
Ownmen

3 leilākais skaitlis

Recommended Posts

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 by Ownmen

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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
}

Share this post


Link to post
Share on other sites

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
}

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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 by Mr.Key

Share this post


Link to post
Share on other sites

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());
}

Share this post


Link to post
Share on other sites

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 by Mr.Key

Share this post


Link to post
Share on other sites

Man lūdzu atrast 264264264 baitu. :D

Share this post


Link to post
Share on other sites

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..

Share this post


Link to post
Share on other sites

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 by codez

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

×
×
  • Create New...