Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вычислить значение выражения в постфиксной (польской) записи https://www.cyberforum.ru/ cpp-beginners/ thread1398779.html
1. Дана постфиксная (польская) запись арифметического выражения, содержащая целые числа типа int и знаки действий +,-,*,/ (знак / означает целочисленное деление). Элементы выражения разделены ...
Потоковый метод ignore(int, char) C++
Опишите механизм работы данного метода. cin.ignore(MAX, '\n'); Я правильно понял, что данный метод удаляет MAX символов из потока, не трогая символ '\n' ? Или же символ '\n' он тоже удаляет?
C++ Обработка матрицы https://www.cyberforum.ru/ cpp-beginners/ thread1398743.html
Дана целочисленная квадратная матрица. Определить: а) произведение элементов в тех строках, которые содержат хотя бы один отрицательный элемент; б) минимум среди сумм элементов диагоналей,...
C++ Нахождение количества простых чисел в матрице https://www.cyberforum.ru/ cpp-beginners/ thread1398725.html
:wall:Помогите пожалуйста написать программу в C++ !!!) Очень нужно !!)) Для периметра массива X определить количество простых чисел. Заменить наибольшее из них средним арифметическим всех элементов...
C++ Создание модульной программы в Dev C++ 5.9.2
Прошу объяснить! Скачал и установил компактный компилятор Dev C++ 5.9.2. На этом ПК операционная система Windows XP. Нормально компилятор транслирует на C и на C++, создается исполняемый файл...
C++ Завершение проекта или "а как запустить?" Все просто до безумия, но ответ не очевиден. Есть законченный и работающий проект, т.е. в Visual Studio 2012 при нажатии ф5 в режиме дебага и релиза выдает полностью устраивающий меня результат. Я... https://www.cyberforum.ru/ cpp-beginners/ thread1398650.html
C++ Судоку проверка написал столько . рповерка для строк написал . а вот для столбцов и для 3*3 ячеек не смог . помогите пожалуйста . ну надо проверить так чтоб не повторялись числа от 1 до 9 #include <iostream>... https://www.cyberforum.ru/ cpp-beginners/ thread1398646.html Разбить цикл на несколько вложенных C++
Помогите разбить большой цикл int n=100; for(int i=1; i<=n; i++) { printf("%d\n",i); } на k более мелких циклов. Причем k можно указывать больше, чем n. В этом случае лишние циклы должны...
C++ Создание односвязного списка Доброго времени суток. И так. Имеется задача. Создание односвязного списка и инициализация его с клавиатуры. Совсем запутался. #include "stdafx.h" #include <iostream> #include <conio.h> https://www.cyberforum.ru/ cpp-beginners/ thread1398616.html C++ Создать бинарный файл, внутри которого можно производить удаление и обновление инфомрации, а также добавление Добрый вечер! Подскажите, если кто-либо знает! Необходимо создать бинарный файл, внутри которого можно производить удаление и обновление инфомрации, а также добавление. Не понимаю, как можно... https://www.cyberforum.ru/ cpp-beginners/ thread1398606.html
Выдать наименьшее количество денег C++
Пусть имеются 10,20,50,100,200,500 гривень.Необходимо определить наименьшое количество купюр, которые необходимо использовать чтобы выдать Sum рублей.Если же сумму выдать нельзя то вывести -1....
C++ Подскажите по поводу перегрузки функции https://www.cyberforum.ru/ cpp-beginners/ thread1398571.html
Ребят где можна посмотреть примеры такого типа задач. 1. Написать перегруженные функции (int, double, char) для выполнения следующих задач:  инициализация квадратной матрицы;...
4772 / 2233 / 283
Регистрация: 01.03.2013
Сообщений: 5,874
Записей в блоге: 25
21.03.2015, 02:04 0

Натуральные числа у которых сумма цифр делится на K - C++ - Ответ 7368674

21.03.2015, 02:04. Показов 1018. Ответов 3
Метки (Все метки)

Ответ

Интересная задачка Выше представленный кот при R=9 уже призадумывается надолго Пришлось делать своего специального боевого генно-модифицированного бездонно-рекурсивно-мемоизационного, который считает влет любые мыслимые R и S, а если вооружить его длинной арифметикой - то и немыслимые:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef unsigned long long int ull;
const int rmax = 100; ull dp [rmax] [rmax*9]; ull f(int, ull, int);
 
ull loop(int i, int r, ull s, ull a) { return (i<10) ? loop(i+1, r, s, a+f(r, s-i, 0)) : a;}
 
ull f(int r, ull s, int i0) {
    if (s==0)                               return 1;
    else if (s<0 || s>r*9 || r==0)          return 0;
    else if (dp[r][s])                      return dp[r][s];
    else { dp[r][s] = loop(i0, r-1, s, 0);  return dp[r][s]; }
}
ull res(int r, ull s, ull k, ull a) {ull d=f(r, s, 1); return (d) ? res(r, s+k, k, a+d) : a;}
 
int _tmain(int argc, _TCHAR* argv[]) {
    int r; ull k; cout << "Input r [<" << rmax << "], k [>0]: "; cin >> r >> k;
    cout << res(r, k, k, 0) << endl;
    system("pause"); return 0;
}
По доброй традиции - без единого цикла, правда с растяжкой на ссылочную переменную (у меня для краткости - глобальная, хотя можно и статическую или в мэйне нарезать и ссылку передавать - не принципиально). Прошу пробовать и делиться впечатлениями

Не по теме:

UPD все-таки решил обратиться за длинной арифметикой (понятно куда :) ), заодно применил и очередной раз проверил позавчера написанный наколенный монадный мемоизатор - получилось очень неплохо:

Haskell
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
evaluateFunction :: Ord a => (a -> Either b ([a], [b] -> b)) -> a -> b
evaluateFunction f n = runST $ do
    ref <- newSTRef Map.empty
 
    let memoDP ref i = do
            mref <- readSTRef ref
            case Map.lookup i mref of
                Just v  -> return v
                Nothing -> do
                    r    <- coreDP (memoDP ref) i
                    mref <- readSTRef ref
                    writeSTRef ref $ Map.insert i r mref
                    return r
 
        coreDP g i = case f i of
            Left  v      -> return v
            Right (l, t) -> do
                r <- mapM g l
                return $ t r
 
    r <- memoDP ref n
    return r
 
core (r, s, i0) | s==0                 = Left 1
                | s<0 || s>r*9 || r==0 = Left 0
                | otherwise            = Right (l, sum)
                where l = zip3 (repeat $ r-1) (map (s-) [i0..9]) (repeat 0)
 
res :: Integer -> Integer -> Integer
res r k = go r k k 0 where
    go r s k a | d==0      = a
               | otherwise = go r (s+k) k (a+d)
               where d = f r s 1
                     f r s i0 = evaluateFunction core (r, s, i0)
 
main = print $ res 210 1137
199704895018197513774162329639806112769763115080354789960779 2907849431
150952108019165330909913076516664078629244995346238309114817 1100805743
858577884141673700025560895751568633662034044980450554852989 2100



Вернуться к обсуждению:
Натуральные числа у которых сумма цифр делится на K C++
2
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.03.2015, 02:04
Готовые ответы и решения:

Найти все 4-х значные натуральные числа, у которых сумма крайних цифр равна сумме средних, а само число делится на A
Найти все четырехзначные натуральные числа, у которых сумма крайних цифр равна сумме средних цифр,...

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

Найти все четырёхзначные числа, у которых сумма крайних цифр равна сумме средних цифр, а само число делится на 6 и 27
найти все четырёхзначные числа , у которых сумма крайних цифр равна сумме средних цифр , а само...

Нужно найти все числа в диапазоне, сумма цифр которых делится на k
Всем добрый день. Нужно найти все числа в диапазоне, сумма цифр которых делится на k. Не могу...

3
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.03.2015, 02:04

Найти все двузначные числа сумма квадратов цифр которых делится на 13
Найти все двузначные числа, сумма квадратов цифр которых делится на 13.

Найти все двузначные числа, сумма квадратов цифр которых делится на 17
Найти все двузначные числа, сумма квадратов цифр которых делится на 17.

На отрезке [2, n] найти все натуральные числа, сумма цифр которых при умножении числа на а не изменится
Помогите,вот задание. На отрезке найти все натуральные числа, сумма цифр которых при умножении...

Вывести числа, сумма десятичных цифр которых равна n и само число делится на m
2)Из чисел от 10 до 99 вывести те, сумма цифр которых равна n и само число делится на m.

Получить все трехзначные натуральные числа, сумма цифр которых равна m
var m, n, s, i: integer; begin write('Введите m (m&lt;27): '); readln(m); for i:= 100 to 999 do...

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

0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru