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ß

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 😄

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

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

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

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 😉

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

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

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

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

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

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

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

Ja dann hau ma die nächste Aufgabe rein 😄

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

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

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)

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

Ja dann hau ma die nächste Aufgabe rein 😁

😁

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

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

Viel Spaß 😄

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

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

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ß

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

So ähnlich hatte ich mir das auch gedacht. Dann darf Herbivore die nächste Aufgabe stellen.

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

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.

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

siehe:

ohne Verwendung einer Stack(artigen)-Klasse

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

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

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.

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

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

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

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

[...]  

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

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.

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

Neue Aufgabe

Eine Implementierung des erweiterten euklidischen Algorithmus
(Rekursiv oder Iterativ)

(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

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.

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

        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?

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

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.

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

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