Как считать каждую цифру в диапазоне целых чисел?

Ваш подход в порядке. Я не уверен, почему вам когда-нибудь понадобится ничего быстрее, чем то, что вы описали.

Или это даст вам мгновенное решение: до того, как вам действительно нужно, рассчитайте, что вам нужно от 1 до некоторого максимального номера. Вы можете хранить номера, необходимые на каждом шаге. Если у вас есть диапазон, как ваш второй пример, это было бы то, что нужно для от 1 до 300, минус, что нужно для от 1 до 50.

Теперь у вас есть таблица поиска, которую можно назвать по желанию. Делать до 10000 займет всего несколько МБ, только что несколько минут вычислить, один раз?

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

#!/usr/bin/ruby1.8

def digits_for_range(min, max, leading_zeros)
  bins = [0] * 10
  format = [
    '%',
    ('0' if leading_zeros),
    max.to_s.size,
    'd',
  ].compact.join
  (min..max).each do |i|
    s = format % i
    for digit in s.scan(/./)
      bins[digit.to_i] +=1  unless digit == ' '
    end
  end
  bins
end

p digits_for_range(1, 49, false) 
# => [4, 15, 15, 15, 15, 5, 5, 5, 5, 5]

p digits_for_range(1, 49, true)
# => [13, 15, 15, 15, 15, 5, 5, 5, 5, 5]

p digits_for_range(1, 10000, false)
# => [2893, 4001, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000]

Ruby 1.8, язык, который, как известно, был "медленной собакой", выполняет вышеупомянутый код через 0,135 секунды. Это включает загрузку интерпретатора. Не бросайте очевидный алгоритм, если вам не нужно больше скорости.

Вы можете отделить каждую цифру ( посмотреть здесь для примера ), создайте гистограмму с записями 0..9 (который будет подсчитать, сколько цифр появилось в номере) и умножить на количество «чисел».

Но если не то, что вы ищете, можете ли вы дать лучший пример?

Отредактировано:

Теперь я думаю, что я получил проблему. Я думаю, что вы можете рассчитывать (псевдо):

int histogram[10];
memset(histogram, 0, sizeof(histogram));

for(i = startNumber; i <= endNumber; ++i)
{
    array = separateDigits(i);
    for(j = 0; k < array.length; ++j)
    {
        histogram[k]++;
    }
}

отдельные цифры реализуют функцию в ссылке.

Каждая позиция гистограммы будет иметь сумму каждой цифры. Например

histogram[0] == total of zeros
histogram[1] == total of ones

...

С уважением

Я предполагаю, что вам нужно решение, где числа находятся в диапазоне, и у вас есть начальное и конечное число. Представьте себе, что вы начинаете со стартового числа и отсчитываете до тех пор, пока не достигнете конечного числа - это сработает, но будет медленно. Думаю, хитрость быстрого алгоритма состоит в том, чтобы понять, что для того, чтобы подняться на одну цифру в месте 10^x и сохранить все остальное неизменным, нужно использовать все цифры до нее 10^x раз плюс все цифры 0-9 10^(x-1) раз. (За исключением того, что ваш подсчет мог быть связан с прохождением x-ой цифры - я исправлю это ниже)

Вот пример. Скажем, вы считаете от 523 до 1004.

• Во-первых, вы считаете от 523 до 524. При этом используются цифры 5, 2 и 4 один раз.
• Во-вторых, считайте от 524 до 604. Самая правая цифра выполняет 6 циклов по всем разрядам, поэтому вам нужно 6 копий каждой цифры. Вторая цифра проходит через цифры от 2 до 0, по 10 раз каждая. Третья цифра - 6 5 раз и 5 100-24 раза.
• Третья цифра - от 604 до 1004. Самая правая цифра делает 40 циклов, поэтому добавьте 40 копий каждой цифры. Вторая цифра справа делает 4 цикла, поэтому добавьте 4 копии каждой цифры. Самая левая цифра делает 100 из 7, 8 и 9, плюс 5 из 0 и 100 - 5 из 6. Последняя цифра - 1 5 раз.

Для ускорения последнего бита посмотрите на часть о двух крайних правых местах. Каждая цифра используется 10 + 1 раз. В общем, 1 + 10 + ... + 10^n = (10^(n+1) - 1)/9, что можно использовать для ускорения счета еще больше.

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

Теперь предположим, что псевдокод засчитывается как язык. Итак, вот что я бы сделал:

convert start and end numbers to digit arrays start[] and end[]
create an array counts[] with 10 elements which stores the number of copies of
     each digit that you need

iterate through start number from right to left. at the i-th digit,
    let d be the number of digits you must count up to get from this digit
        to the i-th digit in the ending number. (i.e. subtract the equivalent
        digits mod 10)
    add d * (10^i - 1)/9 to each entry in count.
    let m be the numerical value of all the digits to the right of this digit,
        n be 10^i - m.
    for each digit e from the left of the starting number up to and including the
        i-th digit, add n to the count for that digit.
    for j in 1 to d
        increment the i-th digit by one, including doing any carries
        for each digit e from the left of the starting number up to and including
            the i-th digit, add 10^i to the count for that digit
    for each digit e from the left of the starting number up to and including the
        i-th digit, add m to the count for that digit.
    set the i-th digit of the starting number to be the i-th digit of the ending
        number.

О, а так как значение i увеличивается на единицу каждый раз, следите за своими старыми 10^i и просто умножайте их на 10, чтобы получить новое, вместо того, чтобы каждый раз объяснять.

Вы должны проверить Effect Games .

Это бесплатный онлайн-сервер Javascript Game Engine, который работает невероятно гладко и поддерживает все основные браузеры. Не верите мне? Воспроизвести демонстрацию или одну .

Те, которые говорят, что вы должны использовать Flash и Javascript слишком медленно, очевидно, не обращали внимания, особенно на новый браузер, такой как Chrome, который использует скомпилированный javascript . Зачем использовать Flash, когда вы можете иметь кроссплатформенную, кросс-браузерную игру, разработанную с использованием собственных функций браузера.

Вы также должны проверить Chrome Experiments , чтобы увидеть, насколько улучшились текущие возможности Javascript (а иногда и HTML5).

Effect Games предоставляет бесплатные, онлайн инструменты для создания, совместного использования и играть в собственные игры на основе браузера.

Ваши игры могут включать звуковые эффекты, музыка и несколько слоев параллакс-прокручивающие плитки и спрайты.

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

Создавайте свои игры с помощью JavaScript и наш пользовательский движок браузера игры, уровень редактор и номер люкс инструментов для разработчиков. Модуль Effect Engine поддерживает Mac OS X, Windows, Linux и все современные браузеры включая IE, Firefox, Chrome, Opera и Сафари.

То, что я делаю в этой ситуации, всегда сначала заполняет страницу содержимым на основе параметров по умолчанию того, что делает вызов Ajax. Тогда я использую ajax javascript только для обновления страницы.

Вот очень плохой ответ, мне стыдно его размещать. Я попросил систему Mathematica подсчитать цифры, используемые во всех числах от 1 до 1 000 000, без первых 0. Вот что я получил:

0   488895
1   600001
2   600000
3   600000
4   600000
5   600000
6   600000
7   600000
8   600000
9   600000

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

Это не отвечает на ваш точный вопрос, но интересно отметить распределение первых цифр согласно Законом Бенфорда . Например, если вы выберете набор чисел наугад, 30% из них начнутся с «1», что несколько противостоит понятным.

Я не знаю о каких-либо дистрибутивах, описывающих последующие цифры, но вы можете определить это эмпирически и придумать простую формулу для вычисления приблизительно количество цифр, необходимых для любого диапазона чисел. Отказ

I задал этот вопрос о переполнении математики, и меня отшлепали за то, что я задал такой простой вопрос. Один из пользователей сжалился надо мной и сказал, что если я размещу его в The Art of Problem Solving, то он ответит, и я ответил.

Вот ответ, который он написал:
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1741600#1741600

Стыдно, но моя математика-фу недостаточна, чтобы понять, что он написал (парню 19 лет...это так удручает). Мне действительно нужно взять несколько уроков математики.

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

Если вам нужна необработанная скорость по многим итерациям, попробуйте таблицу поиска:

1. Создать массив с 2 измерениями: 10 x Max-House-Number

    int nDigits[10000][10] ;   // Don't try this on the stack, kids!

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

    n=0..9999:
       if (n>0) nDigits[n] = nDigits[n-1]
       d=0..9:
           nDigits[n][d] += countOccurrencesOf(n,d)   // 

3. Количество цифр «между« двумя числами »становится простым вычитанием.

       For range=51 to 300, take the counts for 300 and subtract the counts for 50.
       0's = nDigits[300][0] - nDigits[50][0]
       1's = nDigits[300][1] - nDigits[50][1]
       2's = nDigits[300][2] - nDigits[50][2]
       3's = nDigits[300][3] - nDigits[50][3]
       etc.

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

• От 0 до 9, каждая цифра встречается один раз
• От 0 -99, каждая цифра встречается 20 раз (10x в позиции 1 и 10x в позиции 2)
• От 0 до 999 каждая цифра встречается 300 раз (100x в P1, 100x в P2, 100x в P3)

Очевидное образец для любой данной цифры, если диапазон от 0 до степени 10, будет N * 10 ^N-1 , где N - степень 10.

Что, если диапазон не является степенью 10? Начните с наименьшей степени 10, затем увеличивайте. Самый простой случай - это максимальное число, например 399. Мы знаем, что для каждого числа, кратного 100, каждая цифра встречается как минимум 20 раз, но мы должны компенсировать количество раз, когда она встречается в большинстве -significant-digit position, которая будет равна 100 для цифр 0–3 и ровно нулю для всех остальных цифр. В частности, добавляемая дополнительная сумма составляет 10 ^N для соответствующих цифр.

Помещая это в формулу, для верхних границ, которые на 1 меньше некоторого кратного степени 10 (например, 399, 6999 и т. Д.), Получается: M * N * 10 ^N-1 + iif (d <= M, 10 ^N , 0)

Теперь вам просто нужно разобраться с остатком (который мы назовем R ). Возьмем, к примеру, 445. Это какой бы ни был результат для 399 плюс диапазон 400–445. В этом диапазоне MSD встречается R больше раз, и все цифры (включая MSD) также встречаются на тех же частотах, что и в диапазоне [0 - R ].

Теперь нам просто нужно компенсировать ведущие нули. Этот шаблон прост - это просто:

10 ^N + 10 ^N-1 + 10 ^N-2 + ... + ** 10 ⁰

Обновление: Эта версия корректно учитывает «заполняющие нули», то есть нули в средних позициях при работе с остатком ([4 0 0, 4 0 1, 4 0 2, ...]). Выяснение нулей заполнения немного уродливо, но исправленный код (псевдокод в стиле C) справляется с этим:

function countdigits(int d, int low, int high) {
    return countdigits(d, low, high, false);
}

function countdigits(int d, int low, int high, bool inner) {
    if (high == 0)
        return (d == 0) ? 1 : 0;

    if (low > 0)
        return countdigits(d, 0, high) - countdigits(d, 0, low);

    int n = floor(log10(high));
    int m = floor((high + 1) / pow(10, n));
    int r = high - m * pow(10, n);
    return
        (max(m, 1) * n * pow(10, n-1)) +                             // (1)
        ((d < m) ? pow(10, n) : 0) +                                 // (2)
        (((r >= 0) && (n > 0)) ? countdigits(d, 0, r, true) : 0) +   // (3)
        (((r >= 0) && (d == m)) ? (r + 1) : 0) +                     // (4)
        (((r >= 0) && (d == 0)) ? countpaddingzeros(n, r) : 0) -     // (5)
        (((d == 0) && !inner) ? countleadingzeros(n) : 0);           // (6)
}

function countleadingzeros(int n) {
      int tmp= 0;
      do{
         tmp= pow(10, n)+tmp;
         --n;
         }while(n>0);
         return tmp;
         }

function countpaddingzeros(int n, int r) {
    return (r + 1) * max(0, n - max(0, floor(log10(r))) - 1);
}

Как видите, он стал немного уродливее, но все еще выполняется за время O (log n),поэтому, если вам нужно обрабатывать числа в миллиарды, это все равно даст вам мгновенные результаты. :-) И если вы запустите его в диапазоне [0 - 1000000], вы получите точно такой же дистрибутив, что и тот, который опубликовал High-Performance Mark, так что я почти уверен, что это правильно.

К вашему сведению, причина использования внутренней переменной заключается в том, что функция ведущего нуля уже является рекурсивной, поэтому ее можно подсчитать только при первом выполнении countdigits .

Обновление 2: Если код трудно читать, вот ссылка на то, что означает каждая строка оператора возврата countdigits (я пробовал встроенные комментарии, но они усложнили код чтение):

1. Частота любой цифры до максимальной степени 10 (0-99 и т. д.)
2. Частота МСД выше любого кратного максимальной степени 10 (100-399)
3. Частота любых цифр в остатке (400-445, R = 45)
4. Дополнительная частота MSD в остатке
5. Подсчитать нули в средней позиции для диапазона остатка (404, 405 ...)
6. Вычесть ведущие нули только один раз (на крайнем внешнем петля)