4. Dezimalstellen in int array[2000] übertragen?

Dezimalstellen in int array[2000] übertragen?

  • H

    hallo 🙂

    ich habe eine Aufgabe, bei der man Fakultäten berechen soll. Die Berechnung selbst ist kein Problem, allerdings soll man Zahlen bis zu 10000 Dezimalstellen berechnen und diese in ein array mit 2000 feldern übertragen. Somit übernimmt jedes Feld 5 Dezimalstellen. Sobald die nieder wertigen Dezimalstellen überlaufen muss man den Wert per Übertrag an das nächste Feld übergeben.
    Alles so weit so gut, meine Frage ist wie geht das im Code?

    Bsp:

    Es entsteht die Zahl "123 456 789" in der Rechnung
    Die sollte dann so im array stehen:

    int array[0]= 12345 int array[1]= 6789

    verstehe aber nicht ganz wie das ganze in code umgesetzt werden kann.
    Ich denke das modulo und division durch "10000" eine Rolle spielen wird aber eine konkrete idee habe ich nicht.

    kann mir jemand weiterhelfen? 😕

    0
  • ?

    HeapStack schrieb:

    Ich denke das modulo und division durch "10000" eine Rolle spielen wird aber eine konkrete idee habe ich nicht.

    Mit 5 Dezimalstellen hast Du einen Wertebereich von 0 bis 99999 pro Zelle und rechnest damit im 100000-er System. Es funktioniert eigentlich wie im Dezimalsystem, nur denkst Du Dir die Zelleneinträge nicht mehr als Zahlen sondern als Symbole des 100k-Systems. Es ist vllt Hilfreich nochmal im Dual- und Dezimalsystem zu rechnen, Dir die Unterschiede und Gemeinsamkeiten genau anzusehen und es dann auf die Aufgabe zu übertragen.

    Die Frage ist ein bisschen zu Umfangreich um sie mit Beispielcode zu beantworten. Sorry.

    0
  • H

    Code erwarte ich auch nicht, will nur verstehen welche methodik dahinter steckt.
    Mit verschiedenen Zahlensystemen zu rechnen ist eig kein Problem, habs mir auch nochmal angeschaut, aber verstehe da nicht ganz den Bezug zu der Aufgabe.

    3456789 / 100 000 = 34,5678 -> nehme Zahl vor dem Komma als array[1]

    Rest 0,56789* 100 000 = 56789 -> Zahl für aray[0]

    Index is diskutabel, je nachdem ob man von höher oder niederwertigen stellen als ursprung ausgeht. aber ein richtiger algorithmus der wirklich hohe zahlen in so ein array bringt kann ich mir so nicht vorstellen

    0
  • ?

    Hi, ist das hier noch aktuell?
    Ich habe vor ewiger Zeit mal was ähnliches programmiert und jedenfalls noch etwas Code dazu gefunden. Wollte das eigentlich schon anfang die Woche posten, ist aber irgendwie untergegangen.

    Habe alles rausgeworfen, was für die Aufgabe nicht relevant ist. Ob das alles korrekt ist weiß ich nicht, das ist wie gesagt schon länger her, dass ich das mal geschrieben habe und war nur ein privater Test aus langeweile 🙂

    using System;

namespace Big
{
    class Program
    {
        static void Main(string[] args)
        {
            ulong Base = 100000;

            Bignum factorial = new Bignum(Base, 1);
            Bignum max = new Bignum(Base, 100);
            Bignum one = new Bignum(Base, 1);

            for (Bignum i = new Bignum(Base, 1); i <= max; i += one)
            {
                factorial *= i;
            }

            Console.WriteLine(factorial.ToString());
            Console.ReadKey(true);
        }
    }
}

    Das ist das Hauptprogramm um die Fakultät von 100 zu berechnen. Zum Konstruktor der Bignum-Klasse sei gesagt, dass man im letzten Parameter die Ziffern einer Zahl getrennt angibt. Beispiel die Zahl 4711 im Dezimalsystem würden man konstruieren als: new Bignum(10, 4, 7, 1, 1)
    Oben im Beispiel arbeiten wir mit dem 100k-System. Das heißt der max-Wert von 100 wird als einzelne Ziffer dieses Systems angegeben im Konstruktor!

    Die Klasse Bignum verwendet eine Digit-Klasse um eine Ziffer zu repräsentieren:

    using System;

namespace Big
{
    struct Digit : IComparable<Digit>
    {
        public readonly ulong digit;
        public readonly ulong radix;

        public Digit(ulong radix, ulong digit)
        {
            if (digit >= radix)
                throw new ArgumentException("digit>=radix");

            this.digit = digit;
            this.radix = radix;
        }

        public static void Add(Digit a, Digit b, ref Digit carry, out Digit sum)
        {
            ulong radix = a.radix;
            sum = new Digit(radix, (a.digit + b.digit + carry.digit) % radix);
            carry = sum.digit < a.digit || sum.digit < b.digit || a.digit == radix - 1 && b.digit == radix - 1 && carry.digit == 1
                     ? new Digit(radix, 1)
                     : new Digit(radix, 0);
        }

        public static void Sub(Digit a, Digit b, ref Digit carry, out Digit diff)
        {
            ulong radix = a.radix;
            ulong diff_;
            ulong carry_;
            if (a.digit >= (b.digit + carry.digit))
            {
                diff_ = a.digit - (b.digit + carry.digit);
                carry_ = 0;
            }
            else
            {
                diff_ = radix + a.digit - (b.digit + carry.digit);
                carry_ = 1;
            }

            diff = new Digit(radix, diff_);
            carry = new Digit(radix, carry_);
        }

        public static void Mul(Digit a, Digit b, ref Digit carry, out Digit product)
        {
            ulong radix = a.radix;
            product = new Digit(radix, (a.digit * b.digit + carry.digit) % radix);

            //das geht nicht gut für hohe radixe (überlauf)
            carry = new Digit(radix, (a.digit * b.digit + carry.digit) / radix);
        }

        public override bool Equals(object obj)
        {
            return this.CompareTo((Digit)obj) == 0;
        }

        public int CompareTo(Digit other)
        {
            return digit.CompareTo(other.digit);
        }

        public override string ToString()
        {
            if (radix == 16 && digit >= 10)
                return new string(new char[] { (char)('A' + digit - 10) });
            return digit.ToString();
        }
    }
}

    Und nun Bignum selbst:

    using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Big
{
    class Bignum : IComparable<Bignum>
    {
        readonly ulong radix;
        private List<Digit> digits;
        public enum Sign { Pos = 1, Neg = -1 }

        public Bignum(ulong radix, params ulong[] num)
        {
            this.radix = radix;
            digits = num.Select(u => new Digit(radix, u)).Reverse().ToList();
        }

        public Bignum(ulong radix, List<Digit> num)
        {
            this.radix = radix;
            digits = num;
        }

        public Bignum(Bignum other)
        {
            radix = other.radix;
            digits = other.digits.ToList();
        }

        public int DigitCount()
        {
            return digits.Count;
        }

        public int CompareTo(Bignum other)
        {
            if (radix != other.radix)
                throw new ArgumentException("base mismatch");

            int cmp = 0;
            if (digits.Count != other.digits.Count)
                cmp = Math.Sign(digits.Count - other.digits.Count);
            else
                for (int i = digits.Count - 1; i >= 0; --i)
                {
                    int digitCmp = digits[i].CompareTo(other.digits[i]);
                    if (digitCmp != 0)
                    {
                        cmp = digitCmp;
                        break;
                    }
                }

            return cmp;
        }

        public override bool Equals(object obj)
        {
            return this.CompareTo((Bignum)obj) == 0;
        }

        public static Bignum operator *(Bignum a, Bignum b)
        {
            return Mul(a, b);
        }

        public static Bignum operator +(Bignum a, Bignum b)
        {
            return Add(a, b);
        }

        public static bool operator <(Bignum a, Bignum b)
        {
            return a.CompareTo(b) < 0;
        }

        public static bool operator >(Bignum a, Bignum b)
        {
            return a.CompareTo(b) > 0;
        }

        public static bool operator <=(Bignum a, Bignum b)
        {
            int cmp = a.CompareTo(b);
            return cmp < 0 || cmp == 0;
        }

        public static bool operator >=(Bignum a, Bignum b)
        {
            int cmp = a.CompareTo(b);
            return cmp > 0 || cmp == 0;
        }

        public static bool operator ==(Bignum a, Bignum b)
        {
            return a.CompareTo(b) == 0;
        }

        public static bool operator !=(Bignum a, Bignum b)
        {
            return a.CompareTo(b) != 0;
        }

        private static Bignum Mul(Bignum a, Digit d)
        {
            if (a.radix != d.radix)
                throw new ArgumentException("base mismatch");

            ulong radix = a.radix;
            int count = a.digits.Count;
            List<Digit> result = new List<Digit>(count + 1);

            Digit carry = new Digit(radix, 0);
            for (int i = 0; i < count || carry.digit != 0; ++i)
            {
                Digit first = i < a.digits.Count ? a.digits[i] : new Digit(radix, 0);

                Digit prod;
                Digit.Mul(first, d, ref carry, out prod);

                result.Add(prod);
            }

            Bignum product = new Bignum(radix, result);
            //product.Normalize();
            return product;
        }

        public static Bignum Mul(Bignum a, Bignum b)
        {
            if (a.radix != b.radix)
                throw new ArgumentException("base mismatch");

            ulong radix = a.radix;

            Bignum product = new Bignum(radix, 0);
            for (int i = 0; i < b.digits.Count; ++i)
            {
                Bignum mul = Bignum.Mul(a, b.digits[i]);
                mul.ShiftLeft(i);
                product = Bignum.Add(product, mul);
            }

            Bignum zero = new Bignum(radix, 0);

            product.Normalize();
            return product;
        }

        public static Bignum Add(Bignum a, Bignum b)
        {
            if (a.radix != b.radix)
                throw new ArgumentException("base mismatch");

            ulong radix = a.radix;
            int count = Math.Max(a.digits.Count, b.digits.Count);
            List<Digit> result = new List<Digit>(count + 1);

            Digit zero = new Digit(radix, 0);
            Digit carry = zero;
            for (int i = 0; i < count || carry.digit == 1; ++i)
            {
                Digit first = i < a.digits.Count ? a.digits[i] : zero;
                Digit second = i < b.digits.Count ? b.digits[i] : zero;

                Digit sum;
                Digit.Add(first, second, ref carry, out sum);
                result.Add(sum);
            }

            return new Bignum(radix, result);
        }

        public void Normalize()
        {
            int i;
            for (i = digits.Count - 1; i > 0 && digits[i].digit == 0; --i) ;
            digits.RemoveRange(i + 1, digits.Count - 1 - i);
        }

        public void ShiftLeft(int count)
        {
            if (count <= 0)
                return;

            List<Digit> dig = new List<Digit>(digits.Count + count);
            Digit zero = new Digit(radix, 0);

            for (int i = 0; i < digits.Count + count; ++i)
                if (i < count)
                    dig.Add(zero);
                else
                    dig.Add(digits[i - count]);

            digits = dig;
        }

        public override string ToString()
        {
            StringBuilder b = new StringBuilder();

            for (int i = digits.Count - 1; i >= 0; --i)
            {
                b.Append(digits[i].ToString() + " ");
            }

            return b.ToString();
        }
    }
}

    Das Beispiel zur Fakultät von 100 liefert als Ausgabe:
    933 26215 44394 41526 81699 23885 62667 490 71596 82643 81621 46859 29638 95217 59999 32299 15608 94146 39761 56518 28625 36979 20827 22375 82511 85210 91686 40000 0 0 0 0

    Wolfram Alpha sagt 100! =
    933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000 00000 00000 00000 00000

    Auffällig ist die unterschiedliche Anzahl Nullen am Ende. Beachte wieder, dass die Ausgabe oben im 100k-System erfolgt. D.h. jeder 5-er Block Zahlen muss um 100000^k verschoben werden. Die letzte Ziffer != 0 ist 40000 und das wäre im Dezimalsystem: 40000 * 100000^4 = 4000000000000000000000000. Das Ergebnis stimmt also.

    Grüße

    0
Anmelden zum Antworten