VPF::проверка палиндрома - Форум программистов

mes

Дата 28.12.2010, 13:23 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(Dov @ 28.12.2010, 12:13

)

Чего там? У меня не открывается ссылка. Здесь выложи...

Код



int main () {

  unsigned a  = ~0;
  std::cout << "value: "<< a << " len: " << (int)log10(a) << " ?! ";

}

Цитата

value: 4294967295 len: 9 ?!

Добавлено через 13 минут и 41 секунду

Цитата(baldina @ 28.12.2010, 11:24

)

переворачивая половину числа можно не вычислять число цифр

--------------------

http://opendots.net

Dov

Дата 28.12.2010, 19:58 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 11
Всего: 88

Цитата(mes @ 28.12.2010, 12:23

)

value: 4294967295 len: 9 ?!

Не понял тонкого намёка. smile

Цитата(baldina @ 28.12.2010, 11:24

)

переворачивая половину числа можно не вычислять число цифр

Да, алгоритм хороший, но абсолютно не эффективный. Ведь в заданном числе уже первая и последняя цифра могут не совпасть. Зачем же всё это число 'разбирать на запчасти' ? smile

Но по репе заработал всё-равно... smile

Я бы изменил как-то так:

Код

bool is_pal2 (unsigned x)
{
    unsigned y = (unsigned)pow(10., (unsigned)log10(x));
    
    while (y)
    {
        if(x / y % 10 != x % 10)
            return false;

        x /= 10;
        y /= 100;
    }

    return true;
}

Это сообщение отредактировал(а) Dov - 28.12.2010, 20:03

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

mes

Дата 28.12.2010, 20:06 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(Dov @ 28.12.2010, 18:58

)

Не понял тонкого намёка.

в числе

Цитата(Dov @ 28.12.2010, 18:58

)

4294967295

10 цифр(если конечно я правильно подсчитал ), а не 9 smile

Добавлено через 56 секунд
другими словами (int)log10 показывает неправильный результат..

--------------------

http://opendots.net

Dov

Дата 28.12.2010, 20:19 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 11
Всего: 88

Цитата(mes @ 28.12.2010, 19:06

)

другими словами (int)log10 показывает неправильный результат..

всё правильно показывает, так надо. smile

--------------------

baldina

Дата 29.12.2010, 15:03 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

Цитата(Dov @ 28.12.2010, 19:58

)

Цитата(baldina @  28.12.2010,  11:24 )
переворачивая половину числа можно не вычислять число цифр

Да, алгоритм хороший, но абсолютно не эффективный.   Ведь в заданном числе уже первая и последняя цифра могут не совпасть. Зачем же всё это число 'разбирать на запчасти' ?
Но по репе заработал всё-равно...

Ну, положим, из всех вышеприведенных он самый эффективный.
Во-вторых, "могут не совпасть" и "не совпадут" вещи неодинаковые. Надо анализировать средний случай. Для этого надо знать, какова вероятность появления палиндрома среди множества проверяемых чисел.
А то можно и алгоритм линейного поиска называть самым эффективным, т.к. "может совпасть" при первом же сравнении.
Аналитические исследования проводить лениво, а вот стандартный генератор случайных чисел на 200млн значений генерит 2.5млн палиндромов. В этих условиях алгоритм с обработкой половины значительно обгоняет другие. А самые медленные реализации те, что вызывают встроенные pow и log.
Кстати, данный результат неформально можно объяснить так - для определения какая цифра первая, а какая последняя, требуется узнать число цифр. Что сразу делает такой алгоритм зависящим от n, где n - число цифр.
"Алгоритм половины числа" (назовем его так) в среднем (на произвольном числе) зависит от n/2.
зы: за репу спасибо

baldina

Дата 29.12.2010, 17:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

кому интересно, тут результаты:
http://liveworkspace.org/code/5ad1983fdeb2...2368c01d7f3b717

длину числа пришлось ограничить тремя 000, т.к. на более длинных не проходит тест рекурсивного алгоритма Dov (видимо переполнение, не стал вникать).

у себя имею такие результаты (N/A - тест не пройден):
для трехзначных чисел

Код


(darkart):
        0.252 sec,              1091528 palindromes in 10000000 numbers
Simple iterator +1 (baldina):
        0.268 sec,              1091528 palindromes in 10000000 numbers
Compare (Skevalt):
        0.442 sec,              1091528 palindromes in 10000000 numbers
Simple iterator *10 (baldina, mes):
        0.259 sec,              1091528 palindromes in 10000000 numbers
Compare (baldina):
        0.095 sec,              1091528 palindromes in 10000000 numbers
Recursion (Dov):
        0.467 sec,              1091528 palindromes in 10000000 numbers
Compare half (mes, baldina):
        0.123 sec,              1091528 palindromes in 10000000 numbers
Division (Dov):
        0.411 sec,              1091528 palindromes in 10000000 numbers

для любых чисел (32bit)

Код


(darkart):
        0.357 sec,              129934 palindromes in 10000000 numbers
Simple iterator +1 (baldina):
        0.375 sec,              129934 palindromes in 10000000 numbers
Compare (Skevalt):
        0.557 sec,              129934 palindromes in 10000000 numbers
Simple iterator *10 (baldina, mes):
        0.352 sec,              129934 palindromes in 10000000 numbers
Compare (baldina):
        0.176 sec,              129934 palindromes in 10000000 numbers
Recursion (Dov):
        N/A
Compare half (mes, baldina):
        0.139 sec,              129934 palindromes in 10000000 numbers
Division (Dov):
        0.482 sec,              129934 palindromes in 10000000 numbers

для любых чисел (64bit)

Код


(darkart):
        0.75 sec,               129842 palindromes in 10000000 numbers
Simple iterator +1 (baldina):
        0.738 sec,              129842 palindromes in 10000000 numbers
Compare (Skevalt):
        N/A
Simple iterator *10 (baldina, mes):
        0.777 sec,              129842 palindromes in 10000000 numbers
Compare (baldina):
        0.26 sec,               129842 palindromes in 10000000 numbers
Recursion (Dov):
        0.545 sec,              105257 palindromes in 10000000 numbers
Compare half (mes, baldina):
        0.182 sec,              129842 palindromes in 10000000 numbers
Division (Dov):
        N/A

Это сообщение отредактировал(а) baldina - 29.12.2010, 17:53

Skevalt

Дата 29.12.2010, 21:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 30.11.2006

Репутация: нет
Всего: 3

Ура! Я античемпион!

mes

Дата 29.12.2010, 23:31 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(Dov @ 28.12.2010, 19:19

)

всё правильно показывает, так надо.

ах да.. сорри.. запутался в трех соснах smile

но с нулем все равно надо быть осторожным..

Добавлено через 2 минуты и 24 секунды
baldina, не думал, что эта тема может сподвигнуть на подобные исследования smile

--------------------

http://opendots.net

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »