Задача
Сколько раз будет использована цифра $6$, если записать подряд последовательные натуральные числа от $a$ до $b$?
Входные данные
Два натуральных числа $a$ и $b$ [latex](1 ≤ a, b ≤ 10^9)[/latex].
Выходные данные
Количество цифр $6$ в последовательных натуральных числах от $a$ до $b$.
Тесты
| № | Ввод | Вывод |
|---|---|---|
| 1 | 5 256 | 46 |
| 2 | 56 110 | 16 |
| 3 | 27357 43577 | 5852 |
| 4 | 368325775 56 | 296285528 |
| 5 | 584937543 984938576 | 420000314 |
Код
|
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 |
#include <iostream> using namespace std; int count_six(int input){ int rez = 0, mem = 1, length = 0, exp_10 = 1; short num; while(input > 0){ num = input % 10;//узнаём последний знак в числе input /= 10;//убираем последний разряд из числа if (num < 6) rez += num * exp_10 * length; //к результату добавим количество шестёрок в данном разряде else if (num == 6) rez += num * exp_10 * length + mem; //к результату добавим количество шестёрок в данном разряде плюс уже пройденное нами число+1 else rez += num * exp_10 * length + exp_10 * (length == 0? 1 : 10); //к результату добавим количество шестёрок в предыдущем разряде if (length != 0) exp_10 *= 10; //проверяем количество пройденных разрядов mem += num * exp_10; //запоминаем пройденное число length++; //отмечаем пройденный разряд } return rez; } int main() { int a, b; cin >> a >> b; if (a > b) swap(a, b); cout << count_six(b) - count_six(a - 1); return 0; } |
Решение
Выписав и посчитав количества шестёрок от $1$ до [latex]10, 100, 1000, …[/latex] Мы обнаружим закономерность, они равны [latex]1, 20, 300, …[/latex] соответственно.
Доказательство проведем по математической индукции.
- Для [latex]n = 1[/latex] [latex]countSix(10^1) = 1[/latex].
- Для [latex]n ≤ k[/latex] $countSix(10^{k}) = k \cdot 10^{k-1}$
- Для [latex]n = k+1[/latex] $countSix(10^{k+1}) = k\cdot10^{k-1}\cdot10+10^k = (k+1)\cdot10^k$
Разберёмся, как их нужно комбинировать. Для этого в цикле пройдёмся по каждой из цифр числа и полученные результаты просуммируем. В ответ мы выдадим разность количества шестерок без внешней границы.
Вы обнаружили закономерность, но не доказали математически. Предлагаю сделать это по индукции.
В конструкции из нескольких взаимоисключающих if-ов подряд было бы неплохо использовать else.
Смысл переменной mem насколько я могу видеть, не объяснен, а было бы интересно узнать, что она делает. К сожалению, объяснение мне кажется в целом довольно сумбурным/трудным для понимания. Возможно, это из-за того, что Вы объясняете довольно сложные математические операции без помощи формул и обозначений. Предлагаю добавить их для наглядности.
Спасибо, исправила.
И еще, желательно, оформить ссылки в виде не нумерованного списка. Используя теги <ul> и <li>.
*<ul> и <li>
Спасибо, учла.
Добавлю по коду, что нет смысла проверять на больше, если уже проверили на меньше и на равенство. И лучше писать else, чтобы не делать лишних проверок
Похожее замечание было указано выше, уже исправила, спасибо.