[HaBo]
| Programmieraufgaben Hier wird regelmäßig eine neue Programmieraufgabe gestellt, die dann gelöst werden soll und in Zusammenarbeit mit den Moderatoren auch besprochen werden kann. |
rekursive Zahlenreihe
Diskussion: rekursive Zahlenreihe im Forum Programmieraufgaben, in der Kategorie Code Kitchen; Eingereich von xeno: Errechne den 30 sten Wert einer Zahlenreihe, die wie folgt aufgebaut ist: start = 1 1 = ...
 |
06.11.09, 11:11
| #1 (permalink) | |
| Moderator   Registriert seit: 20.07.05  Likes: 156 |  rekursive Zahlenreihe Eingereich von xeno: Errechne den 30 sten Wert einer Zahlenreihe, die wie folgt aufgebaut ist: start = 1 1 = eine eins = 11 11 = zwei einsen = 21 21 = eine zwei, eine eins = 1211 1211 = eine eins, eine zwei, zwei einsen = 111221 111221 = drei einsen, zwei zweien, eine eins = 312211 Zitat:
__________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt. | |
|  |
|
06.11.09, 15:10
| #2 (permalink) |
 Registriert seit: 15.08.05    Likes: 0 | Ok mal schauen gar nicht so easy Das ganze sieht mir nach einer altenrativen Darstell8ung von Zahlen aus sprich man kann entweder sagen xy wobei x angibt wie oft y in der zahl oder einfach dei Zahl als sich selbst e.g 1 = 1 1 : eine eins oder 11 = 1x1 = 1 11 : zwei einsen oder 21 = 2x1 = 2 21 : eine zwei, eine wins oder 1211 = 1x2+1x1 = 3 1211 : eine eins, eine zwei, zwei einsen oder 111221 = 1x1 + 1x2 + 2 x 1 = 5 Komment wir zu der Reihe selbst sie geht also von 1,2,3,5 ? Irgendwie fehlt mir da die 4 also gehen wir davon aus das es sich um die Reihe der Primzahlen handelt gut die naechste waere dann wohl 7 aber 111221: eine Eins , eine eins, eine eins, eine zwei, eine zwei, eine eins oder 21112211 = 2x1 + 1x1 + 2x2 + 1x1 = 6 ? 6 ist nicht Prim aber warum haben wir dann 4 uebersprungen eventuell ist die Zahl egal dann koennten wir also einfach weitermachen und das ergebnis ignorieren 21112211: eine zwei, eine eins, eine eins, eine eins, eine zwei, eine zwei, eine eins, eine eins oder 1221112221 = 1x2 + 2x1 + 1x1 + 2x2 + 2x1 = 11 (braucen wir das ueberhaupt noch) unsere Zahlen haben immer eine gerade Anzahl von Ziffern und nun koeennen wir etwas schreiben das das mapped Jetzt ist die Frage wie schreiben wir das am besten es ist ja rekursiv. Schauen wir uns mal unsere cases an Wir brauchen mal eine funktion die uns eine zahl die naechtfolgende umwandelt base case: Element 1 = 1 easy ok jetzt die advanced es gibt 2 haup untershceidungen: a) a Die Zahl die wir uebergeben haben ist einstellig dann ist under output 1 zahl b) Die Zahl hat 2 oder mehr stellen: Wir schauen ist 1. Stelle == 2. Stelle ? Wenn ja schreiben wir 2 Zahl und haengen das vorne an die konvertirung der Zahl von 3. Stelle aufwaerts e.g original [1 1] 2 1 2= 11 => 2 1 . convert(2 1 2) Wenn die ungleich sind dann schreiben wir 1 Zahl und haengen die konvertirung der zahl von 2. Stelle+ an. : 1 x Erste Stelle . Konvertierung 2. Stelle +. Nun koennen wir also eine Zahl basierend auf der vorherigen berechnen Jetzt brauchen wir nur noch was das unsere Funktion nach und nach aufruft bis wir am base case sind: angenommen wir wollen das 30 element. Ein Element X ist defniert als reihe(x) = convert(x-1) e.g element(30) = konvert(element(29)) = konvert(konvert(element(2  ) = konvert(konvert(konvert(element(27))) ..........nachdem wir eh schon so schoen viel "(" haben und ich mich grade pervers fuehle werden wir das ganze in scheme schreiben :-p Code: (define atomic?
(lambda (it)
(if (pair? it)
#f
#t)))
(define elementat
(lambda (n)
(if (eq? n 1)
(convert (list 1))
(convert (elementat (- n 1))))))
(define convert
(lambda (number)
(if (null? number)
'()
(if (null? (cdr number))
(cons 1 number)
(if (eq? (car number) (cadr number))
(cons 2 (cons (car number) (convert (cddr number))))
(cons '1 (cons (car number) (convert (cdr number))))))))) Code: (elementat 30) 1221112221221112212221221221112221221221112211122122111221222122122111221221112221222122122111221112212212211122212211122122212212211122212212211122111221221221112221221112212221221221112211122122212212211122122111222122111221222122122111221221112221222122122111221112212212211122212211122122212212211122122111222122111221222122122111222122122111221112212221221221112211122122122111222122111221222122122111221112212221221221112212211122212212211122212211122122212212211122212212211122111221221112212221221221112212211122212221221221112211122122122111222122111221222122122111222122122111221112212212211122212211122122212212211122111221222122122111221221112221221221112221221112212221221221112221221221112211122122111221222122122111221221112221222122122111221112212212211122212211122122212212211122111221222122122111221221112221222122122111221112212212211122212211122122212212211122122111222122111221222122122111222122122111221112212211122122212212211122122111222122212212211122111221221221112221221112212221221221112212211122212211122122212212211122212212211122111221222122122111221112212212211122212211122122212212211122111221222122122111221221112221221221112221221112212221221221112221221221112211122122111221222122122111221221112221222122122111221112212212211122212211122122212212211122122111222122111221222122122111222122122111221112212211122122212212211122122111222122212212211122111221221221112221221112212221221221112221221221112211122122122111222122111221222122122111221112212221221221112212211122212221221221112211122122122111222122111221222122122111221112212221221221112212211122212212211122212211122122212212211122212212211122111221221112212221221221112212211122212221221221112211122122122111222122111221222122122111221112212221221221112212211122212221221221112211122122122111222122111221222122122111221221112221221112212221221221112221221221112211122122122111222122111221222122122111222122122111221112212211122122212212211122122111222122212212211122111221221221112221221112212221221221112221221221112211122122122111222122111221222122122111221112212221221221112212211122212211122122212212211122122111222122212212211122111221221221112221221112212221221221112212211122212211122122212212211122212212211122111221222122122111221112212212211122212211122122212212211122111221222122122111221221112221221221112221221112212221221221112221221221112211122122111221222122122111221221112221222122122111221112212212211122212211122122212212211122212212211122111221221221112221221112212221221221112211122122212212211122122111222122122111222122111221222122122111222122122111221112212211122122212212211122122111222122212212211122111221221221112221221112212221221221112211122122212212211122122111222122212212211122111221221221112221221112212221221221112212211122212211122122212212211122212212211122111221221221112221221112212221221221112221221221112211122122111221222122122111221221112221222122122111221112212212211122212211122122212212211122212212211122111221221221112221221112212221221221112211122122212212211122122111222122111221222122122111221221112221222122122111221112212212211122212211122122212212211122122111222122111221222122122111222122122111221112212221221221112211122122122111222122111221222122122111221112212221221221112212211122212212211122212211122122212212211122212212211122111221221112212221221221112212211122212221221221112211122122122111222122111221222122122111221112212221221221112212211122212221221221112211122122122111222122111221222122122111221221112221221112212221221221112221221221112211122122212212211122111221221221112221221112212221221221112211122122212212211122122111222122122111222122111221222122122111222122122111221112212211122122212212211122122111222122212212211122111221221221112221221112212221221221112212211122212211122122212212211122212212211122111221221112212221221221112212211122212221221221112211122122122111222122111221222122122111222122122111221112212212211122212211122122212212211122111221222122122111221221112221 |
|
| |
| HaBOT | |
|
|
06.11.09, 15:27
| #3 (permalink) |
| Moderator  Registriert seit: 09.09.04 Likes: 65 | zur überprüfung auf korrektheit kann übrigens die länge der 30. zahl angeschaut werden, die sollte im optimalfall 5808 sein  gruß und viel spaß, xeno |
| |
|
06.11.09, 15:51
| #4 (permalink) |
| Registriert seit: 15.08.05 Likes: 0 | Sicher @ Xeno ? Ich komm nur auf 3945 bei 30 koennen wir mal outpout vergleichen bis 14 pls Code: (derive 14) ((2 1 2 2 1 2 2 1 1 1 2 2 1 1 1 2 2 1 2 2 1 2 2 1 1 1 2 2 2 1 2 2 1 1 1 2 2 1 2 2 2 1 2 2 1 2 2 1 1 1 2 2 1 1 1 2 2 1 2 2 2 1 2 2 1 2 2 1 1 1 2 2 1 2 2 1 1 1 2 2 2 1) (1 1 2 2 2 1 1 1 2 2 1 2 1 1 2 2 2 1 1 1 2 2 1 1 2 2 1 2 1 1 2 2 1 1 2 2 2 1 1 1 2 2 1 2 1 1 2 2 1 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 1 1) (1 2 2 1 1 1 2 2 2 1 2 2 1 1 1 2 2 1 2 2 2 1 2 2 1 2 2 1 1 1 2 2 2 1 2 2 1 2 2 1 1 1 2 2 1 1 1 2 2 1) (2 1 1 1 2 2 1 1 2 2 1 2 1 1 2 2 1 1 2 2 2 1 1 1 2 2 1 1 2 2 2 1 1 1 2 2 1 2 1 1) (1 1 1 2 2 1 2 2 2 1 2 2 1 2 2 1 1 1 2 2 1 2 2 1 1 1 2 2 2 1) (1 2 1 1 2 2 1 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 1 1) (2 1 2 2 1 2 2 1 1 1 2 2 1 1 1 2 2 1) (1 1 2 2 2 1 1 1 2 2 1 2 1 1) (1 2 2 1 1 1 2 2 2 1) (2 1 1 1 2 2 1 1) (1 1 1 2 2 1) (1 2 1 1) (2 1) (1 1)) |
|
| |
|
06.11.09, 15:55
| #5 (permalink) |
| Moderator Registriert seit: 09.09.04 Likes: 65 | du hast leider fehler im code 111221 = drei einsen, zwei zweien, eine eins = 312211 sorry @CDW: editierst du diese erste reihe mit einer drei mal in den first post rein? |
|
| |
|
06.11.09, 17:40
| #6 (permalink) |
| Registriert seit: 15.08.05 Likes: 0 | Sorry hab die Zeile mit der "3" nicht gesehen ich stand under der Annahme das das System nur 1 und 2 kennt. Werd mich spaetr nochmal dran setzen. MFG |
|
| |
|
06.11.09, 17:47
| #7 (permalink) |
| Registriert seit: 01.11.03 Likes: 0 | Sicher, dass der 30. Wert nicht 4462 Stellen hat und erst der 31. 5808? ("1" ist ja der 1. Wert...) Und die "Erklärung" kann man sich doch sparen. Einfach ein String der rekursiv erstellt wird. Immer die gleichen Zeichen zählen und dann Zeichen und Anzahl ausgeben... |
|
| |
|
06.11.09, 18:26
| #8 (permalink) |
| Moderator Registriert seit: 09.09.04 Likes: 65 | stimmt, hab mich verzählt. beginnt man mit der 1, dann hat der 31. wert eine länge von 5808 und der 30. 4462. |
|
| |
|
06.11.09, 18:43
| #9 (permalink) |
| Registriert seit: 12.01.09  Likes: 1 | Code: // Language: Delphi Language/Pascal
// Typ: Iterativ / nicht Rekursiv!
var
i, j,
k, xLen: integer;
x, y: String;
FirstChar: Char;
const
Iterations = 10;
begin
x := '1';
xLen := 1;
for i := 0 to Iterations - 1 do
begin
Writeln( IntToStr(i+1):2, '. ', x );
y := '';
j := 1;
while j <= xLen do
begin
k := 1;
if j + k <= xLen then
begin
FirstChar := x[j];
while (x[j+k] = FirstChar) and (j+k<=xLen) do
inc(k);
end;
y := y + IntToStr(k) + x[j];
inc(j, k);
end;
x := y;
xLen := Length(x);
end;
Writeln;
Writeln('Done!');
Readln;
end. Iteraions = 5 (CDW-Angabe) |
|
| |
|
08.11.09, 23:20
| #10 (permalink) |
| Registriert seit: 24.11.04 Likes: 0 | wow... das muss ewig her sein, dass ich hier mal was gepostet habe. Erklaerung haengt imho hinreichend in den kommentaren. Anm: effizienztechnisch noch nicht so der burner, und es koennte eine WEITAUS einfachere loesung mit ner gramatik geben. Ich guck mir das mal nochmal an... Code: % recursive predicate. generates the first Y rows from the % initial row X. gen(X,Y) :- Y >= 0, rrow(X,Z), write(Z),nl, Y2 is Y - 1, gen(Z,Y2). % recursion anchor. these two might be redundant. Cuts to % save some inferences. rrow([],[]) :- !. rrow([X|[]],[1,X]) :- !. % main generation predicate. rrow([X1,X2|Rx],[Y1,X1|Ry]) :- % first possibility: two prefixes are identical. might % be more. so: count, and add to the list. ( X1 == X2, countf([X1,X2|Rx],NRX,Y1,X1), rrow(NRX,Ry), ! ); ( % or they are not. so just put in one and go on. X1 \== X2, Y1 is 1, rrow([X2|Rx],Ry), ! ). % count anchor for words with only one letter. countf([X|[]],[],1,X) :- !. % anchor for everything else countf([X|R],[X|R],0,Y) :- X \== Y, !. % simple recursive count countf([X|Rx],Ry,Acc,X) :- countf(Rx,Ry,Acc2,X), Acc is Acc2 + 1. Mfg Tobias |
|
| |
|
09.11.09, 01:40
| #11 (permalink) |
| Moderator Registriert seit: 20.07.05 Likes: 156 | ISO Prolog mit Grammatik
__________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt. |
|
| |
|
09.11.09, 01:56
| #12 (permalink) |
| Member of Honour   Registriert seit: 14.09.07 Likes: 60 | juhuu  got it ist zwar nicht sauber, aber mir ist es zu spät, dass in ne saubere rekursion umzusetzen quick n dirty in php Code: <?php
ini_set('memory_limit', '2048M');
class lol {
private $str = '1';
private $pos = 0;
private $count = 1;
private $newstr = '';
private $i = 0;
public function __construct() {
$this->check(0);
}
private function check() {
$char = $this->str[$this->pos];
while($this->checkNext($char,$this->pos + $this->count)) $this->count++;
$this->newstr .= $this->count . $char;
$this->pos += $this->count;
$this->count = 1;
if ($this->pos >= strlen($this->str)) {
$this->i++;
echo "run {$this->i} [length: ". strlen($this->newstr) ."]\n";
echo $this->str = $this->newstr;
echo "\n";
if ($this->i >= 30) die();
$this->newstr = '';
$this->pos = 0;
}
$this->check();
}
private function checkNext($char,$pos) {
if (!isset($this->str[$pos])) return false;
if ($char === $this->str[$pos]) return true;
return false;
}
}
new lol();
?>  daher das memory limit ;Ddann is mir eingefallen, das das php 32bit ist und daher recht schnell versagt.... -> und zwar genau beim 50ten run, aber mehr als 2gb kann ich dem php ja nicht geben... Code: run 49 [length: 894810] Code: PHP Fatal error: Out of memory (allocated 2009333760) (tried to allocate 261900 bytes) in D:\coding\zahlenreihe.php on line 37 Fatal error: Out of memory (allocated 2009333760) (tried to allocate 261900 bytes) in D:\coding\zahlenreihe.php on line 37 ansonst das erg: erg
__________________ » Flattr mich! - Wenn dir mein Beitrag geholfen hat! « <| 2 AMD Opterons 2384@ 8x3,2ghz | Tyan S2915 | 10GB | 2x 8800GT | 8400GS | Dell 3008WFP + 2x2007FP |> |
|
| |
|
19.10.10, 23:51
| #13 (permalink) |
| Registriert seit: 12.01.09 Likes: 1 | Damn it, hätte zuerst guggen sollen, ob ich es schonmal gelöst habe. Wie auch immer, hier mein second run [delphi] Code: program Project1;
{$APPTYPE CONSOLE}
var
i: Integer;
s: String;
function IntToStr(const I: Integer): String;
begin
Str( I, Result );
end;
function Max(const A, B: Integer): Integer;
begin
if A > B then
Result := A
else
Result := B;
end;
function Convert(const lpNumber: String): String;
var
i, Len,
j, k: Integer;
begin
Result := '';
Len := Length( lpNumber );
if Len > 0 then
begin
i := 1;
repeat
k := 1;
if i + 1 <= Len then
begin
j := 1;
while j <= Len - i do
begin
if lpNumber[i+j] = lpNumber[i] then
inc( k )
else
break;
inc( j );
end;
end;
Result := Result + IntToStr( k ) + lpNumber[i];
inc( i, Max( 1, j ) );
until i > Len;
end;
end;
begin
s := '1';
for i := 1 to 30 do
s := Convert( s );
Writeln( s );
Readln;
end. Resultat (5810 Charakter) Code: 132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133122112231131122211211131221131112311332211213211321322113311213212322211231232112311321322112311311222113311213212322211231131122211311123113321112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131122211213211331121321122112133221123123211231132132211231131122211331121321232221123113112221131112311322311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312211312111322211322111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113222122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321322112312321123113213221123113112221131112311332211211131221131211221321123113213221121113122113121113222123113221132122212231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221231132212312311211132132212312211322212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111311222112132113311213211221121332211322132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311311222113221321123123211231131122211211131221133112132113221321123113121113221112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321133112132113212221221113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113122113221113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231131122211322132112312321123113112211322112211213322112111312211312111322212321121113121112133221132213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221  |
|
| |
|
20.10.10, 10:00
| #14 (permalink) | ||
| Member of Honour Registriert seit: 14.09.07 Likes: 60 | Zitat:
Zitat:
__________________ » Flattr mich! - Wenn dir mein Beitrag geholfen hat! « <| 2 AMD Opterons 2384@ 8x3,2ghz | Tyan S2915 | 10GB | 2x 8800GT | 8400GS | Dell 3008WFP + 2x2007FP |> | ||
|
| |
|
20.10.10, 13:48
| #15 (permalink) | |
| Registriert seit: 21.04.08 Likes: 0 | Kleine, aber meiner Meinung nach, sehr schöne Lösung in Haskell: Code: series :: Int -> [[Int]]
series n = take (n+1) $ iterate (next) [1]
where next = concatMap (\xs -> [length xs, xs !! 0]) . group
main :: IO ()
main = let (xs0, xs1) = (take 5 xs, length . last $ xs)
in mapM_ (print) [show xs0, show xs1]
where xs = series 30 Zitat:
Felix | |
|
| |
|
| | |
|
|
[HaBo] » Software Home » Code Kitchen » Programmieraufgaben » rekursive Zahlenreihe
| Themen-Optionen | |
| Ansicht | |
Linear-Darstellung
| |
Ähnliche Themen | ||||
| Thema | Autor | Forum | Antworten | Letzter Beitrag |
| Zahlenreihe | Xalon | Programmieraufgaben | 63 | 11.11.10 15:10 |
