C# :: Aufgabe #182

3 Lösungen Lösungen öffentlich

Mononacci, Fibonacci, Multinacci

Anfänger - C# von hollst - 09.07.2017 um 12:16 Uhr
Die Fibonacci-Folge beginnt bekanntlich mit {1, 1}, also zwei Einsen
und jedes Folgeglied ist die Summe seiner zwei Vorgänger. Wir wollen die Fibonacci-Folge wegen der zwei Starteinsen "fibo2" nennen.

Unter einer Multinacci-Folge (fibok) sei eine Folge verstanden, die mit k Einsen beginnt
und jedes Folgeglied die Summe der k Vorgängerglieder ist. Ist k = 1, so heiße der Spezialfall Mononacci.

Die Glieder der Multinacci-Folgen werden ab Glied k immer größer und streben gegen unendlich.
Allerdings strebt der Quotient zweier benachbarter Folgeglieder immer gegen einen endlichen Grenzwert, bei fibo2
ist es bekanntlch der goldene Schnitt phi (phi = 1.618034).

Wir wollen den entsprechenden Grenzwert der Multinacci-Folgen mit "phi_fibok" benennen.

Schreibe ein Programm, das für k = 1, 2, 3 ... 100 die ersten 10 Glieder der Multinacci-Folgen ab Glied k und den Grenzwert phi_fibok ausgibt.

Hinweis: Beider der Grenzwertbildung könnt ihr es mit sehr große Zahlen zu tun bekommen, deshalb Ergebnis auf Plausibilität testen!

Lösungen:

vote_ok
von daniel59 (3960 Punkte) - 08.08.2017 um 09:01 Uhr
Quellcode ausblenden C#-Code
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleMultinacci
{
    static class Program
    {
        static void Main(string[] args)
        {
            Console.BufferHeight = 1000;
            for (int i = 1; i <= 100; i++)
            {
                var multinacci = GetMultinacci(i, 50).Skip(i);
                foreach (var item in multinacci.Take(10))
                {
                    Console.Write($"{item} ");
                }
                Console.WriteLine();
                Console.WriteLine($"phi_fibo{i}: {multinacci.GetPhi()}\r\n");
            }
            Console.ReadLine();
        }

        static List<decimal> GetMultinacci(int k, int length)
        {
            List<decimal> multinacci = new List<decimal>();
            for (int i = 0; i < k; i++)
            { multinacci.Add(1); }

            multinacci.Skip(0).Take(k);
            multinacci.AddNextMultinacciNumber(0, k, length);

            return multinacci;
        }

        static void AddNextMultinacciNumber(this List<decimal> multinacci, int index, int k, int length)
        {
            var fn = multinacci.Skip(index).Take(k);
            decimal num = 0;
            foreach (decimal bi in fn)
            {
                num += bi;
            }
            multinacci.Add(num);
            if (index < length)
            {
                multinacci.AddNextMultinacciNumber(index + 1, k, length);
            }
        }

        static decimal GetPhi(this IEnumerable<decimal> multinacci)
        {
            var end = multinacci.Skip(multinacci.Count() - 2);
            return (end.Last() / end.First());
        }
    }
}
1 Kommentar
vote_ok
von brombeere111 (50 Punkte) - 02.09.2017 um 18:08 Uhr
Quellcode ausblenden C#-Code
 private void CmdErzeugen_Click(object sender, EventArgs e)
        {
            int x = 1, y = 0, z;

            do
            {
                z = x + y;
                x = y;
                y = z;
               LblAnzeige.Text += z + "\n";
            }
            while (z <= 100);
        }
1x
vote_ok
von hollst (9460 Punkte) - 15.12.2017 um 11:35 Uhr
Quellcode ausblenden C#-Code
using System;
using static System.Console;

namespace multinacci    {
    /*
        Mononacci, Fibonacci, Multinacci

        Die Fibonacci-Folge beginnt bekanntlich mit {1, 1}, also zwei Einsen 
        und jedes Folgeglied ist die Summe seiner zwei Vorgänger. Wir wollen die Fibonacci-Folge "fibo2" nennen.

        Unter einer Multinacci-Folge (fibok) sei eine Folge verstanden, die mit k Einsen beginnt 
        und jedes Folgeglied ist die Summe der k Vorgängerglieder. Ist k = 1, so heiße die Folge Mononacci.

        Die Glieder der Multinacci-Folgen werden ab Glied k immer größer und streben gegen unendlich.
        Allerdings strebt der Quotient zweier benachbarter Folgeglieder immer gegen einen endlichen Grenzwert, bei fibo2 
        ist es bekanntlch der goldene Schnitt phi (phi = 1.618034).

        Wir wollen den entsprechenden Grenzwert der Multinacci-Folgen mit "phi_fibok" benennen.

        Schreibe ein Programm, das für k = 1, 2, 3 ... 100 die ersten 10 Glieder der Multinacci-Folge ab Glied k und den Grenzwert phi_fibok ausgibt.
    */

    class Program
    {
        static void Main()
        {
            ulong n = 0, k = 2, anzahl = 10;

            Class_Fibo fibo = new Class_Fibo();
            WriteLine();
            for (ulong kk = 1; kk < 101; kk++)            {
                (" k = " + kk.ToString().Chars(3) + ": ").Message();
                for (ulong kkk = kk; kkk < kk + anzahl; kkk++)
                    (fibo.fibok(kkk, kk).ToString("n0").Chars(8)).Message();
                ("    limit: " + fibo.fibostep_phi(kk).ToString()).MessageLine();
            }
            "ready first task".EndMessage();

            fibo.bo_overflow = false;
            k = 2;
            while (!fibo.bo_overflow)
                $"fibok({n}, {k}): {fibo.fibok(n++, k).ToString("n0").Chars(28)} overflow: {fibo.bo_overflow}".MessageLine();
            "ready all".EndMessage();
        }
    }

    public class Class_Fibo    {

        public bool bo_overflow = false;
        public ulong counter = 0;

        public Class_Fibo() {   //constructor
            bo_overflow = false;
            counter = 0;
        }

        public ulong fibok(ulong n, ulong k)        {

            bo_overflow = false;
            counter = 0;

            if (n < k) return 1;

            ulong[] fn = new ulong[k];
            ulong f = 1;

            for (var i = 0; i < fn.Length; i++)
                fn[i] = 1;

            ulong f0 = fn.Sum();   
            for (var i = k - 1; i < n; i++) {
                f = fn.Sum();
                for (var j = 0; j < fn.Length - 1; j++)
                    fn[j] = fn[j + 1];
                fn[fn.Length - 1] = f;
                if (f < f0) {
                    bo_overflow = true;                    
                    return f0;
                }
                f0 = f;
                counter++;
            }
            return f;
        }

        public ulong fibostep(ulong n, ulong k)        {

            bo_overflow = false;
            counter = 0;

            if (n < k) return fibok(n, 2); ;

            ulong[] fn = new ulong[k];
            ulong f = 1;

            for (var i = 0; i < fn.Length; i++)
                fn[i] = fibok((ulong)i, 2);

            ulong f0 = fn.Sum();
            for (var i = k - 1; i < n; i++) {
                f = fn.Sum();
                for (var j = 0; j < fn.Length - 1; j++)
                    fn[j] = fn[j + 1];

                fn[fn.Length - 1] = f;

                if (f < f0) {
                    bo_overflow = true;
                    return f0;
                }
                f0 = f;
                counter++;
            }
            return f;
        }

        public double fibostep_phi(ulong k) {
            if (k == 1)
                return 1.0;
            if (k > 60)
                return 2.0;

            double result = 1;
            ulong n = k - 1;

            bo_overflow = false;

            while (true)    {
                ulong f2 = fibostep(n, k);
                ulong f1 = fibostep(n + 1, k);
                if (bo_overflow)
                    return result;
                result = 1.0 * f1 / f2;
                n++;
            }
        }
    }

        public static class MyExtensions    {

        public static void Message(this string s) => Write(s);

        public static void MessageLine(this string s) => WriteLine(s);

        public static ConsoleKeyInfo EndMessage(this string s)
        { s.MessageLine(); return ReadKey(true); }

        public static ulong Sum(this ulong[] s) {
            ulong ss = 0;
            for (var i = 0; i < s.Length; i++)
                ss += s[i];
            return ss;
        }

        public static string Chars(this string s, int anzahl)   {
            string result = s;
            while (result.Length < anzahl)
                result = " " + result;
            return result;
        }
    }
}