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

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

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

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

06.01.2013, 20:24. Просмотров 1255. Ответов 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 натуральных чисел. Для каждого числа вычислить количество его цифр и...

20
David Sylva
1290 / 952 / 51
Регистрация: 17.05.2012
Сообщений: 2,687
06.01.2013, 20:34 #2
Цитата Сообщение от SeregaC++ Посмотреть сообщение
более быстрым способом?
Покажи свой способ.
0
Issues
430 / 365 / 37
Регистрация: 06.08.2012
Сообщений: 961
06.01.2013, 20:46  [ТС] #3
стандартно:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int FK(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;
}
0
BRcr
4009 / 2298 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
06.01.2013, 20:57 #4
Поделить числа на диапазоны и обрабатывать их в разных потоках. Если и этого мало - выполнять потоки еще и на GPU.
1
Issues
430 / 365 / 37
Регистрация: 06.08.2012
Сообщений: 961
06.01.2013, 20:58  [ТС] #5
BRcr, а можно пример.
0
BRcr
4009 / 2298 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
06.01.2013, 20:59 #6
Можно, но только не сегодня уже...
0
Issues
430 / 365 / 37
Регистрация: 06.08.2012
Сообщений: 961
06.01.2013, 21:01  [ТС] #7

Не по теме:

BRcr, ок

.
0
0x10
2479 / 1652 / 248
Регистрация: 24.11.2012
Сообщений: 4,095
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
we2seek
80 / 80 / 17
Регистрация: 25.01.2010
Сообщений: 385
06.01.2013, 22:13 #9
Цитата Сообщение от 0x10 Посмотреть сообщение
А давайте все комбинаторные задачи решать на 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]. И все-таки придерживаюсь мнения, что такие вещи решаются не перебором) Но думать уже влом, поэтому отправляюсь спать.
Теория классная, но не соответствует поставленной задаче. Вы внимательно прочли условие? Автору необходимо посчитать реальное количество двоек, а вы предлагаете считать возможное количество.
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,203
06.01.2013, 22:47 #10
Цитата Сообщение от SeregaC++ Посмотреть сообщение
for (int i = 0; i <= n; i++)
* *{
зачем начинать с 0?
явно что в первой 10 только одно число 2
во второй 12
значит надо начинать с 20 отсчет а потом к количеству прибавить 2( 2 и 12)
это так на вскидку
уменьшение

Добавлено через 9 минут
попробуем на пальцах в первой 10 1 цифра
в первой сотне 19 цифр
тесть подсчитай сколько двоек в десятке в сотне тысяче и так далее занеси в таблицу
потом зная число
допустим число 156
мы начинаем отсчет со 100 и к результату прибавим 19 чисел в первой сотне
это первое что пришло в голову, может еще что придумаю

Добавлено через 4 минуты
пардон соврал в первой сотне 20 двоек
22 это же 2 двойки

Добавлено через 5 минут
Цитата Сообщение от 0x10 Посмотреть сообщение
Далее. Рассмотрим двузначные числа вида AB. В данном случае A может принять 9 значений, B - 10. Т.е. всего чисел 90. Но в этих числах присутствует двойка. А сколько чисел без двойки? Тогда для A остается 8 вариантов, для B - 9. Всего чисел без двоек - 72. Очевидно, что с двойками - 90 - 72 = 18.
пересчитай
я правда без формулы но смотри в каждой десятке 1 двойка
итого их 10 (смотрим младший разряд)
2 12 22 32 42 52 62 72 82 92
и десять старших двоек в
20 21 22 23 24 25 26 27 28 29
итого 20
гдето ты в формуле ошибся

Добавлено через 5 минут
нашел где
Цитата Сообщение от we2seek Посмотреть сообщение
В данном случае A может принять 9 значений, B - 10. Т.е. всего чисел 90.
почему A только девять значений? мы же рассматриваем числа от 0, значит 10 значений(если 0 не пишется это не значит что его нет)
следовательно не 90 чисел а 100 0....99
1
NeonLost
Пес войны
75 / 86 / 3
Регистрация: 23.02.2012
Сообщений: 653
07.01.2013, 00:16 #11
не парился на счет кода, но вот что получилось
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
#include <iostream>
#include <windows.h>
#define n 100000000
using namespace std;
int kvo = 0;
void first() 
{
   for (int i = 0; i <= n; i++)
   {
       for (int j = i; j != 0; j /= 10)
          if (j%10 == 2) 
             kvo++;
   }
  //boost::this_thread::sleep(boost::posix_time::seconds(5));
}
 
int main() 
{
  int start=GetTickCount();
  first();
  cout<<kvo<<endl;
  int end=GetTickCount();
  cout<<end-start<<endl;
  getchar();
  return 0;
}
время 13759

вот 2 потока
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
#include <boost/thread/thread.hpp>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <iostream>
#include <windows.h>
#define n 100000000
using namespace std;
    int kvo = 0;
void first(boost::mutex& mutex) 
{
  {
  boost::lock_guard<boost::mutex> lock(mutex);
 
   for (int i = 0; i < n/2; i++)
   {
       for (int j = i; j != 0; j /= 10)
          if (j%10 == 2) 
             kvo++;
   }
  }
  //boost::this_thread::sleep(boost::posix_time::seconds(5));
}
 
void second(boost::mutex& mutex)
{
    boost::lock_guard<boost::mutex> lock(mutex);
 
    for (int i = n/2; i <= n; i++)
    {
        for (int j = i; j != 0; j /= 10)
           if (j%10 == 2) 
              kvo++;
    }
}
 
int main() 
{
  int start=GetTickCount();
  boost::mutex io_mutex;
  boost::thread my_thread(boost::bind(&first, boost::ref(io_mutex)));
  boost::thread my_thread2(boost::bind(&second, boost::ref(io_mutex)));
  my_thread.join();
  my_thread2.join();
  cout<<kvo<<endl;
  int end=GetTickCount();
  cout<<end-start<<endl;
  getchar();
  return 0;
}
время 12480

не особая разница...(
может что-то не так делаю?..)

Добавлено через 11 минут
кстати, при варианте без синхронизации время намного меньше
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
#include <boost/thread/thread.hpp>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <iostream>
#include <windows.h>
#define n 100000000
using namespace std;
int one = 0;
int two = 0;
void first() 
{
   for (int i = 0; i < n/2; i++)
   {
       for (int j = i; j != 0; j /= 10)
          if (j%10 == 2) 
             one++;
   }
}
 
void second()
{
    for (int i = n/2; i <= n; i++)
    {
        for (int j = i; j != 0; j /= 10)
           if (j%10 == 2) 
              two++;
    }
}
 
int main() 
{
  int start=GetTickCount();
  boost::thread my_thread(&first);
  boost::thread my_thread2(&second);
  my_thread.join();
  my_thread2.join();
  cout<<one+two<<endl;
  int end=GetTickCount();
  cout<<end-start<<endl;
  getchar();
  return 0;
}
7442
1
BRcr
4009 / 2298 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
07.01.2013, 02:17 #12
Сравнение по количеству потоков... на досуге, может, допинаю сюда метод с предварительно заполненным массивом значений по разрядам, как предложил ValeryS, но тот вообще нисколько времени занимать не будет после заполнения массива, так что смысла особо нет...
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
using namespace std;
// ---------------------------------------------------------------------------
typedef unsigned __int64 ull; // a long, long unsigned value
// ---------------------------------------------------------------------------
ull straight_count_2( ull n ) {
    ull cnt = 0;
 
    for ( ull i = 0, j; i <= n; ++i ) {
        for ( j = i; j != 0; j /= 10 ) {
            if ( j % 10 == 2 ) {
                ++cnt;
            }
        }
    }
    return cnt;
}
// ---------------------------------------------------------------------------
struct thread_data {
    ull begin, end, result;
};
DWORD WINAPI thread_count( LPVOID lpParam ) {
    thread_data *data = ( thread_data* )lpParam;
    ull cnt = 0, end = data->end;
 
    for ( ull i = data->begin, j; i <= end; ++i ) {
        for ( j = i; j != 0; j /= 10 ) {
            if ( j % 10 == 2 ) {
                ++cnt;
            }
        }
    }
    data->result = cnt;
}
ull do_threaded_count( int _threads_amount, ull _seed ) {
    HANDLE *threads = new HANDLE[_threads_amount];
    thread_data *data = new thread_data[_threads_amount];
    ull result = 0, seed_part = _seed / _threads_amount;
 
    for ( size_t i = 0; i < _threads_amount; ++i ) {
        data[i].begin = seed_part * i + 1;
        data[i].end = seed_part * ( i + 1 );
        threads[i] = CreateThread( NULL, 0, &thread_count, &data[i], 0, NULL );
    }
    WaitForMultipleObjects( _threads_amount, threads, TRUE, INFINITE );
 
    for ( size_t i = 0; i < _threads_amount; result += data[i].result, CloseHandle( threads[i] ), ++i );
    delete[]threads;
    delete[]data;
 
    return result;
}
// ---------------------------------------------------------------------------
int _tmain( int argc, _TCHAR *argv[] ) {
    system( "color 2e" ); 
    system( "chcp 1251" );
    system( "cls" );
    //////////////////////////////////////
    t_time_counter tc;
    ull result, seed = 50000000;
 
    tc.start( );
    result = straight_count_2( seed );
    tc.stop( );
    cout << "straight_count_2() elapsed " << tc.mins << ":" << tc.secs << ":" << tc.msecs <<
                   ",  result = " << result << endl;
 
    for ( size_t i = 2; i <= 20; i += 2 ) {
        tc.start( );
        result = do_threaded_count( i, seed );
        tc.stop( );
        cout << i << " threads count elapsed " << tc.mins << ":" << tc.secs << ":" << tc.msecs <<
                       ",  result = " << result << endl;
    }
 
    //////////////////////////////////////
    cout << "\n\n";
    system( "pause" );
    return 0;
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class t_time_counter {
public:
    DWORD full_time;
    int hours, mins, secs, msecs;
    void __fastcall start( ) {
        full_time = GetTickCount( );
    }
    void __fastcall stop( ) {
        full_time = GetTickCount( ) - full_time;
        hours = ( mins = ( secs = full_time / 1000 ) / 60 ) / 60;
        mins %= 60;
        secs %= 60;
        msecs = full_time % 1000;
    }
};
1
Миниатюры
Подсчитывать количество цифр 2  
NeonLost
Пес войны
75 / 86 / 3
Регистрация: 23.02.2012
Сообщений: 653
07.01.2013, 02:24 #13
Цитата Сообщение от BRcr Посмотреть сообщение
Сравнение по количеству потоков... на досуге, может, допинаю сюда метод с предварительно заполненным массивом значений по разрядам, как предложил ValeryS, но тот вообще нисколько времени занимать не будет после заполнения массива, так что смысла особо нет...
смысл делать потоков больше чем ядер на компе?..
0
BRcr
4009 / 2298 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
07.01.2013, 02:27 #14
Ну, у кого больше, у кого - нет... сам знаешь, до чего дошел прогресс.
0
NeonLost
Пес войны
75 / 86 / 3
Регистрация: 23.02.2012
Сообщений: 653
07.01.2013, 02:30 #15
да и значение 1 раз промахнулось...(
0
07.01.2013, 02:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2013, 02:30
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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