Algorithmus gesucht ...



  • ... hab jetzt eine funktionierende map, wo als Schlüssel Zahlen sind, dann wird als Wert eine 1 oder 2 zugeordnet.

    Jetzt brauche ich einen Algorithmus, der mir in einem abgegrenzten Bereich sagt, wieviele Einsen im Werte-Bereich stehen.

    Gibt es zu count irgendwelche Unterbefehle? Bei mir im Buch steht nichts.

    Ich will sowas: Wieviele Einsen sind im Wertebereich von 10 bis 20.



  • Versuch eine geschickte Kombination von std::count_if (in <algorithm> ) und std::map::lower_bound und std::map::upper_bound .



  • Danke, kannst Du mir eine deutsche Seite hier linken, auf der die Befehle, möglichst mit Beispielen erklärt werden...

    in meinem Buch werden die nur erwähnt, ohne irgendwelche Erklärungen.

    Danke



  • Erklärung zu count_if hier: http://de.cppreference.com/w/cpp/algorithm/count
    Du brauchst wirklich count_if weil du nur die Werte vergleichen willst aber nicht die Keys.

    Zu lower_bound/upper_bound gibts nur eine englische Seite: http://en.cppreference.com/w/cpp/container/map/lower_bound
    Ist aber auch nicht so kompliziert die Funktion und die englische Erklärung ist hoffentlich für dich verständlich. Nicht von dem ganzen Zeug ablenken lassen der da sonst noch steht. Eigentlich reicht die Info unter Punkt 1) schon.



  • Sonne55 schrieb:

    Danke, kannst Du mir eine deutsche Seite hier linken, auf der die Befehle, möglichst mit Beispielen erklärt werden...

    Nee. Kann ich nicht. Sorry.
    Siehe sebi707s Links.

    count_if() ist wohl klar.
    std::map::lower_bound gibt das erste Element wieder, dessen Key größer oder gleich dem Argument ist.

    std::map::upper_bound() brauch ich eigentlich gar nicht.

    #include <iostream>
    #include <algorithm>
    #include <map>
    
    using namespace std;
    
    enum { foo=1, bar=2};
    
    // alle "foo-Elemente" im Bereich [10, 20) zaehlen:
    int main(){
      using map_t = map<int,int>;
      map_t m = {{1,foo},{2,foo},{10,foo},{11,foo},{12,foo},{13, bar},{20, foo}};
      // Elemente, die wir suchen:  X        X        X
      // Das letzte foo liegt ausserhalb des Suchbereichs!
    
      // Suchbereich abstecken:
      // erstes Element:
      auto first = m.lower_bound(10);
      // "eins hinter das letzte Element"
      auto last  = m.lower_bound(20);
    
      // is es "foo"?
      auto is_foo = [](const map_t::value_type& p){ return p.second==foo; };
    
      // das eigentliche zaehlen:
      auto n = count_if(first, last, is_foo);
      cout << n << endl; // 3
    }
    


  • Furble Wurble schrieb:

    std::map::upper_bound() brauch ich eigentlich gar nicht.

    Kommt drauf an wie "Wertebereich von 10 bis 20" zu verstehen ist. Wenn die 20 nicht mehr mit drin ist dann ja. Wenn die 20 mit drin sein soll würde man

    auto last  = m.upper_bound(20);
    

    schreiben.



  • [code="cpp"] auto is_foo[code="cpp"]

    das versteh ich nicht!



  • Sonne55 schrieb:

    auto is_foo
    

    das versteh ich nicht!

    Das würde jetzt ein wenig weit führen, auto und Lambdas zu erklären, die seit C++11 (also ca vier Jahre) im Standard sind.

    Lies Dich in beides ein.

    Bis dahin:
    mach eine Funktion draus:

    bool is_foo(const map_t::value_type& p){
      return p.second==foo;
    }
    


  • Ich hab Dein Skript ma angepastt und er sagt bei "auto is_2" "expect a Class oder namespace"

    // erstes Element:
            auto first = prufzahlen.lower_bound(10); // "eins hinter das letzte Element"
            auto last  = prufzahlen.lower_bound(20); // ob es 2 sind?
            auto is_2 = [](const prufzahlen::value_type& p){return p.second=2; };
    
            // das eigentliche zaehlen:
            auto n = count_if(last= 2);
            cout << n << endl;
    


  • Sonne55 schrieb:

    Ich hab Dein Skript ma angepastt und er sagt bei "auto is_2" "expect a Class oder namespace"

    // erstes Element:
            auto first = prufzahlen.lower_bound(10); // "eins hinter das letzte Element"
            auto last  = prufzahlen.lower_bound(20); // ob es 2 sind?
            auto is_2 = [](const prufzahlen::value_type& p){return p.second=2; };
            
            // das eigentliche zaehlen:
            auto n = count_if(last= 2);
            cout << n << endl;
    

    Ich habe mitlerweile Deinen anderen Thread gesehen und gehe davon aus, dass prufzahlen in Z. 4 oben eine variable und kein Typ ist.
    Der Typ ist std::map<int,int> .

    Also wäre korrekt:

    auto is_2 = [](const std::map<int,int>::value_type& p){return p.second==2; }; // noch ein Typo gefixt...
    

    In meinem Beispiel hatte ich mit

    using map_t = std::map<int,int>;
    

    einen eigenen Namen für Diesen Typ eingeführt.

    Wir sprechen übrigens nicht von "Skript" sondern einfach von Programm oder Quellcode.



  • Furble Wurble schrieb:

    Ich habe mitlerweile Deinen anderen Thread gesehen und gehe davon aus, dass prufzahlen in Z. 4 oben eine variable und kein Typ ist.
    Der Typ ist std::map<int,int> .

    Danke

    Furble Wurble schrieb:

    Also wäre korrekt:

    auto is_2 = [](const std::map<int,int>::value_type& p){return p.second==2; }; // noch ein Typo gefixt...
    

    In meinem Beispiel hatte ich mit

    using map_t = std::map<int,int>;
    

    einen eigenen Namen für Diesen Typ eingeführt.

    Aha ...

    bei mir sagt er jetze: "Unused variable "is_2" " Ist wirklich ungewöhnlich ...

    Ich hätte ja auch bei Deiner foo-bar-Lösung bleiben können und mit Pz Vf ersetzen, aber mit denen kann man nicht rechnen, denn ich habe doch als Typ nicht umsonst int genommen.



  • Furble Wurble schrieb:

    Also wäre korrekt:

    auto is_2 = [](const std::map<int,int>::value_type& p){return p.second==2; }; // noch ein Typo gefixt...
    

    Oder wenn dein Compiler schon C++14 (generic lambdas) unterstützt kannst du dort auch auto nutzen:

    auto is_2 = [](const auto& p){return p.second==2; };
    

    Sonne55 schrieb:

    bei mir sagt er jetze: "Unused variable "is_2" " Ist wirklich ungewöhnlich ...

    Das heißt dann das du is_2 (noch) nicht benutzt hast und ist natürlich nur eine Warnung. Das is_2 Objekt brauchst du ja dann für die count_if Funktion und dann sollte auch die Warnung weg sein. Der Code

    auto n = count_if(last= 2);
    

    ist auch falsch. Mache es so wie im Beispiel von Furble Wurble nur mit is_2 , statt is_foo .



  • okay ... jetzt gibt er einen 0 aus ...

    Was ich nicht versteh:

    auto n = count_if(first, last, is_2);
    

    Er soll doch nur in "last" suchen, wieviele 2-en er dort findet. Warum kommt in die Klammer das first rein? In "first" stehen doch nur die PZ drin, und nicht eine einzige 2.

    Sind die Klammerangaben denn nicht,
    a - wo er suchen soll
    b - was er suchen soll?



  • sebi707 schrieb:

    Oder wenn dein Compiler schon C++14 (generic lambdas) unterstützt kannst du dort auch auto nutzen:

    auto is_2 = [](const auto& p){return p.second==2; };
    

    ... habe übrigens yosemite Xcode 6.1.1 ist das schon 14, oder noch 11?



  • Die Variable last ist nur ein Iterator auf ein Element (oder auch gar keins) und nicht mehrere. Du willst aber mehrere Elemente testen und genau das macht count_if . Es durchsucht alle Elemente zwischen first und last ( last nicht mit eingeschlossen). Der dritte Parameter ist dann was überhaupt gesucht wird. In deinem Fall ist das eine Lambda Funktion die prüft ob der Wert gleich 2 ist und den Key unberücksichtigt lässt.

    Sonne55 schrieb:

    ... habe übrigens yosemite Xcode 6.1.1 ist das schon 14, oder noch 11?

    Keine Ahnung. Probier doch einfach aus obs compiliert.



  • Danke, ich dachte fälschlicherweise first und last sind die beiden einanderzugeordnteten int von map.

    Jetzt müssten wir nur noch klären, warum er nicht zählt sondern imer eine Null ausgibt.... ich will nämlich in einem weiteren Schritt first und last noch dynamisieren. Kann ich mit denen rechnen? Drinne sein in map tut ja was, denn er druckt es ja aus ....

    #include <iostream>
    #include <stdio.h>
    #include <cmath>
    #include <map>
    using namespace std;
    
    int pzz=1; //Primzahlzähler
    int vfz=1; //Vielfachenzähler
    int ruz=1; //Rundenzähler
    
    int main()
    {
        map <int,int> prufzahlen;
        map<int,int>::iterator iter;
        int x, i;
        for (x = 31; x <= 1200; x=x+30)
        {
            ruz++;
            for (i = 2; i < x; i++)
            {
                if (x%i == 0)
                    break;
                //cout<<i<<"= i \n";
            }
    
            if (i == x)
            {
                cout<<"Nr. "<<ruz<<" "<<x<<" = "<<pzz<<". Pz. \n";
                pzz++;
                 prufzahlen.insert(pair<int, int>(x, 1));
            }
            else
            {
                cout<<"Nr. "<<ruz<<" "<<x<<" = "<<vfz<<". uVf. \n";
                vfz++;
                prufzahlen.insert(pair<int, int>(x, 2));
            }
    
            for (iter = prufzahlen.begin(); iter != prufzahlen.end(); iter++)
                    {
                    cout << iter->first << " ";
                    cout << iter->second << " ";
                    cout << endl;
    
                    }
            std::cout << "Kette hat " << prufzahlen.size() << " Zahlen"<<'\n';
    
            auto first = prufzahlen.lower_bound(1);// erstes Element:
            auto last  = prufzahlen.lower_bound(20); // "eins hinter das letzte Element"
            auto is_2 = [](const map<int,int>::value_type& p){return p.second==2; };// ob es 2 sind?
    
            // das eigentliche zaehlen:
            auto n = count_if(first, last, is_2);
            cout << n << endl;
    
        }
        return 0;
    }
    


  • Sonne55 schrieb:

    Jetzt müssten wir nur noch klären, warum er nicht zählt sondern imer eine Null ausgibt.... ich will nämlich in einem weiteren Schritt first und last noch dynamisieren. Kann ich mit denen rechnen?

    Du durchsuchst nur Werte mit Key zwischen 1 und 20. Dein kleinster Key ist aber 31 also zählt er natürlich auch nichts. Mit first und last kannst du nicht rechnen. Du kannst aber mit den Zahlen rechnen die du in lower_bound einsetzt.

    Noch eine Anmerkung zum Code: Sollte deine for (x = 31; x <= 1200; x=x+30) Schleife nicht nach dem else enden? Jetzt kommt die komplette Ausgabe nach jedem Element das hinzugefügt wird.



  • sebi707 schrieb:

    Du durchsuchst nur Werte mit Key zwischen 1 und 20. Dein kleinster Key ist aber 31 also zählt er natürlich auch nichts. Mit first und last kannst du nicht rechnen. Du kannst aber mit den Zahlen rechnen die du in lower_bound einsetzt.

    aha ... ich dachte 1 und 20 sind vom 1. bis zum 20. Wertepaar. .... Kann man in Maps die Wertepaare nicht einzeln ansteuern?

    sebi707 schrieb:

    Noch eine Anmerkung zum Code: Sollte deine for (x = 31; x <= 1200; x=x+30) Schleife nicht nach dem else enden? Jetzt kommt die komplette Ausgabe nach jedem Element das hinzugefügt wird.

    Ja, das ist zur Prüfung. Wenn ich nachher richtige Zahlen einsetzte, wird das wegkommentiert.



  • Vielleicht erklärst du nochmal was du überhaupt willst. In deiner ersten Frage redest du von "Wertebereich von 10 bis 20". Darunter habe ich verstanden, dass du den Bereich der Keys einschränken willst auf den Bereich von 10 bis 20. Jetzt willst du aber das 10. bis 20. Wertepaar, egal welchen Key Bereich das abdeckt? Das ist mit einer std::map leider nicht wirklich effizient zu machen. Warum hast du dich überhaupt für eine map entschieden? Im bisher gezeigten Code hätte auch ein vector gereicht.



  • Wat ik will is...

    Er soll jetzt von der ersten Häfte der Zahlenkette mir die Abzagl der PZ ausgeben und von der zweiten Hälfte die Anzahl der Vielfachen.

    Er soll also von 1 - X/2 die Einsen Zählen und von X/2 bis X+1 die Zweien.

    Leider macht er das nicht, weil man den count if Befehl wohl nicht zwei mal hintereinander anwenden kann...

    #include <iostream>
    #include <stdio.h>
    #include <cmath>
    #include <map>
    using namespace std;
    
    int pzz=1; //Primzahlzähler
    int vfz=1; //Vielfachenzähler
    int ruz=1; //Rundenzähler
    
    int main()
    {
        map <int,int> prufzahlen;
        map<int,int>::iterator iter;
        int x, i;
        for (x = 31; x <= 1200; x=x+30)
        {
            ruz++;
            for (i = 2; i < x; i++)
            {
                if (x%i == 0)
                    break;
                //cout<<i<<"= i \n";
            }
    
            if (i == x)
            {
                cout<<"Nr. "<<ruz<<" "<<x<<" = "<<pzz<<". Pz. \n";
                pzz++;
                 prufzahlen.insert(pair<int, int>(x, 1));
            }
            else
            {
                cout<<"Nr. "<<ruz<<" "<<x<<" = "<<vfz<<". uVf. \n";
                vfz++;
                prufzahlen.insert(pair<int, int>(x, 2));
            }
    
            for (iter = prufzahlen.begin(); iter != prufzahlen.end(); iter++)
                    {
                    cout << iter->first << " ";
                    cout << iter->second << " ";
                    cout << endl;
    
                    }
            std::cout << "Kette hat " << prufzahlen.size()+1 << " Glieder"<<'\n';
    
            auto first = prufzahlen.lower_bound(1);// erstes Element:
            auto last  = prufzahlen.lower_bound((x/2)+1); // "eins hinter das letzte Element"
            auto is_1 = [](const map<int,int>::value_type& p){return p.first==1; };// ob es 1 sind?
            // das eigentliche zaehlen:
            auto n = count_if(first, last, is_1);
            cout<<"davon unten "<< n <<" PZ"<< endl;
    
            auto first = prufzahlen.lower_bound(x/2);
            auto last  = prufzahlen.lower_bound(x+1);
            auto is_2 = [](const map<int,int>::value_type& p){return p.second==2; };
            auto nx = count_if(first, last, is_2);
            cout<<"davon "<< nx <<" Vf"<< endl;
    
        }
        return 0;
    }
    

    Er sagt immer Redefinition of last and first, naja mussick ja, wenn ich was andret will, dat er zehlen soll...

    Also bei map kann man 2 Zahlen miteinander verkoppeln. Gibt es auch einen Contener, wo man 3 Zahlen miteinander verkoppeln kann?


Log in to reply