Function zum erstellen einer Adjazenzmatrix

[pythonnewbie1]

Hallo ich bin aktuell beim Bearbeiten von Bäumen und Graphen in der Programmiersprache Python angekommen und komme bei einer Aufgabe aktuell nicht weiter (für jeden kleinen Anhaltspunkt wäre ich dankbar).
Die Aufgabe lautet:
1.
Ein gerichteter, ungewichteter Graph enthält die Knoten 2...n. Eine Kante führt immer dann von x nach y, wenn die Zahl x die Zahl y teilt.
Es soll nun ein Python-Programm geschrieben werden, das eine solche Adjazenzmatrix erzeugt und dann damit arbeitet.
1. Schreiben Sie zunächst eine Funktion, die als Input den Wert n erhält und die zugehörige Adjazenzmatrix erzeugt. Beachten Sie, dass auch der Wert des Knotens abgespeichert werden muss. Der Pseudocode dafür sieht wie folgt aus:
- Von x = 2 bis n:
---Beschrifte den aktuellen Knoten mit x
---Befülle die Matrixzeile mit Null
---Trage für alle Vielfachen von x eine 1 in die Matrixzeile ein

2. Schreiben Sie nun eine Funktion, die die obige Adjazenzmtraix sowie eine Zahl zwischen 2 und n als Input erhält und ausgibt, ob es sich um eine Primzahl hält.



Beim arbeiten/ erstellen einer ungewichteten Adjzenzmatrix hab ich immer den Graph z.B. so angelegt und hab dann "direkt" mit N gearbeitet:

# Knoten anlegen
a, b, c, d = 0, 1, 2, 3

# Adjazenzmatrix
N = [
[0,1,1,0], # Nachfolger von a
[0,0,1,1], # Nachfolger von b
[1,1,0,0], # Nachfolger von c
[1,0,1,0] # Nachfolger von d
]

Jetzt muss ich aber laut der Aufgabe diesen Graph als Funktion erstellen und steh gerade auf dem Schlauch...

[imonbln]

Okay, übersetzt mal diese Zeilen in gültiges Python3.

- Von x = 2 bis n:
---Beschrifte den aktuellen Knoten mit x
---Befülle die Matrixzeile mit Null
---Trage für alle Vielfachen von x eine 1 in die Matrixzeile ein

Wenn du dann immer noch Fragen hast, kannst du deinen Code hier posten (bitte mit Codetags) und wir können dir am konkreten Beispiel helfen.

[__blackjack__]

Eine Lösung in klassischem BASIC. Läuft beispielsweise auf dem C64, aber mit N=20 sogar noch auf einem VIC-20 mit 3,5 KB BASIC RAM (da gehen dann 3 KB für die Matrix drauf). Der Aufruf des Unterprogramms zum ausgeben der Matrix (Zeile 150) ist auskommentiert, weil die Ausgabe der Matrix zwar in der Aufgabe nicht gefordert war, aber beim Entwickeln sinnvoll sein kann. Zur Fehlersuche, aber auch beim überlegen wie man die Testfunktion schreiben kann.

Code: Alles auswählen

   10 N=20:GOSUB 100:REM GOSUB 150:END
   20 FOR I=1 TO N:GOSUB 200:PRINT I,:IF P THEN PRINT"PRIME";
   30 PRINT:NEXT:END
  100 REM CREATE ADJACENCY MATRIX
  110 DIM M(N,N):FOR I=2 TO N:FOR J=I TO N STEP I:M(I,J)=1:NEXT:NEXT:RETURN
  150 REM DISPLAY MATRIX
  160 FOR I=2 TO N:FOR J=2 TO N:PRINT STR$(M(I,J));:NEXT:PRINT:NEXT:RETURN
  200 REM CHECK IF I IS PRIME
  210 S=0:FOR J=0 TO N:S=S+M(J,I):NEXT:P=S=1:RETURN

Die Testfunktion ist hier ”mathematisch” formuliert. Das ist so eigentlich ineffizient. Wenn es auf Laufzeit ankäme, könnte man das so formulieren, dass die Schleife dort abgebrochen wird, sobald das Ergebnis eindeutig fest steht.

[pythonnewbie1]

ich konnte das Problem lösen. Beitrag kann gelöscht werden, danke für die Antworten

[imonbln]

werden

Dann schreib hier in Codetag rein wie du es hinbekommen hast, echt nichts ist für den nächsten Demotivierender als Läuft bei mir Thema kann geschlossen werden.
Wir sind hier keine bezahlten Tutoren, das Forum lebt davon, dass Leute fragen und andere sich Zeit nehmen zu helfen. Ich bin sicher __blackjack__ hat ca 10 min Lebenszeit investiert, dir zu helfen. Das wenigste, was du machen könntest, ist etwas zurückgeben, damit der nächste es leichter hat. Außerdem ist die Wahrscheinlichkeit hoch, dass es noch Optimierungspotential in deinem Programm gibt, welches du verschwendest, weil du deine durch diese Community gefundene Lösung geheim hältst.

[__blackjack__]

Naja, das BASIC macht mir ja Spass. Und so lange hat das nicht gedauert. Die Assembler-Variante für DOS ist da aufwändiger:

Code: Alles auswählen

        cpu 8086
        org 100h

N       equ 200         ; Careful, we have just 64k for program, data and stack,
                        ; and this is going to be squared.

;--------------------------------------
start:
        cld
        
        mov     al, N
        call    init_matrix
        ; call    print_matrix
        
        mov     bx, 1           ; Check all numbers between 1 and N
.prime_loop:
        call    is_prime
        jne     .not_prime
        
        mov     ax, bx
        call    print_byte
                
        mov     ah, 2
        mov     dl, ' '
        int     21h
        
.not_prime:
        inc     bl
        cmp     bl, [n]
        jbe     .prime_loop
        
        ret

;--------------------------------------
init_matrix:
        xor     ah, ah
        mov     [n], al
        inc     ax
        mul     ax
        mov     cx, ax

        mov     di, matrix      ; clear matrix with 0s.
        xor     al, al
        rep stosb

        xor     ah, ah
        mov     ax, [n]
        inc     ax
        add     ax, matrix
        mov     di, ax
        
        mov     ax, 1
.row_loop:
        cmp     ax, [n]
        ja      .rows_done
        
        mov     bx, ax
.column_loop:
        cmp     bx, [n]
        ja      .columns_done
        
        mov     byte [di+bx], 1
        add     bx, ax
        jmp     .column_loop

.columns_done:
        add     di, [n]
        inc     di
        inc     ax
        jmp     .row_loop

.rows_done:
        ret

;--------------------------------------
print_matrix:
        mov     si, matrix
        xor     ch, ch
        mov     cl, [n]
        inc     cx
        
.row_loop:
        push    cx
        mov     cl, [n]
        inc     cx
.column_loop:        
        lodsb
        or      al, '0'
        mov     dl, al
        mov     ah, 2
        int     21h
        loop    .column_loop
        
        mov     dl, 13
        int     21h
        mov     dl, 10
        int     21h
        
        pop     cx
        loop   .row_loop

        ret

;--------------------------------------
is_prime:
        mov     si, matrix
        xor     al, al
        xor     ch, ch
        mov     cl, [n]
        inc     cx

.row_loop:
        add     al, [si+bx]
        add     si, [n]
        inc     si
        loop    .row_loop
        
        cmp     al, 2
        ret

;--------------------------------------
print_byte:
        mov     dl, 10
        xor     cx, cx
.L1:
        xor     ah, ah
        div     dl
        push    ax
        inc     cx
        or      al, al
        jnz     .L1

        mov     ah, 2
.L2:
        pop     dx
        mov     dl, dh
        or      dl, '0'
        int     21h
        loop    .L2
        
        ret
        
;--------------------------------------
section .bss
n:      resb 1

matrix:

[__blackjack__]

Um mal eine visuelle Vorstellung von der Matrix zu bekommen ein BASIC-Programm das eine 640×640 Matrix auf einem Epson-kompatiblen 9-Nadel-Matrixdrucker ausgibt:


Man sieht, dass die Hälfte der Matrix unbesetzt ist und auch die andere Hälfte nur schwach besetzt ist.