Числа, содержащие 1

Question

Как я могу найти QT. число включает 1 в сегменте [1..n]? например: для n = 29 это 12; для n = 100 это 20. n может достигать 10 ^ 9 и ограничение по времени составляет 2 сек. язык C ++

Answer 1

Простой способ проверить, вычисляется ли одно число по модулю 10: если оно равно 1, тогда это так, в противном случае разделите его на 10 и повторите.Если число равно 0, оно не включает 1.

Этого должно быть достаточно для начала.

Answer 2

Умная вещь, которую нужно сделать, - это создать формулу, доказать ее с помощью рекурсии, а затем применить ее.

На самом деле сначала я не буду использовать рекурсию, но некоторые простые математические вычисления: своего рода теория вероятностей / комбинаторная теория, хотя их нетслучайные события здесь.

Учитывая количество цифр, скажем, две, число чисел ниже, которые не имеют никаких 1, всегда будет 9 к степени числа цифр, таким образом, для 00 до 9981 таких номеров.Таким образом, есть 19, которые делают (100-81).

В каждом случае мы будем считать количество чисел, которые не содержат ни одного.

5394, например, является суммой диапазонаОт 0 до 4999 и сумма от 5000 до 5394.

Сумма до 4999 является произведением цифр: 4 * 9 * 9 * 9 (0-4, 0-9, 0-9, 0-9 за исключением 1 в каждом случае)

Сумма от 5000 до 5394 совпадает с суммой от 000 до 394: разделить 000 до 299, от 300 до 394. Таким образом, 2 * 9 * 9 + работает от 00 до 94что составляет 8 * 9 плюс 90-94, что на 4 больше.

Таким образом, от 0 до 5394 есть 4 * 9 * 9 * 9 (2916) + 2 * 9 * 9 (162) + 8 * 9(72) + 4 = 3154

Вычтите из нашего основного числа + 1 (5395), и мы получим решение 2241. (Мы вычитаем из 5395, потому что мы посчитали от 0 до 5394, что составляет 5395 чисел)

Решение - взять каждую цифру> 1, вычесть одну и умножить на 9 для каждой цифры, которая появляется после нее.Если число равно 1, мы не вычитаем одно.Если число равно нулю, мы пропускаем.

Если мы встречаем 1, мы пропускаем все оставшиеся цифры.Таким образом, если наше число 52136, после достижения 1 мы пропускаем все остальные.(У нас будет счет до 52099, и больше не будет).Мы по-прежнему используем целое число для вычитания в конце.

Для последней цифры: Если до сих пор не было 1 цифры, мы добавляем последнюю цифру и добавляем 1, еслиэто 0. Таким образом, добавьте 4 для 5394, 1 для 5390, ничего для 5216, потому что он содержит 1 перед последней цифрой, но все равно добавьте 1 для 5391 (представляющий 5390, который не был включен в более ранний счет).

Затем вычтите эту сумму из нашего числа + 1 и вычтите еще 1 (потому что я от 0 до N, что составляет N + 1 чисел)

n = 29, таким образом, 1 * 9 + 9 = 18. Вычтитеиз n + 1, и мы получаем 12, как вы хотели.

n = 100: 1 * 9 * 9 = 81. Вычтите из 101 (наше число содержит 1), чтобы получить 20.

Вот твоя формула.Теперь перейдите и запрограммируйте его.

** Немного альтернативный способ **

"рекурсивным" способом: мы вычисляем число чисел, которые не содержат 1, строго меньше нашего значения (не считая этого) давайте назовем это именем, f (N)

f (10N) всегда равно f (N) * 9. Мы можем легко это доказать: есть f (N) чисел, которые меньше чемЗатем N умножьте их на 10 и добавьте в каждую из цифр 0 и 2-9 в конце 9 разных цифр.

f (10N + m), где 0 <= m <= 9 - одна цифраиспользует формулу добавления последней цифры, поэтому, если N содержит 1 цифру, это просто f (N) * 9, иначе добавьте 0 для m = 0 1 для m = 1 и m-1 для любого другого. </p>

f (394858) = 7 + 9 * f (39485) f (573940) = 9 * f (57394) f (491029) = 9 * f (49102) (содержит 1 цифру)

Your "f"функция может возвращаться и должна содержать 2 фрагмента информации: содержит ли она 1 цифру и возвращаемое значение.Базовый случай состоит из одной цифры

f (N) - это число чисел, строго меньше N, которые не содержат 1. Чтобы получить число, которое нужно, вычтите это из N и добавьте 1, если наше числосамо содержит 1.

f (10N + M) = 9 * f (N), если N содержит 1, 9 * f (N) + f (M), если N не содержит 1.

f (0) = 0 f (1) = 1 f (M) для 2-9: M-1 f (10) = 9 * f (1) = 9 f (100) = 9 * f(10) = 81 решение - это 100 - 81 + 1 (потому что 100 содержит 1, мы добавляем единицу), что дает нам 20 f (9) = 8 f ​​(99) = 8 * 9 + 8 = 80 вычесть 80 из 99, чтобы датьмы 19 и не добавляем 1, так как 99 не содержит 1. Теперь давайте попробуем кодирование:

struct res 
{
  unsigned int numDigs;
  bool hasOneDig;

  res( unsigned int n, bool h ) : numDigs( n ), hasOneDig( h ) {}
};

res oneDigitCount( unsigned int input )
{
   assert( input < 10 );

   switch( input )
   {
      case 0: 
         return res( 0, false );
      case 1:
         return res( 1, true );
      default:
         return res( input-1, false );
   }
};

res countNoOnes( unsigned int input )
{
   if( input < 10 )
        return oneDigitCount( input ); // base case that ends recursion

   unsigned int quotient = input / 10;
   unsigned int remainder = input % 10;

   res result = countNoOnes( quotient ); // recursive
   result.numDigs *= 9;

   if( !result.hasOneDig )
   {
       res remainderRes = oneDigitCount( remainder );
       result.numDigs += remainderRes.numDigs;
       if( remainderRes.hasOneDig ) // or remainder==1
          result.hasOneDig = true;
   }

   return result;
}

unsigned int countNumsContainingOne( unsigned int input )
{
   res noOnes = countNoOnes(input);
   unsigned int result = input - noOnes.numDigs;
   if(noOnes.hasOneDig)
     ++result; // as this number has a one

   return result;
}

Не очень ОО, может быть легко адаптировано для C (замените конструктор на функцию, которая возвращает структуру), нодолжно работать.

Answer 3

Поскольку это домашнее задание с тегами, я не дам вам код C ++, поскольку вы должны выполнить некоторые работы: -)

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

def containsOne (n):
    if n <= 0:
        return 0
    if n % 10 == 1:
        return 1
    return containsOne (n / 10)

Это вернет 0 для любого числа ноль или меньше и вернет 1, если оно содержит 1. Это делается путем рекурсивной проверки наименьшей значащей цифры для 1. Если это так, он возвращает 1, в противном случае он делит число на 10 (целочисленное деление, подобное 472, становящееся 47) и продолжается.

Тогда у вас есть простая итеративная функция для подсчета:

def countOfOneNumbersOneTo(n):
    count = 0
    for i = 1 to n:
        count = count + containsOne(i)
    return count

Это самый простой код, который поможет.

---

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

import sys

def containsOne (n):
    if n <= 0:
        return 0
    if n % 10 == 1:
        return 1
    return containsOne (n / 10)

def countOfOneNumbersOneTo(n):
    count = 0
    for i in range(1,n+1):
        count = count + containsOne(i)
    return count

print countOfOneNumbersOneTo (int (sys.argv[1]))

и стенограмма:

$ python qq.py -10
0

$ python qq.py 0
0

$ python qq.py 1
1

$ python qq.py 9
1

$ python qq.py 10
2

$ python qq.py 29
12

$ python qq.py 100
20

---

Следует версия C:

#include <stdio.h>
#include <stdlib.h>

static int containsOne (int n) {
    if (n <= 0)
        return 0;
    if (n % 10 == 1)
        return 1;
    return containsOne (n / 10);
}

static int countOfOneNumbersOneTo (int n) {
    int i, count = 0;
    for (i = 1; i <= n; i++)
        count = count + containsOne(i);
    return count;
}

int main (int argc, char *argv[]) {
    printf ("%d\n", countOfOneNumbersOneTo (atoi (argv[1])));
    return 0;
}

---

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

Для номера 10 ⁹ это займет чуть более 8 минут на моем старом ноутбуке с глушителем, и вы должны помнить, что вам не нужно делать это для каждого номера с тех пор, как только вы Вы установили, что 100 имеет 20 результатов, вам просто нужно проверить 101 и добавить 1 (поскольку 101 имеет 1) к 20. Аналогично, зная, что 1999999 имеет 1468559 результатов, проверьте 2000000 и добавьте 0 (так как у него нет 1).

Я уже использовал этот трюк с файлом, содержащим миллионы и миллионы простых чисел. Превратив это в битовую маску в файле, у меня есть метод isPrime(), который выбрасывает большинство вычисляющих вариантов из воды: -)

Answer 4

Для каждого числа сделайте следующее: создайте внешний цикл для всех чисел от 1 до n.

Вы можете printf() передать его в строковый буфер (например, char[10]), затем проверить тот же строковый буфер, если он содержит '1', с простым циклом while.

Я оставлю вам реализацию :) 100 *