Laden...

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

Erstellt von abra_joe vor 14 Jahren Letzter Beitrag vor 3 Jahren 771.494 Views
Hinweis von herbivore vor 14 Jahren

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

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.

A
abra_joe Themenstarter:in
23 Beiträge seit 2008
vor 14 Jahren
Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch

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ß

1.361 Beiträge seit 2007
vor 14 Jahren

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 😄

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

2.891 Beiträge seit 2004
vor 14 Jahren

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

2.891 Beiträge seit 2004
vor 14 Jahren
Römische Zifferndarstellung

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

390 Beiträge seit 2008
vor 14 Jahren

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

using Skill

2.891 Beiträge seit 2004
vor 14 Jahren

//EDIT: DAMN! Die Pyramide ist genau falschrum!

[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... 😁

390 Beiträge seit 2008
vor 14 Jahren

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

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 😉

using Skill

390 Beiträge seit 2008
vor 14 Jahren

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

using Skill

3.430 Beiträge seit 2007
vor 14 Jahren

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

3.430 Beiträge seit 2007
vor 14 Jahren

Hallo,

hier die neue Aufgabe.

Erstellt einen sog. Tromino Tiling Algorithmus.
Der ein 2n mal 2n 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

T
708 Beiträge seit 2008
vor 14 Jahren

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

1.130 Beiträge seit 2007
vor 14 Jahren

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!

4.928 Beiträge seit 2008
vor 14 Jahren

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).

1.361 Beiträge seit 2007
vor 14 Jahren

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

C
401 Beiträge seit 2007
vor 14 Jahren

Ja dann hau ma die nächste Aufgabe rein 😄

1.361 Beiträge seit 2007
vor 14 Jahren

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

C
401 Beiträge seit 2007
vor 14 Jahren

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 😄


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)
  }

1.361 Beiträge seit 2007
vor 14 Jahren

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

C
401 Beiträge seit 2007
vor 14 Jahren

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)

1.361 Beiträge seit 2007
vor 14 Jahren

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

1.361 Beiträge seit 2007
vor 14 Jahren

Ja dann hau ma die nächste Aufgabe rein 😁

😁

C
401 Beiträge seit 2007
vor 14 Jahren

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

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

Viel Spaß 😄

799 Beiträge seit 2007
vor 14 Jahren

        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
1.130 Beiträge seit 2007
vor 14 Jahren

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);
}

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

799 Beiträge seit 2007
vor 14 Jahren

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ß

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
49.485 Beiträge seit 2005
vor 14 Jahren

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

799 Beiträge seit 2007
vor 14 Jahren

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
49.485 Beiträge seit 2005
vor 14 Jahren

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).

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

179 Beiträge seit 2006
vor 14 Jahren

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.

Gelöschter Account
vor 14 Jahren

Ich hoffe Stacks als Repräsentation der Stäbe sind erlaubt

siehe:

ohne Verwendung einer Stack(artigen)-Klasse

179 Beiträge seit 2006
vor 14 Jahren

Ich hatte es sinngemäs so verstanden: Keine Stacks um die Rekursive Variante iterativ zu implementieren.

Aber gut, dann hier das ganze mit Listen


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

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

            for (int i = 0; i < sticks.Length; i++) {
                sticks[i] = new List<int>();
            }
            //Fill Stick 1
            for (int i = n; i > 0; i--) {
                sticks[0].Add(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][sticks[i].Count-1], i + 1, lastTargetStick + 1);
                            sticks[lastTargetStick].Add(sticks[i][sticks[i].Count-1]);
                            sticks[i].RemoveAt(sticks[i].Count - 1);
                            break;
                        } else {
                            if (sticks[(i + 1) % sticks.Length].Count > 0 && sticks[i][sticks[i].Count - 1] > sticks[(i + 1) % sticks.Length][sticks[(i + 1) % sticks.Length].Count -1] &&
                                sticks[(i + 2) % sticks.Length].Count > 0 && sticks[i][sticks[i].Count - 1] > sticks[(i + 2) % sticks.Length][sticks[(i + 2) % sticks.Length].Count - 1]) {
                                continue;
                            }
                            if ((sticks[(i + 1) % sticks.Length].Count == 0 || sticks[i][sticks[i].Count - 1] < sticks[(i + 1) % sticks.Length][sticks[(i + 1) % sticks.Length].Count - 1]) &&
                                (sticks[(i + 1) % sticks.Length].Count > 0 && sticks[i][sticks[i].Count - 1] % 2 != sticks[(i + 1) % sticks.Length][sticks[(i + 1) % sticks.Length].Count - 1] % 2 ||
                                 sticks[(i + 2) % sticks.Length].Count > 0 && sticks[i][sticks[i].Count - 1] % 2 == sticks[(i + 2) % sticks.Length][sticks[(i + 2) % sticks.Length].Count - 1] % 2 ||
                                 sticks[(i + 2) % sticks.Length].Count > 0 && sticks[i][sticks[i].Count - 1] > sticks[(i + 2) % sticks.Length][sticks[(i + 2) % sticks.Length].Count - 1])) {
                                lastTargetStick = (i + 1) % sticks.Length;
                            } else {
                                lastTargetStick = (i + 2) % sticks.Length;
                            }
                            Console.WriteLine("Nr. {0} von {1} nach {2}", sticks[i][sticks[i].Count - 1], i + 1, lastTargetStick + 1);
                            sticks[lastTargetStick].Add(sticks[i][sticks[i].Count - 1]);
                            sticks[i].RemoveAt(sticks[i].Count - 1);
                            break;
                        }
                    }
                }
            }
            
        }

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo dechavue,

Stacks zur Repräsentation des Inhalts der Stäbe sind schon ok. Daran habe ich gar nicht gedacht, weil der Inhalt der Stäbe für die Ausgabe der Zugfolge nicht benötigt wird. Oder anders ausgedrückt, um ausgeben zu können, welche Scheibe man im x-ten Zug von wo nach wo bewegen muss, braucht man keine Repräsentation des Inhalts der Stäbe, sondern kann das alleine aus der Nummer des Zugs (und der Höhe des Anfangsturms) ausrechnen. Siehe Gibt es Rekursionen die sich nicht in eine Iteration umwandeln lassen?.

Insofern war schon deine erste Lösung ok. Du bist also mit der nächsten Aufgabe dran.

(Wobei ich noch verstehen muss, wie deine Lösung funktioniert. Ich habe erstmal nur die Ausgabe überprüft, um den Fortgang dieses Threads nicht zu bremsen. Vielleicht sagst du, wenn du deine Aufgabe stellst, nebenbei auch noch was zu der Idee deines Hanoi-Lösungsansatzes).

herbivore

179 Beiträge seit 2006
vor 14 Jahren

Gut, dann bleiben wir gleich bei Iterativen Varianten.
Ich hätte gerne eine iterative Implementierung des Quicksort

Zu meiner Lösung:
Ich am iPhone ein TvH Spiel, bei dem die Scheiben immer abwechseld gefärbt sind.
Mir ist dann mal aufgefallen, dass beim optimalen Lösen niemals 2 gleichfarbige Scheiben aufeinanderliegen.
Daraus, und aus der Start-Bedingung, dass bei einer geraden Stapelhöhe zuerst auf das "Nicht-Zielfeld" gelegt werden muss und bei einer Ungeraden Stapelhöhe der erste Zug auf das Zielfeld erfolgen muss, ergibt sich der Ablauf von selbst:
Das nächste Ziel ist immer der Stein, mit einer anderen Farbe, bei dem die Breite größer ist, oder ein leeres Feld.
Wichtig ist noch, dass wenn beide Ziele möglich wären, das nicht leere Feld bevorzugt wird.
Die Quelle ergibt sich daraus, dass der zuletzt umgelegte Stein nicht bewegt werden darf + welcher andere Stein umgelegt werden kann.
Die abwechselnden Farben repräsentieren bei mir die Scheibenbreite % 2

Ich habe noch einen Ablauf eines 3er und 4er turms in den Anhang gegeben, zum besseren Verständnis des "Farb - Systems"

Nachtrag: Ich sehe gerade, bei meinem algo könnte man den ersten Zweig des ifs ( if (sticks[(i + 1) % sticks.Length].Count == 0 && sticks[(i + 2) % sticks.Length].Count == 0) {) komplett aus den Schleifen herausziehen, da es nur beim ersten Durchlauf true sein kann. Dann wäre der Algo eventuell auch etwas verständlicher.

F
155 Beiträge seit 2009
vor 14 Jahren

Hallo,

 private static int[] Quicksort(int[] ZuSortieren)
        {
            int[] Sortiert = new int[ZuSortieren.Length];
            int Pivot;
            List<List<List<int>>> Liste = new List<List<List<int>>>();
            List<List<int>> Startliste = new List<List<int>>();
            Startliste.Add(ZuSortieren.ToList());
            Liste.Add(Startliste);

            for (int AnzahlEbenen = 0; AnzahlEbenen < Liste.Count; AnzahlEbenen++)
            {
                List<List<int>> NeuEbene = new List<List<int>>();
                for (int AnzahlListen = 0; AnzahlListen < Liste[AnzahlEbenen].Count; AnzahlListen++)
                {
                    if (Liste[AnzahlEbenen][AnzahlListen].Count > 1)
                    {
                        List<int> Kleiner = new List<int>();
                        List<int> Groesser = new List<int>();
                        List<int> DoppelteWerte = new List<int>();

                        Pivot = Liste[AnzahlEbenen][AnzahlListen][(int)Liste[AnzahlEbenen][AnzahlListen].Count / 2];

                        for (int i = 0; i < Liste[AnzahlEbenen][AnzahlListen].Count; i++)
                        {
                            if (Liste[AnzahlEbenen][AnzahlListen][i] < Pivot)
                                Kleiner.Add(Liste[AnzahlEbenen][AnzahlListen][i]);
                            else if (Liste[AnzahlEbenen][AnzahlListen][i] > Pivot)
                                Groesser.Add(Liste[AnzahlEbenen][AnzahlListen][i]);
                            else
                            {
                                if (Groesser.Contains(Pivot))
                                {
                                    DoppelteWerte.Add(Liste[AnzahlEbenen][AnzahlListen][i]);
                                }
                                else
                                    if (Kleiner.Count > Groesser.Count)
                                        Groesser.Add(Pivot);
                                    else
                                        Kleiner.Add(Pivot);
                            }
                        }
                        NeuEbene.Add(Kleiner);
                        if(DoppelteWerte.Count>0)
                            NeuEbene.Add(DoppelteWerte);
                        NeuEbene.Add(Groesser);
                    }
                    else
                    {
                        NeuEbene.Add(Liste[AnzahlEbenen][AnzahlListen]);
                    }
                    if (Liste[AnzahlEbenen].Count == ZuSortieren.Length)
                    {
                        for (int i = 0; i < ZuSortieren.Length; i++)
                            Sortiert[i] = Liste[AnzahlEbenen][i][0];
                        return Sortiert;

                    }
                }
                Liste.Add(NeuEbene);
            }
            return null;
        }

Aufruf:

            int[] ZuSortieren = {-1, 10, 4, 1, 9, 5, 3,2, 6, 7, 8 ,2};
            ZuSortieren= Quicksort(ZuSortieren);

Ich hoffe ich habe dich richtig verstanden.

Beste Grüße
FZ

EDIT: Es gab Probleme bei gleichen Werten

"We better hurry up and start coding, there are going to be a lot of bugs to fix."

179 Beiträge seit 2006
vor 14 Jahren

Deine Implementierung scheint Probleme zu haben wenn gleiche Werte vorkommen.

Da ich dann weg muss und heute nicht mehr dazukomme mir eine Alternativlösung anzuschauen, lass ichs mal durchgehen.

Dann stell deine Aufgabe

F
155 Beiträge seit 2009
vor 14 Jahren

Hallo,

Danke für den Hinweis, ich werds mir nochmal genauer ansehen.

Die nächste Aufgabe:
Das Pascalsche-Dreick bis zur n-ten Zeile ausgeben.


z.B. n=3
      1
     1 1
    1 2 1
   1 3 3 1

Grüße
FZ

"We better hurry up and start coding, there are going to be a lot of bugs to fix."

T
2 Beiträge seit 2010
vor 14 Jahren

int wert = 3;
Console.Out.WriteLine("1");
for (int i = o; i <= wert; i++)
{
    Console.Out.Write("1");
    for (int a = 1; a <= i; a++)
    {
        Console.Out.Write(i+1);
    }
Console.Out.WriteLine("1");

Gruß Tobi

5.742 Beiträge seit 2007
vor 14 Jahren
[...]  

*Räusper*: Pascalsches Dreieck

Geht sicherlich noch besser, aber egal 😉


int[] currentLine = new int[] { };
int[] previousLine;

int max = 5;
for (int n = 0; n < max; n++)
{
    previousLine = currentLine;
    currentLine = new int[previousLine.Length + 1];
    currentLine[0] = 1;
    currentLine[currentLine.Length - 1] = 1;
    for (int i = 1; i < currentLine.Length - 1; i++)
        currentLine[i] = previousLine[i - 1] + previousLine[i];

    Console.Write(new string(' ', max - currentLine.Length));
    for (int i = 0; i < currentLine.Length; i++)
        Console.Write(currentLine[i] + " ");

    Console.WriteLine();
}

Console.ReadLine();

//EDIT:
Ich wusste, ich habe was vergessen: 🙂

(Gar nicht so leicht irgendetwas zu finden, dann eben etwas Klassisches 😁 )
Ein Programm, das eine Primfaktorzerlegung einer beliebigen Zahl durchführt.

U
282 Beiträge seit 2008
vor 14 Jahren

class Primes {
    static IEnumerable<int> DividerSequence() {
        yield return 2;
        yield return 3;       
        for(int i = 6; true; i+=6){
            yield return i - 1;
            yield return i + 1;
        }
    }

    public static ICollection<int> GetPrimeFactors(int number) {
        if (number <= 0) {
            throw new ArgumentException("Positive integer expected.", "number");
        }

        LinkedList<int> primeFactors = new LinkedList<int>();
        foreach (int factor in DividerSequence()) {
            while (number % factor == 0) {
                primeFactors.AddLast(factor);
                number /= factor;
            }
            if (factor * factor > number) {
                break;
            }
        }
        if (number > 1) {
            primeFactors.AddLast(number);
        }
        return primeFactors;
    }
}

class Program{
    static void Main(string[] args) {
        for (int number = 1; number < 100; number++) {
            ICollection<int> primeFactors = Primes.GetPrimeFactors(number);
            Console.WriteLine(
                "n={0}, Primes=[{1}]", 
                number,
                string.Join(", ", primeFactors.Select(x => x.ToString()).ToArray()));
        }
    }
}

Neue Aufgabe:
Man teste ohne Verwendung der Logarithmusfunktion mit einem einzigen Statement, ob eine Integer eine Zweierpotenz ist.

390 Beiträge seit 2008
vor 14 Jahren

(number & (number - 1)) == 0

Neue Aufgabe

Eine Implementierung des erweiterten euklidischen Algorithmus
(Rekursiv oder Iterativ)

using Skill

1.361 Beiträge seit 2007
vor 14 Jahren
(number & (number - 1)) == 0  

Du musst allerdings noch die 0 ausschließen. (0 ist keine Zweierpotenz)
Siehe Rausfinden ob eine Zahl 2^x ist.

beste Grüße
zommi

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo zommi, hallo edsplash,

es muss mehr ausgeschlossen werden als die 0. Bei der C#-Integer-Arithmetik, muss es heißen:

number > 0 && (number & (number - 1)) == 0

Denn sonst wird zusätzlich zu dem Fehler bei der 0 bei int.MinValue (-2.147.483.648 bzw. 0x80000000) entweder eine OverflowException ausgelöst (checked) oder die Zahl fälschlich als Zweierpotenz erkannt (unchecked).

herbivore

PS: Damit habe ich wohl die erste korrekte Lösung. 😃 Aber ich nehme als nächste Aufgabe einfach die, die edsplash vorgegeben hat.

F
155 Beiträge seit 2009
vor 14 Jahren

Hallo,

static void Main(string[] args)
        {
            int a=10,b=78;
            int[] Werte = Euklid(a, b);
            Console.WriteLine("{0} = {1} * {2} + {3} * {4}", Werte[0], Werte[1], a, Werte[2], b);
            Console.ReadLine();
        }

        private static int[] Euklid(int a, int b)
        {
            if(b==0)
                return new int[]{a,1,0};
            int[] Strich = Euklid(b, a % b);
            int[] Werte = new int[3];
            Werte[0] = Strich[0];
            Werte[1] = Strich[2];
            Werte[2] = Strich[1] - (int)(a / b) * Strich[2]; ;
            return Werte;
        }

Nächste Aufgabe:

Den erweiterten euklidischen Algorithmus iterativ implementieren.

Grüße FZ

"We better hurry up and start coding, there are going to be a lot of bugs to fix."

A
abra_joe Themenstarter:in
23 Beiträge seit 2008
vor 14 Jahren

        static void Main(string[] args)
        {
           int z1 = Int32.Parse(Console.ReadLine());
           int z2 = Int32.Parse(Console.ReadLine());
           while (z2!=0)
           {
               if (z1 > z2)
                   z1 -= z2;
               else
                   z2 -= z1;
           }
           Console.WriteLine(z1);
           Console.ReadLine();
        }

stimmt doch oder?

1.002 Beiträge seit 2007
vor 14 Jahren

Hallo abra_joe,

es geht um den erweiterten euklidischen Algorithmus (s. Wikipedia-Artikel).

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

A
abra_joe Themenstarter:in
23 Beiträge seit 2008
vor 14 Jahren

muss ich wohl übersehen haben
tut mir leid....

72 Beiträge seit 2008
vor 14 Jahren

Vielleicht nicht die schönste Implementierung aber das sollte es eigentlich sein:


static void Main()
{
	bool parseOk = false;
	int a=0, b=0;
	while (!parseOk)
	{
		Console.WriteLine("Integer Wert a: ";);
		parseOk = Int32.TryParse(Console.ReadLine(), out a);
	}
	parseOk = false;
	while (!parseOk)
	{
		Console.WriteLine("Integer Wert b: ";);
		parseOk = Int32.TryParse(Console.ReadLine(), out b);
	}

	int ggT, x, y;

	if (a > b)
	{
		ExtendedEuclidian(a, b, out ggT, out x, out y);
		Console.WriteLine(a + " * " + x + " + " + b + " * " + y + " = " + ggT);
		Console.WriteLine(a * x + b * y == ggT ? "Stimmt!" : "Stimmt net!";);
	}
	else
	{
		ExtendedEuclidian(b, a, out ggT, out x, out y);
		Console.WriteLine(b + " * " + x + " + " + a + " * " + y + " = " + ggT);
		Console.WriteLine(b * x + a * y == ggT ? "Stimmt!" : "Stimmt net!";);
	}
	Console.ReadKey();
}

private static void ExtendedEuclidian(int a, int b, out int ggT, out int x, out int y)
{
	if (a%b == 0)
	{
		x = 0;
		y = 1;
		ggT = b*y;
		return;
	}

	int dggT, dX, dY, divRem;
	ExtendedEuclidian(b, a % b, out dggT, out dX, out dY);
	x = dY;
	y = dX - dY * Math.DivRem(a, b, out divRem);
	ggT = a * x + b * y;
}

Hatte noch ein Pseudocodeschnippsel in alten Vorlesungsunterlagen ....

*EDIT*: Formatierung angepasst.

1.002 Beiträge seit 2007
vor 14 Jahren

Hallo LuckyGeorge,

deine Implementierung ist rekursiv, gewollt war eine iterative ...

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

72 Beiträge seit 2008
vor 14 Jahren

Ok, wer lesen kann ist klar im Vorteil. Nun aber:


        private static void ExtendedEuclidianIterative(int a, int b, out int ggT, out int x, out int y)
        {
            x = 0;
            y = 1;
            int dX = 1, dY = 0;

            while(b != 0)
            {
                int divRem;
                int divQuot = Math.DivRem(a, b, out divRem);
                int temp = b;
                b = divRem;
                a = temp;

                temp = x;
                x = dX - divQuot * x;
                dX = temp;

                temp = y;
                y = dY - divQuot*y;
                dY = temp;
            }

            ggT = a;
            x = dX;
            y = dY;
        }

PS: Stammt natürlich nicht von mir sondern aus der Wiki. Nur was soll man bei solchen Algorithmen denn machen ....

F
155 Beiträge seit 2009
vor 14 Jahren

Hallo LuckyGeorge,

dein Algorithmus scheint in Ordnung zu sein, nun darfst du auch die nächste Aufgabe stellen.

Viel Spaß mit diese Thread wünscht
FZ

"We better hurry up and start coding, there are going to be a lot of bugs to fix."