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

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

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

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

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

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

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

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

Операции с текстом (длина, количество цифр, количество букв) - C++
Составить программу, позволяющую для строки , введенного пользователем , определяет: ( 1) его длину ; (2) количество цифр ; (3) количество...

Сумма цифр и количество цифр - C++
Задача: Вводится два натуральных числа. Нужно написать функции для того, чтобы: (1) найти сумму цифр составляющих это число (545 = 14), ...

Вывести слово, содержащее наибольшее количество цифр и вывести число цифр в слове - C++
Дана строка. Исключить из нее подстроку, расположенную между самой левой открывающейся скобкой «(» и самой правой закрывающейся скобкой...

количество цифр - C++
Нужно программа на Cи, которая после ввода любого числа выводила количество цифр из которых оно состоит(156 - 3 цифры). Если тема уже есть...

Подсчитать количество цифр - C++
Необходимо подсчитать количество цифр полученных в результате, но считает только целую часть,как подсчитать ещё и дробную? вот пример ...

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

Не по теме:

BRcr, ок

.
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,012
06.01.2013, 22:09     Подсчитывать количество цифр 2 #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]. И все-таки придерживаюсь мнения, что такие вещи решаются не перебором) Но думать уже влом, поэтому отправляюсь спать.
we2seek
78 / 78 / 17
Регистрация: 25.01.2010
Сообщений: 380
06.01.2013, 22:13     Подсчитывать количество цифр 2 #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]. И все-таки придерживаюсь мнения, что такие вещи решаются не перебором) Но думать уже влом, поэтому отправляюсь спать.
Теория классная, но не соответствует поставленной задаче. Вы внимательно прочли условие? Автору необходимо посчитать реальное количество двоек, а вы предлагаете считать возможное количество.
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,737
06.01.2013, 22:47     Подсчитывать количество цифр 2 #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
NeonLost
Пес войны
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
07.01.2013, 00:16     Подсчитывать количество цифр 2 #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
BRcr
4008 / 2297 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
07.01.2013, 02:17     Подсчитывать количество цифр 2 #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;
    }
};
Миниатюры
Подсчитывать количество цифр 2  
NeonLost
Пес войны
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
07.01.2013, 02:24     Подсчитывать количество цифр 2 #13
Цитата Сообщение от BRcr Посмотреть сообщение
Сравнение по количеству потоков... на досуге, может, допинаю сюда метод с предварительно заполненным массивом значений по разрядам, как предложил ValeryS, но тот вообще нисколько времени занимать не будет после заполнения массива, так что смысла особо нет...
смысл делать потоков больше чем ядер на компе?..
BRcr
4008 / 2297 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
07.01.2013, 02:27     Подсчитывать количество цифр 2 #14
Ну, у кого больше, у кого - нет... сам знаешь, до чего дошел прогресс.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2013, 02:30     Подсчитывать количество цифр 2
Еще ссылки по теме:

Количество цифр в строке - C++
Написал программу, которая вычисляет количество цифр в строке. Но программа не работает. Что не правильно? #include...

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

Количество цифр в факториале - C++
Найти количество цифр в записи факториала натурального числа N. Не дружу с длинной арифметикой. Ограничение - факториал 1000000 за 5...

Подсчитать количество цифр - C++
Используя рекурсивную подпрограмму: подсчитать количество цифр в заданном натуральном числе. Помогите пожалуйста..я неезнаю как...

Количество цифр в числе - C++
Число указует пользователь и нужно через for цыкл


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

Или воспользуйтесь поиском по форуму:
NeonLost
Пес войны
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
07.01.2013, 02:30     Подсчитывать количество цифр 2 #15
да и значение 1 раз промахнулось...(
Yandex
Объявления
07.01.2013, 02:30     Подсчитывать количество цифр 2
Ответ Создать тему
Опции темы

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