Springen naar inhoud

Algoritme?


  • Log in om te kunnen reageren

#1


  • Gast

Geplaatst op 27 juni 2005 - 17:39

Hallo mensen,

Ik zocht naar een algorithme die van bijvoorbeeld een 5 cijferig getal, alle mogelijkheden weet te vinden die je met de 5 cijfers van dit getal kan maken, waar in elk getal geen van de cijfers 2 keer mag voor komen.

Voorbeeld voor 3 cijferig getal:

123
132
213
231
312
321

Ik wil een algorithme die deze lijstjes ook voor meercijferige getallen kan maken.

Wie kan mij helpen?

Alvast bedankt

Groete Jeroen

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Pollop XXIII

    Pollop XXIII


  • >100 berichten
  • 145 berichten
  • Ervaren gebruiker

Geplaatst op 27 juni 2005 - 19:30

Zoiets staat bekend als 'faculteit'.
Het word genoteerd als vb: 3! (spreek uit: 3 faculteit)
Het geeft het aantal mogelijkheden hoe je de cijfers 1,2 en 3 kan rangschikken.

Verklaring:
Voor het getal dat op de eerste plaats komt zijn er 3 mogelijkheden, nl 1,2 of 3.
Voor het 2e getal zijn er nog maar 2 mogelijkheden, want je hebt immers al een cijfer gebruikt voor het eerste getal, er schieten er nog 2 over.
Voor het laatste getal blijft nog maar 1 getal over, dat getal dat nog niet eerder gekozen was.

Geeft ons: 3.2.1 = 3!

de definitie in symbolen is:
n!= n.(n-1).(n-2). ... .2.1

vb: 8! = 8.7.6.5.4.3.2.1

Ben je daarmee geholpen?
Jan Vonk

#3

TD

    TD


  • >5k berichten
  • 24052 berichten
  • VIP

Geplaatst op 27 juni 2005 - 19:45

Ik wil hierbij alleen even opmerken dat je met die faculteiten weliswaar het aantal mogelijkheden kan berekenen, maar daarmee genereer je ze nog niet. De vragensteller is op zoek naar een algoritme om alle mogelijkheden systematisch af te gaan (en dus te verkrijgen).

#4

Antoon

    Antoon


  • >1k berichten
  • 1750 berichten
  • Ervaren gebruiker

Geplaatst op 27 juni 2005 - 20:43

De vragensteller is op zoek naar een algoritme om alle mogelijkheden systematisch af te gaan  

een boom diagram, maar dat is altijd veel werk.

#5


  • Gast

Geplaatst op 27 juni 2005 - 22:33

Juist TD, het aantal mogelijkheden berekenen was het probleem nog niet.
Maar ik was niet van plan om voor elk cijfer een hele lijst uit te typen...aangezien je bij 5 cijfers dan al 120 mogelijkheden hebt.

Ik heb wel bepaalde verbanden gevonden, maar deze verbanden houden op bij hogere getallen.

Maarja, een algorithme om deze lijstjes te maken heb ik nog niet gevonden.

Toch allemaal bedankt voor de hulp!

Alle ideeen zijn welkom!

Groeten Jeroen

#6

Leuke gast

    Leuke gast


  • >1k berichten
  • 1166 berichten
  • Ervaren gebruiker

Geplaatst op 27 juni 2005 - 23:18

met backtracking (recursief) programmeren gaat dat makkelijk,
U kunt het ook iteratief doen, maar dan zal U zelf een que of stack
moeten programmeren. Deze versie begint vanaf waarde 0,
sorry als het niet helemaal klopt.


#define MAX_DIGIT 100



void CalcLinesAndPrint(int InMaxDigit, int InStartPos, int InDigitArray[MAX_DIGIT] )

{

	int DigitCnt = InStartPos;

   while (DigitCnt < InMaxDigit )

   {

      InDigitArray[DigitCnt] = DigitCnt;



      if (DigitCnt == (InMaxDigit-1) ) // checken op de gewenste breedte van de lijst

      {

     	 // de InDigitArray afdrukken of opslaan

     // Print( InDigitArray)  (InDigitArray afdrukken)

      }





      // even controleren of dit getal al een keer is uitgegeven

      bool found = false;

      int Cnt = 0;

    while ( (Cnt < InStartPos) && (!Found) )

      {

     	 Found = (InDigitArray[Cnt] == DigitCnt)

         Cnr++;

      } // while





      if (!Found)

      {

     	 CalcLines(InMaxDigit, InStartPos+1,  InDigitArray )

      } // if



      DigitCnt++;

   } // while

}





void main (blah blah)

{

   int DigitArray[MAX_DIGIT];



	CalcLinesAndPrint(3, 0, 0, DigitArray);

}

#7


  • Gast

Geplaatst op 28 juni 2005 - 15:11

Leuke gast, ik weet niet helemaal wat je bedoelt. En de taal waarvan je mij een stuk code geeft komt me ook niet helemaal bekend voor...C++..?

Ik heb de formule nodig voor een programma in Visual basic 6.0

Weet je toevallig ook het stukje gegeven code in VB...?!

Of zou je de termen en/of de code die je gebruikt even uit kunnen leggen.

Allemaal heel erg bedankt voor jullie hulp..!

Groeten Jeroen

#8


  • Gast

Geplaatst op 30 juni 2005 - 15:29

Hoi Zarkill,

Laat Sn alle permutaties van de getallen {1,2,3,...,n}. Je kunt alle elementen van Sn neerschrijven met een recursief 'weefproces'. In dit 'weefproces' zijn bevangen de door jouw opgevallen 'patronen'.

Het schrijven van code is aan jou. Ik geef alleen het principe:
- Je begint bij 1;
- Het volgende getal is 2, je schrijft 2 maal '1' onder elkaar;
- Je 'weeft' het volgende getal 2 erdoor heen door het links en rechts van 1 te schrijven, zodat je krijgt: '12' en '21';
- Het volgende getal is 3, je schrijft 3 maal elk van de vorige permutaties onder elkaar, dus 3x '12' en 3x '21';
- Je 'weeft' het volgende getal 3 erdoor heen door het rechts, ertussenin, links, links, ertussenin en rechts te schrijven, zodat je krijgt: '123', '132', '312', '321', '231' en '213' (dus 3! = 6 verschillende);
- Het volgende getal is 4, je schrijft 4 maal elk van de vorige permutaties onder elkaar;
- Je 'weeft' het volgende getal 4 erdoor heen (je krijgt dus 4! = 24 verschillende dingetjes);
- etcetera;
- Op een gegeven moment ben je bij jou n, je hebt dan alle elementen van Sn verkregen.

Eventueel kun je dan (b.v met QSorting) de elementen nog rangschikken op volgorde.

Groeten, Forest

#9

NASE

    NASE


  • >250 berichten
  • 385 berichten
  • Ervaren gebruiker

Geplaatst op 30 juni 2005 - 15:44

en wat met het getal 1552.
De dubbele mogen er niet in, vind ik. En daar zit hem de moeilijkheid. Dat is het punt dat mij weerhoudt om een goed algorithme te schrijven.

P.S. is dat op die manier niet zeer moeilijk om te schrijven.

[edit]
die dubbele er uithalen is op gast zijn manier niet zo moeilijk. Je moet de positie waarop je begint te weven van ieder getal gelijk stellen aan de positite van hetzelfde laatste getal. Je moet dus deze positie opvragen, die van het laatste al bestaande getal. Komt het getal niet voor, dan krijg je normaal -1 terug (bij de talen die ik ken toch). Dan begint hij te weven rechts van het al bestaande en laatste getal en komen er geen dubbelvoor.

dus
152. Beginnen weven vanaf positie 1+1. geeft dan 1552 en 1525.

P.S. het idee is goed, maar mss moet je nog eens een beetje met die posities spelen.

[edit2]
Bij nader inzien is die manier eigelijk veel beter dan wat ik ging voorstellen. Je hebt er geen andere gegevens dragers voor nodig, en de complexiteit is volgens mij dezelfde.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures