Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch

Moderationshinweis von herbivore (18.01.2010 - 10:01:28):

Bitte beachtet folgenden Hinweise und Regeln:

So ein Thread erfordert Disziplin! Bitte nur Aufgaben und Lösungen posten! Keine Kommentare!

Denn wenn zu jeder Lösung 20 Beiträge kommen, die auf irgendwelche Kleinigkeiten hinweisen, die man anders machen könnte oder sogar alles in eine endlose prinzipielle Diskussion über Programmierstil (sagen wir z.B. über den Gebrauch von goto) abgleitet, wird der Thread vollkommen unübersichtlich. Also bleibt streng bei der Sache. Eine Aufgabe gilt als gelöst, wenn der Code das vorgegebene Problem löst, egal wie wie gut oder schlecht der Programmierstil ist.

Postet nur eine Lösung, wenn ihr schon eine neue Aufgabe in petto habt. Nach 24 Stunden ohne neue Aufgabe durch den ersten, der die Aufgabe gelöst hat, darf auch jemand anders die neue Aufgabe stellen.

Bitte postet nur Aufgaben zur Unterhaltung der anderen und nicht welche zu eurem Vorteil. Die Aufgaben sollten in nicht mehr als 50 Zeilen gelöst werden können.

Wenn eine Woche seit dem jeweils letzten Beitrag vergangen ist, ist der Thread wieder frei für eine neue Aufgabe (egal wer die neue Aufgabe stellen möchte und egal ob dieser letzte Beitrag nun eine Aufgabe, eine Nachfrage oder eine Lösung ist und egal ob die Lösung richtig oder falsch war, also einfach: eine Woche Inaktivität = neue Aufgabe erlaubt).

Schreibt mir (herbivore) bitte eine PM, wenn euch noch was einfällt, das geregelt sein sollte.



Hier noch eine Liste der bisher gespielten Aufgaben. Herzlichen Dank an m0rius, der sich diese Mühe - für alle Aufgaben bis zum 1.6.2011 - gemacht hat. Links auf spätere Aufgaben und Lösungen wurden von verschiedenen Moderatoren ergänzt.

  1. Zeichen-Pyramidegelöst von dN!3L
  2. Römische Zifferndarstellunggelöst von edsplash
  3. Sierpinski-Dreieck auf der Konsole ausgebengelöst von michlG
  4. Tromino Tiling Algorithmus implementierengelöst von zommi
  5. Berechnung der Quadratzahl ohne Verwendung von * und /gelöst von Corpsegrinder
  6. Rekursive Implementation der Russian Peasant Multiplication / Ancient Egyptian Multiplicationgelöst von der-schlingel
  7. Iterativer Durchlauf eines Binärbaums in Inorder-Reihenfolgegelöst von herbivore
  8. Iterative Lösung für die "Türme von Hanoi"gelöst von dechavue
  9. Iterative Implementierung des Quicksort-Sortieralgorithmus'gelöst von F.Z.
  10. Pascal'sches Dreieck generierengelöst von winSharp93
  11. Algorithmus zur Primfaktorzerlegung implementierengelöst von Uwe81
  12. Test eines Integers auf Zweierpotenzgelöst von herbivore
  13. Erweiterter euklidischer Algorithmus (rekursiv oder iterativ)gelöst von F.Z.
  14. Erweiterter euklidischer Algorithmus (iterativ)gelöst von LuckyGeorge
  15. Lückenlosen Kreis auf der Konsole zeichnengelöst von MarsStein
  16. Mastermind-Zwischenschritt-Bewertunggelöst von m0rius
  17. Schiffe-Versenken Spielfeldgenerierunggelöst von Floste
  18. Rectangle Invadersgelöst von MarsStein
  19. Queue ohne Collections-Namespaces implementierengelöst von Corpsegrinder
  20. Listenklasse als binären Differenzbaum implementierengelöst von herbivore
  21. SyncQueue<T> erweitern: Enqueue blockiert bei voller Queuegelöst von Corpsegrinder
  22. Eigene, threadsafe Matrix-Klasse implementierengelöst von Floste
  23. Berechnung der TCP/IP-Checksumme über ein Arraygelöst von markus111
  24. Sinuskurve auf der Konsole ausgebengelöst von m0rius
  25. Glückliche Zahlen berechnengelöst von Kaji
  26. Liste von Strings sortieren und ohne GUI-Block in einer ListBox anzeigengelöst von edsplash
  27. Bijektives (eineindeutiges) IMap-Objekt erstellengelöst von inflames2k
  28. Interpreter bzw. Parser für mathematische Formeln entwickelngelöst von MarsStein
  29. Galton-Brett auf der Konsolegelöst von talla
  30. Umsetzung eines gegebenen syntaktischen Konstrukts in C# möglich?gelöst von Corpsegrinder
  31. List<T> um FoldLeft() erweiterngelöst von herbivore
  32. Baum depth-first in-order iterativ durchlaufengelöst von Tarion
  33. Russisch Roulettegelöst von dN!3L
  34. Abstand von Zahlenzwillingen in einer Auflistung natürlicher Zahlengelöst von herbivore
  35. Zahlenfolgen möglichst kompakt darstellengelöst von JAck30lena
  36. Conway's Game of Lifegelöst von MarsStein
  37. Wegfindung im Irrgartengelöst von edsplash
  38. Pi mit dem Monte-Carlo-Algorithmus approximierengelöst von prakti08
  39. Gültige Lösung für gegebenes Sudoku ermittelngelöst von Campac68
  40. Parser entwickelngelöst von MarsStein
  41. Bit-Arithmetik zum Indizieren mehrerer Wertegelöst von zommi
  42. Größte, nicht aus gegebenen Zahlen zusammensetzbare Zahl ermittelngelöst von Floste
  43. ISharpPixelShader — Programm zur Erzeugung von Bildern mit C#gelöst von dN!3L
  44. Left Outer Join einer flüchtigen, beliebig großen Enumerationgelöst von gfoidl
  45. Methode verändern, sodass Tests bestanden werdengelöst von Lennart
  46. Erweiterungsmethoden-Knobeleigelöst von Corpsegrinder
  47. Kleinstes gemeinsames Vielfache mehrerer Zahlen ermittelngelöst von zommi
  48. CLR-Internas: unsafe-Pointer-Arithmetik für SubArray-Bindinggelöst von Floste
  49. Kniffel-Spiel: mögliche Ergebnis-Punktzahlen für gegebenen Wurf ermittelngelöst von TheBrainiac
  50. Einfachen Kompressions-Algorithmus entwickelngelöst von herbivore
  51. Polygonzug auf Offenheit überprüfengelöst von Floste
  52. Alle Zahlenkombinationen aus {1, 2, 3, 4, 5, 6, 7, 8, 9} ermittelngelöst von gfoidl
  53. Zahlenrätsel: Ich denke an 2 Zahlen ...gelöst von Spontifixus
  54. Lokalsierten Texteditor mit den Befehlen Cut, Copy, Paste, Undo, Redo in XAML umsetzengelöst von Spontifixus
  55. Eigenen Cache mit Schlüssel-Zugriff erstellengelöst von gfoidl
  56. Code ohne unsafe-Schlüsselwort oder Marshal-Klasse ergänzengelöst von zommi
  57. Kollisionsfindung für Hashfunktion implementierengelöst von Xander
  58. Wochentag zu gegebenem Datum berechnengelöst von inflames2k
  59. Eigene Liste ohne Collections-Namespaces implementierengelöst von winSharp93
  60. Eigene Liste um Reverse()-Methode ergänzengelöst von MarsStein
  61. Prinzip der Kapselung in .NET aushebelngelöst von Scavanger
  62. Programm zum Feuern von Mitarbeitern manipulierengelöst von zommi
  63. Geheimen Text aus .NET-Applikation entschlüsselngelöst von Joetempes
  64. Anwendung dazu bringen, "korrekt" auszugebengelöst von Scavanger
  65. Lösungsstrategie für Stapel-Kartentrick implementierengelöst von Daniel B.
  66. Leveleditor: Zielpunkt vom Startpunkt aus erreichbar?gelöst von Scavanger
  67. Iterative Lösung für das 8-Damen-Problemgelöst von Floste
  68. Konsolenanwendung dazu bringen, "richtig" auszugebengelöst von Scavanger
  69. Probabilistischen Algorithmus zur Primzahlfindung implementierengelöst von Daniel B.
  70. Conway's Game of Life mit grafischer Ausgabegelöst von Sekkiy
  71. Konsolenanwendunganwendung so ergänzen, dass "Gelöst" ausgegeben wirdgelöst von zommi
  72. string-search Algorithmus á la Boyer-Moore — gelöst von niemand
  73. Ostersonntag eines Jahres ermittelngelöst von ProGamer
  74. Doppelte Zeilen entfernengelöst von Alf Ator
  75. Ship & Asteroidgelöst von Daniel B.
  76. 4 Grundrechnungsarten mit Binärzahlengelöst von stes
  77. StringHider und -Findergelöst von myUnderTakeR
  78. Anzahl der Permutationen unter Nebenbedingunggelöst von Daniel B.
  79. Generischer Binärbaum — gelöst von niemand
  80. Sichere Nachrichtenübermittlunggelöst von Floste
  81. Synthesizer mit OpenALgelöst von Floste
  82. Ausgabe eines 2D-Arrays, aber schöngelöst von stes
  83. MouseBall - kleines Ball-Spielgelöst von Mao
  84. Keyword-Highlightergelöst von Alf Ator und gelöst von herbivore
  85. Regex-Pattern in normalen Code ausprogrammierengelöst von dN!3L
  86. Regex-Pattern mit dem Readable Regular Expressions API aufbauenteilweise gelöst von pdelvo, eigene Lösung von dN!3L
  87. Termine im Kalender grafisch anordnengelöst von herbivore
  88. Dutch national flag problemgelöst von dN!3L
  89. Vigenère-Verschlüsselung knackengelöst von Taipi88
  90. Permutations-Chiffre knackengelöst von Scavanger
  91. Pseudozufallsgenerator in (max.) 1,5 Programmzeilengelöst von MarsStein
  92. Erweiterungsmethode für rekursives Durchlaufen eines Baumsgelöst von DerKleineTomy
  93. Nichtdeterministischer Kellerautomatgelöst von DerKleineTomy
  94. Mandelbrot-Menge zeichnen — ungelöst
  95. Binärzahlen addierengelöst von Scavanger
  96. Zufälliges Element aus einer Auflistung (IEnumerable) mit linearem Aufwand auswählengelöst von Darth Maim
  97. Quinegelöst von Quadsoft
  98. in Zahl verstecktes Wort ermittelngelöst von Alf Ator
  99. Zahlen in Zahlworte umwandelngelöst von jannemann13
  100. Zahlworte in Zahlen umwandeln — ungelöst
  101. Code für Generierung eines gegebenen Bildes ermittelngelöst von Alf Ator
  102. Schach: Pferd und Rösselsprunggelöst von xxxprod
  103. FullMatch - Prüfen ob ein Pattern auf einen Text passt (ohne Regex)gelöst von xxxprod

  104. PS: Wenn euch die Aufgaben in diesem Thread nicht reichen: Auf http://pexforfun.com/, einer Art "automatisiertem Programmierspiel", gibt es noch viele weitere interessante Aufgaben.

    Dort bekommt man einen Quellcode-Rahmen angezeigt, den man entsprechend der Aufgabe ausfüllen muss, nur dass die Aufgabe nicht als Text vorgeben ist, sondern man den Code auf Verdacht ändert und sich nach jeder Code-Änderung anzeigen lassen kann, mit welchen Testdaten der White-Box-Testdatengenerator PEX das eigene Programm füttert, welche Ausgabe es daraus errechnet und was das jeweils erwünschte Ergebnis ist. Das Prinzip hat ein bisschen was von Mastermind, wo man auch eine mögliche Lösung ausprobiert und vom Gegenüber Hinweise bekommt, was schon stimmt und was noch nicht.

abra_joe
myCSharp.de - Member



Dabei seit:
Beiträge: 27

Themenstarter:

Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch

beantworten | zitieren | melden

Hier soll von nun an ein Programmierspiel gestartet werden.

Es wird eine kleine Aufgabe vorgegeben, die der nachfolgende Poster zu bewältigen hat. Wie er die Problemlösung damit umsetzt, ist egal.
Hauptsache der Code liefert das gewünschte Ergebnis.

Derjenige, der die Aufgabe am schnellsten löst, darf dann eine eigene stellen.

Regeln:
Lediglich kleine Aufgaben, keine "Projekte" wie: Programmiere ein Gästebuch.
Jegliche Quellen müssen angegeben werden. Wer kann, sollte jedoch darauf verzichten.
Ein schön eingerückter Code, sodass es anderen Usern möglich ist, zu sehen, wie man an das Ergebnis gekommen ist.

Also hier mal die erste Aufgabe:
Eine Pyramide soll je nach Benutzereingabe erstellt werden.
Diese Benutzereingabe soll die Basis für die Pyramide sein:
Benutzereingabe "H":
[frame]
[CENTER]
A
ABA
ABCBA
ABCDCBA
ABCDEDCBA
ABCDEFEDCBA
ABCDEFGFEDCBA
ABCDEFGHGFEDCBA[/CENTER]
[/frame]

Viel spaß
Dieser Beitrag wurde 6 mal editiert, zum letzten Mal von abra_joe am .
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Also ich find die Idee doch nett.

static void Main(string[] args)
{
    int end = Console.ReadKey().KeyChar - 'A';
    char[] s = new String(' ', end*2+1).ToCharArray();
    Console.Clear();
    for (int c = 0; c ≤ end; c++)
    {
        s[end + c] = s[end - c] = (char)('A' + c);
        Console.WriteLine(new String(s));
    }
}

//EDIT: DAMN! Die Pyramide ist genau falschrum ! *gruml* :D


Ich find den schon relativ elegant. Vielleicht geht aber noch besser ? (=kürzer, schöner, cooler)

Ich versuch mal was auszudenken (kann aber etwas dauern ;) )

beste Grüße
zommi
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von zommi am .
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von zommi
Vielleicht geht aber noch besser ? (=kürzer, schöner, cooler)
Hehe:


private static string foo(char target)
{
	return String.Join("\r\n",
			 Enumerable
				 .Range(1,target-'A'+1)
				 .Select(count => Enumerable
					 .Range('A',count)
					 .Select(index => (char)index))
				 .Select(sequence => sequence.Concat(sequence.Reverse().Skip(1)))
				 .Select(sequence => "".PadLeft(target-'A'-sequence.Count()/2)+new String(sequence.ToArray()))
				 .ToArray());
}

Gruß,
dN!3L
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

Römische Zifferndarstellung

beantworten | zitieren | melden

Zitat von abra_joe
dN!3L darf die nächste Aufgabe stellen
Hm... also:
Eine Zahl soll in eine Zeichenkettenrepräsentation überführt werden, die diese Zahl in römischen Ziffern darstellt.
Einschränkungen: Ziffern I bis M. Subtraktionsregel.
Beispiel: 1984 -> MCMLXXXIV
private Nachricht | Beiträge des Benutzers
edsplash
myCSharp.de - Member

Avatar #avatar-3111.jpg


Dabei seit:
Beiträge: 411

beantworten | zitieren | melden


static void Main(string[] args)
    {
      int originalNumber = 1984;
      StringBuilder romNumber = new StringBuilder();

      Queue<KeyValuePair<string, int>> queue = new Queue<KeyValuePair<string, int>>();
      queue.Enqueue(new KeyValuePair<string, int>("M", 1000));
      queue.Enqueue(new KeyValuePair<string, int>("D", 500));
      queue.Enqueue(new KeyValuePair<string, int>("C", 100));
      queue.Enqueue(new KeyValuePair<string, int>("L", 50));
      queue.Enqueue(new KeyValuePair<string, int>("X", 10));
      queue.Enqueue(new KeyValuePair<string, int>("V", 5));
      queue.Enqueue(new KeyValuePair<string, int>("I", 1));

      foreach (KeyValuePair<string, int> pair in queue)
      {
        int times = (int)Math.Round((double)(originalNumber / pair.Value), 0);
        originalNumber -= pair.Value * times;

        for (int k = 0; k < times; k++)
        {
          romNumber.Append(pair.Key);
        }
      }

      Console.WriteLine(romNumber.ToString());
    }

[edit] Mist, hab ich doch glatt das mit der Subtraktionsregel übersehen
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von edsplash am .
using Skill
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von zommi
//EDIT: DAMN! Die Pyramide ist genau falschrum!
Zitat von edsplash
[edit] Mist, hab ich doch glatt das mit der Subtraktionsregel übersehen
Hehe, das wäre hier doch der ideale Platz, um mal TDD zu üben.
Der Fragensteller gibt zur Aufgabenstellung ein Interface und einen Test (oder mehrere vor), die bestanden werden müssen... :D
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
edsplash
myCSharp.de - Member

Avatar #avatar-3111.jpg


Dabei seit:
Beiträge: 411

beantworten | zitieren | melden

Zitat von dN!3L

Hehe, das wäre hier doch der ideale Platz, um mal TDD zu üben.

Da kann man sich mal über die Effizienz amüsieren ;) Zwei Aufgaben und zweimal in der ersten Lösung die gepostet wurde ein elementarer Fehler, der mit einer Überprüfung der Aufgabenstellung vor dem Post hätte gesehen werden können.

Nichtsdestotrotz meine endgültige Lösung:


private static string DecimalToRoman(int originalNumber)
    {
      string romanNumber = string.Empty;

      Dictionary<int, char> digits = new Dictionary<int, char>();
      digits.Add(1000, 'M');
      digits.Add(500, 'D');
      digits.Add(100, 'C');
      digits.Add(50, 'L');
      digits.Add(10, 'X');
      digits.Add(5, 'V');
      digits.Add(1, 'I');

      int[] decades = new int[4];
      decades[0] = originalNumber % 10;
      decades[1] = originalNumber % 100 - decades[0];
      decades[2] = originalNumber % 1000 - decades[1] - decades[0];
      decades[3] = originalNumber % 10000 - decades[2] - decades[1] - decades[0];

      for (int k = 3; k ≥ 0; k--)
      {
        int decadeValue = decades[k];
        int decadeFloor = (int)Math.Pow(10, k);
        int times = decadeValue / decadeFloor;
        Action standardConvert = () =>
        {
          for (int i = 0; i < times; i++)
            romanNumber += digits[decadeFloor];
        };

        if (times ≥ 5)
        {
          if (times == 9)
          {
            romanNumber += digits[decadeFloor];
            romanNumber += digits[10 * decadeFloor];
          }
          else
          {
            decadeValue -= 5 * decadeFloor;
            romanNumber += digits[5 * decadeFloor];
            times = decadeValue / decadeFloor;
            standardConvert();
          }
        }
        else
        {
          if (times == 4)
          {
            if (decadeFloor == 1000)
              standardConvert();
            else
            {
              romanNumber += digits[decadeFloor];
              romanNumber += digits[5 * decadeFloor];
            }
          }
          else
            standardConvert();
        }
      }
      return romanNumber;
    }

Wäre wohl mit weniger Code gegangen, aber ist das was mir auf die Schnelle so gelungen ist ;)

EDIT: ujr hat mich auf einen 'kleinen' Bug in meiner Lösung aufmerksam gemacht, welchen ich mittlerweile beseitigt habe. Das alte Beispiel mit dem Fehler wurde durch ein neues ersetzt ;)
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von edsplash am .
using Skill
private Nachricht | Beiträge des Benutzers
edsplash
myCSharp.de - Member

Avatar #avatar-3111.jpg


Dabei seit:
Beiträge: 411

beantworten | zitieren | melden

Hallo Zusammen

Hier meine Aufgabe:

Ziel ist folgendes Konstrukt dynamisch auf der Konsole auszugeben

#
##
# #
####
#   #
##  ##
# # # #
########
#       #
##      ##
# #     # #
####    ####
#   #   #   #
##  ##  ##  ##
# # # # # # # #
################
#               #
##              ##
# #             # #
####            ####
#   #           #   #
##  ##          ##  ##
# # # #         # # # #
########        ########
#       #       #       #
##      ##      ##      ##
# #     # #     # #     # #
####    ####    ####    ####
#   #   #   #   #   #   #   #
##  ##  ##  ##  ##  ##  ##  ##
# # # # # # # # # # # # # # # #
################################

Die gesetzten Pixel/Buchstaben ergeben sich jeweils aus dem direkt über diesem liegendem Feld und dem links darüberligendem.
Die Linke obere Ecke ist als Ausgangspunkt bekannt.

Viel Spass und Vielen Dank an Floste für den Tipp
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von edsplash am .
using Skill
private Nachricht | Beiträge des Benutzers
michlG
myCSharp.de - Experte

Avatar #avatar-2909.png


Dabei seit:
Beiträge: 3652
Herkunft: Naturns - Südtirol - Italien

beantworten | zitieren | melden

Hallo Leute,

hier die Lösung dazu


    private static void PrintTriangles(int count)
    {
      bool[,] arr = new bool[count,count];
      arr[0, 0] = true;
      Console.WriteLine("#");

      for (int i = 1; i < count; i++)
      {
        arr[i, 0] = true;
        Console.Write("#");
        for (int j = 1; j < count; j++)
        {
          arr[i, j] = arr[i - 1, j] ^ arr[i - 1, j - 1];
          Console.Write(arr[i,j] ? "#" : " ");
        }
        Console.WriteLine();
      }
    }

Einfach PrintTriangles(32) aufrufen dann gibts die geforderte Ausgabe

Die neue Aufgabe folgt gleich

Gruss
Michael
private Nachricht | Beiträge des Benutzers
michlG
myCSharp.de - Experte

Avatar #avatar-2909.png


Dabei seit:
Beiträge: 3652
Herkunft: Naturns - Südtirol - Italien

beantworten | zitieren | melden

Hallo,

hier die neue Aufgabe.

Erstellt einen sog. Tromino Tiling Algorithmus.
Der ein 2^n mal 2^n großen Array mit den einzelnen Trominos aufteilt.

Ein Tromino wäre also sowas

0000
0220
0210
0000

Am Anfang muss ein Loch (1) an einer beliebigen Position gesetzt werden.
Dann wird die ganze Fläche schön mit den Trominos ausgefüllt.
Gestartet wird mit der 2, weiter gehts mit der 3 usw. Am Ende muss es halt schön foll sein.

Am Bild seht ihr wie der Array zu beginn aussieht. Also nur das Loch (1) ist bekannt.
Am Ende muss es dann so wie rechts gezeigt ausgegeben werden

Die Ausgabe sollte in der Konsole sein (wenn sich das Zeug aufgrund der unterschiedlichen Zeichenlänge nicht zusehr verschiebt).

Viel Spass damit

Gruss
Michael
Attachments
private Nachricht | Beiträge des Benutzers
trib
myCSharp.de - Member



Dabei seit:
Beiträge: 691

beantworten | zitieren | melden

Da ich überhaupt nicht verstanden habe was MichlG mir mit den Trominos sagen wollte, habe ich mal Google konsultiert und eine grafische Erklärung gefunden.
Die wollte ich euch nicht vorenthalten:

http://oneweb.utc.edu/~Christopher-Mawata/trominos/

Gruß
TriB
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Ganz schön schwer, wenn man sich selbst was ausdenkt.
Ich hab einfach mal brute force try und error gemacht, braucht ewig für n≥5, aber die in dem bild da sind eh nur n=3:

public static void Main()
        {
            while (true)
            {
                int xpos, ypos, n;
                do { Console.Write("X="); }
                while (!int.TryParse(Console.ReadLine(), out xpos));
                do Console.Write("Y=");
                while (!int.TryParse(Console.ReadLine(), out ypos));
                do Console.Write("N=");
                while (!int.TryParse(Console.ReadLine(), out n));
                int num = 1 << (byte)n;
                int[,] feld = new int[num, num];
                feld[xpos, ypos] = -1;
                if (!BruteForce(feld, num, 1))
                {
                    Console.WriteLine("Nicht gelöst");
                }
                else
                {
                    for (int y = 0; y < num; y++)
                    {
                        for (int x = 0; x < num; x++)
                        {
                            Console.Write(feld[x, y].ToString().PadRight(3));
                        }
                        Console.WriteLine();
                        Console.WriteLine();
                    }
                }
            }
        }


        private static bool BruteForce(int[,] feld, int num, int tiefe)
        {
            for (int y = 0; y < num; y++)
                for (int x = 0; x < num; x++)
                    if (feld[x, y] == 0)
                    {
                        Point[] points = new Point[3];
                        for (int square = 0; square < 4; square++)
                        {
                            int sx = (square & 1) + x - 1;
                            int sy = ((square & 2) >> 1) + y - 1;
                            for (int ep = 0; ep < 4; ep++)
                            {
                                int i = 0;
                                for (int p = 0; p < 4; p++)
                                {
                                    if (p != ep)
                                        points[i++] = new Point(
                                            (p & 1) + sx,
                                            ((p & 2) >> 1) + sy);
                                    else if (((p & 1) + sx == x) && (((p & 2) >> 1) + sy) == y) goto bad_ep;
                                }
                                if (TrominoTesten(feld, num, tiefe, points)) return true;
                            bad_ep: { }
                            }
                        }
                        return false;
                    }
            return true;
        }

        private static bool TrominoTesten(int[,] feld, int num, int tiefe, IEnumerable<Point> points)
        {
            foreach (Point p in points)
            {
                if (p.X < 0 || p.X ≥ num) return false;
                if (p.Y < 0 || p.Y ≥ num) return false;
                if (feld[p.X, p.Y] != 0) return false;
            }
            foreach (Point p in points)
                feld[p.X, p.Y] = tiefe;
            if (BruteForce(feld, num, tiefe+1)) return true;
            foreach (Point p in points)
                    feld[p.X, p.Y] = 0;
            return false;
        }
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
Th69
myCSharp.de - Experte

Avatar #avatar-2578.jpg


Dabei seit:
Beiträge: 4093

beantworten | zitieren | melden

Unter http://www.projektwoche.jku.at/2004/p4_1.pdf ist sowohl der Beweis als auch ein effizienter Algorithmus für das Tromino-Problem angegeben (2. Problem).
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Jea, ich habs!
Hab Floste Programmrahmen als Basis genommen.

using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;

namespace Tromino
{
    class Program
    {
        public static void Main()
        {
            while (true)
            {
                int xpos, ypos, n;
                do { Console.Write("X="); }
                while (!int.TryParse(Console.ReadLine(), out xpos));
                do Console.Write("Y=");
                while (!int.TryParse(Console.ReadLine(), out ypos));
                do Console.Write("N=");
                while (!int.TryParse(Console.ReadLine(), out n));
                int num = 1 << (byte)n;
                int[,] feld = new int[num, num];
                feld[xpos, ypos] = -1;

                globalCount = 0;
                tile(feld, new Point(xpos, ypos));

                char[,] res = renderOutlineOfField(feld);

                res[xpos * 2 + 1, ypos * 2 + 1] = 'X';

                {
                    for (int y = 0; y < res.GetLength(0); y++)
                    {
                        for (int x = 0; x < res.GetLength(1); x++)
                        {
                            Console.Write(res[x, y]);
                        }
                        //Console.WriteLine();
                        Console.WriteLine();
                    }
                }
            }
        }


        static int globalCount = 0;

        private static void tile(int[,] feld, Point hole)
        {
            tile(feld, Point.Empty, hole, new Size(feld.GetLength(0), feld.GetLength(1)));
        }

        // *********************************************************
        // *********************************************************
        // *********************************************************
        // Kern des Algos (gemäß Divide and Conquer)
        private static void tile(int[,] feld, Point fieldStart, Point hole, Size size)
        {
            int trominoSymbol = globalCount++;

            // Rekursionsabbruch bei trivialem Fall (Conquer)
            if (size == new Size(2, 2))
            {
                for (int x = fieldStart.X; x < (fieldStart + size).X; x++)
                    for (int y = fieldStart.Y; y < (fieldStart + size).Y; y++)
                    {
                        if (!(x == hole.X && y == hole.Y))
                        {
                            feld[x, y] = trominoSymbol;
                        }
                    }
                return;
            }

            // Divide-Schritt (in 4 Unterprobleme)
            Size halfSize = new Size(size.Width / 2, size.Height / 2);
            for (int i = 0; i < 2; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    Point subFieldStart = fieldStart + new Size(halfSize.Width * i, halfSize.Height * j);
                    Point newHole = fieldStart + halfSize - new Size(1 - i, 1 - j);
                    if (new Rectangle(subFieldStart, halfSize).Contains(hole))
                    {
                        newHole = hole;
                    }
                    else
                    {
                        feld[newHole.X, newHole.Y] = trominoSymbol;
                    }
                    tile(feld, subFieldStart, newHole, halfSize);
                }
            }
        }
        // *********************************************************
        // *********************************************************
        // *********************************************************


        // Diese Method ist nur Deko, macht was hübsches, ansehliches draus
        static char[,] renderOutlineOfField(int[,] feld)
        {
            char[,] res = new char[feld.GetLength(0) * 2 + 1, feld.GetLength(1) * 2 + 1];
            //rand
            for (int x = 1; x < res.GetLength(0) - 1; x++)
                res[x, 0] = res[x, res.GetLength(1) - 1] = symbols[10];
            for (int y = 1; y < res.GetLength(1) - 1; y++)
                res[0, y] = res[res.GetLength(0) - 1, y] = symbols[5];
            //ecken
            res[0, 0] = symbols[6];
            res[res.GetLength(0) - 1, 0] = symbols[12];
            res[0, res.GetLength(1) - 1] = symbols[3];
            res[res.GetLength(0) - 1, res.GetLength(1) - 1] = symbols[9];

            for (int x = 1; x < res.GetLength(0) - 1; x++)
            {
                for (int y = 1; y < res.GetLength(1) - 1; y++)
                {
                    int selection = 0;
                    if (feld[(x - 1) / 2, (y - 1) / 2] != feld[(x - 0) / 2, (y - 1) / 2])
                        selection |= 1;
                    if (feld[(x - 0) / 2, (y - 1) / 2] != feld[(x - 0) / 2, (y - 0) / 2])
                        selection |= 2;
                    if (feld[(x - 1) / 2, (y - 0) / 2] != feld[(x - 0) / 2, (y - 0) / 2])
                        selection |= 4;
                    if (feld[(x - 1) / 2, (y - 1) / 2] != feld[(x - 1) / 2, (y - 0) / 2])
                        selection |= 8;
                    res[x, y] = symbols[selection];
                }
            }
            return res;
        }

        static char[] symbols = new char[] { ' ', '?', '?', '\u2514', '?', '\u2502', '\u250C', '\u251C', '?', '\u2518', '\u2500', '\u2534', '\u2510', '\u2524', '\u252C', '\u253C' };

    }
}
(benötigt wegen dem Drawing-Namespace nochn Verweis auf System.Drawing)

beste Grüße
zommi
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von zommi am .
Attachments
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

Ja dann hau ma die nächste Aufgabe rein :D
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Also meine Aufgabe:

programmiere eine einzige Methode f(n) zum Berechnen der Quadratzahl n^2.
Allerdings sind * und / nicht zugelassen. Was als arithmetische Operation zugelassen ist, sind: + und - .
Ahso und lokale/temporäre Variablen sind natürlich auch nich zugelassen ;)

beste Grüße
zommi
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

Zitat von zommi
Also meine Aufgabe:

programmiere eine einzige Methode f(n) zum Berechnen der Quadratzahl n^2.
Allerdings sind * und / nicht zugelassen. Was als arithmetische Operation zugelassen ist, sind: + und - .
Ahso und lokale/temporäre Variablen sind natürlich auch nich zugelassen ;)

beste Grüße
zommi

Also ich bezweifel, dass es mit nur einer Methode möglich ist ;-) du musst ja irgendwie ne Laufvariable und ne tmp mitgeben. Hab das aber mal in Scala gelöst mit nur "einer" Methode :D

def square(value: Int) = {
    def sq(value: Int, tmp: Int, count: Int): Int = {
      if(count == 0)
        tmp
      else
        sq(value, tmp + value, count-1)
    }
    sq(value, 0, value)
  }
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Zitat
Also ich bezweifel, dass es mit nur einer Methode möglich ist ;-)
Mit nur einer Methode!
Und mit keiner zusätzlichen Variable.
Und ohneMultiplikation.

8)

beste Grüße
zommi
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von zommi am .
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

Okay... wieder was gelernt... den Weg kannte ich noch nicht :-)


public static int square(int val)
{
  if (val == 1)
    return 1;
  else
    return val + (val - 1) + square(val - 1);
}

Achso... Quelle: http://en.wikipedia.org/wiki/Square_(algebra)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Corpsegrinder am .
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Jup, perfekt

(wobei ich bei n=0 die Abbruch-Bedingung gemacht hätte)
Ich lös es noch mit kurzer Erklärung auf:

Berechnung per Rekursion! Wir nutzen aus:
(n+1)² = n² + 2n + 1
Und mit n statt (n+1) ergibt sich dann
n² = (n-1)² + 2*(n-1) + 1
n² = (n-1)² + 2*n - 1
n² = (n-1)² + n + n - 1

Dann noch bei n=0 die Abbruchbedingung mit 0²=0 und fertig ist die Methode.
Als Einzeiler:

square(int n)
{
     return (n==0)?0:square(n-1) + n + n - 1;
}

beste Grüße
zommi
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Zitat von Corpsegrinder
Ja dann hau ma die nächste Aufgabe rein
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

Jajaja... muss ja erstmal was überlegen...

Eine hübsche Rekursive Implementation der Russian Peasant Multiplication / Ancient Egyptian Multiplication...


Viel Spaß :-D
private Nachricht | Beiträge des Benutzers
der-schlingel
myCSharp.de - Member

Avatar #avatar-3239.jpg


Dabei seit:
Beiträge: 820
Herkunft: Österreich/Wien

beantworten | zitieren | melden


        static int RussianMultiply(int factor1, int factor2)
        {
            if (factor1 == 0 || factor2 == 0)
                return 0;

	        int f1 = (int)Math.Floor((double)factor1 / 2);
	        int f2 = factor2 * 2;
        	
	        return ( (factor1 % 2 == 0) ? 0 : factor2 ) + RussianMultiply(f1, f2);
        }
As a man thinketh in his heart, so he is.
- Jun Fan
Es gibt nichts Gutes, außer man tut es.
- Erich Kästner
Krawutzi-Kaputzi
- Kasperl
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Geht das nicht *etwas* einfacher?


int mul(int a,int b)
{
    if(a==0)return 0;
    return (((a&1)==0)?0:b)+mul(a>>1,b<<1);
}
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
der-schlingel
myCSharp.de - Member

Avatar #avatar-3239.jpg


Dabei seit:
Beiträge: 820
Herkunft: Österreich/Wien

beantworten | zitieren | melden

Zitat
Derjenige, der die Aufgabe am schnellsten löst, darf dann eine eigene stellen.

Meine Aufgabe ist es einen iterativer Durchlauf eines Binärbaums in Inorder-Reihenfolge zu kreieren. Der rekursive Algorithmus sieht mit der angegebenen Datenstruktur so aus:


 public class Node
 {
    public Node Left { get; set; }
    public Node Right { get; set; }
    public int Key { get; set; }
 
    public Node()
    {
       Left = null;      
       Right = null;
    }
 }


 public void Inorder(Node n)
 {
   if(n != null)
   {
     Inorder(n.Left);
     Console.WriteLine(n.Key);
     Inorder(n.Right);
   }
 }

Eure Aufgabe ist es einen Algorithmus zu basteln der ohne rekursivem Aufruf auskommt. Sehr hilfreich sind dabei die Stack- sowie die Queue-Datenstrukturen.

Viel Spaß
Dieser Beitrag wurde 7 mal editiert, zum letzten Mal von der-schlingel am .
As a man thinketh in his heart, so he is.
- Jun Fan
Es gibt nichts Gutes, außer man tut es.
- Erich Kästner
Krawutzi-Kaputzi
- Kasperl
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo der-schlingel,

ich liebe iterative Umsetzung von rekursiven Funktionen genauso wie rekursive Funktionen selbst. Deshalb habe ich mich mal ran gemacht.

Ich habe deine Node-Klasse für .NET 2.0 angepasst und eine Komfort-Änderung vorgenommen, aber das Prinzip ist gleich geblieben.

Hier meine Lösung:

using System;
using System.Collections.Generic;

public class NodeDirection
{
   public NodeDirection (Node node)
   {
      _node = node;
      _fLeft = true;
   }

   public bool Left
   {
      get { return _fLeft; }
      set { _fLeft = value; }
   }
   private bool _fLeft;

   public Node Node
   {
      get { return _node; }
   }
   private Node _node;
}

public class Node
{
   public Node Left
   {
      get { return _nodeLeft; }
      set { _nodeLeft = value; }
   }
   private Node _nodeLeft;

   public Node Right
   {
      get { return _nodeRight; }
      set { _nodeRight = value; }
   }
   private Node _nodeRight;

   public int Key
   {
      get { return _iKey; }
      set { _iKey = value; }
   }
   private int _iKey;

   public Node (int iKey)
   {
      _nodeLeft  = null;
      _nodeRight = null;
      _iKey      = iKey;
   }

   public void Inorder ()
   {
      Stack <NodeDirection> stk = new Stack <NodeDirection> ();

      // Wurzel zur Bearbeitung setzen
      stk.Push (new NodeDirection (this));

      // Solange noch Knoten zu bearbeiten sind ...
      while (stk.Count > 0) {

         // Anstehenden Konten holen
         NodeDirection nd = stk.Peek ();

         // Prüfen, ob von dem anstehenden Knoten der linke oder rechte
         // Unterknoten bearbeitet werden muss.
         if (nd.Left) {

            // Linken Unterknoten als schon berücksichtigt kennzeichnen
            nd.Left = false;

            // Linken Unterknoten (falls vorhanden) zur Bearbeitung setzen
            if (nd.Node.Left != null) {
               stk.Push (new NodeDirection (nd.Node.Left));
            }
         } else {

            // Knoten selbst behandeln
            Console.WriteLine (nd.Node.Key);

            // Rechten Unterknoten als schon berücksichtigt kennzeichnen
            stk.Pop ();

            // Rechten Unterknoten (falls vorhanden) zur Bearbeitung setzen
            if (nd.Node.Right != null) {
               stk.Push (new NodeDirection (nd.Node.Right));
            }
         }
      }
   }
}

static class App
{
   public static void Main (string [] astrArg)
   {
      Node node = new Node (1);

      node.Left  = new Node (2);
      node.Right = new Node (3);

      node.Left.Right = new Node (4);

      node.Right.Left = new Node (5);

      node.Inorder ();
   }
}

herbivore
private Nachricht | Beiträge des Benutzers
der-schlingel
myCSharp.de - Member

Avatar #avatar-3239.jpg


Dabei seit:
Beiträge: 820
Herkunft: Österreich/Wien

beantworten | zitieren | melden

So ähnlich hatte ich mir das auch gedacht. Dann darf Herbivore die nächste Aufgabe stellen.
As a man thinketh in his heart, so he is.
- Jun Fan
Es gibt nichts Gutes, außer man tut es.
- Erich Kästner
Krawutzi-Kaputzi
- Kasperl
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,

dann hätte ich gerne ein iteratives Türme von Hanoi. Natürlich eine selbst entwickelte Lösung, möglichst ganz ohne Verwendung einer Stack(artigen)-Klasse (ja, das geht).
Zitat von Wikipedia
Das Spiel besteht aus drei Stäben A, B und C, auf die mehrere gelochte Scheiben gelegt werden, alle verschieden groß. Zu Beginn liegen alle Scheiben auf Stab A, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist es, den kompletten Scheiben-Stapel von A nach C zu versetzen.

Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes auf einen der beiden anderen Stäbe gelegt werden, vorausgesetzt, dort liegt nicht schon eine kleinere Scheibe. Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Feld der Größe nach geordnet.

EDIT: Die zu schreibenden Methode Move soll Ausgaben der Form

"Nr. 4 von 1 nach 3"

machen, was bedeutet, dass in diesem Zug, die Scheibe Nummer 4 von Stab 1 (bzw. A) auf Stab 3 (bzw. C) verschoben wird. Die Scheibe Nummer 1 ist die kleinste, die Scheibe Nummer n ist die größte, wobei die Höhe n des Ausgangsturms als Parameter an Move übergeben wird.

herbivore
private Nachricht | Beiträge des Benutzers
dechavue
myCSharp.de - Member

Avatar #avatar-2999.png


Dabei seit:
Beiträge: 180
Herkunft: Österreich

beantworten | zitieren | melden

Als Fan von Türme von Hanoi musst ich es natürlich gleich probieren.

Hier meine Lösung:

 
        static void Main(string[] args) {
            for (int i = 1; i < 7; i++) {
                Console.WriteLine("== {0} =============================", i);
                Move(i);
            }
        }

        static void Move(int n) {
            Stack<int>[] sticks = new Stack<int>[3];

            for (int i = 0; i < sticks.Length; i++) { 
                sticks[i] = new Stack<int>(); 
            }
            //Fill Stick 1
            for (int i = n; i > 0; i--) {
                sticks[0].Push(i);
            }


            int lastTargetStick = -1;


            while (sticks[0].Count > 0 || sticks[1].Count > 0) {
                for (int i = 0; i < sticks.Length; i++) {
                    if (lastTargetStick != i && sticks[i].Count > 0) {
                        if (sticks[(i + 1) % sticks.Length].Count == 0 && sticks[(i + 2) % sticks.Length].Count == 0) {
                            if (sticks[i].Count % 2 == 0) {
                                lastTargetStick = (i + 1) % sticks.Length;
                            } else {
                                lastTargetStick = (i + 2) % sticks.Length;
                            }
                            Console.WriteLine("Nr. {0} von {1} nach {2}", sticks[i].Peek(), i+1, lastTargetStick+1);
                            sticks[lastTargetStick].Push(sticks[i].Pop());
                            break;
                        } else {
                            if (sticks[(i + 1) % sticks.Length].Count > 0 && sticks[i].Peek() > sticks[(i + 1) % sticks.Length].Peek() &&
                                sticks[(i + 2) % sticks.Length].Count > 0 && sticks[i].Peek() > sticks[(i + 2) % sticks.Length].Peek()) {
                                continue;
                            }
                            if ((sticks[(i + 1) % sticks.Length].Count == 0 || sticks[i].Peek()      < sticks[(i + 1) % sticks.Length].Peek())    && 
                                (sticks[(i + 1) % sticks.Length].Count > 0 && sticks[i].Peek() % 2 != sticks[(i + 1) % sticks.Length].Peek() % 2 ||
                                 sticks[(i + 2) % sticks.Length].Count > 0 && sticks[i].Peek() % 2 == sticks[(i + 2) % sticks.Length].Peek() % 2 ||
                                 sticks[(i + 2) % sticks.Length].Count > 0 && sticks[i].Peek()      > sticks[(i + 2) % sticks.Length].Peek())) {
                                lastTargetStick = (i + 1) % sticks.Length;
                            } else {
                                lastTargetStick = (i + 2) % sticks.Length;
                            }
                            Console.WriteLine("Nr. {0} von {1} nach {2}", sticks[i].Peek(), i+1, lastTargetStick+1);
                            sticks[lastTargetStick].Push(sticks[i].Pop());
                            break;
                        }
                    }
                }
            }
            
        }
    }

Ich hoffe Stacks als Repräsentation der Stäbe sind erlaubt, sonst baue ich es noch um auf Arrays.
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

Zitat
Ich hoffe Stacks als Repräsentation der Stäbe sind erlaubt
siehe:
Zitat von bedingung von herbivore
ohne Verwendung einer Stack(artigen)-Klasse