Array auf letzte Zahl ungleich 0 kürzen



  • Hallo zusammen,
    ich habe ein Programm geschrieben, dass die Fakultät einer großen Zahl n berechnet. Dadurch, dass Integer und Double zu klein sind habe ich einen eigenen Datentyp "zahl" erstellt, welcher das große Ergebnis in Form eines Arrays darstellen kann. (Jede Ziffer der Ergebnis-Zahl hat einen eigenen Array-Platz).
    Problem ist das beispielsweise 8! was eigentlich 40320 ergibt, so angezeigt wird: Ergebnis-Zahl = {0,2,3,0,4,0,0,0,0,0,0,0,0,0,0}
    Mir ist bewusst das das Ergebnis verkehrt herum ist, die passende Funktion, die das Ergebnis umdreht habe ich.
    Jedoch stören mich die führenden Nullen, denn ich möchte das Array auf die letzte Zahl im Array, die ungleich Null ist kürzen und danach erst umdrehen.
    Also {0,2,3,0,4,0,0,0,0,0,0,0,0,0,0} wird zu {0,2,3,0,4} wird zu {4,0,3,2,0}.
    Wie kann ich das umsetzen?



  • @quantix sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Wie kann ich das umsetzen?

    Indem Du Nullen nur ausgibst speicherst wenn zuvor etwas anderes als Null ausgegeben gespeichert wurde.

    @quantix sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Jede Ziffer der Ergebnis-Zahl hat einen eigenen Array-Platz

    Dir ist schon klar daß das ziemlich ineffizient ist? (Alleine schon speichern im Dezimalsystem)



  • @Swordfish sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Dir ist schon klar daß das ziemlich ineffizient ist? (Alleine schon speichern im Dezimalsystem)

    Vielen Dank für die Antwort, ja das ist mir bewusst. Ich bin allerdings Anfänger und mir geht es hier nicht um Effizienz.



  • @Swordfish sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Indem Du Nullen nur ausgibst speicherst wenn zuvor etwas anderes als Null ausgegeben gespeichert wurde.

    Ich denke das klappt bei vielen nicht: 22! = 1124000727777607680000.
    Da gibt es viele aufeinander folgende 0-en.
    Ich denke ich brauche einen Algorithmus, der die Position der letzten Zahl im Array != 0 ausgibt, damit ich bis zu dieser Stelle die Zahl ausgeben kann.



  • @quantix sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Da gibt es viele aufeinander folgende 0-en.

    Und?

    #include <algorithm>
    #include <iostream>
    #include <iterator>
    #include <vector>
    
    int main()
    {
    	std::vector<int> foo{ 0, 2, 3, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    	std::copy(foo.begin(), foo.end(), std::ostream_iterator<int>{ std::cout, " " });
    	std::cout.put('\n');
    
    	// letzte Null von rechts aus (reverse) finden:
    	auto last_zero{ std::find_if_not(foo.rbegin(), foo.rend(), [](int digit) { return digit == 0; }).base() };
    
    	if (last_zero == foo.end() || last_zero == foo.begin()) {
    		std::cout << "Nix zu tun.\n\n";
    		return 0;
    	}
    
    	// Nullen loeschen:
    	foo.erase(last_zero, foo.end());
    	// umdrehen:
    	std::reverse(foo.begin(), foo.end());
    
    	std::copy(foo.begin(), foo.end(), std::ostream_iterator<int>{ std::cout, " " });
    	std::cout.put('\n');
    }
    

    zu Fuß:

    #include <iostream>
    #include <vector>
    
    int main()
    {
    	int foo[] { 0, 2, 3, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    	for (auto i : foo)
    		std::cout << i << ' ';
    	std::cout.put('\n');
    	
    	auto index_last_zero{ std::size(foo) };
    	for (; index_last_zero && !foo[index_last_zero - 1]; --index_last_zero);
    
    	if (index_last_zero == std::size(foo) || !index_last_zero) {
    		std::cout << "Nix zu tun.\n\n";
    		return 0;
    	}
    
    	// weil ich nicht weisz wie "array kuerzen" geht:
    	std::vector<int> bar;
    	for (auto i{ index_last_zero }; i; --i)
    		bar.push_back(foo[i - 1]);
    
    	for (auto i : bar)
    		std::cout << i << ' ';
    	std::cout.put('\n');
    
    }
    


  • @Swordfish sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Und?

    Danke, perfekt, das funktioniert.
    Ich versuche mal mein Programm zu verändern, sodass er direkt die Nullen weglässt, also direkt {0,2,3,0,4} ausspuckt statt {0,2,3,0,4,0,0,0,0,0,0,0,0,0,0} .
    Komisch ist das die Anzahl der 0-en variieren.
    Bei 8! = {0,2,3,0,4,0,0,0,0,0,0,0,0,0,0} sind es zehn 0-en.
    Bei 9! = {0,8,8,2,6,3,0,0,0,0,0,0,0,0,0,0,0} sind es mehr 0-en.
    Ich weiß nicht woher die herkommen.



  • @quantix sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Ich weiß nicht woher die herkommen.

    Jemand anderes kann das auch nicht wissen weil Du keinen Code zeigst.



  • #include <iostream>
    using namespace std;
    
    struct zahl {
    	int folge[1000];
    	int laenge;
    };
    int aufruf() {
    	cout << "Geben Sie eine Zahl n ein, die n-Fakultaet berechnet werden soll" << endl;
    	int n;
    	cin >> n;
    	return n;
    }
    void ausgabe(int zahl) {
    	cout << zahl << endl;
    }
    
    int laenge_zahl(double zahl)
    {
    	return log10(zahl) + 1;
    }
    
    int laenge_array(int eingabe_array[]) {
    	int laenge = 0;
    	int u = 0;
    	while (eingabe_array[u] >= 0) {
    		++laenge;
    		++u;
    	}
    	return laenge;
    }
    void arraydreher(int arr[], int laenge) {
    	for (int i = laenge - 1; i >= 0; --i) {
    		cout << arr[i];
    	}
    }
    void spalter(int zahl, int ausgabearray[]) {
    	int laenge = laenge_zahl(zahl);
    	ausgabearray[laenge];
    	for (int i = 0; i < laenge; ++i) {
    		ausgabearray[i] = zahl % 10;
    		zahl = zahl / 10;
    	}
    
    }
    void addierer(int arr[], int laenge)
    {
    
    	int help = 0;
    	for (int i = 0; i <= laenge; ++i) {
    		arr[i] += help;
    		help = 0;
    		if (arr[i] >= 10) {
    			help = arr[i] / 10;
    			arr[i] = arr[i] % 10;
    		}
    	}
    	//for (int i = 0; i < laenge; ++i) cout << arr[i] << endl;
    }
    void arraymulti_mit_klein(int arr[], int laenge, int klein, int ergebnis_array[]) {
    	zahl zwischen;
    	int ergeb = 0;
    	int ergebnis_laenge = 0;
    	for (int i = 0; i < laenge; ++i) {
    		ergeb = (arr[i] * klein);
    		ergebnis_laenge = laenge_zahl(ergeb);
    		zwischen.folge[i] = ergeb;
    	}
    	int h1 = 0;
    	int h2 = 0;
    	ergebnis_array[0] = (h1 / 100) % 10 + (h2 / 10) % 10 + zwischen.folge[0] % 10;
    	ergebnis_array[1] = (h2 / 100) % 10 + (zwischen.folge[0]/10) % 10 + zwischen.folge[1] % 10;
    	//cout << ergebnis_array[0] << endl;
    	//cout << ergebnis_array[1] << endl;
    	int a = 0;
    	int b = 0;
    	laenge = laenge + 2;
    	for (int i = 2; i < laenge; ++i) {
    		a = ((zwischen.folge[i - 2] / 100) % 10);
    		b = ((zwischen.folge[i - 1] / 10) % 10);
    		if (a < 0) a = 0;
    		if (b < 0) b = 0;
    		ergebnis_array[i] = a + b + (zwischen.folge[i] % 10);
    		a = 0;
    		b = 0;
    		//cout << ergebnis_array[i] << endl;
    	}
    	addierer(ergebnis_array, laenge);
    	--klein;
    	if (klein > 0) arraymulti_mit_klein(ergebnis_array, laenge, klein, ergebnis_array);
    }
    
    int main() {
    	zahl arr, erg;
    	arr.folge;
    	erg.folge;
    	int n;
    	n = aufruf();
    	//ausgabe(n);
    	int klein = n - 1;
    	int laenge = 0;
    	laenge = laenge_zahl(n);
    	cout << "laennegweg= " << laenge << endl;
    	spalter(n, arr.folge); 
    	//for (int i = 0; i < laenge; ++i) {
    	//	cout << arr[i] << endl;
    	//}
    
    	arraymulti_mit_klein(arr.folge, laenge, klein, erg.folge);
    	int laengearray = laenge_array(erg.folge);
    	cout << laengearray << endl;
    	/*cout << laengearray;*/
    	
    	for(int i=0; i<laengearray; ++i)
    		if(erg.folge[i] >= 0) cout << erg.folge[i];
    	return 0;
    }
    


  • Ne sorry, das ist mir zu wirr.
    Was haben die Zeilen 39, 95 und 96 für einen Effekt?
    Wie viele Stellen hat 0?



  • @Swordfish sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Was haben die Zeilen 39, 95 und 96 für einen Effekt?

    Die Prozedur "spalter" ist dazu da die Zahl mit der die Fakultät beginnt in einen Array aufzuspalten.
    Zeile 39 erstellt ein Array der Größe, die von der Zifferanzahl der Zahl abhängt.

    Zeile 95 und 96 sind egal, die kann ich entfernen, die bewirken nichts.



  • @Swordfish sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Wie viele Stellen hat 0?

    Ich weiß nicht genau was du damit meinst.
    Ahh ich glaube daran könnte es liegen.
    0 hat ja null Zifferstellen, somit die Länge 0
    1,2,3,4,5,6,7,8,9 haben eine Ziffernstelle, somit die Länge 1

    Das könnte ich einbauen. Die Länge wird bei der Zahl 0 falsch berechnet



  • @quantix sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Zeile 39 erstellt ein Array der Größe, die von der Zifferanzahl der Zahl abhängt.

    Nope. Die Zeile ist genauso sinnlos wie die anderen beiden.

    @quantix sagte in Array auf letzte Zahl ungleich 0 kürzen:

    0 hat ja null Zifferstellen, somit die Länge 0

    Das letzte mal als ich gezählt habe hatte 0 eine Dezimalstelle. (Aber der Logarithmus für 0 ist undefiniert, deshalb stimmt auch das Ergebnis von laenge_zahl(0) nicht.)



  • @Swordfish sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Das letzte mal als ich gezählt habe hatte 0 eine Dezimalstelle. (Aber der Logarithmus für 0 ist undefiniert, deshalb stimmt auch das Ergebnis von laenge_zahl(0) nicht.)

    Ja genau, dann bau ich in die laenge_zahl-Funktion eine if-Abfrage ein, die Falls die Zahl == 0 ist, 0 returned.



  • @quantix sagte in Array auf letzte Zahl ungleich 0 kürzen:

    die Falls die Zahl == 0 ist, 0 returned.

    @Swordfish sagte in Array auf letzte Zahl ungleich 0 kürzen:

    Das letzte mal als ich gezählt habe hatte 0 eine Dezimalstelle.



  • @Swordfish
    Ich denke das Problem liegt an der Arraylänge (laengearray, die in Zeile 110 berechnet wird, sie ist immer zu groß)

    Wenn ich in Zeile 115 die if-Abfrage änder in: " if(erg.folge[i] > 0) cout << erg.folge[i];"
    also ">" statt ">=".
    Dann verschwinden die 0-en, ABER leider auch die wichtigen:
    9! = 362880
    mein Programm sagt vor der Änderung: 9! = 08826300000000000
    nach der Änderung: 9! = 88263
    leider fehlt jetzt die 0 hinten 😞



  • Du musst offensichtlich Nullen anders behandeln wenn zuvor schon eine andere Ziffer aufgetaucht ist.



  • @Swordfish

    	for(int i=0; i<laengearray; ++i)
    		if(erg.folge[i] > 0 || erg.folge[i+1] >0) cout << erg.folge[i];
    

    mit einer Abfrage, die abfragt ob die Zahlstelle oder die nächste >0 ist klappt es.
    Aber nur wenn die Ergebniszahl keine aufeinanderfolgenden 0-en hat.

    Aber das ist doch keine wirkliche Lösung, da müsste ich ja viele oder-Bedingungen einbauen bei 22! zum Beispiel wo es 3+ aufeinanderfolgende 0-en gibt



  • @Swordfish
    Deine Lösung die du vorher geschrieben hast klappt. Danke für deine Hilfe.
    Allerdings möchte ich es ohne Bibliotheken (die ich nicht kenne etc) schaffen.



  • Führende Nullen willst Du nicht ausgeben. Merk dir ob schon etwas anderes als Null aufgetaucht ist. Wenn ja: Nullen ausgeben.



  • Ich habe es gelöst.
    Ich habe die Prozedur, welche den Array umdreht so verändert, dass sie zuerst die führenden 0-en zählt, bis sie die vorderste Zahl trifft, die != 0 ist.
    Die neue Länge des Arrays ist die (Alte Länge minus 1 minus Anzahl der 0-en)
    Daraufhin gibt die Prozedur nacheinander rückwärts die Arrayelemente aus und zwar so lange wie die neue Länge.

    void arraydreher(int arr[], int laenge) {
    	int zaehler = 0;//Variable die die führenden 0-en zählt
    	int help; //Hilfsvariable für die Länge
    	help = laenge-1;
    	while (arr[help] == 0){
    		++zaehler;
    		--help;
    	}
    
    	cout <<"Fuehrende 0-en:" << zaehler << endl;
    
    	for (int i = laenge -1 -zaehler; i >= 0; --i) {
    		cout << arr[i];
    	}
    }
    

    Das Programm berechnet jetzt die Fakultät von 1 bis 115 korrekt, ab 116 stimmen die Ergebnisse nicht mehr, aber das ist mir jetzt egal.


Anmelden zum Antworten