Не простая задача на c++

146

01 января 2022, 15:30

Ломал голову час, но ничего кроме как решить задачу через массив не получилось. Преподаватель требует решить задачу без использования массивов. Выручайте :(

Среди всех n-значных чисел указать те, сумма цифр которых равна данному числу k (пользователь вводит n и k).

Answer 1

Вот простейшее тупое переборное решение...

unsigned int sum(unsigned int i)
{
    unsigned int s = 0;
    while(i)
    {
        s += i%10;
        i /= 10;
    }
    return s;
}
int main()
{
    unsigned int n;
    cin >> n;
    unsigned int k;
    cin >> k;
    unsigned int start = 1;
    for(unsigned int i = 1; i < n; ++i) start *= 10;
    for(unsigned int i = start; i < start*10; ++i)
        if (sum(i) == k) cout << i << endl;
}

Может, вы что-то путаете? потому что я что-то не понимаю, а зачем тут массив...

Можно извратиться и сделать рекурсивно :)

void rdoit(unsigned int n, unsigned int k, string r = "", bool zero = false)
{
    if (n == 0 && k == 0) cout << r << endl;
    if (n == 0) return;
    for(unsigned int i = (zero) ? 0 : 1; i <= 9; ++i)
    {
        if (k < i) break;
        rdoit(n-1,k-i,r + to_string(i),true);
    }
}