168 / 90 / 44
Регистрация: 22.09.2019
Сообщений: 390
1

Палиндромы и в 10й с/с, и в 2й с/с

26.02.2020, 21:44. Показов 1050. Ответов 9

Доброго времени суток! Понадобилось написать программу, которая вычисляет все палиндромы и в десятичной, и в двоичной системе до некоторого максимального значения. Конкретно тут предел 1е6. Нужно использовать строки типа string(не С-строки!) для хранения чисел. Программа рабочая, всё как надо. Меня смущает её время выполнения. В среднем около 3,8 с. На С-строках прога с подобным алгоритмом работает гораздо быстрее. Предложите свои идеи для оптимизации скорости выполнения данного решения. От меня спасиба и + в карму.
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <string>
#include <iomanip>
#include <ctime>
 
using namespace std;
 
void FromNumToString(string &str10, int num) {
    str10 = to_string(num);
}
 
bool IsPal(string &str) {
    bool flag = true;
    int len = str.size();
    for (int j = 0; j < len / 2; ++j) {
        if (str[j] != str[len - j - 1]) {
            flag = false;
            break;
        }
    }
    return flag;
}
 
bool From10To2(string &str2, int num) {
    bool flag = true;
    string bytes = "";
    int temp1 = num;
    do {
        char temp = static_cast<char>(num % 2 + 48);
        bytes += temp;
        num /= 2;
    } while (num);
 
    reverse(bytes.begin(), bytes.end());
    str2 += bytes;
    if (!str2[0]) flag = false;
    return flag;
}
 
int main() {
    const double max = 1e6;
    string str_10 = "", str_2 = "";
    for (int value = 10; value < max; ++value) {
        FromNumToString(str_10, value);
        if (IsPal(str_10))
            if (From10To2(str_2, value))
                if (IsPal(str_2))
                    cout << setw(6) << str_10 << " <----> " << setw(5) << str_2 << endl;
        str_10.clear();
        str_2.clear();
    }
    cout << clock() / 1000.;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.02.2020, 21:44
Ответы с готовыми решениями:

Найти в заданном тексте, состоящем из n строк, все слова палиндромы и числа палиндромы
Сроки жутко горят :( поэтому надеюсь на вашу помощь: Задача: Найти в заданном тексте, состоящем...

Найти все числа-палиндромы, которые не больше 100, и их квадраты тоже палиндромы
Натуральное число называется палиндромом, если его запись читается однинакого с начала и с конца...

Найти все палиндромы, не превышающие 100, которые при возведении в квадрат также дают палиндромы
Натуральное число называется палиндромом, если его запись читается одинаково с начала и с конца...

Найти целые числа палиндромы, которые при возведении в квадрат также дают палиндромы (22^2=484)
Найти целые числа-палиндромы, которые при возведении в квадрат также дают палиндромы (22^2=484)...

9
Нарушитель
8510 / 4526 / 1046
Регистрация: 12.03.2015
Сообщений: 21,281
26.02.2020, 21:47 2
А ваще без строк никак низзя? У тебя там основной тормоз - это постоянное перераспределение памяти при преобразовании числа в строку. И выглядит это чудовищно.
Покаж задание.
0
168 / 90 / 44
Регистрация: 22.09.2019
Сообщений: 390
26.02.2020, 21:55  [ТС] 3
Verevkin, дословно: "Получить все натуральные числа https://www.cyberforum.ru/cgi-bin/latex.cgi?\leq {10}^{6}, которые являются палиндромами как в десятичной, так и в двоичной системах. Выполнить задание, используя string-строки для представления данных. Задание выполнить через функции".
0
Нарушитель
8510 / 4526 / 1046
Регистрация: 12.03.2015
Сообщений: 21,281
26.02.2020, 22:23 4
Цитата Сообщение от alo_wu Посмотреть сообщение
Выполнить задание, используя string-строки для представления данных.
Чистое вредительство.
Без строк брутфорс от 0 до 999999 длится:

Палиндромы и в 10й с/с, и в 2й с/с


Через строки не буду делать.
Лень.
0
168 / 90 / 44
Регистрация: 22.09.2019
Сообщений: 390
26.02.2020, 22:30  [ТС] 5
Собсна, никто не заставляет
Понятное дело, что можно сделать другими способами гораздо быстрее. Суть задания в овладении навыков работы со строками))
0
Нарушитель
8510 / 4526 / 1046
Регистрация: 12.03.2015
Сообщений: 21,281
26.02.2020, 22:42 6
Цитата Сообщение от alo_wu Посмотреть сообщение
Суть задания в овладении навыков работы со строками
Удачи, бро.
0
194 / 151 / 44
Регистрация: 11.11.2019
Сообщений: 345
26.02.2020, 23:10 7
Лучший ответ Сообщение было отмечено alo_wu как решение

Решение

alo_wu, можно ускорить более чем в 2 раза, если переработать преобразование числа в строку
C++
1
2
3
4
5
6
7
8
9
10
11
void FromNumToString(string &str10, int num) {
 
    //str10 = to_string(num);
 
    while (num)
    {
        const int rem = num % 10;
        num /= 10;
        str10.push_back(static_cast<char>(rem + '0'));
    }   
}
1
168 / 90 / 44
Регистрация: 22.09.2019
Сообщений: 390
26.02.2020, 23:39  [ТС] 8
fao, Спасибо! Я не думал, что этот способ приведет к такому увеличению скорости работы. Стоило попробовать, прежде чем сюда писать
0
194 / 151 / 44
Регистрация: 11.11.2019
Сообщений: 345
26.02.2020, 23:55 9
alo_wu, перераспределение памяти здесь будет возникать в тех случаях, когда очередной добавленный символ будет выводить строку за пределы ее capacity. Однако, таких перераспределений будет немного, т.к. числа не часто увеличивают количество разрядов. Чтобы вообще исключить перераспределение можно в том месте, где Вы объявляете строки, дописать:

C++
1
2
string str_10;
str_10.reserve(20); // число, которое точно будет вмещать все возможные в данном контексте строки
0
случайный прохожий
2382 / 1599 / 550
Регистрация: 20.07.2013
Сообщений: 4,483
27.02.2020, 01:15 10
Можно глянуть тут (билдер): Найти простые числа, двоичная запись которых представляет собой симметричную последовательность нулей и единиц
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.02.2020, 01:15
Помогаю со студенческими работами здесь

Найти числа от 1 до 99 - палиндромы, которые при возведении в квадрат также дают палиндромы (используя циклы)
Задание: Натуральное число является палиндромом, если его запись читается одинаково с начала и с...

Ошибка в Опере 9.64. В 10й версии работает нормально.
Есть такой код страницы: ... &lt;p&gt; ...&lt;br/&gt; Побед: 16492&lt;br/&gt; Поражений: 1460&lt;br/&gt; &lt;a...

Ввод\вывод способами 9й , 10й функции 21h прерывания
Помогите решить задачу по асм... Задан текст, в котором есть хотя бы одна точка. Преобразовать...

Установка - Установка 7й поверх 10й
В общем форумчане есть вопрос приспичило прям 1) стоит win 10 x64 с начала инсайда 2) приспичило...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru