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

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

Войти
Регистрация
Восстановить пароль
 
_D4rki_
1 / 1 / 0
Регистрация: 10.10.2016
Сообщений: 29
#1

Сортировка разрядов в числе - C++

18.10.2016, 18:40. Просмотров 230. Ответов 2
Метки нет (Все метки)

Условие задачи:

Числовые последовательности являются очень интересными математическими объектами. Рассмотрим последовательность, которая получается с помощью двух операций: удвоения и «сортировка разрядов». Последняя операция заключается в том, что разряды десятичной записи числа упорядочиваются по возрастанию. Например, число 5726 после сортировки превращается в 2567.
Первым членом последовательности является число 1, каждый следующий член получается умножением предыдущего на 2 и последующей сортировкой разрядов. Первые члены последовательности будут выглядеть так:
1, 2, 4, 8, 16, 23, 46, 29, 58, 116, 223, 446, 289, 578, 1156, …
Напишите программу, которая по номеру элемента последовательности вычисляет его значение.

Я написал правильно работающую программу, суть которой в том, что всё число поразрядно записывается в массив, и затем в массиве сортируются. Проблема в том, что если введенный номер элемента достаточно большой, то время работы программы очень долгое.

Как можно ускорить работу программы.

Вот мой код:
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 <iostream>
using namespace std;
int a[100];
template< class T >
void insertSort(T* a, int size)
{
    T tmp;
    for (int i = 1, j; i < size; ++i)
    {
        tmp = a[i];
        for (j = i - 1; j >= 0 && a[j] > tmp; --j)
            a[j + 1] = a[j];
        a[j + 1] = tmp;
    }
}
int sort(unsigned long long k) {
    int i = 1, c;
    while (k != 0) {
        a[i] = k % 10;
        k = k / 10;
        i++;
    }
    insertSort(a, i);
    k = 0;
    for (c = 1; c < i; c++) {
        k = k * 10 + a[c];
    }
    return k;
}
int main() {
    long long n;
    unsigned long long k;
    cin >> n;
    k = 1;
    for (int i = 1; i <= n - 1; i++) {
        k = k * 2;
        k = sort(k);
    }
    cout << k;
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.10.2016, 18:40
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Сортировка разрядов в числе (C++):

Проверить как изменится количество разрядов в числе M по сравнению с количеством разрядов числа N - C++
Дано натуральное число N. Определить M=N! Проверить как измениться количевство разрядов в числе M по сравнению с количеством разрядов...

Проверить, как изменилось количество разрядов в числе M по сравнению с количеством разрядов числа N - C++
Выручайте....Дано натуральное число N. Определить M=N!. Проверить, как изменилось количество разрядов в числе M по сравнению с...

Перебор высших разрядов в бинарном числе - C++
возникла необходимость перебора в цикле бинарного числа с высшими разрядами, например: 1 11 111 1111 11111 111111 и...

Функция, инвертирующая в целом числе n разрядов, начиная с позиции p - C++
Пожалуйста помогите. Надо написать функцию , которая возвращает число , полученное из целого числа x , в котором инвертированы n разрядов ,...

В каждом числе массива определить количество разрядов, равных "1" - C++
В каждом числе массива определить количество разрядов, равных &quot;1&quot;. Записать это количество в отдельный массив. Все вроде сделал,только...

В каждом числе массива определить количество разрядов, равных "1" - C++
Вот задание В каждом числе массива определить количество разрядов, равных &quot;1&quot;. Записать это количество в отдельный массив. Числа...

2
sergestus
77 / 77 / 23
Регистрация: 26.10.2011
Сообщений: 220
Завершенные тесты: 1
19.10.2016, 01:34 #2
Цитата Сообщение от _D4rki_ Посмотреть сообщение
Как можно ускорить работу программы.
Можно, за счет использования дополнительной памяти (примерно в полтора раза):
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
unsigned char m[10];
unsigned long long d[10]=
{ 
    0,
    1111111111,
    2222222222,
    3333333333,       
    4444444444,
    5555555555,
    6666666666,
    7777777777,
    8888888888,
    9999999999,
};
 
unsigned long long e[10]=
{ 
    1,
    10,
    100,
    1000,       
    10000,
    100000,
    1000000,
    10000000,
    100000000,
    1000000000,
};
 
unsigned int sort(unsigned int k) 
{
    while (k != 0) 
    {
        unsigned char digit = k % 10;
        m[digit]++;
        k = k / 10;
    }
 
    for (unsigned char i = 1,r=m[1]; i <= 9; ++i,r=m[i]) 
    {
        if(!r) continue;
        k = k*e[r]+d[i]/e[10-r];
        m[i]=0;
    }
    return k;
}
0
Mr.X
Эксперт С++
3060 / 1705 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
19.10.2016, 11:13 #3
На самом деле последовательность зацикливается с номера 31 с периодом 6, поэтому все элементарно:
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
///////////////////////////////////////////////////////////////////////////////
//1.
///////////////////////////////////////////////////////////////////////////////
//Числовые последовательности являются очень интересными математическими
//объектами. Рассмотрим последовательность, которая получается с помощью
//двух операций: удвоения и «сортировка разрядов». Последняя операция
//заключается в том, что разряды десятичной записи числа упорядочиваются
//по возрастанию. Например, число 5726 после сортировки превращается в 2567.
//Первым членом последовательности является число 1, каждый следующий
//член получается умножением предыдущего на 2 и последующей сортировкой
//разрядов. Первые члены последовательности будут выглядеть так:
//1, 2, 4, 8, 16, 23, 46, 29, 58, 116, 223, 446, 289, 578, 1156, …
//Напишите программу, которая по номеру элемента последовательности
//вычисляет его значение.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <string>
///////////////////////////////////////////////////////////////////////////////
typedef std::string         T_str;
typedef unsigned long long  T_int;
///////////////////////////////////////////////////////////////////////////////
T_int   get_elem_with_ind( T_int    n )
{
    const
    T_int   PERIOD                  {6};
    T_int   res                     {1};
    T_int   prev_res_with_ind_0     {};
    bool    latest_iteration        {};
    --n;
 
    for( T_int  i{}; ; ++i )
    {
        if  (
                i % PERIOD   ==  0
            )
        {
            if  (
                    res     ==  prev_res_with_ind_0
                )
            {
                latest_iteration    =   true;
            }
 
            prev_res_with_ind_0     =   res;
        }//if
 
        if  (
                    i == n
 
                ||      latest_iteration
                    &&  i % PERIOD   ==  n % PERIOD
            )
        {
            return  res;
        }
 
        res   *=  2;
 
        auto    res_str     =   std::to_string(res);
 
        std::sort
            (
                res_str.begin   (),
                res_str.end     ()
            );
 
        res   =   std::stoull( res_str );
    }//for
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_int   n{};
    std::cout   <<  "n = ";
    std::cin    >>  n;
 
    std::cout   <<  get_elem_with_ind(n)
                <<  std::endl;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.10.2016, 11:13
Привет! Вот еще темы с ответами:

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

Определение количества разрядов у числа - C++
Написал программку, которая должна определять количество разрядов у чисел. При вводе двухзначных и трехзначных, программа правильно...

Посчитать m последних разрядов числа n - C++
Всем привет! В свободное от работы время занимаюсь программированием - подтягиваю свой уровень до того, который был когда-то раньше,...

поиск разрядов в двухбайтовых словах - C++
Дан файл состоящий из двубайтовых слов,количество слов=4096(или он равен 8192 байта) C начало(начиная с первого слова) надо искать в 14...


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

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

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