Ein Zahlenproblem

**radbruch** · 29.07.2011, 22:47

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

**iBot** · 30.07.2011, 00:13

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.

**SprinterSB** · 30.07.2011, 09:28

Zitat von radbruch

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.

**justin** · 31.07.2011, 00:29

Nur so als Hinweis:

http://de.wikipedia.org/wiki/Prolog_...n_R.C3.A4tsels

**Searcher** · 31.07.2011, 13:52

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

**iBot** · 31.07.2011, 14:14

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

**Searcher** · 31.07.2011, 14:21

Zitat von iBot

@Searcher:
Wenn ich mich nicht irre macht doch das Programm von radbruch das Selbe oder?

Hi,
ich kann radbruchs C Programme nicht verstehen. Seine Bascom Programme, wenn ich das richtig verstehe, nehmen Ziffern und vergleichen, ob diese schon in der Kombination vorhanden sind.???

Mein Programm verzichtet darauf und tauscht stur die Stellen durch.

Bitte um Berichtigung, wenn ich da was falsch interpretiert habe.

Gruß
Searcher

**radbruch** · 31.07.2011, 14:29

Hallo Searcher

Deine Lösung funktioniert leider auch nicht richtig, weil sie nicht alle Ziffern von '0' bis 9' berücksichtigt. Ausgabe deiner Variante:

Code:

Kombinationen und Anzahl der Kombinationen. Richtig wäre 10*9*8*7=5040 Kombinationen. Hier die Kombinationen mit drei Stellen:
https://www.roboternetz.de/community...2&d=1312105805

Gruß

mic

[Edit]

Das C-programm macht genau desselbe wie die Bascom-Variante. Es wird ein Array mit der Anzahl der gewünschten Stellen erzeugt und jede Stelle nacheinander mit allen Werten ausprobiert. Wenn der Wert für die aktuelle Stelle schon im Array vorhanden ist, wird dieser Wert übersprungen. Wenn man mit dem Wert für die erste Stelle startet, kann man alle weiteren Stellen mit dem selben Algorithmus errechnen:

Code:

void suchen(uint8_t z) // z ist der Index im Array, es wird also die z-Stelle erzeugt
{
	for(x[z]=0; x[z]<10; x[z]++) // Werte von 0 bis 9 erzeugen
	{
		gefunden=0; // flag wird gestezt, wenn Wert schon im Array erhalten ist
		for(y=0; y<z; y++) if(x[y]==x[z]) gefunden=1; // Alle Elemente im Array vor aktuellem Index prüfen
		if(!gefunden) // Wenn der Wert erstmalig im Array auftritt wird er im Array unter dem aktuellen Index espeichert
		{
			if(z < (ziffern-1)) suchen(z+1); // Rekursion! // Wenn noch nicht alle Stellen berechnet sind wird die nächste Stelle berechnet
			else
			{
				ausgabe(); // Ausgabe der Ziffernkombinationen in x[0] bis x[ziffern-1] 
				nr++;
			}
		}
	}
}

**Searcher** · 31.07.2011, 14:37

Hallo radbruch,
das war ja schnell getestet! Die Ausgabe ist Absicht.

Wenn die Anzahl der Stellen auf 4 begrenzt ist, werden alle Permutationen der Ziffern 0, 1, 2, 3 ausgegeben. Zu Testzwecken durch die REMs auf 4 begrenzt.

Wenn die Anzahl der Stellen auf 10 ist, werden alle Permutationen der Ziffern 0, 1, 2, 3 ... 9 ausgegeben.

Gruß
Searcher