Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Issues
430 / 365 / 37
Регистрация: 06.08.2012
Сообщений: 961
#1

Подсчитывать количество цифр 2 - C++

06.01.2013, 20:24. Просмотров 1226. Ответов 20
Метки нет (Все метки)

Всем привет, вот нашёл задачку:
Напишите метод который будет подсчитывать количество цифр 2, используемых в записи чилес от 0 до n включительно.
Впринципе она кажется лёгкой, я сделал её стандартным методом (разбор числа на цифры, и проверка есть ли в нём 2), когда я задаю n = 1000000, то программа выполняется довольно быстро, но если n = к примеру 1000000000, то естественно, ждать приходидся не мало. Может кто-то может сделать эту задачу более быстрым способом? Зарание спасибо
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2013, 20:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Подсчитывать количество цифр 2 (C++):

Написать программу, которая будет подсчитывать количество гласных букв в строке, введенной с клавиатуры. - C++
:wall: help

дано натуральное число N. Определить,во сколько раз произведение цифр числа больше суммы цифр.Найти количество чётных цифр в записи числа!! - C++
дано натуральное число N. Определить,во сколько раз произведение цифр числа больше суммы цифр.Найти количество чётных цифр в записи числа!!...

Пользователь вводит строку. Определить количество букв (рус eng), количество цифр и количество остальных - C++
в чем проблема не пойму работает на английских буквах на цифрах и остальные символы вроде считает а вот русские не хочет их забивает как...

Определить количество цифр в числе n и сумму всех его цифр - C++
Дано натуральное n , определить количество цифр в числе n и сумму всех его цифр. Значение n ввести с клавиатуры. Добавлено через...

Рекурсия: количество цифр в числе, сумма цифр и реверс числа - C++
Вот задание: Написать программу, которая запрашивает у пользователя целое число, на экран выводит сколько цифр в числе, их сумму и...

Функция вычисляющая количество цифр числа и сумму этих цифр - C++
Не могу найти ошибку. Помогите пожалуйста. Дана последовательность n натуральных чисел. Для каждого числа вычислить количество его цифр и...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BRcr
4008 / 2297 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
07.01.2013, 02:35 #16
Аккуратнее надо на группы разбивать, а мне влом. А почему столько негатива? Live and let live!
0
NeonLost
Пес войны
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
07.01.2013, 02:45 #17
Цитата Сообщение от BRcr Посмотреть сообщение
Аккуратнее надо на группы разбивать, а мне влом. А почему столько негатива? Live and let live!
не пойму почему мой код с синхронизацией работает медленно, а без нее как надо...)
0
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,847
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

т.е
примерно так
C++
1
2
3
4
5
6
7
8
9
10
11
12
kol2=0;
kol_raz=0;
while(n)
{
n=/10;
kol_raz++;
}
kol2=kol_raz;
for( int i=1;i<kol_raz;i++)
{
 kol2*=10;
}
а дальше перебором

Добавлено через 42 минуты
вот так например
C++
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
27
28
29
30
31
32
int fnc(int N)
{
int n=N;
int kol2_1=0;
int kol2_2=0;
int kol2=0;
int kol_raz=0;
int tmp=1;
 if(n<2)
   return 0;
 
while(n>9)
{
 n/=10;
kol_raz++;
tmp*=10;
}
kol2_1=kol_raz;
for( int i=1;i<kol_raz;i++)
{
 kol2_1*=10;
}
 
for(int i=tmp;i<=N;i++)
  {
       for (int j = i; j != 0; j /= 10)
          if (j%10 == 2) 
             kol2_2++;
   }
 kol2=kol2_2+kol2_1;
return kol2;
}
проверил вроде работает

Добавлено через 9 минут
Цитата Сообщение от ValeryS Посмотреть сообщение
for (int j = i; j != 0; j /= 10)
* * * * * if (j%10 == 2)
* * * * * * *kol2_2++;
вот еще бы от этого тормозного цикла избавится
может раскладывать число в массив и по нему проходить ?
остаток от деления выбросим
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.01.2013, 17:07 #19
Как-то так оно решается
C++
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
#include <iostream>
 
typedef unsigned long long big_t;
 
long long foo(big_t n)
{
    big_t count = 0, res =  n % 10 > 1;
 
    for (big_t cur = 10; n >= cur; cur *= 10)
    {
        count = count * 10 + cur / 10;
        
        int z = n / cur % 10;
        res += z * count + (z > 2) * cur + (z == 2) * (1 + n % cur);
    }
 
    return res;
}
 
int main()
{
    big_t n = big_t(1e18) + 2;
 
    std::cout << foo(n) << std::endl;
}
Это динамика + комбинаторика, сложность O( log10(n) )
В моей быдлореализации считает ответ для n = 10104 за секунду.
http://liveworkspace.org/code/4DGGDA

P.S. особо не тестировал, возможны ошибки.
1
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,847
07.01.2013, 17:52 #20
короче доработал еще
Кликните здесь для просмотра всего текста
C++
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
 
 
#include <windows.h>// это только для замера времени 
#pragma comment (lib,"Winmm.lib")
 
int metod1(int N)
{
   int kvo = 0;
 
   for (int i = 0; i <= N; i++)
   {
       for (int j = i; j != 0; j /= 10)
          if (j%10 == 2) 
             kvo++;
   }
 
   return kvo;
}
 
int metod2(int N)
{
int n=N;
int kol2_1=0;
int kol2_2=0;
int kol2=0;
int kol_raz=0;
int tmp=1;
 if(n<2)
   return 0;
 
while(n>9)
{
 n/=10;
kol_raz++;
tmp*=10;
}
kol2_1=kol_raz;
for( int i=1;i<kol_raz;i++)
{
 kol2_1*=10;
}
 
for(int i=tmp;i<=N;i++)
  {
       for (int j = i; j != 0; j /= 10)
          if (j%10 == 2) 
             kol2_2++;
   }
 kol2=kol2_2+kol2_1;
return kol2;
}
 
 
 
 
int metod3(int N)
{
int n=N;
int kol2_1=0;
int kol2_2=0;
int kol2=0;
int kol_raz=0;
int factor=1;
 
while(n>9)
{
 n/=10;
kol_raz++;
factor*=10;
}
kol2_1=kol_raz;
for( int i=1;i<kol_raz;i++)
{
 kol2_1*=10;
}
 
 
 
n=N-factor;
int ofset=1;
while(n>factor)
{
 
if(ofset==2)
  {
   kol2_2+=factor;
  }
  kol2_2+=kol2_1; 
  ofset++;
  n-=factor;
 
}
 
for(int i=ofset*factor;i<=N;i++)
  {
    for (int j = i; j != 0; j /= 10)
          if (j%10 == 2) 
             kol2_2++;
   }
kol2=kol2_2+kol2_1;
return kol2;
}
 
 
int main()
{
int n= 10000000-1;
 
int t0=timeGetTime();
int n1=metod1(n);
int t1=timeGetTime()-t0;
 
t0=timeGetTime();
int n2=metod2(n);
int t2=timeGetTime()-t0;
 
t0=timeGetTime();
int n3=metod3(n);
int t3=timeGetTime()-t0;
 
printf("n= %d\n metod1 =%d  time %d \n metod2 =%d  time %d \n metod3 =%d  time %d \n",n,n1,t1,n2,t2,n3,t3);
system ("pause");
    return 0;
}



первый метод тупой перебор
второй подсчитываем до начала разряда потом перебор
третий подсчитываем до совпадения разряда потом перебор
т.е если взять число 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 минут
Цитата Сообщение от diagon Посмотреть сообщение
В моей быдлореализации считает ответ для n = 10104 за секунду.
мой алгоритм тоже считает числа 10 в степени достаточно быстро (правда я до таких монстров не доходил)
а вот типа 99999999 уже медленно присутствует перебор от которого я не избавился
не смог угадать формулу по твоим исходникам, подскажи
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.01.2013, 18:12 #21
Цитата Сообщение от ValeryS Посмотреть сообщение
не смог угадать формулу по твоим исходникам, подскажи
Одну формулу вы уже угадали
Цитата Сообщение от ValeryS Посмотреть сообщение
количество двоек равно количеству разрядов умноженное на 10 в степени количество разрядов-1
Далее пробегаемся по цифрам исходного числа.
Если цифра меньше двух, то ответ для нее равен [цифра * количество двоек в записи всех n-значных чисел], где n = разряд цифры - 1. Для остальных цифр нужно сделать также, но у них будут дополнительные условия. Это соответствует
C++
1
z * count
в моем исходнике.
z - текущая цифра, count - количество двоек в n-значных числах.

Если цифра больше двойки, то нужно прибавить к ответу количество всех n-значных чисел.
C++
1
(z > 2) * cur

И если цифра равна двойке, то нужно просто прибавить к ответу число, все разряды которого младше рассматриваемой цифры, увеличенное на единицу.
C++
1
(z == 2) * (1 + n % cur)
Ответы для каждой цифры нужно просуммировать.

Итого: никакого перебора, просто один цикл по цифрам числа.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2013, 18:12
Привет! Вот еще темы с ответами:

Напишите программу, выводящую на экран количество цифр в этом числе и сумму этих цифр - C++
я начинающий! помогите! мне на екзам! Дано натуральное число а (a&lt;100). Напишите программу, выводящую на экран количество цифр в этом...

С клавиатуры вводится положительное натуральное число. Определить количество цифр в числе (сумму цифр) - C++
С клавиатуры вводится положительное натуральное число. Определить количество цифр в числе (сумму цифр)

Дана последовательность n натуральных чисел. Для каждого числа вычислить количество его цифр и сумму этих цифр. Вывести на экран каждое число, количес - C++
Дана последовательность n натуральных чисел. Для каждого числа вычислить количество его цифр и сумму этих цифр. Вывести на экран каждое...

Создать файл, ввести символы, вывести на экран количество не латинских букв, количество цифр - C++
Есть код к заднию , но он не правильно показывает данные - киррилицу не ищет а латиницу больше выводит... Задание: Создать текстовый...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.01.2013, 18:12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru