Количество n-значных чисел

@Csharper@ · Регистрация: 18.09.2013

Студворк — интернет-сервис помощи студентам

Задано натуральные числа N и M.

Посчитайте количество N-значных натуральных чисел, сумма цифр в которых равна M.

Значения N и M (1 ≤ N ≤ 9, 1 ≤ M ≤ 81).

Как решить задачу? Разложить на множители?

Заранее благодарю!

@_Ivana · 23.03.2015, 19:55

До дома пока не добрался, но еще раз воспроизвел второго хаскельного кота с однократной внутримонадной мемоизацией. Повторюсь, если воспользоваться библиотечной мемоизацией, будет в 2 раза короче. res - функция из кота выше, результаты совпадают, время различается заметно.

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
memoRes (r, k, i0) = 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 (r, s, i0) | s==0                 = return 1
                            | s<0 || s>r*9 || r==0 = return 0
                            | otherwise            = do
                                 v <- mapM g $ zip3 (repeat $ r-1) (map (s-) [i0..9]) (repeat 0)
                                 return $ sum v
 
    v <- mapM (memoDP ref) $ map (\x -> (r,x,1)) [k,2*k..r*9`div`k*k]
    return $ sum v
 
res' :: Integer -> Integer -> Integer
res' r k = memoRes (r, k, 1)
 
main = do
    print $ res 71 37
    print $ res' 71 37

@S_el · 23.03.2015, 19:55

Сообщение от Csharper@

А можно хоть чуть чуть объяснения этих рекурсий.

выше уже написали:

Сообщение от _Ivana

а словами попозже - ухожу из онлайна

@_Ivana · 23.03.2015, 20:09

Ну давайте объяснение алгоритма (не рекурсий, я на С сначала с циклами пишу, а потом в рекурсии их заворачиваю

)
Алгоритм прост - пишем функцию-ядро, рассчитывающую количество вариантов получения суммы s с помощью r слагаемых, каждое из которых может быть от 0 до 9, исключая первое - оно от 1 до 9. А пишется она просто - если s=0 то возвращаем 1 - нашли очередной вариант (и даже если r еще не 0, то все равно прекращаем безобразие и возвращаем - считаем что хвост добьем нулями

), если s<0, r=0 или s>9*r - возвращаем ноль, т.к. или влезли в отрицательную сумму, или выбрали все r слагаемых и не дошли до 0, или наша сумма больше чем максимально возможная из r цифр - последнее условие существенно уменьшает перебор ненужных вариантов. А иначе возвращаем сумму значений, полученных путем рекурсивного применения этой функции к набору сумм, полученных вычитанием из исходной суммы чисел от 0 (или от 1 для первого прогона) до 9. Все. Эта функция считает количество r разрядных чисел, сумма цифр которых равна s. Для задачи ТС это то что нужно, осталось только мемоизировать ее расчет, в С это тривиально, а хаскеле чуть подумать. А далее мой кот, который находит количество чисел, сумма цифр которых кратна k, просто вызывает эту функцию для набора k, 2k, ... и до максимально возможного значения, которое кратно k и можно набрать r цифрами и складывает результаты. Все

ЗЫ единственный тонкий момент, требующий исследования - это достаточно ли моей сишной мемоизации по 2 параметрам - может случиться так, что одинаковые их значения вызываются для первого прогона (с 1) и для второго (с 0) и должны дать разный результат. Но если даже так, то это лечится добавлением третьего измерения в мемо-массив, и мемоизацию с 0 или 1 в нем. В хаскеле у меня честная мемоизация по всем параметрам функции, так что там такого риска нет.

@Igor3D · 24.03.2015, 14:59

Без оптимизации

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int numDone = 0;
 
void Calc( int sum, int val, int num )
{
 if (num <= 0 || val > sum) return;
 if (val == sum) 
  ++numDone;
 else
   for (int i = 0; i < 9; ++i)
    Calc(sum - i, val + i, num - 1);
}
 
int main( void )
{
  int sum = 12;
  int num = 9;
  Calc(sum, 0, num);
  printf("numDone = %d\n", numDone);
  return 0;
}

Идея оптимизации очевидна, но сейчас тупая работа с UI и котелок не варит

Смысл такой: вот есть какой-то ответ, напр 1234, сумма равна нужной (10). Разобьем на 2 группы. В первой число 3, значит во второй должно быть 7. Общее число ответов для расклада 3 + 7 равно числу сумм-троек в первой помножить на число сумм-семерок во второй. Дальше не додумал, убегаю

@Shamil1 · 27.03.2015, 23:52

Сообщение от Igor3D

Без оптимизации

C++
1
int numDone = 0;

Считает неправильно.
Для N=9 и M=80 должно получаться 9 (9 вариантов поставить "8").

Добавлено через 6 часов 48 минут
В данном случае нужно использовать не хеширование, а предпостроение. Всё равно для вычисления F(n, m) по данному алгоритму требуется вычислить значения F для всех меньших значений (n, m).

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
void Main()
{
    int M = 40, N = 9;
    var res = CountNumbers(M, N);
    Console.WriteLine("N = {0}, M = {1}, Count = {2}", N, M, res);
}
 
private static int CountNumbers(int sum, int size)
{
    if(sum > size*9) return 0;
    var prev = new int[sum+1];
    var curr = new int[sum+1];
    for(int j = 1; j <= size; j++)
    {
        var tmp = curr; curr = prev; prev = tmp; //swap
        curr[0] = 1;
        var max = Math.Min(sum, 9);
        for(int i = 1; i <= max; i++)
            curr[i] = curr[i-1] + prev[i];
        max = Math.Min(sum, 9*j);
        for(int i = 10; i <= max; i++)
            curr[i] = curr[i-1] + prev[i] - prev[i-10];
            
    }
    return curr[sum] - prev[sum];
}

Время я засекать не стал, так как выполняется быстрее миллисекунды.
В принципе можно записать в два раза короче (объединить два внутренних цикла в один). Будет немного лишних вычислений, но разница в скорости незаметна.

Алгоритм очень простой. Например, в Excel было бы достаточно написать "1" в ячейку B12, в соседнюю С12 ячейку написать формулу "=SUM(B3:B12)" и протянуть её на m и n вниз и вправо.

Количество n-разрядных чисел с суммой цифр m можно вычислить по формуле:
F(n, m) = F(n-1, m) + ... + F(n-1, m-9)
где F(n-1, m) - количество n-разрядных чисел с цифрой 0 на первом месте... и так далее.

Для вычисления суммы будем к сумме, вычисленной на предыдущем шаге, добавлять новое значение и вычитать лишнее.
F(n, m) = F(n, m-1) + F(n-1, m) - F(n-1, m-10)

Вычисленное значение F(n, m) включает числа с цифрой 0 на первом месте. Но, к счастью, мы знаем количество таких чисел - это F(n-1, m).

@Qwertiy · 29.03.2015, 16:30

Вижу 2 способа:
1. Meet in the middle + перебор.
2. Динамика res[k][s] количество чисел из k знаков с суммой цифр s.
Верочтно, второй порще и правильнее.

@_Ivana · 04.04.2015, 17:17

Написал безмонадный вариант реализации мемоизированного расчета значений любой рекурсивной функции для заданного списка аргументов с последующей сверткой его по любому моноиду. Если использовать эту функцию как библиотечную, то кот для задачи (количества r-значных чисел, сумма цифр которых кратна k) будет лаконичен, как и предполагалось (описание рекурсивной функции и вызов ее свертки по сложению на списке аргументов):

Haskell
1
2
3
4
5
6
7
f (r, s, i0) | s==0                 = Left 1
             | s<0 || s>r*9 || r==0 = Left 0
             | otherwise            = Right
                 (zip3 (repeat $ r-1) (map (s-) [i0..9]) (repeat 0), sum)
 
task :: Integer -> Integer -> Integer
task r k = getSum . monofold f $ zip3 (repeat r) (map (k*) [1..r*9`div`k]) (repeat 1)

Да и собственно сама функция мемоизированного расчета со сверткой тоже не особо длинная:

Haskell
1
2
3
4
5
6
7
8
monofold f = snd . foldr (\n (m,a) -> fmap (<>a) $ go n m) (Map.empty, mempty) where
    go i m = case f i of
        Left  v      -> (m, v)
        Right (l, t) -> (Map.insert i r m', r) where
            (m', r) = fmap t $ foldr gf (m, []) l
            gf i (m, l) = fmap (:l) $ case Map.lookup i m of
                Just v  -> (m, v)
                Nothing -> go i m

@Shamil1 · 05.04.2015, 02:43

_Ivana,
А можно на Haskell эффективно реализовать вариант с построением результата снизу вверх?

Я для сравнения написал на C# вариант через рекурсию с сохранением промежуточных результатов в хэш-таблице (Dictionary<Tuple<int, int>, int>), и этот вариант работает на 2 порядка медленней. Меня этот результат не удивляет - пройтись по массиву в порядке возрастания индекса гораздо быстрее, чем искать каждое значение в хэш-таблице.

Добавлено через 11 минут
Сравнение двух вариантов:
N = 20, M = 90, Count = 2785022004925340460 (00:00:00.0000128)
N = 20, M = 90, Count = 2785022004925340460 (00:00:00.0023891)

@_Ivana · 05.04.2015, 02:53

Shamil1, как я всегда говорю своим заказчикам - на вопрос "а можно?" я, как честный человек, вынужден ответить - можно

Но для этого мне надо постичь алгоритм "снизу вверх", я его детально не разбирал, игрался с безмонадной мемоизацией для любых функций. Таблица - да, перестраивается при добавлениях для поддержания сбалансированности дерева. Тех же Фибоначчей лучше итеративно считать чем запоминать все промежуточные результаты в таблицу, но не для любых задач можно просто придумать итеративный алгоритм. Вы его судя по всему для данной задачи придумали и реализовали, поэтому и быстро считает.

Добавлено через 2 минуты
ЗЫ хотел уже предложить замерить для 200 - 90 и сравнить с хаскелем, но вспомнил, что у вас вряд ли есть бесплатные длинные числа в С#

@Shamil1 · 05.04.2015, 05:01

Бесплатные длинные числа есть... но они реализованы как велью тайп и из-за этого работают медленно.
В идеале нужно скачать gmp и собрать её на своём компе. Но лень возиться (разбираться) с MinGW и прочими штуками. Можно, конечно, скачать готовую длл, оптимизированную под эни цпу.
Я не знаю, mpir сейчас так же быстро как gmp работает или отстаёт по-прежнему.

Добавлено через 7 минут
N = 20, M = 90, Count = 2785022004925340460 (00:00:00.0000141)
N = 20, M = 90, Count = 2785022004925340460 (00:00:00.0004045) <-- версия с BigInteger
N = 200, M = 90, Count = 1104336300797459950516437233167717673221 9489057091429478032739165357996660843 (00:00:00.0044512)
N = 90, M = 200, Count = 8121318273904738091374714621561728069990 41727200974796074850352620119032648 (00:00:00.0042630)

@_Ivana · 05.04.2015, 14:10

Да и так неплохо, все равно у меня в 40 раз медленнее

http://ideone.com/6Rozeh Но я использовал нехешированную таблицу, реализованную внутри через самобалансирующееся бинарное дерево, если не ошибаюсь. С массивами или векторами с прямым доступом по индексу за О(1) будет конечно быстрее - спасет то, что аргументы - три целых числа в малом диапазоне.

@Qwertiy · 05.04.2015, 14:29

Зачем хэш-таблица, когда можно использовать массив?

@_Ivana · 06.04.2015, 00:06

Хм. Не прошло и полдня разбирательства с мутабельными векторами, как кот с оптимизацией компиляции с мемоизацией на этих векторах рассчитывает N = 200, M = 90 за 0.015 сек - по замерам винды, но время плавает от запуска к запуску, использую наверное не лучший таймер для замеров. Но в любом случае порядок величин теперь совпадает - могу успокоиться

ЗЫ прошлые времена я вообще не то что в неоптимизированном экзешнике, а в интерпретаторе замерял - со всеми вытекающими

Добавлено через 24 минуты
Qwertiy, кстати, на ваш вопрос - потому что я реализовал универсальную мемоизацию на мапе, и вызвал частный случай с этой задачей. Кстати, на мапе в экзешнике считает те же аргументы за 0.05 сек - не намного дольше мутабельных векторов. Зато универсально

@Shamil1 · 06.04.2015, 21:35

Я откопал у себя самописную (но так и не дописанную) длинную арифметику на C#. Она работает в 5 раз быстрее, чем BigInteger на данной задаче.

Добавлено через 2 часа 35 минут

Не по теме:

Тип BigInteger изначально был создан для F#. Проблема BigInteger в том, что это немутабельный тип. А немутабельность - это общая "проблема" функциональных языков. Я изучил F#, когда он только появился, и даже решил на нём порядка 70 задач "эйлера". Но, все мои программы на F# работали медленнее, чем C# программы. И любую программу на F# я могу практически один в один переписать на C#. Поэтому я забросил F#, так и не поняв, в чём преимущества функционального программирования.

@Qwertiy · 06.04.2015, 22:42

Сообщение от Shamil1

И любую программу на F# я могу практически один в один переписать на C#.

Эм.. Это, вероятно, означает, что ты им неправильно пользовался.
Функциональные языки - они другие. Не надо на них так писать.

PS: F# не знаю, но некоторые штуки про его стилистику видел.

@Ev_Hyper · 07.04.2015, 00:05

Сообщение от Shamil1

И любую программу на F# я могу практически один в один переписать на C#. Поэтому я забросил F#, так и не поняв, в чём преимущества функционального программирования.

Shamil1, в том то и дело, что писать на F# как на C# - зло.

@_Ivana · 07.04.2015, 00:35

Не по теме:

В далекие студенческие годы писал темы для нашей группы, в фа-диез миноре было привычнее и проще, чем в до-диезе :) Конечно вы скажете, что можно просто транспонировать в другую тональность как есть, но играть неудобнее :)

@Shamil1 · 07.04.2015, 00:37

Утверждать не могу, но, по-моему, я правильно им пользовался. Вот, например, ткнул в первую попавшуюся задачу эйлера (Find the sum of the digits in the number 100!) и обнаружил там:

F#
1
2
let problem20c number =
  (Seq.reduce ( * ) {1I..number}).ToString() |> Seq.map (fun c -> int c - int '0') |> Seq.sum

То же самое я могу записать на c# так:

C#
1
2
3
4
int Problem20(int max)
{
    return Enumerable.Range(1,max).Select(x => new BigInteger(x)).Aggregate((a, b) => a * b).ToString().ToCharArray().Select(x => x - '0').Sum();
}

Единственная разница в том, что в c# нет синтаксического сахара для генерации последовательностей... (ещё для match и т.п.).

Можете предложить другую задачу для сравнения. (Только учтите, что F# я уже успел забыть)

@_Ivana · 07.04.2015, 00:56

Haskell
1
main = print.length.show.product $ [1..100]

Вообще местный раздел "священных войн" наполнен темами про сравнение языков, где далеко не все участники утруждают себя рамками приличий. В нашем случае я верю, что мы эти рамки не нарушим, но не очень понимаю смысл спора

Добавлено через 9 минут
А вообще, хотите задачу - реализуйте то про что я говорил выше - мемоизатор расчета любой рекурсивной функции любого количества аргументов (единственное ограничение - на них должно быть определено отношение порядка), причем в мемоизатор чтобы было можно передавать список нужных аргументов для расчета и также функцию на этом списке, которая применяется к нему чтобы получить итоговый результат. А когда реализуете, сравните с моим вариантом выше - 8 строчек

@Shamil1 · 07.04.2015, 01:16

Сообщение от _Ivana

Haskell
1
main = print.length.show.product $ [1..100]

Вообще местный раздел "священных войн" наполнен темами про сравнение языков, где далеко не все участники утруждают себя рамками приличий. В нашем случае я верю, что мы эти рамки не нарушим, но не очень понимаю смысл спора

Ваш код возвращает длину этого числа? (не уверен, так как не знаю Хаскеля). Там надо сумму цифр. Но я верю, что на Хаскеле код будет короче. Но ведь дело не в том, какой код короче? Вот, например, короткий вариант, который мне совсем не нравится:

Code
1
+/"."0":!100x

Я не любитель "священных войн", просто я не понимаю. То есть, я не спорю, а спрашиваю.
Современные развивающиеся языки вбирают в себя всё лучшее из других языков. В частности, LINQ (который мне нравится), можно сказать, позаимствован из функциональных языков.

Новые блоги и статьи Все статьи Все блоги /
Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	23.03.2015, 20:09
	Ну давайте объяснение алгоритма (не рекурсий, я на С сначала с циклами пишу, а потом в рекурсии их заворачиваю ) Алгоритм прост - пишем функцию-ядро, рассчитывающую количество вариантов получения суммы s с помощью r слагаемых, каждое из которых может быть от 0 до 9, исключая первое - оно от 1 до 9. А пишется она просто - если s=0 то возвращаем 1 - нашли очередной вариант (и даже если r еще не 0, то все равно прекращаем безобразие и возвращаем - считаем что хвост добьем нулями ), если s<0, r=0 или s>9*r - возвращаем ноль, т.к. или влезли в отрицательную сумму, или выбрали все r слагаемых и не дошли до 0, или наша сумма больше чем максимально возможная из r цифр - последнее условие существенно уменьшает перебор ненужных вариантов. А иначе возвращаем сумму значений, полученных путем рекурсивного применения этой функции к набору сумм, полученных вычитанием из исходной суммы чисел от 0 (или от 1 для первого прогона) до 9. Все. Эта функция считает количество r разрядных чисел, сумма цифр которых равна s. Для задачи ТС это то что нужно, осталось только мемоизировать ее расчет, в С это тривиально, а хаскеле чуть подумать. А далее мой кот, который находит количество чисел, сумма цифр которых кратна k, просто вызывает эту функцию для набора k, 2k, ... и до максимально возможного значения, которое кратно k и можно набрать r цифрами и складывает результаты. Все ЗЫ единственный тонкий момент, требующий исследования - это достаточно ли моей сишной мемоизации по 2 параметрам - может случиться так, что одинаковые их значения вызываются для первого прогона (с 1) и для второго (с 0) и должны дать разный результат. Но если даже так, то это лечится добавлением третьего измерения в мемо-массив, и мемоизацию с 0 или 1 в нем. В хаскеле у меня честная мемоизация по всем параметрам функции, так что там такого риска нет. 1

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	29.03.2015, 16:30
	Вижу 2 способа: 1. Meet in the middle + перебор. 2. Динамика res[k][s] количество чисел из k знаков с суммой цифр s. Верочтно, второй порще и правильнее. 0

@Shamil1 Модератор 3141 / 2289 / 469 Регистрация: 26.03.2015 Сообщений: 8,920
	05.04.2015, 02:43
	_Ivana, А можно на Haskell эффективно реализовать вариант с построением результата снизу вверх? Я для сравнения написал на C# вариант через рекурсию с сохранением промежуточных результатов в хэш-таблице (Dictionary<Tuple<int, int>, int>), и этот вариант работает на 2 порядка медленней. Меня этот результат не удивляет - пройтись по массиву в порядке возрастания индекса гораздо быстрее, чем искать каждое значение в хэш-таблице. Добавлено через 11 минут Сравнение двух вариантов: N = 20, M = 90, Count = 2785022004925340460 (00:00:00.0000128) N = 20, M = 90, Count = 2785022004925340460 (00:00:00.0023891) 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	05.04.2015, 02:53
	Shamil1, как я всегда говорю своим заказчикам - на вопрос "а можно?" я, как честный человек, вынужден ответить - можно Но для этого мне надо постичь алгоритм "снизу вверх", я его детально не разбирал, игрался с безмонадной мемоизацией для любых функций. Таблица - да, перестраивается при добавлениях для поддержания сбалансированности дерева. Тех же Фибоначчей лучше итеративно считать чем запоминать все промежуточные результаты в таблицу, но не для любых задач можно просто придумать итеративный алгоритм. Вы его судя по всему для данной задачи придумали и реализовали, поэтому и быстро считает. Добавлено через 2 минуты ЗЫ хотел уже предложить замерить для 200 - 90 и сравнить с хаскелем, но вспомнил, что у вас вряд ли есть бесплатные длинные числа в С# 0

@Shamil1 Модератор 3141 / 2289 / 469 Регистрация: 26.03.2015 Сообщений: 8,920
	05.04.2015, 05:01
	Бесплатные длинные числа есть... но они реализованы как велью тайп и из-за этого работают медленно. В идеале нужно скачать gmp и собрать её на своём компе. Но лень возиться (разбираться) с MinGW и прочими штуками. Можно, конечно, скачать готовую длл, оптимизированную под эни цпу. Я не знаю, mpir сейчас так же быстро как gmp работает или отстаёт по-прежнему. Добавлено через 7 минут N = 20, M = 90, Count = 2785022004925340460 (00:00:00.0000141) N = 20, M = 90, Count = 2785022004925340460 (00:00:00.0004045) <-- версия с BigInteger N = 200, M = 90, Count = 1104336300797459950516437233167717673221 9489057091429478032739165357996660843 (00:00:00.0044512) N = 90, M = 200, Count = 8121318273904738091374714621561728069990 41727200974796074850352620119032648 (00:00:00.0042630) 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	05.04.2015, 14:10
	Да и так неплохо, все равно у меня в 40 раз медленнее http://ideone.com/6Rozeh Но я использовал нехешированную таблицу, реализованную внутри через самобалансирующееся бинарное дерево, если не ошибаюсь. С массивами или векторами с прямым доступом по индексу за О(1) будет конечно быстрее - спасет то, что аргументы - три целых числа в малом диапазоне. 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	05.04.2015, 14:29
	Зачем хэш-таблица, когда можно использовать массив? 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	06.04.2015, 00:06
	Хм. Не прошло и полдня разбирательства с мутабельными векторами, как кот с оптимизацией компиляции с мемоизацией на этих векторах рассчитывает N = 200, M = 90 за 0.015 сек - по замерам винды, но время плавает от запуска к запуску, использую наверное не лучший таймер для замеров. Но в любом случае порядок величин теперь совпадает - могу успокоиться ЗЫ прошлые времена я вообще не то что в неоптимизированном экзешнике, а в интерпретаторе замерял - со всеми вытекающими Добавлено через 24 минуты Qwertiy, кстати, на ваш вопрос - потому что я реализовал универсальную мемоизацию на мапе, и вызвал частный случай с этой задачей. Кстати, на мапе в экзешнике считает те же аргументы за 0.05 сек - не намного дольше мутабельных векторов. Зато универсально 0

@Shamil1 Модератор 3141 / 2289 / 469 Регистрация: 26.03.2015 Сообщений: 8,920
	06.04.2015, 21:35
	Я откопал у себя самописную (но так и не дописанную) длинную арифметику на C#. Она работает в 5 раз быстрее, чем BigInteger на данной задаче. Добавлено через 2 часа 35 минут Не по теме: Тип BigInteger изначально был создан для F#. Проблема BigInteger в том, что это немутабельный тип. А немутабельность - это общая "проблема" функциональных языков. Я изучил F#, когда он только появился, и даже решил на нём порядка 70 задач "эйлера". Но, все мои программы на F# работали медленнее, чем C# программы. И любую программу на F# я могу практически один в один переписать на C#. Поэтому я забросил F#, так и не поняв, в чём преимущества функционального программирования. 0

@_Ivana
	07.04.2015, 00:35
	Не по теме: В далекие студенческие годы писал темы для нашей группы, в фа-диез миноре было привычнее и проще, чем в до-диезе :) Конечно вы скажете, что можно просто транспонировать в другую тональность как есть, но играть неудобнее :) 0