Wszystkie liczby których suma cyfr wynosi X

pytanie zadane 10 listopada 2020 w Algorytmy przez amtrax Dyskutant (9,630 p.)

Cześć,

Mam podane dwie zmienne:

a - liczba cyfr w liczbie

b - pożądana suma

Moim zadaniem jest znalezienie wszystkich liczb o długości a, których suma wynosi b.

Zastanawiam się czy istnieje wydajny algorytm, który pozwala znaleźć takie liczby? Od czego byście zaczęli rozwiązując tego typu problem?

1	komentarz 10 listopada 2020 przez Whistleroosh Maniak (57,400 p.) To zależy od tego czy masz wypisać wszystkie te liczby czy może policzyć ile ich jest. Mogę podpowiedzieć, że można to rozwiązać albo rekurencją albo programowaniem dynamicznym

komentarz 10 listopada 2020 przez mokrowski Mędrzec (158,960 p.)

@amtrax, rozumiem że chodzi o notację dziesiętną? Zacznij od algorytmu brutalnego. Czyli przeszukania przestrzeni rozwiązań liniowo. To wyjaśni Ci kilka elementów ostatecznego rozwiązania i da oszacowanie dla mniej wydajnego rozwiązania. I co ważniejsze pozwoli wpaść na lepsze metody rozwiązania :)