Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/2: Рейтинг темы: голосов - 2, средняя оценка - 4.50
egorichevs
0 / 0 / 1
Регистрация: 09.02.2015
Сообщений: 24
1

Количество N-разрядных натуральных чисел, у которых сумма цифр делится на K

12.03.2015, 02:15. Просмотров 494. Ответов 1
Метки нет (Все метки)

Пожалуйста, помогите решить задачу:

Определите количество N-разрядных натуральных чисел, у которых сумма цифр делится на K.

Входные данные:
числа N и K через пробел, N от 1 до 10, K от 1 до 9N.

Выходные данные:
количество таких чисел

Пример входных данных:
2 17

Пример выходных данных:
2

Примечание 1: это числа 89 и 98.

Примечание 2: при реализации "ленивого" динамического программирования
(дополнением к рекурсии) стоит запоминать в матрице и нулевые решения,
иначе можно получить предел времени.


Добавлено через 8 часов 28 минут
Господа, сделал на коленке такое решение методом перебора.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL, "Russian");
    int N,K;
    do {
    std::cout << "Введите N:  ";
    std::cin >> N;
    }
    while (N < 1 || N > 10);
    do 
    {
        std::cout << "Введите K:  ";
        std::cin >> K; 
    }
    while (K < 1 || K > 9*N);
    std::cout << "Количество чисел: " << Ncount(N, K) << "\n";
    system("pause");
    return 0;
}
 
int Ncount(int N, int K)
{
    auto d = 1, count = 0;
    for(auto i = 0; i < N ; i++) d *= 10;
    d -= 1;
    for(auto i = K ; i <= d ; i++)
    {
        int n = i, sum = 0;
        while( n != 0 )
        {
            sum += n%10;
            n /=10;
        }
        if (sum % K == 0) count++;  
    }
    return count;
}
Каким образом это все можно сделать на основе рекурсии? Не пойму с чего начать.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2015, 02:15
Ответы с готовыми решениями:

Найти количество N-разрядных натуральных чисел, у которых сумма цифр делится на K
Условие задачи: Определите количество N-разрядных натуральных чисел, у которых сумма цифр делится...

Определить количество трехзначных натуральных чисел, сумма цифр которых равна заданному числу N
Определить количество трехзначных натуральных чисел, сумма цифр которых равна заданному числу N.

Определить количество трёхзначных натуральных чисел сумма цифр которых равна заданному числу
Всем Привет! Помогите пожалуйста написать простенькую программу без сильно замороченного кода на...

Определить количество натуральных трехзначных чисел, сумма цифр которых равна заданному числу N
1. Определить количество натуральных трехзначных чисел, сумма цифр которых равна заданному числу N.

Определить количество трехзначных натуральных чисел, сумма цифр которых равна данному числу
П. 5.4. Правил Запрещено создавать темы с бессмысленными названиями вроде &quot;Помогите!&quot;, &quot;Вопрос&quot; и...

1
Katiss
7 / 7 / 1
Регистрация: 15.02.2015
Сообщений: 46
16.03.2015, 19:46 2
Та же проблема. Но код немного другой:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
    int  N, K, sum, num, n, m, k, i=0, num10;
    cin>>N;
    if (N<0||N>=10);
    cin>>K;
    if (K<0||K>9*N) 
    for (int i=2; i<=m; i++) num*=10;
    num10=num*10;
    for (; num<num10; num++)
    {
        int numn=num;
        sum=0;
    do
    {
        sum+=numn%10;
        numn/=100;
    }
    while (numn>0);
    if(sum==n) k++;
    }
    cout<<k<<" "<<m<<" "<<n<<"\n";
    return 0;
}
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2015, 19:46

Найти количество N-значных натуральных чисел, сумма цифр каждого из которых равняется M (оптимизирвать код)
Здравствуйте, уважаемые знатоки. Мне снова нужна помощь по оптимизации решения. Со сложностью...

Определить количество М-значных натуральных чисел, у которых сумма цифр, стоящих в нечетных разрядах, равна N
Определить количество М-значных натуральных чисел, у которых сумма цифр, стоящих в нечетных...

Подсчитать количество n-значных натуральных чисел, у которых сумма цифр нечетная, а младшая цифра четная
Пожалуйста, помогите сделать задачу , спасибо кто откликнется! Подсчитать количество...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.