Das deutsche Python-Forum

Seit 2002 Diskussionen rund um die Programmiersprache Python
https://www.python-forum.de/

Problem bei ersten python versuchen

https://www.python-forum.de/viewtopic.php?t=27583

Seite 2 von 2

Re: Problem bei ersten python versuchen

Verfasst: Sonntag 16. Oktober 2011, 15:45
von BlackJack
Problem 1 in CoffeeScript:

Code: Alles auswählen

#!/usr/bin/env coffee

Number :: isDivisibleBy7 = -> this % 7 is 0

Number :: containsDigit7 = -> this.toString().indexOf("7") isnt -1

test = (n) -> n.isDivisibleBy7() or n.containsDigit7()

console.log(if test i then "*" else i) for i in [1..100]
Ist der Io-Lösung sehr ähnlich.

Problem 2 zeige ich mal nicht, weil sich daraus eine Python-Lösung ziemlich 1:1 ergibt.

Re: Problem bei ersten python versuchen

Verfasst: Montag 17. Oktober 2011, 09:37
von BlackJack
Auch eine Haskell-Variante der Lösungen von mir:

Problem 1:

Code: Alles auswählen

isDivisibleBy7 = (==) 0 . mod 7

containsDigit7 = elem '7' . show

convertNumber n = if test n then "*" else show n
    where test n = isDivisibleBy7 n || containsDigit7 n

main = putStr . unlines $ map convertNumber [1..100]
Problem 2:

Code: Alles auswählen

faks = scanl (\a b -> a * succ b) 1

outputPairs r = zip r (faks r)

formatOutputPair (a,b) = show a ++ "! = " ++ show b

main = putStr . unlines $ map formatOutputPair $ outputPairs [0..10]

Re: Problem bei ersten python versuchen

Verfasst: Dienstag 18. Oktober 2011, 10:27
von BlackJack
Da Hyperion sich den C64 schon mit BASIC als Zielplattform ausgesucht hat, und mein BASIC-Programm nicht viel anders ausgesehen hätte, habe ich mal Forth auf dem Brotkasten bemüht.

Problem 1:

Code: Alles auswählen

\ Seven-Star                        bj11

: div-by-7? ( n -- ? )
  7 mod 0= ;

: contains-7? ( n -- ? )
  10 /mod 7 =  swap 7 =  or ;

: main ( -- )
  101 1 ?do
    i div-by-7?  i contains-7?  or
    if ." * " else i . then
  loop cr ;

\\ Print all numbers from 1 to 100 but
an asterisk if the number is divisible
by 7 or contains the digit 7.
Problem 2:

Code: Alles auswählen

\ Fac-Table                         bj11

: main ( -- )
  1
  9 0 ?do
    i . del ." ! = " dup u. cr
    i 1+ *
  loop
  drop ;

\\ Print a fac table. Unfortunately only
up to 8! because that is the limit for
the 16 bit integers of VolksFORTH on the
Commodore 64.
Es steht ja schon im Kommentar — mit 16-Bit-Werten kommt man bei der Fakultät nicht all zu weit. :-(

Re: Problem bei ersten python versuchen

Verfasst: Dienstag 18. Oktober 2011, 12:24
von Hyperion
BlackJack hat geschrieben:Da Hyperion sich den C64 schon mit BASIC als Zielplattform ausgesucht hat, und mein BASIC-Programm nicht viel anders ausgesehen hätte, habe ich mal Forth auf dem Brotkasten bemüht.
Hehe... sorry ;-)

Sag mal weißt Du evtl. wie man Modulo auf dem Brotkasten in Assembler ausdrücken kann? Ich war ja fast versucht, meine bescheidenen Assemblerkenntnisse wieder aufzufrischen, aber dafür hatte ich keine Idee.

Re: Problem bei ersten python versuchen

Verfasst: Dienstag 18. Oktober 2011, 13:25
von lunar
Da Haskell bereits vergeben ist, bleibt mir noch SWI-Prolog:

Code: Alles auswählen

format_number('*', X) :- 0 is X mod 7, !.
format_number('*', X) :- number_chars(X, L), memberchk('7', L), !.
format_number(S, X) :- swritef(S, "%t", [X]).

write_number(X) :- format_number(S, X), writef("%t\n", [S]).

main :- forall(between(1, 100, X), write_number(X)).
Und Problem 2:

Code: Alles auswählen

factorial(1, 0).
factorial(1, 1).
factorial(F, X) :- P is X - 1, factorial(PF, P), F is PF * X.

format_factorial(S, X) :- factorial(F, X), swritef(S, "%t! = %t", [X, F]).

write_factorial(X) :- format_factorial(S, X), writef("%t\n", [S]).

main :- forall(between(0, 10, X), write_factorial(X)).

Re: Problem bei ersten python versuchen

Verfasst: Dienstag 18. Oktober 2011, 17:22
von BlackJack
@Hyperion: Der Prozessor kann ja nur addieren, subtrahieren, und Bits verschieben. Daraus muss man sich das selber basteln. Simpelste, aber vielleicht nicht eleganteste Variante für ``a % b`` ist so lange `b` von `a` abziehen wie ``b > a`` gilt. Das was dann übrig bleibt wäre der Rest der Division. Wenn man mit zählt wie oft man das gemacht hat, bekommt man auch den ganzzahligen Anteil der Division heraus.

Trotz fehlender Eleganz wäre das bei dieser Aufgabe aber IMHO sogar im Bereich des Tolerierbaren. Das wären maximal 14 Schleifendurchläufe für 100 und 7.

Ansonsten muss man sich eine effizientere Division basteln, wo auch der Rest bei heraus fällt. Ist bei Byte/Byte auch nur eine Handvoll Befehle in einer Schleife.

Ich habe sowohl das Modulo-7 als auch das Teilen durch 10 für die Ausgabe umgangen. Ersteres, in dem ich einfach parallel einen Zähler laufen lasse um jeden 7. Durchlauf der Schleife zu erkennen. Und für die Umwandlung in eine Zeichenkette bemühe ich Routinen im BASIC-ROM:

Code: Alles auswählen

        !to "test.prg", cbm
        
        chrout = $ffd2
        strout = $ab1e
        ldf_u8 = $b3a2
        f2str  = $bddd
        
        i = $fa
        j = $fb
        
        * = $c000

        lda #1          ; i = 1
        sta i
        lda #7          ; j = 7
        sta j
loop
        dec j           ; every 7th iteration -> print asterisk
        bne .not_div_7
        lda #7
        sta j
        bne print_asterisk
.not_div_7

        ldy i           ; FAC = i
        jsr ldf_u8
        jsr f2str       ; $0100... = STR(FAC) + 0x00; A/Y = $0100
        
        lda #"7"        ; compare digits with "7"
        cmp $0101
        beq print_asterisk
        cmp $0102
        beq print_asterisk

        tya             ; print number (A/Y = $0101)
        jsr strout
        jmp print_space

print_asterisk
        lda #"*"
        jsr chrout

print_space
        lda #" "
        jsr chrout
        
        inc i           ; i++
        ldy i
        cpy #101        ; already i == 101?
        bne loop
        
        lda #13         ; print newline
        jmp chrout
Und wo ich schon dabei war, hier das Problem 2:

Code: Alles auswählen

        !to "test.prg", cbm
        
        intout = $bdcd
        strout = $ab1e
        ldf    = $bba2
        stf    = $bbd4
        ldf_u8 = $b3a2
        fltmul = $ba28
        fltout = $aabc
        
        i = $fa
        f_one  = $bfe8

        * = $c000

        ldx #4          ; n = 1.0
-       lda f_one,x
        sta n,x
        dex
        bpl -
        
        lda #0          ; i = 0
        sta i
loop
        lda #0          ; print i
        ldx i
        jsr intout
        
        lda #<txt       ; print "! ="
        ldy #>txt
        jsr strout
        
        lda #<n         ; FAC = n
        ldy #>n
        jsr ldf
        
        jsr fltout      ; print FAC + newline
        
        ldy i           ; FAC = i + 1
        iny
        jsr ldf_u8
        
        lda #<n         ; FAC *= n
        ldy #>n
        jsr fltmul
        
        ldx #<n         ; n = FAC
        ldy #>n
        jsr stf
        
        inc i           ; i++
        lda i           ; loop finished?
        cmp #11
        bne loop
        
        rts

txt:    !pet "! =", 0

n:      * = * + 5
Da mache ich auch Gebrauch von den Gleitpunktzahl-Routinen im BASIC-ROM um die Multiplikation und die Umwandlung in Dezimaldarstellung nicht selbst implementieren zu müssen. Da kann man nun natürlich streiten ob das geschummelt ist.

Ach ja: Quelltext ist für den ACME-(Cross-)Assembler.

Re: Problem bei ersten python versuchen

Verfasst: Dienstag 18. Oktober 2011, 17:47
von Hyperion
@BlackJack: Danke :-) Gute Erklärung und auch die "Tricks" Deiner Umsetzung habe ich verstanden. Da hätte ich wirklich selber drauf kommen können!

Re: Problem bei ersten python versuchen

Verfasst: Dienstag 18. Oktober 2011, 19:28
von BlackJack
Nochmal zu der 6510-Assembler-Lösung von Problem 1: Wenn man die Umwandlung von `i` in Zeichen und die Ausgabe der Zeichenkette nicht mehr über das ROM macht, kommt das Programm mit einer Unterroutine zur Ausgabe eines einzelnen Zeichens als „externe“ Abhängigkeit aus und wird damit portierbarer. Dazu muss man den Code zwischen ``.not_div_7`` und ``print_asterisk`` durch dieses hier ersetzen:

Code: Alles auswählen

        lda i           ; X/Y/A = decimal digits of i
        ldx #"0"-1
        sec
-       inx
        sbc #100
        bcs -
        ldy #"9"+1
-       dey
        adc #10
        bmi -
        adc #"0"-1
        
        cpy #"7"        ; check if there is a "7"
        beq print_asterisk
        cmp #"7"
        beq print_asterisk

        pha             ; print digits in X/Y/A without leading "0"s
        cpx #"0"
        beq +
        txa
        jsr chrout
        jmp ++
+       cpy #"0"
        beq +++
++      tya
        jsr chrout
+++     pla
        jsr chrout
        jmp print_space
Insgesamt wächst dadurch der Code um 38% von 70 auf 97 Bytes. Jetzt muss ich nur noch die zweite Zählvariable durch eine gescheite Division/Modulo ersetzen, dann ist es nicht mehr so „geschummelt“.

Re: Problem bei ersten python versuchen

Verfasst: Mittwoch 19. Oktober 2011, 11:24
von BlackJack
Okay, ich denke das ist jetzt die finale 6510-Assembler-Version für Problem 1. Keine zweite Zählschleife mehr, sondern eine Modulo-Rechnung, so dass man die Grenzen jetzt im Rahmen von 1 bis 255 ändern kann, in dem man die Konstanten am Anfang setzt:

Code: Alles auswählen

        !to "test.prg", cbm
        
        chrout  = $ffd2
        
        i       = $fa
        tmp     = $fb
        
        * = $c000

        FROM    = 1
        TO      = 100
        
        ldy #FROM       ; i = FROM
        sty i
loop
        sty tmp         ; tmp = (i / 7) / 2; A = i % 7
        lda #0
        ldx #7
        clc
-       rol tmp
        rol
        cmp #7
        bcc +
        sbc #7
+       dex
        bpl -
        
        cmp #0          ; divisible by 7?
        beq print_asterisk

        lda i           ; X/Y/A = decimal digits of i
        ldx #"0"-1
        sec
-       inx
        sbc #100
        bcs -
        ldy #"9"+1
-       dey
        adc #10
        bmi -
        adc #"0"-1
        
        cpy #"7"        ; check if there is a "7"
        beq print_asterisk
        cmp #"7"
        beq print_asterisk

        pha             ; print digits in X/Y/A without leading "0"s
        cpx #"0"
        beq +
        txa
        jsr chrout
        jmp ++
+       cpy #"0"
        beq +++
++      tya
        jsr chrout
+++     pla
        jsr chrout
        jmp print_space

print_asterisk
        lda #"*"
        jsr chrout

print_space
        lda #" "
        jsr chrout
        
        inc i           ; i++
        ldy i           ; already finished?
        cpy #TO+1
        bne loop
        
        lda #13         ; print newline and return to caller
        jmp chrout
Ist jetzt bei 106 Bytes, könnte aber, da keine Abhängigkeit vom BASIC-ROM mehr besteht, 50 KiB RAM am Stück verwenden wenn man das ROM ausblendet. :-)

Re: Problem bei ersten python versuchen

Verfasst: Mittwoch 19. Oktober 2011, 13:34
von Hyperion
BlackJack hat geschrieben: Ist jetzt bei 106 Bytes, könnte aber, da keine Abhängigkeit vom BASIC-ROM mehr besteht, 50 KiB RAM am Stück verwenden wenn man das ROM ausblendet. :-)
Fehlt nur noch die Killerapplikation, die diese 50KiB ausnutzt und diese Routine benötigt :-D

Ob wir den OP irgend wie vergrault haben? :K

Re: Problem bei ersten python versuchen

Verfasst: Mittwoch 19. Oktober 2011, 16:06
von lunar
@Hyperion: Ich glaube, der OP hat jetzt Angst… hätte ich auch, wenn ich nicht schon länger hier unterwegs wäre ;)

Re: Problem bei ersten python versuchen

Verfasst: Mittwoch 19. Oktober 2011, 16:27
von Masaru
In jedem Witz steckt ein Fünkchen Wahrheit ... wenn ich über die Jahre hinweg, die ich dieses Forum nun schon lese (und auch lange Zeit meinen Brei dazugegeben habe), betrachte -> wieviele Neulinge verschlissen, verratzt und mundtot gemacht worden sind (direkt, wie indirekt) *lach*und nie wieder einen Fuß in die Foren-Territorialität gesetzt haben ... *TräneAusAugewisch* ... dann hat es fast schon wieder etwas komisches an sich.

Jaja, Wattebäuschen bis ich blute - ich weiss :roll:

Re: Problem bei ersten python versuchen

Verfasst: Mittwoch 19. Oktober 2011, 18:38
von Dav1d
Ich persönlich hab solche Threads gerne :D. Man lernt was (BlackJacks Assembler) und es macht Spass das Problem auch in anderen Sprachen zu lösen und die Ergebnisse zu vergleichen.

Re: Problem bei ersten python versuchen

Verfasst: Donnerstag 20. Oktober 2011, 17:01
von T64
Für alle, die die gleiche Aufgabe haben und noch eine Lösung suchen, das hier müsste für 2. funktionieren:

Code: Alles auswählen

def fak(x):
    if x == 0: return 1
    y = 1
    for i in range(1, x +1):
        y = y*i
    return y

for i in range(10):
    print "%s! = %s" % (i, fak(i))
Edit: Bei mir war auch ein kleiner Fehler drin :O ...

Re: Problem bei ersten python versuchen

Verfasst: Donnerstag 20. Oktober 2011, 17:11
von derdon
Das auch:

Code: Alles auswählen

>>> print '\n'.join("%d! = %d" % (index, value) for index, value in enumerate(imap(math.factorial, xrange(1, 10)), 1))
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
Edit: Fehler behoben, den hoffentlich noch keiner bemerkt hat :P

Re: Problem bei ersten python versuchen

Verfasst: Donnerstag 20. Oktober 2011, 17:30
von EyDu
@derdon: Jetzt musst du uns nur noch erklären, warum du `enumerate` UND `xrange` brauchst ;-)

Code: Alles auswählen

print "\n".join("%d! = %d" % (x, math.factorial(x)) for x in range(1, 10))

Re: Problem bei ersten python versuchen

Verfasst: Donnerstag 20. Oktober 2011, 17:39
von lunar
Ich finde ja einen endlosen Iterator mit allen Paaren viel schöner :)

Code: Alles auswählen

facs = ((x, math.factorial(x)) for x in count())
print '\n'.join('{0}! = {1}'.format(x, y) for x, y in islice(facs, 10))
Ansonsten fängt die Fakultät ja eigentlich bei 0 an ;)

Re: Problem bei ersten python versuchen

Verfasst: Donnerstag 20. Oktober 2011, 17:49
von derdon
Ihr habt ja soooo Recht :D

EyDu: Das kann ich nicht erklären :oops:

Re: Problem bei ersten python versuchen

Verfasst: Donnerstag 20. Oktober 2011, 22:18
von BlackJack
Die eigenständigere 6510-Assembler-Variante ohne Rückgriff auf die Rechenroutinen im BASIC-ROM des C64 ist noch in Arbeit. Aber zwischendurch mal schnell der BASIC-Einzeiler, der das selbe macht (wie die Assembler-Variante, die wohl irgendwo bei ≈200 Zeilen enden wird):

Code: Alles auswählen

1 N=1:FOR I=0 TO 12:PRINT I "!=" N:N=N*(I+1):NEXT

Re: Problem bei ersten python versuchen

Verfasst: Sonntag 23. Oktober 2011, 00:15
von BlackJack
Okay, hier ist nun die Assemblervariante für Problem 2 die nicht die Rechenroutinen im BASIC-ROM verwendet: http://pastebin.com/uCCF6UXb

Edit: Noch mal ein Nachtrag zur Forth-Lösung auf dem C64. Jetzt auch hier mit 32-Bit, also bis 12!:

Code: Alles auswählen

\ Fac-Table                           bj


: d*u ( d u -- d*u )
  dup rot * -rot um* rot + ;


: main ( -- )
  page 1.
  13 0 ?do
    i . del ." ! = " 2dup d. cr
    i 1+ d*u
  loop
  2drop ;

\\ Print a fac table from 0! to 12!
Alle Zeiten sind UTC+01:00
Seite 2 von 2

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de