Найти количество страниц книги, если дана сумма цифр номеров страниц

#алгоритм

Здравствуйте. Есть такая интересная задачка:


  Сумма цифр номеров страниц в книге равна 1050.
      Сколько страниц в книге?


Как просчитать ответ?
    

Ответы

Ответ 1

У каждого числа, обозначающего страницу, имеется цифра на месте единиц. При n страниц
имеется n цифр, стоящих на месте единиц. У всех, за исключением первых 9 страниц, числа
являются как минимум двухзначными. Поэтому добавим еще n-9 цифр. У всех, за исключением
первых 99 страниц, числа являются трехзначными, что добавляет еще n-99 цифр.
n+(n-9)+(n-99) = 1050
при его решении получаем 386.
Видимо, не на всех страницах стоял номер...


Ответ 2

Пример на С++.

Короткий алгоритм: Я находил сумму всех цифр чисел страниц, пока эта сумма не равна
данному числу (1050).  

#include 
using namespace std;

int get_number_sum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10; // Суммируем последнюю цифру
        n /= 10;       // делим на 10, чтобы пройтись на другой десяток числа
    }
    return sum;
}

int main() {
    int out = 1050;   // Число, которое дано

    int i = 3, sum = 0;
    while (sum < out) {
        sum += get_number_sum(i); // Ищем сумму цифр страницы
        i++;
    }

    cout << i + 2 << endl;
    return 0;
}


Ответ: 128.

@Akina хорошо заметил, что все номера страниц в книге начинаются с 3, таким образом
начинаем считать с i = 3, ну и в конце прибавляем ещё первую и вторую страницы.


Ответ 3

Вариант в лоб, который если запустить, покажет, что 1050 не является суммой цифр
номеров страниц в книге, если страницы с 1 нумеруются. Если начать нумеровать страницы
с 3, то номер старшей страницы 125, то есть количество нумерованных страниц 123:



/** Decimal digital sum */
function sum_of_digits(i) {
  var sum = 0
  while (i > 0) {
    sum += i % 10
    i = Math.floor(i / 10)
  }
  return sum
}

/** Find *n* such that sum of digits of number from *start* to n (including) 
  * is *digits_sum*
  */
function find_n(digits_sum, start=1) {
  // brute force
  var sum = 0
  for (var i = start; ; ++i) {
     sum += sum_of_digits(i)
     if (sum == digits_sum) {
       return i
     } else if (sum > digits_sum) {
       throw RangeError(`${digits_sum} can't be the sum of digits from ${start} to n`)
     }
  }
}

var start = 3
console.log(find_n(1050, start=start) - start + 1)




Подход с использованием рекурсии (Sum of digits of number from 1 to n):



/** Decimal digital sum */
function sum_of_digits(i) {
  var sum = 0
  while (i > 0) {
    sum += i % 10
    i = Math.floor(i / 10)
  }
  return sum
}

/** Sum of the digital sum of i for i from 0 to n.
  *
  * https://oeis.org/A037123
  */
function D(n) {
  if (n < 1) {
    return 0
  }
  console.assert(n > 0, n)
  // n = 10*q + r
  var q = Math.floor(n / 10),
      r = n % 10;
  return 45*q + 10*D(q - 1) + r*(r+1)/2 + (r+1)*sum_of_digits(q)
}

/** Find *n* such that sum of digits of number from *start* to n (including)
  *  is *digits_sum*
  */
function find_n(digits_sum, start=1) {
  for (var i = start; ; ++i) {
     var sum = D(i) - D(start - 1)
     if (sum == digits_sum) {
       return i
     } else if (sum > digits_sum) {
       throw RangeError(`${digits_sum} can't be the sum of digits from ${start} to n`)
     }
  }
}

var start = 3
console.log(find_n(1050, start=start) - start + 1)


Ответ 4

Арифметическая прогрессия с a^(n) = a^(n-1) + 1;
У нас есть сумма членов, а из формулы S^(n) = (2 * a^(1) + d* ( n - 1) ) *n / 2;
Следовательно 2a^(1) + dn^2 -d = 2S
n^2 +2n -2101 = 0;
n = +-44.8475;
Похоже, сумма страниц несколько неверна:)
** ^(n) значок индекса, если формулы не понятны, в гугле есть более понятные если
необходимо)
Проверим для 45 ст:



var a = 0;
for ( var i = 1; i <= 45; i++) {
a += i;
}
console.log('сумма страниц = ', a);