PHP Knifflig...

[sfranz]

Folgende Aufgabe:

Es wird eine Zahl gesucht, die alle Ziffern höchstens und mindestens einmal enthält. (z.B. 1234567890)

Die erste Stelle muss jedoch durch 1, die ersten beiden Stellen durch 2, die ersten drei Stellen durch 3, die ersten vier Stellen durch 4, [usw.] die gesamte Zahl durch 10 teilbar sein.

Wie wäre euer Lösungsansatz, wenn ihr das in PHP programmieren würdet?

Folgendes kann man ja von vornherein schon festmachen:

- die 10. Ziffer muss die 0 sein, da nur eine Zahl mit einer 0 am Ende durch 10 teilbar ist
- die 5. Ziffer muss 5 sein, da nur sie durch 5 teilbar ist und die 0 bereits ausgeschlossen werden kann
- die 2., 4., 6. und 8. Ziffer müssen gerade sein

Ich stehe da etwas auf dem Schlauch. Mein Denkvermögen reicht zugegebenermaßen nicht aus, um die ganzen Eventualitäten in ein Script zu packen. Vielleicht macht Euch ja die Lösung Spaß und verratet mir, wie ich die Aufgabe per PHP am sinnvollsten lösen könnte.

 

[Cobinja]

Das sieht nach einer Hausaufgabe aus. Da wird dir hier wohl keiner eine fertige Lösung präsentieren.


Aber einen kleinen Denkanstoss kann man geben:

Brute Force: Geh von der kleinsten möglichen Zahl (die du oben schon hingeschrieben hast) los und probier jede Zahl aus, in dem überprüfst, ob alle Kriterien erfüllt sind.

Oder
Backtracking: geh Stelle für Stelle durch und probier, ob du einen passenden Wert für diese Stelle findest. Wenn ja, gehe zur nächsten Stelle und mach dort weiter. Wenn du keinen passenden Wert findest, geh eine Stelle zurück, suche dort nach einem anderen passenden Wert und mach dann mit der nächsten Stelle weiter. das ganze passiert solange, bis du entweder eine Lösung gefunden hast, oder bis du merkst, das es keine Lösung gibt.

 

[sfranz]

Ja, ist eine Hausaufgabe. Aber ich bin schon 10 Jahre aus der Schule draußen. Die Aufgabe hat mir ein Junge aus unserem Sportverein gegeben.

An Bruteforce hatte ich auch gedacht, denke aber, dass das "verschwenderisches" Programmieren ist. Deshalb wollte ich wissen, ob es noch andere Wege zum Ziel gibt.

Trotzdem vielen Dank.

 

[mensch183]

Da 2 Positionen feststehen (die 0 und die 5) und an den anderen 8 Positionen jeweils nur 4 Ziffern in Frage kommen (gerade Ziffern an Position 2,4,6,8 --> für die restlichen 4 Positionen bleiben nur die 4 ungeraden Ziffern übrig) hat man bereits ohne weitere "schlaue Überlegungen" nur 4!*4! = 24*24 = 576 Kombinationen zu testen. Da bietet sich tatsächlich Bruteforce für den Rest der Arbeit an.

 

[asseskiller]

Hier mein Webserver bricht ab weils zu lange dauert musste ma auf nem lokalen testen oder so

<?

function zeichentest($char, $string)
	{
	$string_laenge = strlen($string);
	$i = 0;
	$counter = 0;
	while($i < $string_laenge)
		{
		if($string[$i] == $char)
			{
			$counter++;
			}
		$i++;
		}
	if(counter != 1)
		{
		return False;
		}
	else
		{
		return True;
		}
	}

$i = 1234567890;
while($i < 9876543210)
	{
	$stelle12 = $i[0].$i[1];
	$stelle123 = $i[0].$i[1].$i[2];
	$stelle1234 = $i[0].$i[1].$i[2].$i[3];
	$stelle12345 = $i[0].$i[1].$i[2].$i[3].$i[4];
	$stelle123456 = $i[0].$i[1].$i[2].$i[3].$i[4].$i[5];
	$stelle1234567 = $i[0].$i[1].$i[2].$i[3].$i[4].$i[5].$i[6];
    $stelle12345678 = $i[0].$i[1].$i[2].$i[3].$i[4].$i[5].$i[6].$i[7];
	$stelle123456789 = $i[0].$i[1].$i[2].$i[3].$i[4].$i[5].$i[6].$i[7].$i[8];
	
	if(($stelle12%2) == 0)
		{
		if(($stelle123%3) == 0)
			{
			if(($stelle1234%4) == 0)
				{
				if(($stelle12345%5) == 0)
					{
					if(($stelle123456%6) == 0)
						{
						if(($stelle1234567%7) == 0)
							{
							if(($stelle12345678%8) == 0)
								{
								if(($stelle123456789%9) == 0)
									{
									$cond = True;
									while($k<strlen($i))
										{
										if(zeichentest($i[$k], $i) == False)
											{
											$cond = False;
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	
	if($cond = False)
		{
		$i = $i+10;
		}
	else
		{
		$i = 9876543210;
		$zahl = $i;
		}
	}
echo $zahl;


?>

 

[darkservant2]

so?

<?php
  $arrEven = array(2,4,6,8);
  $arrOdd = array(1,3,7,9);

  //to check: OEOE5EOEO0
  foreach($arrOdd as $p1) {
    foreach($arrEven as $p2) {
      foreach($arrOdd as $p3) {
        if ($p3 == $p1) continue;
        foreach ($arrEven as $p4) {
          if($p4 == $p2) continue;
          $p5 = 5;
            foreach($arrEven as $p6) {
              if ($p6 == $p4 || $p6 == $p2) continue;
              foreach($arrOdd as $p7) {
                if ($p7 == $p3 || $p7 == $p1) continue;
                foreach($arrEven as $p8) {
                  if ($p6 == $p4 || $p6 == $p2 || $p8==$p6) continue;
                  foreach($arrOdd as $p9) {
                    if ($p9 == $p7 || $p9 == $p1 || $p9 == $p3) continue;
                    $p10 = 0;
                    //p1 % 1 == 0 ok
                    //p2 % 2 == 0 ok
                    if (($p1.$p2.$p3)%3!=0) continue;
                    if (($p1.$p2.$p3.$p4)%4!=0) continue;
                    //p5%5 == 0 ok
                    if (($p1.$p2.$p3.$p4."5".$p6)%6!=0) continue;
                    if (($p1.$p2.$p3.$p4."5".$p6.$p7)%7!=0) continue;
                    if (($p1.$p2.$p3.$p4."5".$p6.$p7.$p8)%8!=0) continue;
                    if (($p1.$p2.$p3.$p4."5".$p6.$p7.$p8.$p9)%9!=0) continue;
                    else echo "Eine Zahl: ".$p1.$p2.$p3.$p4."5".$p6.$p7.$p8.$p9."0<br>";
                  }
                }
              }
            }
        }

      }
    }
  }
?>

 

[mensch183]

Zumindest die Iterationen über die 8 4er Arrays sehen gut aus. Dürfte genau die 576 Möglichkeiten abgrasen. Optimierungsfähig sind die Teilbarkeitstests. Die mußt du nicht alle erst in der innersten Schleife machen sondern idealerweise möglicht weit außen, also z.B. ($p1.$p2.$p3)%3 schon am Beginn der $p3-loop.

Was kommt eigentlich raus?

 

[darkservant2]

hätte man gleich teilen können, stimmt. Aber Schleifendurchläufe kosten ja echt keine Rechenzeit, dass wollt ich nachher nicht nochmal verschieben

Rauskommt 3816547290 und das Script läuft auf meiner p3 Gurke 0.036886 Sekunden

 

[mensch183]

Oha, nur ein Treffer. Interessant. Gerade mal ein php5 auf meinem Router installiert (K6-2, 400 MHz) und ausprobiert. 284 ms beim Original, 173 ms mit umgebauten Teilertests wie unten. Im p8-loop war noch ein copy&paste-Fehler im 1. Test, der zum Glück das Ergebnis nicht änderte.

BTW: Schöne Umsetzung von dir. Ich selbst hätte mangels PHP-Ahnung ohne rumgoogeln nur Pseudocode für meinen Ansatz liefern können. Die Aufgabe ist gut, da (zumindest für mich) nicht offensichtlich war, was rauskommt.

<?php
  $arrEven = array(2,4,6,8);
  $arrOdd = array(1,3,7,9);   

  //to check: OEOE5EOEO0
  foreach($arrOdd as $p1) {
    foreach($arrEven as $p2) {
      foreach($arrOdd as $p3) {
        if ($p3 == $p1) continue; 
        if (($p1.$p2.$p3)%3) continue;
        foreach ($arrEven as $p4) {   
          if($p4 == $p2) continue;
          if (($p1.$p2.$p3.$p4)%4) continue;
            foreach($arrEven as $p6) { 
              if ($p6 == $p4 || $p6 == $p2) continue;  
              if (($p1.$p2.$p3.$p4."5".$p6)%6) continue;
              foreach($arrOdd as $p7) {   
                if ($p7 == $p3 || $p7 == $p1) continue;
                if (($p1.$p2.$p3.$p4."5".$p6.$p7)%7) continue;
                foreach($arrEven as $p8) { 
                  if ($p8 == $p4 || $p8 == $p2 || $p8==$p6) continue;
                  if (($p1.$p2.$p3.$p4."5".$p6.$p7.$p8)%8) continue;
                  foreach($arrOdd as $p9) {
                    if ($p9 == $p7 || $p9 == $p1 || $p9 == $p3) continue;
                    if (($p1.$p2.$p3.$p4."5".$p6.$p7.$p8.$p9)%9) continue;
                    echo "Eine Zahl: ".$p1.$p2.$p3.$p4."5".$p6.$p7.$p8.$p9."0<br>";
                  }
                }
              }
            }
        }
   
      }
    }
  }
?>

 

[darkservant2]

hm - krass
meine lösung: runtime 0.03678
dein verschieben: runtime 0.00252
ich hätte nicht gedacht das man das so merkt... da ist doch echt nix dahinter...

 

[mensch183]

Naja, die Teilbarkeitstests gehen recht oft schief, womit man sich den weiter inneren Kram auch recht oft spart. Hier mal die "Trefferraten" der Teilertests. Mit Treffer meine ich, daß die Zahl nicht teilbar ist, also der If-Zweig wahr ist und somit per continue der Ablauf verkürzt wird.

%3: 28 von 48 Fälle
%4: 30 von 60 Fälle
%6: 40 von 60 Fälle
%7: 32 von 40 Fälle
%8: 7 von 8 Fälle
%9: 0 von 1 Fälle

 

[darkservant2]

stimmt, ich hatte einen Denkfehler drin, ich probier ja die innerste Zahl durch auch wenn der erste Test schon schief geht. Blöde Sache Ich dachte meine Version würde genau so springen wie du es jetzt machst - aber die Continues sind ja nur in der inneren Schleife.

Erst denken, dann was schreiben

 

[sfranz]

@mensch183: Danke für deine Lösung. Geht ja echt fix. Mein Lösungsansatz hatte nach 10 Minuten noch kein richtiges Ergebnis gefunden... da sieht man die Erfahrungsunterschiede. Ich werde mir mal dein Script zu Gemüte führen und hoffentlich daraus lernen.

 

[ag3nt]

Also so kompliziert ist die Aufgabe nun wirklich nicht, dass man die
Lösungen durchtesten muss. Viele der Möglichkeiten lassen sich
sehr schnell ausschließen.

Erster Hinweis:

• Die ersten 3 Zahlen sind durch 3 teilbar (Quersumme durch 3 teilbar)
• Die ersten 6 Zahlen sind durch 6 teilbar (und natürlich durch 3)
• Die ersten 9 Zahlen sind durch 9 teilbar (und natürlich durch 3, Quersumme ist durch 9 Teilbar)

Zweiter Hinweis:

• Die ersten 4 Zahlen sind durch 4 teilbar
• Die ersten 8 Zahlen sind durch 8 teilbar (die letzten 3 Ziffern müssen dafür durch 8 teilbar sein, ausserdem ist die Zahl durch 4 teilbar)

Es gibt aber auch einen nutzlosen Hinweis, da jede mögliche Kombination durch 9 teilbar ist!


Würde an der 4. Stelle eine 4 oder 8 stehen, so müssten auch die ersten
3 Zahlen multpliziert 10 durch durch 4 Teilbar sein. Es gibt aber keine
Zahl die durch 4 Teilbar ist und eine der folgenden Formen besitzt:

• ...14
• ...18
• ...34
• ...38
• ...74
• ...78
• ...94
• ...98

An der 4. Stelle muss also entweder eine 2 oder eine 6 stehen. Es bleiben also die
Folgen:

• 25x
• 65x

Da diese Folge durch 3 teilbar sein muss (sie ist ja auch durch 6 teilbar), kommt nur eine einzige Möglichkeit
in Frage, nämlich:

• 654

Jede andere gültige Kombination ist nämlich nicht durch 3 teilbar!

Dadurch bleiben für die Positionen 1-3 bzw 7-9 noch die folgenden Möglichkeiten:
A

• 327
• 723
• 729
• 927

B

• 183
• 381
• 189
• 981

Das sind bereits jetzt nur noch 4² Möglichkeiten (im Vergleich zu den (4!)² am Anfang)

Wir wissen das, die ersten 8 zahlen durch 4 teilbar sein müssen, also kann man den gleichen Trick
wie bei den ersten 4 Zahlen anwenden: die 8. Zahl muss demnach eine 2 sein! (Es bleiben 4*2 Möglichkeiten)

Wegen der Teilbarkeitsregel von 8 fällt aber weitere Folge heraus (492 ist nicht durch 8 teilbar).

• 327
• 723
• 729

Jetzt muss man lediglich noch folgende Zahlen auf die Teilbarkeit durch 7 prüfen:

• 1836547..
• 3816547..
• 1896547..
• 9816547..
• 1836543..
• 3816543..
• 1896543..
• 9816543..

Hierbei ist lediglich 3816547 durch 7 teilbar, womit 381654729 die gesuchte Lösung ist.


Die Aufgabe ist also auch ohne "BruteForce" gut lösbar, den Taschenrechner braucht man wirklich nur am Schluss.

 

[mensch183]

Schön. Bisher ist leider niemand mal konsequent die Teilbarkeitsregeln durchgegangen, wie man vor allem am %9-Test sieht. :-)

Das liegt sicher daran, daß man sich bei geforderter Lösung per Programm gern mit seinem Lösungsweg zufrieden gibt, sobald man den Aufwand auf ein leicht per Programm beherrschbares Maß gesenkt hat. Wäre eine Zettel+Bleistift-Lösung gefordert, wäre man um mehr Grübeln nicht herumgekommen. Die paar %7-Tests hätte man auch dem Papier machen können.