Polydivisible



  • Hallo, ich habe ein kleines Programm geschrieben, das polydivisible Zahlen in jeden Zahlensystem findet. Leider brauch das Programm ewig ab 13 Zahlen, deswegen will ich hier fragen, ob jemand einen Tipp für mich hat, wie ich den Code verbessern bzw. schneller machen kann.

    #include <iostream>
    #include <string>
    #include <sstream>
    #include <vector>
    #include <algorithm>
    #include <boost/range/adaptor/reversed.hpp>
    
    int forming(const std::vector<int>& values)
    {
        int count = 1;
        int value = 0;
    
        for(auto i : boost::adaptors::reverse(values))
        {
            value += (i * count);
    
            count *= 10;
        }
    
        return value;
    }
    
    bool isPolydivisible(const std::vector<int>& values)
    {
       std::size_t count = 1;
    
       while(count != values.size())
       {
           std::vector<int> value;
    
           for(std::size_t i = 0; i < count + 1; ++i)
           {
               value.push_back(values[i]);
           }
    
           int sum = forming(value);
    
           if(sum % (count+1) != 0)
           {
               return false;
           }
    
           ++count;
       }
    
       return true;
    }
    
    int main()
    {
        int count = 1;
        std::vector<int> values;
    
        while(count<15)
        {
            values.push_back(count);
    
            std::cout << "trying to find polydivisible values in number system " << values.size() + 1 << "\n";
    
            do
            {
                if(isPolydivisible(values))
                {
                    std::cout << "we have found a polydivisible value!\n"
                              << "at combination: ";
    
                    for(const auto& iter : values)
                    {
                        std::cout << iter << " ";
                    }
                    std::cout << std::endl;
                }
            } while(std::next_permutation(values.begin(), values.end()));
    
        ++count;
        }
    }
    


  • Irgendwie ist dein Programm nicht ganz richtig, zumindest nach dem "Polydivisible Number" Wikipedia Artikel. Dein Programm nimmst einfach aufsteigende Zahlen und versuchst daraus eine Polydivisible Number zur Basis 10 (wegen dem *10 in forming) zu finden und nicht in Unterschiedlichen Zahlensystemen.

    OK und nun zur Performance. Ich würde versuchen die Polydivisible Numbers nach und nach aufzubauen, statt alle Kombinationen durchzuprobieren. Angenommen du hast alle 3-stelligen Polydivisible Numbers in einer bestimmten Basis und willst nun alle 4-stelligen Polydivisible Numbers. Dann können die 4-stelligen Zahlen nur genauso anfangen wie die 3-stelligen Zahlen + eine vierte Zahl. Und so baust du nach und nach immer längere Zahlen.


Log in to reply