433 / 368 / 149
Регистрация: 06.08.2012
Сообщений: 961
|
|
1 | |
Подсчитывать количество цифр 206.01.2013, 20:24. Показов 4673. Ответов 20
Метки нет (Все метки)
Всем привет, вот нашёл задачку:
Напишите метод который будет подсчитывать количество цифр 2, используемых в записи чилес от 0 до n включительно. Впринципе она кажется лёгкой, я сделал её стандартным методом (разбор числа на цифры, и проверка есть ли в нём 2), когда я задаю n = 1000000, то программа выполняется довольно быстро, но если n = к примеру 1000000000, то естественно, ждать приходидся не мало. Может кто-то может сделать эту задачу более быстрым способом? Зарание спасибо
0
|
06.01.2013, 20:24 | |
Ответы с готовыми решениями:
20
дано натуральное число N. Определить,во сколько раз произведение цифр числа больше суммы цифр.Найти количество чётных цифр в записи числа!! Пользователь вводит строку. Определить количество букв (рус eng), количество цифр и количество остальных Вывести на экран количество цифр в заданном числе и сумму этих цифр |
1321 / 983 / 267
Регистрация: 17.05.2012
Сообщений: 2,687
|
|
06.01.2013, 20:34 | 2 |
0
|
433 / 368 / 149
Регистрация: 06.08.2012
Сообщений: 961
|
||||||
06.01.2013, 20:46 [ТС] | 3 | |||||
стандартно:
0
|
433 / 368 / 149
Регистрация: 06.08.2012
Сообщений: 961
|
|
06.01.2013, 20:58 [ТС] | 5 |
BRcr, а можно пример.
0
|
433 / 368 / 149
Регистрация: 06.08.2012
Сообщений: 961
|
|
06.01.2013, 21:01 [ТС] | 7 |
Не по теме: BRcr, ок
0
|
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
|
|
06.01.2013, 22:09 | 8 |
А давайте все комбинаторные задачи решать на GPU в 100500 потоков?)
В данном конкретном случае нас интересует только количество знаков в числе n. Рассматриваем числа, состоящие из 1 знака. Сколько их может быть? Вместе с нулем - 10. Сколько может встретиться двоек? Одна. Тут все как будто бы просто. Далее. Рассмотрим двузначные числа вида AB. В данном случае A может принять 9 значений, B - 10. Т.е. всего чисел 90. Но в этих числах присутствует двойка. А сколько чисел без двойки? Тогда для A остается 8 вариантов, для B - 9. Всего чисел без двоек - 72. Очевидно, что с двойками - 90 - 72 = 18. Таким образом можно просчитать для всех k-значных чисел, а в конце сложить результаты. Добавлено через 5 минут Нюанс: такой подход не учитывает кривой верхней границы. Т.е. сработает для диапазона [0, 999], но выдаст ерунду для [0, 500]. И все-таки придерживаюсь мнения, что такие вещи решаются не перебором) Но думать уже влом, поэтому отправляюсь спать.
1
|
84 / 84 / 42
Регистрация: 25.01.2010
Сообщений: 386
|
|
06.01.2013, 22:13 | 9 |
Теория классная, но не соответствует поставленной задаче. Вы внимательно прочли условие? Автору необходимо посчитать реальное количество двоек, а вы предлагаете считать возможное количество.
0
|
Модератор
8902 / 6672 / 917
Регистрация: 14.02.2011
Сообщений: 23,500
|
|
06.01.2013, 22:47 | 10 |
зачем начинать с 0?
явно что в первой 10 только одно число 2 во второй 12 значит надо начинать с 20 отсчет а потом к количеству прибавить 2( 2 и 12) это так на вскидку уменьшение Добавлено через 9 минут попробуем на пальцах в первой 10 1 цифра в первой сотне 19 цифр тесть подсчитай сколько двоек в десятке в сотне тысяче и так далее занеси в таблицу потом зная число допустим число 156 мы начинаем отсчет со 100 и к результату прибавим 19 чисел в первой сотне это первое что пришло в голову, может еще что придумаю Добавлено через 4 минуты пардон соврал в первой сотне 20 двоек 22 это же 2 двойки Добавлено через 5 минут пересчитай я правда без формулы но смотри в каждой десятке 1 двойка итого их 10 (смотрим младший разряд) 2 12 22 32 42 52 62 72 82 92 и десять старших двоек в 20 21 22 23 24 25 26 27 28 29 итого 20 гдето ты в формуле ошибся Добавлено через 5 минут нашел где почему A только девять значений? мы же рассматриваем числа от 0, значит 10 значений(если 0 не пишется это не значит что его нет) следовательно не 90 чисел а 100 0....99
1
|
Пес войны
111 / 88 / 22
Регистрация: 23.02.2012
Сообщений: 653
|
||||||||||||||||
07.01.2013, 00:16 | 11 | |||||||||||||||
не парился на счет кода, но вот что получилось
вот 2 потока
не особая разница...( может что-то не так делаю?..) Добавлено через 11 минут кстати, при варианте без синхронизации время намного меньше
1
|
07.01.2013, 02:17 | 12 | ||||||||||
Сравнение по количеству потоков... на досуге, может, допинаю сюда метод с предварительно заполненным массивом значений по разрядам, как предложил ValeryS, но тот вообще нисколько времени занимать не будет после заполнения массива, так что смысла особо нет...
1
|
Пес войны
111 / 88 / 22
Регистрация: 23.02.2012
Сообщений: 653
|
|
07.01.2013, 02:24 | 13 |
0
|
Пес войны
111 / 88 / 22
Регистрация: 23.02.2012
Сообщений: 653
|
|
07.01.2013, 02:30 | 15 |
да и значение 1 раз промахнулось...(
0
|
Пес войны
111 / 88 / 22
Регистрация: 23.02.2012
Сообщений: 653
|
|
07.01.2013, 02:45 | 17 |
не пойму почему мой код с синхронизацией работает медленно, а без нее как надо...)
0
|
Модератор
8902 / 6672 / 917
Регистрация: 14.02.2011
Сообщений: 23,500
|
|||||||||||
07.01.2013, 04:11 | 18 | ||||||||||
короче сейчас подсчитал
0-10 1 0-100 20 0-1000 300 0-10000 4000 0-100000 50000 0-1000000 600000 тут даже таблицы не надо количество двоек равно количеству разрядов умноженное на 10 в степени количество разрядов-1 т.е примерно так
Добавлено через 42 минуты вот так например
Добавлено через 9 минут вот еще бы от этого тормозного цикла избавится может раскладывать число в массив и по нему проходить ? остаток от деления выбросим
1
|
Higher
|
||||||
07.01.2013, 17:07 | 19 | |||||
Как-то так оно решается
В моей быдлореализации считает ответ для n = 10104 за секунду. http://liveworkspace.org/code/4DGGDA P.S. особо не тестировал, возможны ошибки.
1
|
Модератор
8902 / 6672 / 917
Регистрация: 14.02.2011
Сообщений: 23,500
|
||||||
07.01.2013, 17:52 | 20 | |||||
короче доработал еще
Кликните здесь для просмотра всего текста
первый метод тупой перебор второй подсчитываем до начала разряда потом перебор третий подсчитываем до совпадения разряда потом перебор т.е если взять число 9999(для этого алгоритма самый сложный вариант) то первый метод цикл 0 до 9999 второй - 1000 до 9999 третий 9000 до 9999 вот временные параметры Кликните здесь для просмотра всего текста
n=1000000000;
metod1 =900000000 time 176248 metod2 =900000000 time 0 metod3 =900000000 time 0 n= 999999999 metod1 =900000000 time 174380 metod2 =900000000 time 158050 metod3 =900000000 time 20105 n= 99999 metod1 =50000 time 0 metod2 =50000 time 13 metod3 =50000 time 0 n= 999999 metod1 =600000 time 100 metod2 =600000 time 90 metod3 =600000 time 10 n= 10000000 metod1 =7000000 time 1211 metod2 =7000000 time 0 metod3 =7000000 time 0 n= 9999999 metod1 =7000000 time 1220 metod2 =7000000 time 1117 metod3 =7000000 time 123 видно что второй метод иногда медленней n= 99999 окончательно от перебора не смог уйти, не смог нащупать формулу Добавлено через 10 минут мой алгоритм тоже считает числа 10 в степени достаточно быстро (правда я до таких монстров не доходил) а вот типа 99999999 уже медленно присутствует перебор от которого я не избавился не смог угадать формулу по твоим исходникам, подскажи
0
|
07.01.2013, 17:52 | |
07.01.2013, 17:52 | |
Помогаю со студенческими работами здесь
20
Определить количество цифр в числе n и сумму всех его цифр Функция вычисляющая количество цифр числа и сумму этих цифр Рекурсия: количество цифр в числе, сумма цифр и реверс числа С клавиатуры вводится положительное натуральное число. Определить количество цифр в числе (сумму цифр) Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |