Frage zur Programmierung eines Prüfbitgenerator

[__blackjack__]

@frank123: Auch wenn kein Python-Programm gefragt ist, trotzdem mal ein paar Anmerkungen zu dem Quelltext von Dir.

Der fängt mit der Ausgabe einer Lüge an. Es ist sehr wohl möglich etwas anderes als 0 und 1 einzugeben. Wenn der Benutzer keine Zahlen eingibt, bricht das Programm mit einem `ValueError` ab. Wenn er Zahlen eingibt, kann er für jedes Bit eine beliebige ganze Zahl eingeben, auch negative.

Ein- oder zweibuchstabige Variablennamen sind in der Regel keine guten Namen. Namen sollen dem Leser vermitteln was der Wert hinter dem Namen bedeutet. Wenn man `bit` meint, sollte man auch `bit` schreiben, und nicht nur `b`. Das `bx` ein Tupel mit Bitwerten oder `bz` eine Summe von Bits ist, lässt sich aus dem Namen (in Python) nicht erkennen.

Wenn man anfängt Namen durchzunummerieren, dann will man in der Regel bessere Namen wählen, oder gar keine einzelnen Werte sondern eine Datenstruktur. Meistens eine Liste. So auch hier. Statt jedes Bit an einen eigenen Namen zu binden, würde man die in eine Liste stecken. Die Abfrage kann dann in einer Schleife erfolgen, womit man weniger Code hat. Auch das aufaddieren wird dann mit der `sum()`-Funktion einfacher. `bx` fällt dann weg, beziehungsweise wird durch die Liste ersetzt.

`b8` wird am Anfang unnötigerweise mit 0 belegt, diese 0 wird aber (bei korrekter Benutzereingabe) nie verwendet.

Bei dem langen ``if``/``elif``-Konstrukt gibt es im Grunde nur zwei mögliche Ausgänge: Das Prüfbit wird auf 0 oder auf 1 gesetzt. Dazu kann man die ganzen Bedingungen für den jeweiligen Fall auch kombinieren.

Da würde dann diese vier Zeilen bei übrig bleiben:

Code: Alles auswählen

    if bit_sum == 1 or bit_sum == 3 or bit_sum == 5 or bit_sum == 7:
        check_bit = 1
    elif bit_sum == 0 or bit_sum == 2 or bit_sum == 4 or bit_sum == 6:
        check_bit = 0

Da immer `bit_sum` gegen verschiedene Werte auf Gleichheit geprüft wird, kann man sich mit dem ``in``-Operator und einer Liste der Werte die vielen Wiederholungen vom Namen `bit_sum` sparen:

Code: Alles auswählen

    if bit_sum in [1, 3, 5, 7]:
        check_bit = 1
    elif bit_sum in [0, 2, 4, 6]:
        check_bit = 0

Letztlich braucht man aber auch gar keine Tests, weil man den Wert von `check_bit` aus dem Wert von `bit_sum` einfach berechnen kann. Entweder der Rest beim Teilen durch zwei (Modulo-Operator) oder in dem man das niederwertigste Bit mit einer bitweisen Und-Verknüpfung ausmaskiert:

Code: Alles auswählen

    check_bit = sum(bits) & 1

`bneu` wird definiert, aber nirgends verwendet.

Zuguterletzt würde ich noch feste Zahlen aus dem Code verbannen. Also die Anzahl der Eingabebits als Variable oder Konstante definieren und die Längenangabe bei der Ausgabe der Dualzahlen nicht fest in die Zeichenkette(n) schreiben, sondern anhand der Länge der `bits`-Liste ermitteln.

Zwischenstand:

Code: Alles auswählen

#/usr/bin/env python3
"""Prüfbitbitgenerator"""


def main():
    input_bit_count = 7
    # 
    # TODO Actually enforce this restriction!
    #     
    print('!! Nur Eingaben von je einer 0 oder 1 sind möglich !!')
    bits = list()
    for i in range(1, input_bit_count + 1):
        bits.append(int(input(f'{i}. Bit: ')))
    assert len(bits) == input_bit_count and set(bits) == {0, 1}
    
    print(f'Ihre eingegebene {len(bits)}-stellige Dualzahl lautet: {bits}')

    check_bit = sum(bits) & 1
    bits.append(check_bit)
    
    print()
    print('Das Prüfbit ist eine: ', check_bit)
    print()
    print(f'Die {len(bits)}-stellige Dualzahldarstellung lautet: {bits}')


if __name__ == '__main__':
    main()

[Sirius3]

@__blackjack__: bei Dir wäre die Eingabe von nur 0en oder nur 1en ein Fehler.

Code: Alles auswählen

def input_bits(input_bit_count):
    while True:
        bits = input(f'Bitte eine {input_bit_count}-stellige Dualzahl eingeben:').strip()
        if len(bits) == input_bit_count and set(bits).issubset('01'):
            return bits
        print("Fehleingabe")

def main():
    input_bit_count = 7
    bits = input_bits(input_bit_count)
    print(f'Ihre eingegebene {input_bit_count}-stellige Dualzahl lautet: {bits}')
    check_bit = bits.count('1') & 1
    print()
    print('Das Prüfbit ist eine: ', check_bit)
    print()
    print(f'Die {input_bit_count+1}-stellige Dualzahl lautet: {bits}{check_bit}')

if __name__ == '__main__':
    main()

[__blackjack__]

Stimmt.

[__blackjack__]

Das wäre die Variante die ich aus der Aufgabenstellung heraus lese:

Die Knotenbeschriftung ist die jeweilige Ausgabe die beim Übergang/Eintritt gemacht wird.

[__deets__]

Ich nicht ich denke nicht, das ein Epsilonübergang wirklich gefragt ist. Simple 3 Zustände Start, Odd, Even - das wird denke ich gereicht haben.

[__blackjack__]

Wobei der hier ja eigentlich auch nicht wirklich kompliziert ist. Das wiederholt sich im Grunde ja bloss für jedes Bit im Mittelteil. Man kann den Graph in der Mitte aufteilen, wobei links die Zustände für Prüfbit = 0 sind und rechts die Zustände für Prüfbit = 1 und dann braucht man halt für jedes Bit die beiden Varianten das die Eingabe 0 oder 1 ist und wieder die gleiche Ausgabe ergeben muss. Wenn die Eingabe 0 ist, bleibt man in der gleichen Häfte, wenn sie 1 ist, wechselt man in die andere Hälfte, weil sich damit die Anzahl der 1en und damit das Prüfbit ändert.

Da könnte man durch ein bisschen Nachdenken drauf kommen. Wobei ich ja schon zugegeben habe, das mir die Erklärung erst nachträglich beim betrachten des Graphen wie Schuppen von den Augen gefallen ist.

Der Graph ist durch die Überlegung entstanden, dass ein Zustand durch die Eingabe zu maximal zwei Folgezuständen führen kann, und das bei 7 Eingaben maximal ein Baum mit 127 Knoten entsteht. Man kann davon aber Knoten zusammenfassen, da ein Zustand beschrieben werden kann aus der Bitnummer 0 bis 8 (0 = noch kein Bit eingegeben = Startzustand), der Ausgabe die gemacht werden muss (0 oder 1), und dem Prüfbitwert bis dahin (0 oder 1). Das ganze habe ich Kotlin programmiert. Das Programm spuckt den Quelltext im Graphviz-Format aus, mit dem die Grafik erstellt wurde:

Code: Alles auswählen

package de.python_forum.blackjack

data class State (
        val bitNumber: Int = 0,
        val output: String = "",
        val parity: Boolean = false
) : Comparable<State> {
    fun nextLevel(bit: Boolean) = this.copy(
            bitNumber = bitNumber + 1,
            output = if (bit) "1" else "0",
            parity = parity xor bit
    )

    fun parityOutputState() = this.copy(
            bitNumber = bitNumber + 1,
            output = if (parity) "1" else "0"
    )

    override fun compareTo(other: State) = when {
        bitNumber != other.bitNumber -> bitNumber - other.bitNumber
        output != other.output -> output.compareTo(other.output)
        else -> parity.compareTo(other.parity)
    }
}

class Node(val state: State) : Comparable<Node> {
    private val _id = nextId++
    private val _children = HashMap<String, Node>()
    val id: String
        get() = "n$_id"
    val children: Iterable<Map.Entry<String, Node>>
        get() = _children.asIterable()

    fun add(input: String, node: Node) {
        _children[input] = node
    }

    override fun compareTo(other: Node): Int = state.compareTo(other.state)

    companion object {
        private var nextId: Int = 0
    }
}

class Graph(start: State) {
    private val stateToNode = HashMap<State, Node>()
    val nodes: Iterable<Node>
        get() = stateToNode.values

    init {
        stateToNode[start] = Node(start)
    }

    fun get(state: State) = stateToNode.computeIfAbsent(state, ::Node)

    fun connect(stateA: State, stateB: State, input: String) {
        get(stateA).add(input, get(stateB))
    }
}

fun buildNodes(bitCount: Int): Iterable<Node> {
    val startState = State()
    val graph = Graph(startState)
    var level = listOf(startState)

    repeat(bitCount) {
        val nextLevel = ArrayList<State>(level.size * 2)
        for (state in level) {
            for (bit in arrayOf(false, true)) {
                val nextState = state.nextLevel(bit)
                nextLevel.add(nextState)
                graph.connect(state, nextState, if (bit) "1" else "0")
            }
        }
        level = nextLevel
    }
    for (state in level.toSet()) {
        graph.connect(state, state.parityOutputState(), "")
    }
    return graph.nodes
}

private fun printNode(node: Node) {
    println("  ${node.id} [label=\"${node.state.output}\"];")
}

private fun printEdges(node: Node) {
    for ((edge, child) in node.children) {
        println("  ${node.id} -> ${child.id}" +
                " [label=\"${if (edge.isEmpty()) "ε" else edge}\"]")
    }
}

fun printGraphviz(nodes: Iterable<Node>) {
    val sortedNodes = nodes.sorted()
    println("digraph {")
    sortedNodes.forEach(::printNode)
    sortedNodes.forEach(::printEdges)
    println("}")
}

fun main() {
    printGraphviz(buildNodes(7))
}