tommyk
Ich suche nach einem effizienten Algorithmus, um eine Zahl umzukehren, z
Eingang: 3456789
Ausgabe: 9876543
In C++ gibt es viele Optionen mit Verschiebungen und Bitmasken, aber was wäre der effizienteste Weg?
Meine Plattform: x86_64
Nummernbereich: XXX – XXXXXXXXXX (3 – 9 Ziffern)
BEARBEITEN
Die letzte Ziffer meiner Eingabe wird niemals eine Null sein, daher gibt es kein Problem mit führenden Nullen.
So etwas wird funktionieren:
#include <iostream>
int main()
{
long in = 3456789;
long out = 0;
while(in)
{
out *= 10;
out += in % 10;
in /= 10;
}
std::cout << out << std::endl;
return 0;
}
@ H2CO3 Diese Antwort ist wirklich sehr häufig. Nicht sehr hart oder beeindruckend genug, um kopiert zu werden.
– Raptz
12. März 2013 um 6:59 Uhr
@ H2CO3 nein, ich habe eigentlich separat geschrieben
– Stefan Lin
12. März 2013 um 6:59 Uhr
@H2CO3 – Hm, ich habe auf Ihre Antwort geantwortet, aber Sie scheinen Ihre Antwort gelöscht zu haben. Ich habe meine positive Bewertung nur vorübergehend entfernt, weil mir klar wurde, dass ich math.stackexchange.com recherchieren sollte, falls eine effizientere Lösung gefunden wird (z.B eine Ein-Schritt-Formel) existierte. Aber die Mathematiker dort haben sich nichts dergleichen einfallen lassen, nur eine kompakte Form des Algorithmus, den Sie (und Stephen Lin) geschrieben haben. Also, Upvote im Geiste wiederhergestellt.
– Schlappschwanz
12. März 2013 um 7:03 Uhr
@acheong87 Danke. Ich habe meine Antwort entfernt, da sie sich als falsch herausstellte, genau wie diese. Es zählt keine nachgestellten Nullen, XYZ0 wird ZYX Anstatt von 0ZYX.
– Benutzer529758
12. März 2013 um 7:05 Uhr
@ H2CO3 Es macht mir nichts aus, dies auch zu notieren, aber es ist nicht klar, was OP will, da er Bitverschiebungen und dergleichen erwähnt (also will er vermutlich eher eine numerische als eine Zeichenfolgendarstellung).
– Stefan Lin
12. März 2013 um 7:07 Uhr
#include <stdio.h>
unsigned int reverse(unsigned int val)
{
unsigned int retval = 0;
while( val > 0)
{
retval = 10*retval + val%10;
val /= 10;
}
printf("returning - %d", retval);
return retval;
}
int main()
{
reverse(123);
}
Sie können die Zahl in eine Zeichenfolge konvertieren und die Zeichenfolge dann mit STL-Algorithmen umkehren. Der folgende Code sollte funktionieren:
long number = 123456789;
stringstream ss;
ss << number;
string numberToStr = ss.str();
std::reverse(numberToStr.begin(), numberToStr.end());
cout << atol(numberToStr.c_str());
Möglicherweise müssen Sie diese relevanten Header-Dateien einschließen. Ich bin mir nicht sicher, ob es der effizienteste Weg ist, aber STL-Algorithmen sind im Allgemeinen sehr effizient.
static public int getReverseInt(int value) {
int resultNumber = 0;
for (int i = value; i != 0;) {
int d = i / 10;
resultNumber = (resultNumber - d) * 10 + i;
i = d;
}
return resultNumber;
}
Ich denke, dies wird die schnellstmögliche Methode ohne Verwendung sein asm. Beachten Sie, dass d*10 + i ist äquivalent zu i%10 aber viel schneller, da Modulo etwa 10-mal langsamer ist als die Multiplikation.
Ich habe es getestet und es ist etwa 25 % schneller als andere Antworten.
Pratiush Prasunn
int ans=0;
int rev(int n)
{
ans=(ans+(n%10))*10; // using recursive function to reverse a number;
if(n>9)
rev(n/10);
}
int main()
{
int m=rev(456123); // m=32
return 0;
}
ist es der effizienteste Weg, dies zu tun?
– Hariom Singh
12. August 2017 um 18:18 Uhr
Nicht im Hinblick auf das Gedächtnis, aber praktisch beim Lösen von Problemen 🙂
– Pratiush Prasunn
13. August 2017 um 15:44 Uhr
Roshan
//Recursive method to find the reverse of a number
#include <bits/stdc++.h>
using namespace std;
int reversDigits(int num)
{
static int rev_num = 0;
static int base_pos = 1;
if(num > 0)
{
reversDigits(num/10);
rev_num += (num%10)*base_pos;
base_pos *= 10;
}
return rev_num;
}
int main()
{
int num = 4562;
cout << "Reverse " << reversDigits(num);
} ``
ist es der effizienteste Weg, dies zu tun?
– Hariom Singh
12. August 2017 um 18:18 Uhr
Nicht im Hinblick auf das Gedächtnis, aber praktisch beim Lösen von Problemen 🙂
– Pratiush Prasunn
13. August 2017 um 15:44 Uhr
mufeez-shaikh
// recursive method to reverse number. lang = java
static void reverseNumber(int number){
// number == 0 is the base case
if(number !=0 ){
//recursive case
System.out.print(number %10);
reverseNumber(number /10);
}
}
Wenn Sie es nicht als Zahl behandeln, warum lesen Sie es nicht einfach als Zeichenfolge? Das Umkehren ist dann trivial.
– Benutzer743382
12. März 2013 um 6:55 Uhr
@hvd Dies würde Aufrufe von String-Konstruktor, Zuweisungsoperator, Destruktor verursachen … Ich bin mir nicht sicher, ob dies der effizienteste Weg ist.
– Tommyk
12. März 2013 um 6:59 Uhr
Möchten Sie führende Nullen? Beide Antworten schlagen für Fälle mit führenden Nullen fehl.
– Raptz
12. März 2013 um 7:00 Uhr
Brauchen Sie wirklich „den effizientesten Weg“? Ist dies wirklich der Ort, an dem die gesamte Verarbeitungszeit in Ihrem Programm verbracht wird? Klingt für mich nach verfrühter Optimierung.
– Matthew Strawbridge
12. März 2013 um 7:05 Uhr
Verschiebung und Bitmasken? Nicht in Basis 10. Wenn Sie dies in Basis 16 tun wollten, hätte ich ein paar nette Tricks im Ärmel, aber Binärcomputer mögen Basis 10 einfach nicht.
– Harald
12. März 2013 um 12:07 Uhr