-         
Seite 2 von 3 ErsteErste 123 LetzteLetzte
Ergebnis 11 bis 20 von 25

Thema: Ein Zahlenproblem

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

    @radbruch:
    Du bist echt ein Held. Hab das Programm für Bascom mal eben im Simulator laufen lassen und es funktioniert wirklich einwandfrei.
    Sag mal wie hast du das so schnell hinbekommen? Ich hätte dafür sicher noch einige Wochen grübeln müssen…
    Und jetz auch noch in C
    Allerdings hab ich mal noch eine Frage: Warum kommst du nur auf 362880 Möglichkeiten ? Es müssten doch 3628800 sein…
    bzw. was meinst du mit "
    Da der Zähler voreilt…"?

    @PICture:
    Na zum Glück muss es nur Ausgegeben und nicht gespeichert werden .


  2. #12
    Erfahrener Benutzer Lebende Robotik Legende Avatar von PICture
    Registriert seit
    10.10.2005
    Ort
    Freyung bei Passau in Bayern
    Alter
    68
    Beiträge
    11.078
    Ich bin eher an Hexzahlen gewöhnt um alle mögliche Kombinationen zu erstellen, da es am einfachsten geht. Die grösste Zahl wäre 9876543210 d = 24CB016EA h was "nur" 34 Bits braucht und die grössere bis 2FFFFFFFF h könnte man weg lassen. Danach muss man natürlich jede Hexzahl in eine Dezimale wandeln.

    Es müssten natürlich noch dezimale Zahlen, wo sich gleiche Ziffern wiederholen, entfernt werden.
    Geändert von PICture (29.07.2011 um 20:19 Uhr)
    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!

  3. #13
    Moderator Robotik Visionär Avatar von radbruch
    Registriert seit
    27.12.2006
    Ort
    Stuttgart
    Alter
    56
    Beiträge
    5.796
    Blog-Einträge
    8
    Sag mal wie hast du das so schnell hinbekommen?
    Das ist reine Übungssache :) Allerdings war es zufällig auch mein erstes C-Programm mit Rekursion.

    ...Danach muss man natürlich jede Hexzahl in eine Dezimale wandeln.
    Und dann muss mannur noch alle Zahlen mit doppelten Ziffern entfernen...

    Allerdings hab ich mal noch eine Frage: Warum kommst du nur auf 362880 Möglichkeiten ? Es müssten doch 3628800 sein…
    bzw. was meinst du mit "Da der Zähler voreilt…"?
    Die Ausgabe des Zählerstandes erfolgt am Ende der For-Schleife für die erste Ziffer:
    Code:
        Print "Zwischenstand: " ; Nr ; " Kombinationen erzeugt"
    Next N(1)
    
    Decr Nr
    Zu diesem Zeitpunkt sind alle Kombinationen die mit "0" anfangen generiert. Allerdings wurde die Nr-Variable schon für die nächste Runde erhöht, deshalb eilt der Zähler an dieser Stelle immer um 1 vor.

    Ich denke, auch das Symmetrieproblem ist gelöst:
    Code:
    				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("  ", 2);
    					for(y=0; y<ziffern; y++)
    					{
    						while(!(UCSRA & 0x20));
    						UDR = 9-muster[y]+'0';
    					}
    					SerWrite("\r\n", 2);
    				}
    Damit kann man die äußerste Schleife im Hauptprogramm von 0 bis 4 laufen lassen und durch die Spiegelung der Werte wird der Bereich 5 bis 9 generiert.

    Wozu kann man solche Kombinationen eigentlich nutzen?

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

  4. #14
    Erfahrener Benutzer Robotik Einstein Avatar von SprinterSB
    Registriert seit
    09.06.2005
    Ort
    An der Saar
    Beiträge
    2.801
    Falls das Problem noch aktuell ist, hier meine Lösung in C.

    Eingegeben wird die Anzahl der zu permutierenden Zeichen (N)
    und die Nummer der auszugebenden Permutation (n).

    Beispiel mit N = 5, n = 1
    #1: 12345

    Beispiel mit N = 5, n = 120
    #120: 54321

    Beispiel mit N = 3, n = 0
    #1: 123
    #2: 132
    ...
    #6: 321

    Beispiel mit n = 12, n = 100000
    #100000: 12368AB59704

    Code:
    #include <stdio.h>
    #include <string.h>
    
    #define DIGITS "1234567890ABCDEF"
    
    int print_perm (unsigned int N, unsigned int n0)
    {
        char *l, letters[] = DIGITS;
        int j, digit[N];
        unsigned int n = n0;
        
        // n0 in faktorielle Darstellung umwandeln
        
        for (unsigned int i = 1; i <= N; i++)
        {
            digit[i-1] = n % i;
            n /= i;
        }
        
        if (n)
            return 0;
            
        // n0-te Permutation ausdrucken
        
        printf ("#%d: ", n0 + 1);
        
        for (int i = N-1; i >= 0; i--)
        {
            for (j = -1, l = letters - 1; j < digit[i]; j += *++l != ' ');
            printf ("%c", *l);
    
            // Gedruckte Zeichen aus Liste entfernen
            *l = ' ';
        }
        
        printf ("\n");
        
        return 1;
    }
    
    int main ()
    {
        unsigned int n, N;
        
        printf ("\nAnzahl Zeichen: ");
        scanf ("%u", &N);
    
        printf ("\nPermutation Nr. (0 fuer alle): ");
        scanf ("%u", &n);
        
        if (N == 0 || N > strlen (DIGITS))
        {
            printf ("Ungueltige Eingabe: Anzahl Zeichen in 1..%d\n",
                    strlen (DIGITS));
            return 1;
        }
        
        if (n)
            print_perm (N, n-1);
        else
            while (print_perm (N, n++));
        
        return 0;
    }
    Der Code ist einfach gehalten und berechnet die faktorielle Darstellung für jede Permutation neu.
    Für eine effiziente Implementierung falls alle Permutationen gebraucht werden oder nur eine Teilmenge aus einer Obermenge auszuwählen ist, kann man eine Arithmetik auf der faktoriellen Darstellung implementieren.
    Disclaimer: none. Sue me.

  5. #15
    Moderator Robotik Visionär Avatar von radbruch
    Registriert seit
    27.12.2006
    Ort
    Stuttgart
    Alter
    56
    Beiträge
    5.796
    Blog-Einträge
    8
    Ja, das sieht echt clever aus, vor allem die imponierende for-Schleife. Allerdings funktioniert es irgendwie nicht richtig. Da mein asuro die stdio.h nicht richtig anwendet habe ich versucht, das Programm anzupassen:
    Code:
    #include "asuro-probot.h"
    #include "asuro-probot.c"
    //#include <stdio.h>
    //#include <string.h>
    
    #define DIGITS "1234567890ABCDEF"
    
    int print_perm (unsigned int N, unsigned int n0)
    {
        char *l, letters[] = DIGITS;
        int j, digit[N];
        unsigned int n = n0;
        unsigned int i;
        
        // n0 in faktorielle Darstellung umwandeln
    
        for (i = 1; i <= N; i++)
        {
            digit[i-1] = n % i;
            n /= i;
    
    			//while(!(UCSRA & 0x20));
    			//UDR = digit[i-1]+'0';
        }
    		//SerWrite("\r\n\n",3);
    
        if (n)
            return 0;
    
        // n0-te Permutation ausdrucken
    
        //printf ("#%d: ", n0 + 1);
          PrintInt(n0+1);
          SerWrite(": ",2);
    
        for (i = N-1; i >= 0; i--)
        {
            for (j = -1, l = letters - 1; j < digit[i]; j += *++l != ' ');
            //printf ("%c", *l);
    
    			while(!(UCSRA & 0x20)); // Warten bis USART fertig ist
    			//UDR = *l; // Wert an Adresse l senden
    			UDR = *l+'0'; // Wert an Adresse l als Ascii-Zeichen senden
    			//UDR = i+'0'; // i als Ascii-Zeichen senden
    
            // Gedruckte Zeichen aus Liste entfernen
            *l = ' ';
        }
    
        //printf ("\n");
     		SerWrite("\r\n",2); // neue Zeile
    
        return 1;
    }
    
    int main (void)
    {
        unsigned int n=0, N=3;
    
    /*    printf ("\nAnzahl Zeichen: ");
        scanf ("%u", &N);
    
        printf ("\nPermutation Nr. (0 fuer alle): ");
        scanf ("%u", &n);
    
        if (N == 0 || N > strlen (DIGITS))
        {
            printf ("Ungueltige Eingabe: Anzahl Zeichen in 1..%d\n",
                    strlen (DIGITS));
            return 1;
        }
    */
     		SerWrite("\r\n\n",3); // neue Zeile
    
        if (n)
            print_perm (N, n-1);
        else
            while (print_perm (N, n++));
            
    	 while(1);
        return 0;
    }
    Die Ausgabe:
    Code:
    1    : 123R 6Eƈ "¤    "×"  ˆ Cø (usw....)
    Liegts an mir oder am Programm?

    Gruß

    mic

    [Edit]
    Die Lösung sollte doch so aussehen:

    Beispiel mit N = 3, n = 0
    #1: 123
    #2: 132
    ...
    #720: 098
    Geändert von radbruch (30.07.2011 um 02:31 Uhr)

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

  6. #16
    Erfahrener Benutzer Fleißiges Mitglied Avatar von iBot
    Registriert seit
    12.05.2008
    Ort
    ca. 20km von Nürnberg
    Beiträge
    160
    Ok also ich hänge immer noch bei der ersten guten Idee von radbruch fest.
    Aber ich glaube das Problem ist jetzt im Großen und Ganzen gelöst.

    Wozu kann man solche Kombinationen eigentlich nutzen?
    ich sag nur Brute Force-Angriffe
    Nein natürlich nicht.
    In der Zeitschrift "Gong" gibt es jede Woche ein neues sogenanntes "Rechenproblem" , dabei hat man 6 in einander verschachtelte Gleichungen die aus Symbolen bestehen welche je für eine Zahl von 0-9 Stehen. Das Ganze ist oft ziemlich kniffelig zu lösen und weil ich oft nicht bis zur nächsten Ausgabe warten kann und weil es mich irgendwie interessierte, wie das ein Computer lösen könnte, musste ich als erstes erst einmal einen Weg finden, alle erdenklichen Kombinationen für die Variablen bzw. Symbole des Rechenproblems zu finden. Das Einsetzen lassen und auf Richtigkeit überprüfen dürfte da deutlich leichter gehen.
    Geändert von iBot (30.07.2011 um 01:23 Uhr)


  7. #17
    Erfahrener Benutzer Robotik Einstein Avatar von SprinterSB
    Registriert seit
    09.06.2005
    Ort
    An der Saar
    Beiträge
    2.801
    Zitat Zitat von radbruch Beitrag anzeigen
    Ja, das sieht echt clever aus, vor allem die imponierende for-Schleife. Allerdings funktioniert es irgendwie nicht richtig. [...] Liegts an mir oder am Programm?
    Die Folge "123" wird ja ausgegeben; irgendwas hast du da geändert oder veränderst Optionen, die das ABI verändern (unsigned-char?).

    Ich hab's eben genau so auf einem ATmega88 getestet: Funktioniert ebenso wie das PC-Original. Ich verwende Zusatzmodule, so daß ich ganz normal mit printf etc arbeiten kann ohne immer die Quelle für AVR/PC umändern zu müssen. Für solche kleinen Tests ist das super praktisch.

    Wenn du alle Permutationen nacheinander willst, ist es wie gesagt günstiger, immer 1 auf die faktorielle Darstellen zu addieren anstatt für jedes n die Darstellung neu zu berechnen. Bei der faktoriellen Darstellung wächst die Wertigkeit der Stellen: 1, 2, 3, 4, ... während sie z.B. beim Dualsystem 2, 2, 2, ... oder beim Zezimalsystem 10, 10, 10, ... ist. Einfach bei der kleinsten Ziffer Eins aufaddieren und stellenweise Überträge berücksichtigen.

    Anstsatt "Brutaler Gewalt" würd ich eher bissl Hirnschmalz auf die Lösung inverstieren; so schwer sind die Rätsel ja nicht. Bisher hab ich von denen noch keins gesehen, das nicht durch Überlegen zu knacken gewesen wäre.
    Geändert von SprinterSB (30.07.2011 um 17:52 Uhr)
    Disclaimer: none. Sue me.

  8. #18
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    23.07.2009
    Alter
    25
    Beiträge
    133

  9. #19
    Erfahrener Benutzer Roboter Genie Avatar von Searcher
    Registriert seit
    07.06.2009
    Ort
    NRW
    Beiträge
    1.553
    Blog-Einträge
    127
    Hallo,
    da ich durch C nicht durchblicke, hier noch ein Versuch durch Tauschen der Stellen in der Richtung wie Manf vorgeschlagen hat ?

    Code:
    $regfile = "attiny45.dat"
    $framesize = 32
    $swstack = 32
    $hwstack = 36
    $crystal = 8000000
    
    Const Max_positionen = 4                'Anzahl Stellen
    Const Max_pos_decr = Max_positionen - 1 'Hilfskonstante
    
    Dim Zahl(max_positionen) As Byte        'enthält jeweilige Kombination
    Dim Roll_pos(max_positionen) As Byte    'Hilfsvariable für Rollpositionen
    Dim Zahl_str As String * Max_positionen 'variable für Ausgabe der Kombination
    
    Dim Ab_stelle As Byte                   'Übergabevariable in Sub "rollen"
    Dim I As Byte , Zw1 As Byte , Zw2 As Byte
    Dim Moeglichkeit_nr As Long             'zählt gefundene Möglichkeiten durch
    
    Defbyte S                               'Noch nicht decl. Variablen beg. mit S as byte
    
    Declare Sub Rollen(ab_stelle As Byte)
    Declare Sub Ausgabe
    
    '####################
    'Beginn Hauptprogramm
    
    Moeglichkeit_nr = 0
    
    For I = 1 To Max_positionen
      Zahl(i) = I - 1
      Roll_pos(i) = Max_positionen - I
    Next I
    
    'Zahlarray mit maximal 10 Stellen mit Ziffern 0..9
    'links ist Stelle 10 - ST10 , rechts ist Stelle 1 - ST1
    'läuft mit 4 Stellen
    'zum Erweitern Kommentare entfernen UND Konstante Max_positionen anpassen
    
    'For St10 = 1 To 10
    '  For St9 = 1 To 9
    '    For St8 = 1 To 8
    '      For St7 = 1 To 7
    '        For St6 = 1 To 6
    '          For St5 = 1 To 5
                For St4 = 1 To 4
                  For St3 = 1 To 3
                    For St2 = 1 To 2
                      For St1 = 1 To 1
                        Ausgabe
                      Next St1
                      Rollen Roll_pos(1)
                    Next St2
                    Rollen Roll_pos(2)
                  Next St3
                  Rollen Roll_pos(3)
                Next St4
    '            Rollen Roll_pos(4)
    '          Next St5
    '          Rollen Roll_pos(5)
    '        Next St6
    '        Rollen Roll_pos(6)
    '      Next St7
    '      Rollen Roll_pos(7)
    '    Next St8
    '    Rollen Roll_pos(8)
    '  Next St9
    '  Rollen Roll_pos(9)
    'Next St10
    
    End                                     'end program
    
    '##########
    'Beginn Unterprogrammdefinitionen
    
    Sub Rollen(ab_stelle As Byte)           'links rollen um 1 der rechten Stellen in "Zahl" ab "ab_stelle"
      Zw1 = Zahl(ab_stelle)
      For I = Ab_stelle To Max_pos_decr
        Zw2 = I + 1
        Zahl(i) = Zahl(zw2)
      Next
      Zahl(max_positionen) = Zw1
    End Sub
    
    Sub Ausgabe
    
      Incr Moeglichkeit_nr                  'Wieder eine Möglichkeit mehr zur Ausgabe
      'Hier eigene Ausgabeanweisungen rein
      'zb Print
       Zahl_str = ""
       For I = 1 To Max_positionen
         Zahl_str = Zahl_str + Str(zahl(i)) 'Kombination im Zahl array in String geben
       Next I
    End Sub
    Algorithmus ist mit Turbo Pascal ausprobiert, Bascom Prg aber nur bis 4 Stellen im Simulator getestet.


    EDIT: Etwas spät, aber ich möchte die Arbeitsweise vom Programm noch etwas erklären:

    Das Array "Zahl" enthält soviele Elemente, wie verschiedene Elemente vorhanden sind, von denen Permutationen gebildet werden sollen. In diesem Fall 10 für die Zahlen 0 bis 9.

    Das Array wird dann mit den Zahlen 0..9 gefüllt. Möglich sind auch Buchstaben oder sonstwas, wenn es dem Arraytyp entspricht bzw der Arraytyp angepaßt wird.

    Danach läuft das Programm in die For-To Schleifen und landet bei "Ausgabe" -> es wird die Initialisierung von "Zahl" als erste Möglichkeit ausgegeben.

    Nach der Ausgabe wird der Inhalt nur der beiden letzten Arrayelemente nach links gerollt (was für die beiden ein Austausch bedeutet.)

    Das wird dann als nächste Möglichkeit wieder zur Ausgabe gebracht und die letzten beiden Arrayelementinhalte wieder getauscht, was zum Initialisierungszustand zurückführt.

    Nun ist ST2 aber erfüllt und ein Rollen von 3 Elementen ab dem drittletzten Element findet statt und danach ausgegeben.
    Die letzten beiden Elemente werden wieder gerollt und ausgegeben, weiter wie oben.

    Das findet für ST3 drei Mal statt - Initialisierungszustand wieder erreicht, der nicht ausgegeben wird - ab viertletztem Element gerollt - Ausgabe
    ...und so weiter.


    Gruß
    Searcher
    Geändert von Searcher (01.08.2011 um 10:05 Uhr)
    Hoffentlich liegt das Ziel auch am Weg
    ..................................................................Der Weg zu einigen meiner Konstruktionen

  10. #20
    Erfahrener Benutzer Fleißiges Mitglied Avatar von iBot
    Registriert seit
    12.05.2008
    Ort
    ca. 20km von Nürnberg
    Beiträge
    160
    @Searcher:
    Wenn ich mich nicht irre macht doch das Programm von radbruch das Selbe oder?

    Ich glaube das Rätsel wurde (in mehreren Sprachen gleich ) gelüftet und der Thread kann geschlossen werden.
    Danke für eure Beteiligung.


Seite 2 von 3 ErsteErste 123 LetzteLetzte

Berechtigungen

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