-         

Seite 1 von 3 123 LetzteLetzte
Ergebnis 1 bis 10 von 25

Thema: Ein Zahlenproblem

  1. #1
    Erfahrener Benutzer Fleißiges Mitglied Avatar von iBot
    Registriert seit
    12.05.2008
    Ort
    ca. 20km von Nürnberg
    Beiträge
    160

    Ein Zahlenproblem

    Anzeige

    Hallo Leute,
    eigentlich hat das Problem rein gar nichts mit Robotik zu tun, außer vlt dass es um Automatisierung geht.
    Aber jetzt ohne langes Reden gleich zum Problem :

    Ich habe 10 Zahlen (0-9) und ich möchte nun alle Kombinationsmöglichkeiten, wobei jede Zahl nur ein mal pro Kombination vorkommt (z. B. 1345267098 ) mittels eines Algorithmus ermitteln. (Später soll das dann mal in einem Programm für einen µC enden.)

    Laut Rechnung wären das 3628800 Möglichkeiten (k=n! bzw. k=1*2*3*4*5*6*7*8*9*10).

    Eine Idee wäre die Zahlen immer um einen Platz zu verschieben, also:
    Code:
    'ausgegangen von der Zahl abcdefghij
    
    a=b
    b=c
    c=d
    d=e
    e=f
    f=g
    g=h
    h=i
    i=j
    j=a
    
    z=z+1                    'bis z irgendwann 10 ist
    Das würde schon mal die Möglichkeiten deutlich verringern (wenn ich mich nicht irre wäre es dann nur noch 1/10 )
    Aber wie komm ich zu den restlichen 362880 Möglichkeiten ?

    Falls ich irgendwo einen Denkfehler hineingebracht habe, bitte bescheid geben.
    Geändert von iBot (29.07.2011 um 01:50 Uhr)


  2. #2
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    23.07.2009
    Alter
    23
    Beiträge
    133
    Ohne jetzt länger drüber nachgedacht zu haben (ist ja schon spät) in irgendeiner Java-ähnlichen Fantasiesprache:
    Code:
    void schreibeAlleKombinationen(List<Ziffer> kombinationBisher, List<Ziffer> moeglicheZiffern){
    Iterator<Ziffer> i = moeglicheZiffern.getIterator();
    boolean foundSomething = false;
    while(i.hasNext()){
    Ziffer next = i.next();
    if(! kombinationBisher.contains(next)){
    schreibeAlleKombinationen(kombinationBisher.append(next),moeglicheZiffern);
    foundSomething = true;
    }
    }
    if(! foundSomething){
    System.out.println(kombinationBisher.toString());
    }
    }

  3. #3
    Super-Moderator Lebende Robotik Legende Avatar von Manf
    Registriert seit
    30.01.2004
    Ort
    München
    Alter
    64
    Beiträge
    12.367
    Die Positionen nacheinander betrachten:
    An der ersten Position steht nacheinander jede der Ziffern a-j.
    Für jeden der Fälle steht an der zweiten Position jede der Ziffern a-j mit Ausnahme der schon für die Position 1 ausgewählten Ziffer.
    Für jeden der Fälle steht an der dritten Position jede der Ziffern a-j mit Ausnahme der schon für die Position 1 und 2 ausgewählten Ziffern.
    ...

  4. #4
    Moderator Robotik Visionär Avatar von radbruch
    Registriert seit
    27.12.2006
    Ort
    Stuttgart
    Alter
    54
    Beiträge
    5.781
    Blog-Einträge
    8
    Hallo

    Mein erster Gedanke:

    1:
    0123456789

    3628800:
    9876543210

    Ich vermute, man muss nur die Hälfte der Kombinationen errechnen, denn das Ergebniss sollte nach der Mitte gespiegelt sein.

    Gruß

    mic

    Atmel’s products are not intended, authorized, or warranted for use
    as components in applications intended to support or sustain life!

  5. #5
    Super-Moderator Robotik Visionär Avatar von PicNick
    Registriert seit
    23.11.2004
    Ort
    Wien
    Beiträge
    6.836
    Ich würde den Hinweis von Manf in eine Formel fassen, das geht sicher am schnellsten
    (10)*(10-1)*(10-2).........
    mfg robert
    Wer glaubt zu wissen, muß wissen, er glaubt.

  6. #6
    Erfahrener Benutzer Fleißiges Mitglied Avatar von iBot
    Registriert seit
    12.05.2008
    Ort
    ca. 20km von Nürnberg
    Beiträge
    160
    Danke für die vielen Antworten so früh

    @justin:
    Ich kann leider kein Java, aber hab ich das richtig verstanden? Du meinst es gäbe einen Befehl mit dem man das direkt machen kann?

    @Manf:
    ich versteh den Gedanken jetzt nicht 100%ig, kannst du das vlt in eine kleine Basic-Schleife verpacken?

    @radbruch:
    Ah ja, stimmt, das würde die erforderlichen Möglichkeiten noch einmal halbieren…
    Sprich: Es wären nur noch 181440 möglichkeiten


  7. #7
    Super-Moderator Lebende Robotik Legende Avatar von Manf
    Registriert seit
    30.01.2004
    Ort
    München
    Alter
    64
    Beiträge
    12.367
    Man kann auch von der anderen Seite kommen und das System in der Anzahl der Stellen aufstocken. Für nur eine Ziffer heißt die Liste der Zahlen :1.

    Eine weitere Ziffer ergänzt man indem man sie für jede bisherige Kombination dahinter, in jeden Zwischenraum und davor stellt, also 12; 21.

    Dann ergänzt man die 12 mit 3 zu 123; 132; 312; und man ergänzt die 21 mit 3 zu 213; 231; 321.

    Damit ergibt sich für die n-te Ergänzung einer Ziffer eine Vervielfachung der Kombinationen um n. Damit sind es n! Kombinationen.

    Ich bin mal gespannt, welche Lösung der vorgesehenen Auflösung in diesem Quiz entspricht.

  8. #8
    Moderator Robotik Visionär Avatar von radbruch
    Registriert seit
    27.12.2006
    Ort
    Stuttgart
    Alter
    54
    Beiträge
    5.781
    Blog-Einträge
    8
    Ein Ansatz in Bascom mit 4 Ziffern aus "0" -"9" ergeben 5040 Kombinationen:
    Code:
    ' Zahlenproblem                                                                 29.7.2011 mic
    
    ' http://www.roboternetz.de/community/showthread.php?54210-Ein-Zahlenproblem
    
    $regfile = "m8def.dat"                                      ' asuro mit Mega8
    $crystal = 8000000                                          ' taktet mit 8MHz
    $baud = 2400                                                ' IR-Baudrate
    
    
    Dim Muster(10) As Byte
    Dim N(10) As Byte , M As Byte
    Dim Gefunden As Byte,
    Dim Nr As Long
    
    Print "{027}[1;1H";                                         ' Home
    Print "{027}[2J";                                           ' clear terminal screen
    Print "{027}[1m";                                           ' bold on
    Print "Zahlenproblem                                  29.7.2011 mic"
    Print "{027}[0m";                                           ' Attribute off
    Print
    
    Nr = 1
    For N(1) = 0 To 9                                           ' erste Ziffer festlegen
        Muster(1) = N(1)
    
        'If N(1) = 1 Then N(1) = 8                               ' Abkürzung!
    
        For N(2) = 0 To 9
    
          If Muster(1) <> N(2) Then                             ' wenn zweite Ziffer ungleich
             Muster(2) = N(2)                                   ' zweite Ziffer festlegen
    
             For N(3) = 0 To 9                                  ' dritte Ziffer mit den anderen Ziffern vergleichen
                 Gefunden = 0                                   ' ab hier könnte man das auch rekrusiv lösen
                 For M = 1 To 2                                 ' aber so scheint es mir übersichtlicher
                     If Muster(m) = N(3) Then Gefunden = 1
                 Next M
                 If Gefunden = 0 Then
                    Muster(3) = N(3)
    
                    For N(4) = 0 To 9                           ' n. Ziffer
                      Gefunden = 0
                      For M = 1 To 3                            ' Stellen 1 bis n-1 überprüfen
                          If Muster(m) = N(4) Then Gefunden = 1
                      Next M
                      If Gefunden = 0 Then                      ' wenn schon vorhanden, Ziffer überspringen
                         Muster(4) = N(4)                       ' letzte Ziffer komplett
    
                         Print Nr ; " - " ; Muster(1) ; Muster(2) ; Muster(3) ; Muster(4)
                         Incr Nr
    
                      End If
                    Next N(4)
                 End If
             Next N(3)
          End If
        Next N(2)
    Next N(1)
    
    Decr Nr
    Print
    Print "Erzeugte Kombinationen: " ;
    Print Nr
    
    Do
    Loop
    End                                                         'end program
    [Edit]
    Weil ich ja schon fast am Ziel war habe ich mein Programm auf 10 Ziffern aufgebohrt:
    Code:
    ' Zahlenproblem                                                                 29.7.2011 mic
    
    ' http://www.roboternetz.de/community/showthread.php?54210-Ein-Zahlenproblem
    
    $regfile = "m8def.dat"                                      ' asuro mit Mega8
    $crystal = 8000000                                          ' taktet mit 8MHz
    $baud = 2400                                                ' IR-Baudrate
    
    
    Config Pind.5 = Output                                      'speaker
    
    Dim Muster(10) As Byte
    Dim N(10) As Byte , M As Byte
    Dim Gefunden As Byte,
    Dim Nr As Long
    
    Print "{027}[1;1H";                                         ' Home
    Print "{027}[2J";                                           ' clear terminal screen
    Print "{027}[1m";                                           ' bold on
    Print "Zahlenproblem                                  29.7.2011 mic"
    Print "{027}[0m";                                           ' Attribute off
    Print
    
    For Nr = 0 To 4000
       Toggle Portd.5
       Waitus 250
    Next Nr
    
    Nr = 1
    For N(1) = 0 To 9                                           ' erste Ziffer festlegen
        Print "1: " ; N(1)
        Muster(1) = N(1)
    
        'If N(1) = 1 Then N(1) = 8                               ' Abkürzung!
    
        For N(2) = 0 To 9
          Print "2: " ; N(2)
    
          If Muster(1) <> N(2) Then                             ' wenn zweite Ziffer ungleich
             Muster(2) = N(2)                                   ' zweite Ziffer festlegen
    
             For N(3) = 0 To 9                                  ' dritte Ziffer mit den anderen Ziffern vergleichen
                Print "3: " ; N(3)
                Gefunden = 0                                    ' ab hier könnte man das auch rekrusiv lösen
                For M = 1 To 2                                  ' aber so scheint es mir übersichtlicher
                   If Muster(m) = N(3) Then Gefunden = 1
                Next M
                If Gefunden = 0 Then
                    Muster(3) = N(3)
    
                    For N(4) = 0 To 9                           ' n. Ziffer
                      Gefunden = 0
                      For M = 1 To 3                            ' Stellen 1 bis n-1 überprüfen
                          If Muster(m) = N(4) Then Gefunden = 1
                      Next M
                      If Gefunden = 0 Then                      ' wenn schon vorhanden, Ziffer überspringen
                         Muster(4) = N(4)                       ' letzte Ziffer komplett
    
                    For N(5) = 0 To 9
                      Gefunden = 0
                      For M = 1 To 4
                          If Muster(m) = N(5) Then Gefunden = 1
                      Next M
                      If Gefunden = 0 Then
                         Muster(5) = N(5)
    
                    For N(6) = 0 To 9
                      Gefunden = 0
                      For M = 1 To 5
                          If Muster(m) = N(6) Then Gefunden = 1
                      Next M
                      If Gefunden = 0 Then
                         Muster(6) = N(6)
    
                    For N(7) = 0 To 9
                      Gefunden = 0
                      For M = 1 To 6
                          If Muster(m) = N(7) Then Gefunden = 1
                      Next M
                      If Gefunden = 0 Then
                         Muster(7) = N(7)
    
                    For N(8) = 0 To 9
                      Gefunden = 0
                      For M = 1 To 7
                          If Muster(m) = N(8) Then Gefunden = 1
                      Next M
                      If Gefunden = 0 Then
                         Muster(8) = N(8)
    
                    For N(9) = 0 To 9
                      Gefunden = 0
                      For M = 1 To 8
                          If Muster(m) = N(9) Then Gefunden = 1
                      Next M
                      If Gefunden = 0 Then
                         Muster(9) = N(9)
    
                    For N(10) = 0 To 9
                      Gefunden = 0
                      For M = 1 To 9
                          If Muster(m) = N(10) Then Gefunden = 1
                      Next M
                      If Gefunden = 0 Then
                         Muster(10) = N(10)
    
                         'Print Nr ; " - " ; Muster(1) ; Muster(2) ; Muster(3) ; Muster(4) ; Muster(5) ;
                         'Print Muster(6) ; Muster(7) ; Muster(8) ; Muster(9) ; Muster(10)
                         Incr Nr
    
                      End If
                    Next N(10)
                      End If
                    Next N(9)
                      End If
                    Next N(8)
                      End If
                    Next N(7)
                      End If
                    Next N(6)
                      End If
                    Next N(5)
                      End If
                    Next N(4)
                 End If
             Next N(3)
          End If
        Next N(2)
        Print "Zwischenstand: " ; Nr ; " Kombinationen erzeugt"
    Next N(1)
    
    Decr Nr
    
    Do
    Print
    Print "Erzeugte Kombinationen: " ;
    Print Nr
    Toggle Portd.5
    Loop
    End                                                         'end program
    Zum Debuggen lasse ich die Schleifenwerte der ersten drei Stellen ausgeben, hier der Start:
    Code:
    1: 0 ' erste Ziffer ist "0"
    2: 0 ' zweite Ziffer, "0" ist belegt,
    2: 1 ' deshalb zweite Ziffer ist "1"
    3: 0 ' dritte Ziffer, "0" ist belegt,
    3: 1 ' "1" ebenfalls, 
    3: 2 ' also ist "2" die dritte Ziffer 
    2: 3 ' ab hier wirds dann unübersichtlich, 
    3: 4 ' weil die inneren Schleifen keine Ausgabe
    3: 5 ' machen und man deshalb die Sprünge
    3: 6 ' nicht nachvollziehen kann
    2: 7
    
    ... (4 Minuten später!)...
    
    2: 9 ' zweite Stelle bei "9"
    3: 0
    3: 1
    3: 2
    3: 3
    3: 4
    3: 5
    3: 6
    3: 7
    3: 8
    3: 9 ' dritte Stelle bei "9"
    Zwischenstand: 362881 Kombinationen erzeugt
    1: 1 ' Übertrag zur ersten Stelle! Erste Ziffer ist jetzt "1" 
    2: 0
    3: 0
    3: 1
    3: 2
    3: 3
    Da der Zähler voreilt sind es in Wirklichkeit "nur" 362880 Kombinationen die mit "0" beginnen. Erfreulicherweise stimmt hier die Theorie mit der Praxis überein:
    9*8*7*6*5*4*3*2=362880 :)

    Wenn man die Zeit für die Ausgabe vernachlässigt ist mein 8MHz nach etwas mehr als 40 Minuten fertig mit allen Kombinationen...
    Geändert von radbruch (29.07.2011 um 15:29 Uhr)

    Atmel’s products are not intended, authorized, or warranted for use
    as components in applications intended to support or sustain life!

  9. #9
    Erfahrener Benutzer Lebende Robotik Legende Avatar von PICture
    Registriert seit
    10.10.2005
    Ort
    Freyung bei Passau in Bayern
    Alter
    66
    Beiträge
    10.970
    Hallo!

    Mir ist dazu nur eingefallen (falls ich mich nicht irre), dass zum Abspeichern von allen Kombinationen werden in BCD Kodierung 5 * 3628800 = 18 144 000 Bytes, also über 18 MB benötigt.
    MfG (Mit feinem Grübeln) Wir unterstützen dich bei deinen Projekten, aber wir entwickeln sie nicht für dich. (radbruch) "Irgendwas" geht "irgendwie" immer...(Rabenauge) Machs - und berichte.(oberallgeier) Man weißt wie, aber nie warum. Gut zu wissen, was man nicht weiß. Zuerst messen, danach fragen. Was heute geht, wurde gestern gebastelt. http://www.youtube.com/watch?v=qOAnVO3y2u8 Danke!

  10. #10
    Moderator Robotik Visionär Avatar von radbruch
    Registriert seit
    27.12.2006
    Ort
    Stuttgart
    Alter
    54
    Beiträge
    5.781
    Blog-Einträge
    8
    Rekursiv in C (für den asuro):
    Code:
    // Zahlenproblem rekursiv in C :)                                       29.7.2011 mic
    
    #include "asuro-probot.h"
    #include "asuro-probot.c"
    
    #define ziffern 4
    
    uint8_t muster[ziffern];
    uint8_t x[10], gefunden;
    uint32_t nr=0;
    
    void suchen(uint8_t z)
    {
    	uint8_t y;
    
    	for(x[z]=0; x[z]<10; x[z]++)
    	{
    		gefunden=0;
    		for(y=0; y<z; y++)
    		   if(muster[y]==x[z]) gefunden=1;
    		if(!gefunden)
    		{
    			muster[z]=x[z];
    			if(z < (ziffern-1))
    			{
    				suchen(z+1); // Rekursion!
    			}
    			else
    			{
    				if(0) // 1 bedeutet: Ausgabe der Ziffernkombinationen
    				{
    					PrintInt(nr);
    					SerWrite(": ", 2);
    					for(y=0; y<ziffern; y++)
    					{
    						while(!(UCSRA & 0x20));
    						UDR = muster[y]+'0';
    					}
    					SerWrite("\r\n", 2);
    				}
    				nr++;
    			}
    		}
    	}
    }
    
    int main(void)
    {
    	Init();
    	PORTC |= 3; // Odo-PullUps simulieren für PollSwitch()
    	StatusLED(RED);
    
    	for(x[0]=0; x[0]<10; x[0]++)
    	{
       	muster[0]=x[0];
    		suchen(1);
    	}
    	while(1)
    	{
       	PrintInt(nr);
    		SerWrite("\r\n", 2);
    		Beep(50);
    	}
    return(0);
    }
    Probelauf mit 4 Ziffern ergibt wieder 5040. Speichern will ich das Ergebniss natürlich nicht. Fragt sich nun, wie man die Symmetrien der Ziffernfolgen einbauen könnte.

    Gruß

    mic

    [Edit]
    Nach der Optimierung:
    Code:
    // Zahlenproblem rekursiv in C :)                                       31.7.2011 mic
    
    #include <avr/io.h>
    #include <stdlib.h>
    
    #define ziffern 3
    
    uint8_t x[10], y, gefunden;
    uint32_t nr=1;
    
    void SerWrite(char *data, uint8_t length); // char???
    void PrintInt32(uint32_t wert);
    void ausgabe(void);
    
    void suchen(uint8_t z)
    {
    	for(x[z]=0; x[z]<10; x[z]++)
    	{
    		gefunden=0;
    		for(y=0; y<z; y++) if(x[y]==x[z]) gefunden=1;
    		if(!gefunden)
    		{
    			if(z < (ziffern-1)) suchen(z+1); // Rekursion!
    			else
    			{
    				ausgabe(); // Ausgabe der Ziffernkombinationen in x[0] bis x[ziffern-1]
    				nr++;
    			}
    		}
    	}
    }
    
    int main(void)
    {
    	SerWrite("\033[1;1H", 6); // home  VT100-Emulation
    	SerWrite("\033[2J", 4); //clear terminal screen
    
    	for(x[0]=0; x[0]<5; x[0]++) suchen(1);
    
    	nr--;
    	DDRD |= (1<<PD5); // Led
    	while(1)
    	{
       	PrintInt32(nr);
    		SerWrite("\r\n", 2);
    		if(PIND & (1<<PD5)) PORTD &= ~(1<<PD5); else PORTD |= (1<<PD5); // blinken
    	}
    return(0);
    }
    
    void SerWrite(char *data, uint8_t length) // aus der asuro-Lib
    {
    	unsigned char i = 0;
    	UCSRB = 0x08; // enable transmitter
    	while (length > 0) {
    		if (UCSRA & 0x20) { // wait for empty transmit buffer
    			UDR = data[i++];
    			length --;
    		}
    	}
    	while (!(UCSRA & 0x40));
    	//for (i = 0; i < 0xFE; i++)
    		//for(length = 0; length < 0xFE; length++);
    }
    
    void PrintInt32(uint32_t wert) // aus der asuro-Lib
    {  char text[7]="       ";
    	itoa(wert,text,10);
    	SerWrite(text,7);
    }
    
    void ausgabe(void)
    {
    	for(y=0; y<ziffern; y++)
    	{
    		while(!(UCSRA & 0x20));
    		UDR = x[y]+'0';
    	}
     	SerWrite("  ",2);
    	for(y=0; y<ziffern; y++)
    	{
    		while(!(UCSRA & 0x20));
    		UDR = 9-x[y]+'0';
    	}
     	SerWrite("  ",2);
    	PrintInt32(nr);
     	SerWrite("\r\n",2);
    }
    Ohne Ausgabe schafft mein asuro die 10-stelligen Kombinationen in knapp 22 Minuten :)
    Angehängte Dateien Angehängte Dateien
    Geändert von radbruch (31.07.2011 um 12:11 Uhr) Grund: optimierte Version angefügt

    Atmel’s products are not intended, authorized, or warranted for use
    as components in applications intended to support or sustain life!

Seite 1 von 3 123 LetzteLetzte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •