Ein nicht-rekursiver Algorithmus!

2 Lösungen

#310

Anfänger - C# von Labi1995 - 19.04.2020 um 20:52 Uhr

Was leistet folgender rekursiver Algorithmus für natürliche Zahlen n mit n>0?

int DoSomething(int n) 
{ 
   if (n == 1) 
      return n - 1; 
   else 
   { 
      if ((n / 2) * 2 == n) 
      { 
         return 1 + DoSomething(n - 1); 
      } 
      else 
      { 
         return DoSomething(n - 1); 
      } 
   } 
}

Geben Sie einen nicht-rekursiven Algorithmus an, der dasselbe leistet.

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von daniel59 (4260 Punkte) - 27.04.2020 um 11:10 Uhr

C#-Code

using System;

namespace ConsoleNichtRekursiv
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 1; i <= 10000; i++)
            {
                int recursive = DoSomethingRecurvive(i);
                int loop = DoSomethingLoop(i);
                int simple = DoSomethingSimple(i);

                if (!(recursive == loop && loop == simple))
                {
                    Console.WriteLine(i);
                }
            }

            Console.ReadLine();
        }

        static int DoSomethingRecurvive(int n) // Führt zu StackOverflowException und funktioniert nur bei n >= 1
        {
            if (n == 1)
            { return n - 1; }
            else
            {
                if ((n / 2) * 2 == n) //Endergebnis um 1 erhöhen, wenn n gerade ist bzw. durch 2 ohne Rest teilbar ist
                {
                    return 1 + DoSomethingRecurvive(n - 1); //n um 1 verringern
                }
                else
                {
                    return DoSomethingRecurvive(n - 1); //n um 1 verringern
                }
            }
        }

        static int DoSomethingLoop(int n) // Führt nicht zu StackOverflowException und funktioniert nur bei n >= 1
        {
            int tmp = n;
            int result = 0;
            while (tmp != 1)
            {
                if ((tmp / 2) * 2 == tmp) //Endergebnis um 1 erhöhen, wenn n gerade ist bzw. durch 2 ohne Rest teilbar ist
                {
                    result++;
                }

                tmp--; //n um 1 verringern
            }

            return result;
        }

        static int DoSomethingSimple(int n) // Führt nicht zu StackOverflowException und funktioniert bei allen möglichen n-Werten und ist effektiver
        {
            return n / 2;
        }
    }
}