ALGORITHMEN - Teil XIX: Stromausfall im Aussenhirn

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    Unsere Datenschutzerklärung wurde aktualisiert. Mit der Nutzung unseres Forums akzeptierst Du unsere Datenschutzerklärung. Du bestätigst zudem, dass Du mindestens 16 Jahre alt bist.

    • Lösung zu AneR 08
      --------------------
      Spoiler anzeigen

      1*1 = 1 ... noch nicht zweiziffrig
      4*4=16, 5*5=25, 6*6=36,7*7=49,8*8=64,9*9=81
      10*10=100 ... nicht mehr zweiziffrig
      Kandidaten sind daher: 16, 25, 36, 49, 64, 81
      Antwort: +/- 1 neben 10er-Zahl sind 49 und 81, also 2 Zahlen.
      +/- 6 neben einer 10er-Zahl sind 16, 36 und 64, also 3 Zahlen.
    • Abt. AneR 09 ´Zusammen´
      ==================
      Alice und Bruno sind zusammen 39,
      Bruno und Christiane sind zusammen 40,
      Christiane und Daniel sind zusammen 38,
      Daniel und Eva sind zusammen 44.
      Alice, Bruno, Christiane, Daniel und Eva sind zusammen 105 Jahre alt.
      Frage: Wer von den fünfen ist am jüngsten?
    • Abt. Jaro-Winkler String-Ähnlichkeit
      =======================
      Der Jaro-Algorithmus ist ein Maß für gemeinsame Zeichen, die innerhalb von "nicht mehr als der halben Länge der längeren Zeichenkette" liegen, unter Berücksichtigung von Transpositionen (Verdrehungen). Winkler modifizierte diesen Algorithmus, um das Faktum zu berücksichtigen, dass Unterschiede am Anfang der Zeichenkette signifikanter sind als Unterschiede am Ende der Zeichenkette. Jaro und Jaro-Winkler eignen sich für den Vergleich kleinerer Zeichenketten wie Wörter und Namen.

      Spoiler anzeigen
      Für Stringähnlichkeitsvergleiche hatten wir u.a. bereits den Levenshtein-Algorithmus programmiert. Levenshtein zählt die Anzahl der Bearbeitungen (Einfügungen, Löschungen oder Substitutionen), die erforderlich sind, um eine Zeichenkette in die andere zu konvertieren. Damerau-Levenshtein ist eine modifizierte Version, die Transpositionen auch als Einzelbearbeitung betrachtet. Obwohl die Ausgabe die ganzzahlige Anzahl der Bearbeitungen ist, kann dies normalisiert werden, um einen Ähnlichkeitswert durch eine Formel zu erhalten.

      In der Praxis ist es wichtig, eine Methode zu wählen, die der Art der Zeichenketten entspricht, die man vergleichen will. Manche Verfahre sind viel aufwändiger als etwa die Berechnung einer phonetischen Vorab-Kodierung. Viele Details kann man der folgenden Dissertation [Christen 1966] entnehmen: LINK

      Von der Geschwindigkeit her ist die Reihenfolge demnach: 1. Jaro, 2. Jaro-Winkler, 3. Levenshtein, 4. Damerau-Levenshtein, wobei zwischen schnellstem und langsamsten Algorithmus ein Faktor 2 bis 3 liegt. (Text teilweise übersetzt mit DeepL)

      Gruss

      Quellcode

      1. WindowTitle "Jaro-Winkler String-Ähnlichkeit"
      2. 'Q: http://rosettacode.org/wiki/Jaro_distance#Pascal
      3. 'Thema: https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance
      4. 'Dissertation [Christen 2006]: Systemvergleich Jaro - Levenshtein
      5. 'http://users.cecs.anu.edu.au/~Peter.Christen/publications/tr-cs-06-02.pdf
      6. '(D) Demo translation, 2018-10-28 by P.Specht, Vienna/EU
      7. 'Ohne jede Gewähr! No warranty whatsoever!
      8. CLS:font 2
      9. print format$("0.#######", JaroWinkler("DWAYNE","DUANE"))
      10. print format$("0.#######", JaroWinkler("MARTHA","MARHTA"))
      11. print format$("0.#######", JaroWinkler("DIXON","DICKSONX"))
      12. print format$("0.#######", JaroWinkler("JELLYFISH","SMELLYFISH"))
      13. ' Solloutput:
      14. ' 0.822222
      15. ' 0.944444
      16. ' 0.766667
      17. ' 0.896296
      18. waitinput
      19. END
      20. Proc JaroWinkler :parameters s1$,s2$
      21. declare l1&,l2&,match_distance&,matches&,i&,k&,trans&,gr&,kl&
      22. declare bs1&[255],bs2&[255] 'max string length is here 255
      23. l1&=len(s1$):l2&=len(s2$)
      24. ifnot l1&:ifnot l2&:return 1:else:return 0:endif:endif
      25. match_distance&= if(l1&>l2&,l1&,l2&)\2-1
      26. ' matches&=0
      27. ' trans&=0
      28. Whileloop l1&:i&=&Loop
      29. gr&=i&-match_distance&
      30. kl&=i&+match_distance&
      31. whileloop if(1>gr&,1,gr&),if(kl&<l2&,kl&,l2&):k&=&Loop
      32. case bs2&[k&]:continue
      33. case mid$(s1$,i&,1)<>mid$(s2$,k&,1):continue
      34. bs1&[i&]=1:bs2&[k&]=1 '1=true
      35. inc matches&:break
      36. endwhile
      37. endwhile
      38. casenot matches&:return 0
      39. k&=1
      40. whileloop l1&:i&=&Loop
      41. casenot bs1&[i&]:continue
      42. :whilenot bs2&[k&]:inc k&:endwhile
      43. case mid$(s1$,i&,1)<>mid$(s2$,k&,1):inc trans&
      44. inc k&
      45. endwhile
      46. trans&=trans&\2
      47. return ((matches&/l1&)+(matches&/l2&)+((matches&-trans&)/matches&))/3
      48. endproc
      Alles anzeigen
    • Hallo p.specht,

      das war jetzt aber schwer. :wacko:

      p. specht schrieb:

      Abt. AneR 09 ´Zusammen´
      ==================
      Alice und Bruno sind zusammen 39,
      Bruno und Christiane sind zusammen 40,
      Christiane und Daniel sind zusammen 38,
      Daniel und Eva sind zusammen 44.
      Alice, Bruno, Christiane, Daniel und Eva sind zusammen 105 Jahre alt.
      Frage: Wer von den fünfen ist am jüngsten?
      A + B = 39
      C + D = 38
      -> A+B+C+D = 77
      Dann ist E = 28 (105-77)

      Daraus folgt:
      Daniel ist der Jüngste mit 16 Jahren.
      Eva hat aber schon 28 Jahre auf dem Buckel.

      Tschau
    • @oldie-40: Bravo, korrekt gelöst! Hier noch die ...

      Offizielle Lösung zu AneR 09
      --------------------------------
      Spoiler anzeigen

      Ansatz:
      (Namens-Anfangsbbuchstaben:)
      A+B+C+D+E=105
      A+B = 39
      _ B+C = 40
      ___ C+D = 38
      _____ D+E = 44

      Wir wissen:
      E = (A+B+C+D+E) - (A+B+C+D)
      (A+B) sowie (C+D) sind aber bekannt!:
      E = (A+B+C+D+E) - (A+B) - (C+D)
      E = 105 - 39 - 38 = 28
      D = 44 - E = 44 - 28 = 16
      C = 38 - D = 38 - 16 = 22
      B = 40 - C = 40 - 22 = 18
      A = 39 - B = 39 - 18 = 21
      ---
      Antwort: Daniel (D) ist mit 16 Jahren der Jüngste.
    • Abt. AneR 10 ´Kreis an Kreis´
      ===================
      Einem Quadrat ist ein Viertelkreis bündig eingeschrieben - im Eck entsteht ein Zwickel. Einem solchen Zwickel ist ein kleiner Kreis bündig eingeschrieben. Welchen Radius hat der kleine Kreis im Vergleich mit dem Radius des Viertelkreises?
    • Lösung zu AneR 10
      ------------------
      Spoiler anzeigen

      Die Länge der Quadratseite entspricht dem Radius R des Viertelkreises. Wir wissen, dass die Diagonale im Quadrat dessen Seitenlänge mal Sqrt(2) ist. Bedenkt man, dass das auch für ein gedachtes kleines Quadrat um den kleinen Kreis im Zwickel gilt (Radius klein-r, Diagonale r*Sqrt(2)), dann kann man sich die große Diagonale aus drei Teilen zusammengesetzt denken:
      R * sqrt(2) = R + r + r * sqrt(2)
      R * sqrt(2) - R = r + r * sqrt(2)
      R *(sqrt(2)-1) = r * (sqrt(2)+1)
      ==> r = R * (sqrt(2)-1)/(sqrt(2)+1)
      Antwort: r/R = 0.17157287525380996
    • Abt. 10 Gebote, egal wo sie herkommen
      =========================
      1. Höre auf dein Gewissen. Die Stimme der Gerechtigkeit ist gesunden Menschen angeboren.
      2. Spotte nicht über den Glauben anderer, solange sie dich in Ruhe lassen.
      3. Reserviere Zeit für Gewissensfragen und Sinnfindung.
      4. Behandle Familienangehörige respektvoll und wohlwollend.
      5. Du sollst nicht morden. Und du sollst nicht töten, wenn es nicht notwendig ist.
      6. Du sollst nicht herumvögeln, wenn es die Gefühle deiner/s Partner/In/nen verletzen könnte.
      7. Du sollst nicht stehlen, egal in welcher Form.
      8. Du sollst nicht falsch für oder gegen Mitmenschen aussagen.
      9. Achte Rechte und Beziehungen anderer.
      10. Zügle deine Gier.
    • Abt. Kardaschow-Skala der Zivilisationen
      ===========================
      Wie viele intelligente Zivilisationen gibt es in unserer Galaxis? Seti-Pionier Frank Drake konstruierte dafür 1960 eine Formel: A = Z*•A s •Z p •Z e •A l •A i •A k •L. In der Universität Edinburgh setzte man kürzlich aktuelle Daten ein und rechnete alles durch. Das Ergebnis: „Es könnten tausende sein“. Dem gegenüber steht aber das Fermi-Paradoxon, nämlich die Frage. "Wo sind denn alle?"

      Die Kardaschow-Skala unterscheidet drei Kategorien, in die Zivilisationen auf der Basis ihrer Energienutzung (Verfügungsgewalt über physikalische Leistung) eingeordnet werden:

      Typ I: Die Zivilisation ist auf der technologischen Stufe der heutigen Erde (definiert in 1964) mit einem Energieverbrauch von 4·10^12 Watt. Später wurde dies daraufhin geändert, dass die Zivilisation in der Lage ist, die gesamte auf einem Planeten verfügbare Leistung zu nutzen. Das sind ungefähr 10^16–10^17 W. (Für die Erde ist dieser Wert etwas größer als 1.74·10^17 W). Die Fähigkeit der Menschheit, Energie zu nutzen, stieg in der Geschichte an. Im letzten Jahrhundert stieg die Menschheit auf der Kardaschow-Skala daher von etwa 0.582 auf etwa 0.72, das ist derzeit noch immer deutlich unterhalb von Typ I.

      Typ II: Die Zivilisation ist in der Lage, die Gesamtleistung ihres Zentralsterns zu nutzen. Das sind ungefähr 4*10^26 W. Eine Typ-II-Zivilisation ist mit 10 Milliarden Typ-I-Zivilisationen vergleichbar.
      Technisch wäre das z.B. mit einer Dyson-Sphäre zu bewältigen - oder gleich mit mehreren. Diesfalls ensteht ein sog. Matrjoschka-Gehirn.

      Typ III: Die Zivilisation ist in der Lage, die Gesamtleistung einer Galaxie zu nutzen. Das sind ungefähr 4*10^37 W. Eine Typ-III-Zivilisation ist etwa mit 100 Milliarden Typ-II-Zivilisationen vergleichbar.

      Gruss

      Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von p. specht ()

    • Abt. AneR 14 ´Halbkreise´
      =========================
      Auf der X-Achse bei 0 startet ein Halbkreis mit dem Mittelpunkt8 bei x=4. Wieder bei x angekommen startet ein zweiter Halbkreis mit dem Mittelpunkt bei x=6, und es schließt ein dritter Halbkreis mit Mittelpunkt x=3 an. Frage: Bei welchem x-Wert endet der dritte Halbkreis?
    • p. specht schrieb:

      Auf der X-Achse bei 0 startet ein Halbkreis mit dem Mittelpunkt8 bei x=4. Wieder bei x angekommen startet ein zweiter Halbkreis mit dem Mittelpunkt bei x=6, und es schließt ein dritter Halbkreis mit Mittelpunkt x=3 an. Frage: Bei welchem x-Wert endet der dritte Halbkreis?
      Gehört die 8 dazu?

      Ist bei allen Halbkreisen der Startpunkt die Null?


      Spoiler anzeigen

      Dann endet der letzte bei 6, sonst ist es wohl die 2.

      Start bei 0, Mitte bei 4, Ende bei 8
      Start bei 8, Mitte bei 6, Ende bei 4
      Start bei 4, Mitte bei 3, Ende bei 2

      Programmieren, das spannendste Detektivspiel der Welt.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Michael Wodrich ()

    • @Michael Wodrich: Nein, es ist stets der Drehpunkt angegeben, wobei aber ein Linienzug aus Halbkreisen entstehen soll. Daher ist deine im obigen Spoiler angegebene Lösung korrekt - bravo!

      Offizielle Lösung:
      ----------------
      Spoiler anzeigen

      Der 1. Halbkreis startet bei 0 und landet auf der x-Achse bei 0 + 2*(4-0) = 8.
      Der 2. Halbkreis startet deshalb bei 8 und dreht um 6, landet also bei 8 + 2*(6-8) = 8 - 4 = 4.
      Der 3. Halbkreis startet daher bei 4, dreht sich um 3 und landet schließlich bei 4 + 2*(3-4) = 4 - 2 = 2.
      Antwort: Der dritte Halbkreis landet bei x=2.