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

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

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

Сумма цифр и количество цифр C++
C++ Написать программу, которая будет подсчитывать количество гласных букв в строке, введенной с клавиатуры.
количество цифр C++
C++ В последовательности символов подсчитать количество букв и количество цифр
Вывести слово, содержащее наибольшее количество цифр и вывести число цифр в слове C++
C++ подсчитать количество цифр
C++ Подсчитать количество "счастливых" шестизначных автобусных билетов(сумма первых трех цифр равна сумме трех последних цифр)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
David Sylva
 Аватар для David Sylva
1283 / 945 / 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
 Аватар для BRcr
4004 / 2293 / 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
 Аватар для BRcr
4004 / 2293 / 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
2437 / 1609 / 235
Регистрация: 24.11.2012
Сообщений: 3,949
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
 Аватар для we2seek
61 / 61 / 13
Регистрация: 25.01.2010
Сообщений: 313
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
Модератор
6413 / 4879 / 448
Регистрация: 14.02.2011
Сообщений: 16,177
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
Пес войны
 Аватар для 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
 Аватар для BRcr
4004 / 2293 / 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
Пес войны
 Аватар для NeonLost
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
07.01.2013, 02:24     Подсчитывать количество цифр 2 #13
Цитата Сообщение от BRcr Посмотреть сообщение
Сравнение по количеству потоков... на досуге, может, допинаю сюда метод с предварительно заполненным массивом значений по разрядам, как предложил ValeryS, но тот вообще нисколько времени занимать не будет после заполнения массива, так что смысла особо нет...
смысл делать потоков больше чем ядер на компе?..
BRcr
 Аватар для BRcr
4004 / 2293 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
07.01.2013, 02:27     Подсчитывать количество цифр 2 #14
Ну, у кого больше, у кого - нет... сам знаешь, до чего дошел прогресс.
NeonLost
Пес войны
 Аватар для NeonLost
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
07.01.2013, 02:30     Подсчитывать количество цифр 2 #15
да и значение 1 раз промахнулось...(
BRcr
 Аватар для BRcr
4004 / 2293 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
07.01.2013, 02:35     Подсчитывать количество цифр 2 #16
Аккуратнее надо на группы разбивать, а мне влом. А почему столько негатива? Live and let live!
NeonLost
Пес войны
 Аватар для NeonLost
74 / 85 / 3
Регистрация: 23.02.2012
Сообщений: 653
07.01.2013, 02:45     Подсчитывать количество цифр 2 #17
Цитата Сообщение от BRcr Посмотреть сообщение
Аккуратнее надо на группы разбивать, а мне влом. А почему столько негатива? Live and let live!
не пойму почему мой код с синхронизацией работает медленно, а без нее как надо...)
ValeryS
Модератор
6413 / 4879 / 448
Регистрация: 14.02.2011
Сообщений: 16,177
07.01.2013, 04:11     Подсчитывать количество цифр 2 #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++;
вот еще бы от этого тормозного цикла избавится
может раскладывать число в массив и по нему проходить ?
остаток от деления выбросим
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.01.2013, 17:07     Подсчитывать количество цифр 2 #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. особо не тестировал, возможны ошибки.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2013, 17:52     Подсчитывать количество цифр 2
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6413 / 4879 / 448
Регистрация: 14.02.2011
Сообщений: 16,177
07.01.2013, 17:52     Подсчитывать количество цифр 2 #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 уже медленно присутствует перебор от которого я не избавился
не смог угадать формулу по твоим исходникам, подскажи
Yandex
Объявления
07.01.2013, 17:52     Подсчитывать количество цифр 2
Ответ Создать тему
Опции темы

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