3. Einfaches Tool voller Fehler

Einfaches Tool voller Fehler

  • B

    Ich wollte jetz, daß er noch die einstelligen, die zweistelligen, die dreistelligen -ich hab inzwischen auf dreistellig erhöht, es funktioniert - Ergebnisse absolut und relativ zusammenzählt. Ich würde das mit einer if-Struktur in der letzten for -Schleife machen. Sicher gibt es was eleganteres.

    0
  • C

    Nachwelchen Kriterien willst du die Ergebnisse zusammenzählen? Wenn du von den Faktoren ausgehen willst, solltest du das direkt beim Erstellen der der Produkt-Liste erledigen, wenn du vom der Stellenzahl der Ergebnisse ausgehst, kannst du das in beiden Schleifen machen.

    0
  • B

    Bei dreistelligen Querprodukten, also bis 999 alle durchmultipliziert, gibt es genau 729 Ergebnisse größer als 0, davon nur 100 verschiedene, davon 9 einstellig, 36 zweistellig und 55 dreistellig.

    Diese zahle interessieren. Mit If-Schleifen ist zu fehleranfällig.

    0
  • C

    Die Länge einer Zahl kannst du entweder per if-Auswahl ermitteln oder mit Elementarmathematik: len(x) = ceil(log10(x+1) (bei der Rundung bin ich nicht 100% sicher) - damit kannst du die Anzahlen dann in einem Array oder map<> aufsummieren.

    PS: zur www.if-schleife.de sage ich jetzt nichts 😃

    0
  • B
     

    #include <iostream> 
#include <string> 
#include <sstream> 
#include <map>
using namespace std; 
int zl = 0;
int st1 = 0;
int st2 = 0;
int st3 = 0;
int main () 
{ 
    map<int,int> Ergebnisse; 
    for (int Ziffer1=0; Ziffer1<10; Ziffer1++) 
    { 
        for (int Ziffer2=0; Ziffer2<10; Ziffer2++) 
        { 
		 for (int Ziffer3=0; Ziffer3<10; Ziffer3++) 
		{ 
				++Ergebnisse[Ziffer1*Ziffer2*Ziffer3]; 
		}  
	}       
} 

for(map<int,int>::iterator pos=Ergebnisse.begin();pos!=Ergebnisse.end();++pos) 
{ 
	++zl;
        cout<<"Nr. "<<zl<<" Zahl: "<<pos->first<<" kommt "<<pos->second<<" mal als QP vor"<<endl; 

	if (first < 10)
	st1=st1+1;
	if (first > 10 && first < 100)
	st2=st2+1;
	if (first > 100 && first <1000)
	st3=st3+1;
	}
	cout<<"Innerhalb der Zahlen bis 999 kommen folgende Querprodukte vor";  
	cout<<"1stellig"<<st1<<"\n";
	cout<<"2stellig"<<st2<<"\n";
	cout<<"3stellig"<<st3<<"\n";
}

    Das hab ich geschrieben, aber irgendwie ist der Effekt verschwunden vom Compiler, daß die Befehle farbig sind, alles ist schwarz-weiss, und auf der Konsole läuft nur noch die alte Version, wenn ich auf Run tippe.....+

    0
  • C

    Da sollte dir eigentlich dein Compiler mitteilen, daß die for()-Schleife frei im Raum steht - die sollte schon in der main()-Funktion bleiben. Außerdem wird die 10 (=1*2*5) und 100 (=4*5*5) nicht mitgezählt.

    PS: Und "first" als eigenständige Variable existiert auch nicht - die if-Kaskade sollte eher so aussehen:

    if(pos->first < 10)
  st1+=pos->second;
else if(pos->first < 100)
  st2+=pos->second;
else
  st3+=pos->second;

    Oder die Variante mit STL-Algorithmen:

    int stlimits[] = {0,10,100,1000};
int stellen[5];
for( map<int,int>::iterator pos=Ergebnisse.begin(); pos!=Ergebnisse.end(); ++pos)
{
  cout<<...
  int st = lower_bound(stlimits,stlimits+4,pos->first);
  stellen[st] += pos->second;
}
    0
  • B

    Erst mal ist das das Problem:

    irgendwie ist der Effekt verschwunden vom Compiler, daß die Befehle farbig sind, alles ist schwarz-weiss, und auf der Konsole läuft nur noch die alte Version, wenn ich auf Run tippe.....

    0
  • C

    Bekell schrieb:

    irgendwie ist der Effekt verschwunden vom Compiler, daß die Befehle farbig sind, alles ist schwarz-weiss, und auf der Konsole läuft nur noch die alte Version, wenn ich auf Run tippe.....

    Hast du mal "Rebuild all" ausprobiert? Wenn ich raten müsste, würde ich sagen, daß der Compiler durch die global stehende for()-Schleife ein wenig aus dem Konzept geraten ist.

    (über konkrete Fragen zu deiner IDE kann ich leider nichts sagen)

    0
  • B

    Ich mach mit X-code, bei einer fehlenden Klammer von for würd er das bei error anzeigen. Das Error-Fenster bleibt aber leer, und alle die farbigen Befehle sind auch weg......

    0
  • C

    OK, ich korrgiere mich, die Schleife steht doch nicht global - deine Einrückung ist nur katastrophal.

    Aber die Fehlermeldung von Ideone dürfte das Problem umschreiben:

    prog.cpp: In function ‘int main()’:
    prog.cpp:29: error: ‘first’ was not declared in this scope
    prog.cpp:31: error: ‘first’ was not declared in this scope
    prog.cpp:33: error: ‘first’ was not declared in this scope

    -> Das heißt im Klartext: Die Variable heißt nicht "first", sondern "pos->first"

    0
  • B

    Funktioniert alles, bin schon bei der 8. Stelle, nur beginnt jetz der Comp zu rauchen...:-)

    Ab 09. 05 bin ich wieder hier.

    0
  • C

    Bekell schrieb:

    Funktioniert alles, bin schon bei der 8. Stelle, nur beginnt jetz der Comp zu rauchen...:-)

    Vielleicht solltest du langsam anfangen, diese geschachtelten Schleifen durch einen rekursiven Funktionsaufruf ersetzen, das wird auf Dauer übersichtlicher 😉
    (und bei 100 Millionen Produkten ist es kein Wunder, wenn dein Rechner ne Weile beschäftigt ist)

    0
  • ?

    Wenn Performance langsam kritisch wird, ist es sinnvoll, statt std::map eine Hashtable wie std::tr1::unordered_map zu benutzen und die Ergebnisse am Ende zu sortieren. Die Anzahl der Elemente der Ergebnismenge steigt recht langsam - bei einer Rekursionstiefe von 10 sind es 4357 betroffene Zahlen.

    Es ist schneller, 4357 Zahlen zu sortieren, als sich 10 Millarden mal durch bis zu 12 Baumknoten zu hangeln. Im Bereich einer Rekursionstiefe von 9-10 kann ich auf die Art mit gcc 4.6.0 und -O2 etwa Faktor 2 herausholen:

    #include <iostream>
#include <map>
#include <tr1/unordered_map>

typedef std::tr1::unordered_map<unsigned, unsigned> result_t;
typedef std::map<unsigned, unsigned> sorter_t;

//typedef std::map<unsigned, unsigned> result_t;

void trace_products_rec(result_t &results,
                        unsigned depth_left,
                        unsigned precomputed) {
  if(depth_left == 0) {
    ++results[precomputed];
  } else {
    for(unsigned x = 0; x < 10; ++x) {
      trace_products_rec(results, depth_left - 1, precomputed * x);
    }
  }
}

void trace_products(result_t &results,
                    unsigned depth) {
  results.clear();
  results.max_load_factor(0.7);
  trace_products_rec(results, depth, 1);
}

int main() {
  result_t results;
  sorter_t results_sorted;

  trace_products(results, 9);

  results_sorted.insert(results.begin(), results.end());

  for(sorter_t::const_iterator iter = results_sorted.begin();
      iter != results_sorted.end();
      ++iter) {
    std::cout << iter->first << ": " << iter->second << '\n';
  }

  /*
  for(result_t::const_iterator iter = results.begin();
      iter != results.end();
      ++iter) {
    std::cout << iter->first << ": " << iter->second << '\n';
  }
  */
}

    Bei größeren Rekursionstiefen (dann mit 64-Bit-Integern) geht die Schere noch weiter auf, aber nicht unglaublich schnell. Begründung: Sei n die Rekursionstiefe, N = 10^n und f(N) die Anzahl der Zahlen, die sich in n Faktoren < 10 zerlegen lassen, dann ist die Laufzeitkomplexität für den Map-Ansatz O(N * log(f(N))) und die für Hashtable mit nachfolgender Sortierung O(N + f(N) * log(f(N))). Es sieht für mich sehr danach aus, als sei O(f(N) * log(f(N))) < O(N), in welchem Fall O(Hashtable) = O(N) wäre, auf jeden Fall aber ist O(f(N)) < O(N) und somit O(Hashtable) < O(Map).

    0
  • ?

    Nachtrag: Wo ich genauer darüber nachdenke, kann man sich einen Haufen Arbeit auch sparen, indem man iterativ an die Sache herangeht und sich Zwischenergebnisse merkt:

    #include <iostream>
#include <map>
#include <tr1/unordered_map>

typedef std::tr1::unordered_map<unsigned, unsigned> result_t;
typedef std::map<unsigned, unsigned> sorter_t;

void trace_numbers(result_t &result,
                   unsigned depth)
{
  result_t last_stage;

  last_stage[1] = 1;

  for(unsigned i = 0; i < depth; ++i) {
    result_t new_stage;

    for(result_t::const_iterator iter = last_stage.begin(); iter != last_stage.end(); ++iter) {
      for(unsigned j = 0; j < 10; ++j) {
        new_stage[iter->first * j] += iter->second;
      }
    }

    last_stage.swap(new_stage);
  }

  result.swap(last_stage);
}

int main() {
  result_t result;

  trace_numbers(result, 10);

  sorter_t result_sorted(result.begin(), result.end());

  for(sorter_t::const_iterator iter = result_sorted.begin(); iter != result_sorted.end(); ++iter) {
    std::cout << iter->first << ": " << iter->second << '\n';
  }
}
    0
Anmelden zum Antworten