Дано пятизначное число и нужно проверить является данное число палиндромом. Можно использовать только арифметические/логические операции и операторы while/if. Массивы использовать нельзя. Начала с изучения основ программирования на С++, не могу понять какой алгоритм данной задачи. И вопрос немного отходя от темы. Сам придумать алгоритм я не могу и не понять пока что как решить такую задачу, не является это признаком того что программированием я заниматься не смогу?

Пытаясь придумать алгоритм в "компьютерной записи" Вы пропустили важный момент:
для начала сформулируйте понятные для человека признаки по которым можно проверить палиндром ли это.. 
а после уже спокойно и без проблем перевести на ЯП.. 

Не тестил. Скорее всего есть ошибки. Спать хочу.

Это сообщение отредактировал(а) Игорь1024 - 31.12.2010, 18:35

Игорь1024, а причем здесь ассемблер?

хм..  в разделе "C++ для новичков" предлагать asm код...     
да к тому же неправильный.. палиндром же задан не в 16ричной системе   

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

Это сообщение отредактировал(а) Игорь1024 - 27.12.2010, 15:35

так у Вас же "12321" есть десятичное число   

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

 


Это сообщение отредактировал(а) mes - 27.12.2010, 15:58

Баю-баюшки баю...   

нет, не является   
любое боль-менее сложное занятие требует знаний и практики. всё получится

определим палиндром как слово (строка) S длиной N в некотором алфавите,  (т.е. просто последовательность букв алфавита), обладающая свойством
S(i) = S(N-i-1), i изменяется от 0 до N-1
говоря неформально, палиндром - симметричная строка, читающаяся одинаково слева направа и справа налево.
для определенности будем считать пустую строку палиндромом.
для проверки надо последовательно проверить совпадение первого с последним, второго с предпоследним и т.д.

обобщенный алгоритм проверки (в реализации на С++) будет такой:

это не самая общая (и не вполне правильная) реализация на С++, она приводится для простоты введения в тему. вышеприведенный код будет работать для итераторов произвольного доступа, если входная последовательность непуста.
более общий и правильный код будет ниже, а пока поговорим об этом.
ключевое место алгоритма - понятие итератора (у нас это begin и end), который позволяет
1. идентифицировать элемент в последовательности
2. передвигаться вперед и назад
сам алгоритм прост и вытекает из определения палиндрома. замечу, что он использует только цикл, логические и арифметические операции. операции над итераторами в алгоритме похожи на операции с указателями и массивами, однако тут они выражают семантику алгоритма и необязательно работают с массивами и реальными указателями. все зависит от того, чем конкретно является (как реализован) тип Iterator.

В данной задаче алфавитом являются десятичные цифры 0...9, а строкой - запись числа в десятичной системе. т.к. числа в компьютере представлены в двоичном виде, нужно уметь получать первую, вторую...последнюю (десятичную) цифру числа из внутреннего представления. если это решить, останется просто применить вышеприведенный тривиальный алгоритм.

полностью решение приводить не буду, но путь следующий:
операция 

помещает в переменную y остаток от деления числа x на 10, т.е. значение последней цифры.

в качестве приложения - менее очевидный, но более общий и правильный код, работающий и для  последовательных итераторов, и пустых строк:

эту функцию можно непосредственно применить к явным последовательностям (контейнерам, имеющим двунаправленные итераторы, в т.ч. к обычным массивам), например

M bsa

Поиск: палиндром

bsa, не то. там все про массивы, тут низзя

Уже привели правильные решения, напишу и этот вариант на всякий случай

продолжим...
надеюсь, ТС подумал самостоятельно прежде чем читать дальше   
требуется построить итератор для целых чисел такой, что бы были корректно реализованы операции сравнения итераторов, разыменования (получения значения, на которое указывает итератор), инкремента и декремента
такой итератор в простейшей реализации мог бы выглядеть так:

т.е. итератор хранит само число х и текущую позицию p. инкремент/декремент производится тривиальным образом, для разыменования (получение цифры в позиции p) используется выражение
(x/pow10(p)) % 10; Здесь самая трудоемкая операция - возведение в степень.
И хотя реализация нашего алгоритма с этим итератором и "правильной" реализацией возведения в степень чуть быстрее реализации darkart, интуитивно чувствуется, что резерв есть, и можно придумать алгоритм быстрее.

идея следующая: если удастся простым способом получить "перевернутое" число, его можно просто сравнить с исходным.
такой алгоритм потребует вычисления остатка от деления на 10 для всех цифр исходного числа и формирования из остатков перевернутого числа, умножаемого на 10.
т.е. получается довольно простой цикл.
пока я это писал Skevalt привел почти тот самый алгоритм. если "отсечь лишнее", получится попроще (и побыстрее).

может позицию хранить не как индекс, а как степень десяти ?
т.е. итерацию проводить не как ++/--, а как *=10 / /=10

Добавлено через 3 минуты и 40 секунд

у этого алгоритма есть недостаток возможно  переполнение и как следствие не правильный результат..

Добавлено через 4 минуты и 37 секунд

а чем не устраивает хранение промежуточного числа как строки ?

в упор не вижу где?

это тот же массив

не устраивает ТС'а т.к. по условию массивы нельзя использовать.

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


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

ну на примере unsigned char : 
126 -> [621] -> 109

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


Добавлено через 2 минуты и 52 секунды

это смотря как подходить к вопросу.. мне кажется можноэтим подходом как раз повысить ясность..сейчас попробую.. 

да, ступил  

хотя при этом алгоритм может и работать правильно, надо проверить

отвлекся.. вот выбрал минутку и сделал набросок :

Да чего уж там? Запрещать, так запрещать. Тогда уж и без if/while обойдёмся...   





Ты бы, для начала, с полом определил(ась/ся) бы...    

тогда уж и без рекурсии 

а вообще для 5ти-значного числа из задания, все гораздо проще :


Добавлено через 2 минуты и 16 секунд
или, как было приведено выше :

mes, все верно. вчера спешил и не сразу сообразил)))
точнее, сам себя запутал)

Это сообщение отредактировал(а) baldina - 28.12.2010, 10:32

http://liveworkspace.org/code/bbaad377991f...faf6e91ea7d57b8

чтоб не было переполнения можно ведь переворачивать только половину числа.. 


Добавлено @ 11:19
вот еще один вариант получения длины числа (32х битного):

этот "switch" можно метагенерить, но мне сейчас лень об этом думать

Это сообщение отредактировал(а) mes - 28.12.2010, 11:26

  

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

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

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

  

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


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

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





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

в числе

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

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

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

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

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

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

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


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


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



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

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

ах да.. сорри.. запутался в трех соснах 
но с нулем все равно надо быть осторожным..

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