PROBLEM WITH INTEGER SUM


  • Mod

    Das ist übrigens A051885, falls sich ein Leser wundert, was die Aufgabe soll.


  • Gesperrt

    @bugsfinder2022 If all "functions" in a class are static-defined, there is no need for such a class, especially if it contains no more than two functions.

    Moreover, the class does not contain any attributes at all...



  • Yes, I agree that we dont need classes nor static members here.


  • Gesperrt

    Ich hab mir mal die Mühe gemacht und das implementiert... Ich wäre froh, wenn noch mal jemand draufschauen könnte... 🙂

    #include <iostream>
    #include <vector>
    
    class Smallest
    {
    public:
        long smallest_number_whose_sum_of_digits_is_n(const unsigned int n)
        {
    	if(numbers.size() < n) {
    	    for(unsigned int i = numbers.size(); i < n; i++) {
    		smallest_number_whose_sum_of_digits_is_n(i);
    	    }
    	    return smallest_number_whose_sum_of_digits_is_n(n);
    	}
    	if(numbers.size() == n) {
    	    long start = numbers.back();
    	    long sum;
    	    while((sum = sum_of_digits(start)) != n) {
    		start++;
    	    }
    	    numbers.push_back(start);
    	}
    	return numbers[n];
        }
        long sum_of_digits(long n)
        {
    	long sum = 0;
    	while(n > 0) {
    	    sum += n % 10;
    	    n /= 10;
    	}
    	return sum;
        }
    
    private:
        std::vector<long> numbers { 0 };
    };
    
    int main(int argc, char** argv)
    {
        Smallest s;
        std::cout << " 5: " << s.smallest_number_whose_sum_of_digits_is_n(5) << "\n";
        std::cout << "19: " << s.smallest_number_whose_sum_of_digits_is_n(19) << "\n";
        for(int i = 10; i <= 30; i++) {
    	std::cout << i << ": " << s.smallest_number_whose_sum_of_digits_is_n(i) << "\n";
        }
        return 0;
    }
    
    

    In der main-Methode stehen ein paar Testausgaben.


  • Gesperrt

    Upps, klar gab es noch ein paar Unstimmigkeiten:

    #include <iostream>
    #include <vector>
    
    class Smallest
    {
    public:
        long smallest_number_whose_sum_of_digits_is_n(const unsigned int n)
        {
    	if(numbers.size() < n) {
    	    for(unsigned int i = numbers.size(); i < n; i++) {
    		smallest_number_whose_sum_of_digits_is_n(i);
    	    }
    	}
    	if(numbers.size() == n) {
    	    long start = numbers.back();
    	    while(sum_of_digits(++start) != n)
    		;
    	    numbers.push_back(start);
    	}
    	return numbers[n];
        }
        long sum_of_digits(long n)
        {
    	long sum = 0;
    	while(n > 0) {
    	    sum += n % 10;
    	    n /= 10;
    	}
    	return sum;
        }
    
    private:
        std::vector<long> numbers { 0 };
    };
    
    int main(int argc, char** argv)
    {
        Smallest s;
        std::cout << " 5: " << s.smallest_number_whose_sum_of_digits_is_n(5) << "\n";
        std::cout << "19: " << s.smallest_number_whose_sum_of_digits_is_n(19) << "\n";
        for(int i = 0; i <= 30; i++) {
    	std::cout << i << ": " << s.smallest_number_whose_sum_of_digits_is_n(i) << "\n";
        }
        return 0;
    }
    
    

  • Gesperrt

    @EinNutzer0 sagte in PROBLEM WITH INTEGER SUM:

    ++start

    Das ist nicht besonders performant... Beispiel:

        for(int i = 0; i < std::numeric_limits<int>::max(); i++) {
    	std::cout << i << ": " << s.smallest_number_whose_sum_of_digits_is_n(i) << "\n";
        }
    

    😭


  • Gesperrt

    Jetzt aber / Now for it:

    #include <algorithm>
    #include <iostream>
    #include <limits>
    #include <vector>
    
    class Smallest
    {
    public:
        long smallest_number_whose_sum_of_digits_is_n(const unsigned int n)
        {
    	if(n > 162) {
    	    return -1;
    	}
    	if(numbers.size() < n) {
    	    for(unsigned int i = numbers.size(); i < n; i++) {
    		smallest_number_whose_sum_of_digits_is_n(i);
    	    }
    	}
    	if(numbers.size() == n) {
    	    long start = numbers.back();
    	    while(sum_of_digits(start = inc_backwards(start)) != n)
    		;
    	    numbers.push_back(start);
    	}
    	return numbers[n];
        }
        long sum_of_digits(long n)
        {
    	long sum = 0;
    	while(n > 0) {
    	    sum += n % 10;
    	    n /= 10;
    	}
    	return sum;
        }
        long inc_backwards(long n)
        {
    	std::string s = std::to_string(n);
    	std::reverse(s.begin(), s.end());
    	if(s.back() == '9') {
    	    s.push_back('0');
    	}
    	s = std::to_string(std::stol(s) + 1);
    	std::reverse(s.begin(), s.end());
    	return std::stol(s);
        }
    
    private:
        std::vector<long> numbers { 0 };
    };
    
    int main(int argc, char** argv)
    {
        Smallest s;
        for(int i = 0; i <= 200; i++) {
    	std::cout << i << ": " << s.smallest_number_whose_sum_of_digits_is_n(i) << "\n";
        }
        return 0;
    }
    
    


  • @EinNutzer0 Warum nicht die Formel?

    #include <iostream>
    #include <cmath>
    
    int main(int argc, char** argv)
    {
        for(int i = 0; i <= 50; i++) {
            std::cout << i << ": " << (i%9 + 1) * std::pow(10, i / 9) - 1 << "\n";
        }
    }
    

  • Gesperrt

    @Leon0402 Das sieht auch gut aus, ich dachte zunächst, es sollte algorithmisch gelöst werden. 😕


Anmelden zum Antworten