Hjelp til algoritmar

[ratata]

Dette er ikkje nødvendigvis c++ relatert,

men kan vera det om dykk vil ^^

 

Har fått ei øving i eit fag som omhandlar algoritmar

og algoritmedesign. Dette er flotte saker, men dessverre

skjønar eg ingenting... Eg lurar då på om nokon kan hjelpe

litt, sette meg på rett spor elns.

 

1)

Lag ein metode som finn minimum og maksimum verdi i ein tabell med tal. Dette skal gjerast på under 3n/2 samanlikningar.

 

Byrjer med denne oppgåva... tar evt fleire etterkvart

[NevroMance]

Siden du for å finne maks/min verdier i en tilfeldig tabell med tall må sjekke alle verdier vil jeg anbefalle deg å se på forskjellige sorteringsalgoritmer som kan hjelpe deg med dette. Har ikke algoritmeboka mi her nå, så får ikke tipset deg om algoritmen, men vil tro det burde sorteres først, da du har sortert det er det kun å ta ut første og siste verdi.

[ratata]

sortering blir feil fordi ein får for mange unødvendige operasjonar (kopiering av element)...

Har forøvrig eit hint, men forstår ikkje heilt kva som er meint; "First construct a group of candidate minimums and a group of candidate maximums."

[Zethyr]

1. Begynn med å finne ut hvilket som er størst og minst blandt to og to elementer utover i lista di.. dette blir n/2 sammenlikninger.

2. Så sjekker du hvilken som er minst av de to minimumene, og hvilken som er størst av de to maksimumene, for hvert "par av par" utover i lista. Gjenta steg 2 til du kun har én sammenlikning å gjøre.

 

Jeg er veldig dårlig til å forklare, men fremgangsmåten er enkel.. den ender opp med 3n/2 - 2 sammenlikninger. Det står litt om den i "Introduction to algorithms" skrevet av Cormen.

 

Har forøvrig eit hint, men forstår ikkje heilt kva som er meint; "First construct a group of candidate minimums and a group of candidate maximums."

Dette er det jeg mente med steg nr 1. Altså du sjekker to og to elementer og finner ut hvilke som er størst og minst der.. legg dem gjerne inn i hver sine nye lister om du vil

[GeirGrusom]

void MinMax(int[] array, int count, int &max, int &min)
{
 max = 0x80000000; // Sett maksimum like laveste mulige tallet
 min = 0xFEFFFFFF; // Sett minimum lik høyeste mulige tallet
 for(int i = 0; i < count; i++)
 {
if(array[i] > max)
  max = array[i]
else if(array[i] < min)
  min = array[i];
 }
}

 

Eller er jeg på viddene nå?

[Zethyr]

Geir: Du har den algoritmen som antakeligvis er raskest i praksis, men du vil risikere 2n sammenlikninger. Regner btw med at count er antallet elementer i arrayet?

[Daunt]

jeg har selv begynt å sett litt på det der med spillprogrammering, og da kom algoritmer inn i bildet.

Koden bruker jeg til mer high score relaterte ting...

 

Uansett, her har du koden jeg bruker ihvertfall:

 

#include <iostream>
#include <sstream>
#include <conio.h>
using namespace std;

void Pause()
{
 cout<<"Press any key to continue...";
 getch();
}
class Set
{
  private:
  protected:
  public:
	int Value[50];
	int ValueC;

  Set()
  {
	for(int i = 0; i<50;i++)
	  Value[i] = -1;


	ValueC = 0;
  }

  void Push(int Number)
  {
	//add new item
	ValueC++;
	Value[ValueC] = Number;


	//goto to top
	if(ValueC <= 1)
	  return;

	bool swap = true;
	int CurrentItem = ValueC;

	while(swap)
	{
	  swap = false;

	  //get parent item
	  int ParentIndex = 1;

	  if(CurrentItem%2 == 0) //if even number
		ParentIndex = CurrentItem/2;
	  else
		ParentIndex = (CurrentItem-1)/2;

	  if(Value[ParentIndex] > Value[CurrentItem])
	  {
		//swap
		int tmpItem = Value[ParentIndex];
		Value[ParentIndex] = Value[CurrentItem];
		Value[CurrentItem] = tmpItem;

		if(ParentIndex == 1) //if top item
		  return;

		CurrentItem = ParentIndex;

		swap = true;

		continue;
	  }
	  return;
	}
  }

  int move()
  {
	if(ValueC <= 0)
	  return 0;

	int Number = Value[1]; //get first item

	Value[1] = Value[ValueC]; //last to front

	ValueC--;

	if(ValueC <= 1) //if no items, or last item
	  return Number;

	//goto bottom
	int CurrentItem = 1;
	bool swap = true;

	while(swap)
	{
	  swap = false;
	  int FC= CurrentItem * 2; //first child
	  int SC= (CurrentItem * 2) + 1; //second child
	  int LowestIndex = FC;

	  //check if second is lowest
	  if(SC<= ValueC)
		if(Value[SC] < Value[FC])
		  LowestIndex = SC;

	  if(Value[CurrentItem] > Value[LowestIndex])
	  {
		//swap
		int tmpNumber = Value[LowestIndex];
		Value[LowestIndex] = Value[CurrentItem];
		Value[CurrentItem] = tmpNumber;

		CurrentItem = LowestIndex;

		//if no children - return
		if((CurrentItem*2) > ValueC)
		  return Number;

		swap = true;
	  }
	  return Number;
	}
  }

};

int main(int argc, char *argv[])
{
Set set;

set.Push(5);
set.Push(7);
set.Push(1);
set.Push(9);
set.Push(19);

cout<<set.move()<<"\n"; // 1
cout<<set.move()<<"\n"; // 5
cout<<set.move()<<"\n"; // 7 
cout<<set.move()<<"\n"; // 9
cout<<set.move()<<"\n"; // 19

Pause();
return 0;

}

 

Denne koden sjekker hvilket tall som er minst, og plasserer den først.

Håper dette gjør det mer forståelig?

[MindProse]

Hva med å bruke Algoritme bibloteket som kommer med C++ (normalt sett).

Det du kan gjøre er å bruke min() og max() i <algorithm> , nå har jeg ikke hatt algoritme-faget ennå så dette er et løsskudd fra min side (vet ikke som den holder 3n/2 kravet) men uansett her har du litt info om min() og max().

 

#include <algorithm>  // må inkluderes for å bruke max() og min()

template<typename T> const T& max(const T& a, const T& b);  // hvis a og b er like stor vil a returneres
template<typename T> const T& min(const T& a, const T& b);  // hvis a og b er like liten vil a returneres

 

 

Her har du et fungerende eksempel med min() og max()

 

#include <iostream>
#include <algorithm>
using namespace std;  // unngå å bruke denne, bruk istedet std::cout istedet for cout

int main(int argc, char *argv[])
{
int tall[] = { 1, 4, 6, 9, 5, 3, 2, 4, 5, 6 };	// sett opp noen tall!

cout << "Vis max: " << max( tall[3], tall[7] ) << endl;	// finn største tall av a og b
cout << "Vis min: " << min( tall[3], tall[7] ) << endl; // finn minste tall av a og b

return 0;
}

 

Håper dette kan være nyttig!

[NevroMance]

Det max og min gjør er jo å returnere max og min av to tall:

 

template <class T> const T& max ( const T& a, const T& b ) {
 return (b<a)?a:b;	 // or: return comp(b,a)?a:b; for the comp version
}

 

dette er koden til max(). Det trådstarter her vil er å finne max og min av en mengde tall, ikke bare to. Det som kunne blitt brukt av c++ biblioteket er max_element. Men dette er heller ingen løsning på oppgaven. Personen skal nemlig lage seg en algoritme som finner det, ikke bruke noe innebygd. Hvordan max_element fungerer vites heller ikke, og derfor vanskelig å vite om algoritmen bruker mindre enn 3n/2 sammenlikninger, som var ett krav i oppgaven hans.

[Zethyr]

max_element må nødvendigvis bruke mer enn n sammenlikninger, og det samme må min_element. Hvis man da blindt kombinerer de to vil man bruke minst 2n sammenlikninger, og man har brutt kravet om 3n/2.