Здравствуйте, Abyx, Вы писали:
A>Здравствуйте, shrecher, Вы писали:
A>
A>string Power( int X, short Y) // вернуть строчное представление результата X в степени Y
A>{
A> return lexical_cast<string>(pow(X, Y));
A>}
A>
A>в чем проблема?
Н-да. pow вернет double, что есть максимальное число в нем — 1.79769e+308. Очевидно, что если аргументы к примеру, X=100000, Y=32000, то результат будет много больше.
Здравствуйте, shrecher, Вы писали:
S>Н-да. pow вернет double, что есть максимальное число в нем — 1.79769e+308. Очевидно, что если аргументы к примеру, X=100000, Y=32000, то результат будет много больше.
ну будет +inf, ну и что?
вы умножаете int32*int32 и не думаете о том что оно может переполнится
Здравствуйте, Abyx, Вы писали:
A>Здравствуйте, shrecher, Вы писали:
S>>Н-да. pow вернет double, что есть максимальное число в нем — 1.79769e+308. Очевидно, что если аргументы к примеру, X=100000, Y=32000, то результат будет много больше.
A>ну будет +inf, ну и что? A>вы умножаете int32*int32 и не думаете о том что оно может переполнится
авторы вопроса хотят для всех всех возможных значений int и short, т.е. два миллиарда в степени тридцать две тысячи. Длинная такая строка.
Здравствуйте, shrecher, Вы писали:
S>Здравствуйте, Abyx, Вы писали:
A>>Здравствуйте, shrecher, Вы писали:
A>>
A>>string Power( int X, short Y) // вернуть строчное представление результата X в степени Y
A>>{
A>> return lexical_cast<string>(pow(X, Y));
A>>}
A>>
A>>в чем проблема?
S>Н-да. pow вернет double, что есть максимальное число в нем — 1.79769e+308. Очевидно, что если аргументы к примеру, X=100000, Y=32000, то результат будет много больше.
Очевидно что во Вселенной где нам выпало счастье жить, атомов 10^80 Что как бы намекает, что 10^300 на реальной задаче не переполнится
Опыт — это такая вещь, которая появляется сразу после того, как была нужна...
Здравствуйте, ZOI4, Вы писали:
ZOI>Здравствуйте, shrecher, Вы писали:
S>>Как такой вопрос на собеседовании, был задан на позиции C++ разработчика?
ZOI>Зависит от того сколько времени дают на решение.
Минут 15-20. Можно, не все решение, но хотя бы определиться со структурами данных и написать основу алгоритма.
Если в лоб, то на пятой минуте пришла в голову идея просто перемножать Х друг на друга по очереди Y раз, а промежуточные результаты запихивать в строку%))) Но пожалуй еще подумаю%)
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
В общем, на вскидку надо определить сколько раз Х можно умножить на Х, чтобы результат помещался в double, например, если погрешности пофик, или в _int64, если точность важна. И потом считать сколько таких произведений получится при проходе X*X Y раз, плюс последнее перемножение Х-ов, которое может быть меньше. В общем:
1. Сколько раз X*X*...*X, чтоб _int64 не переполнился.
2. Считаем сколько таких произведений требуется, чтобы Х на Х умножился до около Y раз, с мешьшей стороны.
3. Домножаем оставшееся.
4. Переводим это дело в строку, вручную умножая наше произведение из п.1 вручную от младшего разряда к старшему на получившееся число оных, не забывая приплюсовать остаток из п.3.
В общем как-то так, если непонятно, то сорри, вечер после рабочего дня — моска уже нет.
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
Здравствуйте, ZOI4, Вы писали:
ZOI>Здравствуйте, shrecher, Вы писали:
ZOI>В общем как-то так, если непонятно, то сорри, вечер после рабочего дня — моска уже нет.
Возможно это и так. Меня больше интересует адекватность этого вопроса. Его задали моему знакомому и мы тут спорили о смысле спрашивать такое. За много лет прогерской жизни я ни разу не писал ничего подобного. Как-то лавки стали спрашивать что-то очень мудреное, видать разворот строки уже всем надоел
Здравствуйте, shrecher, Вы писали:
S>Здравствуйте, ZOI4, Вы писали:
ZOI>>Здравствуйте, shrecher, Вы писали:
ZOI>>В общем как-то так, если непонятно, то сорри, вечер после рабочего дня — моска уже нет.
S>Возможно это и так. Меня больше интересует адекватность этого вопроса. Его задали моему знакомому и мы тут спорили о смысле спрашивать такое. За много лет прогерской жизни я ни разу не писал ничего подобного. Как-то лавки стали спрашивать что-то очень мудреное, видать разворот строки уже всем надоел
Да это ж школьная задача, реализовать перемножение двух длинных чисел. В тривиальном случае хранишь по одному десятичному разряду в элементе массива, и перемножаешь как на листочке.
Здравствуйте, shrecher, Вы писали:
S>Возможно это и так. Меня больше интересует адекватность этого вопроса. Его задали моему знакомому и мы тут спорили о смысле спрашивать такое. За много лет прогерской жизни я ни разу не писал ничего подобного. Как-то лавки стали спрашивать что-то очень мудреное, видать разворот строки уже всем надоел
Если оценивать как один из вопросов на смекалку, то нормально, имхо. Хотя 15-20 минут мне кажется маловато, все-таки.
ЗЫ Зато виртуальные деструкторы до сих пор не стареют — ходил тут тоже по собеседованиям не так давно — хиты номер один — виртуальные деструкторы и организация контейнеров
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
ZOI>1. Сколько раз X*X*...*X, чтоб _int64 не переполнился. ZOI>2. Считаем сколько таких произведений требуется, чтобы Х на Х умножился до около Y раз, с мешьшей стороны. ZOI>3. Домножаем оставшееся. ZOI>4. Переводим это дело в строку, вручную умножая наше произведение из п.1 вручную от младшего разряда к старшему на получившееся число оных, не забывая приплюсовать остаток из п.3.
Да, тут еще похоже еще одного unsigned _int64 не хватит для подсчета произведений из пункта 1. Значит надо вводить еще одно измерение и считать, сколько сумм произведений из пункта 1, поместиться еще в один unsigned _int64
ЗЫ Хы, написал, но не отправил%) Определенно, пора спать%)
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
Здравствуйте, ZOI4, Вы писали:
ZOI>Здравствуйте, shrecher,
ZOI>Если в лоб, то на пятой минуте пришла в голову идея просто перемножать Х друг на друга по очереди Y раз, а промежуточные результаты запихивать в строку%))) Но пожалуй еще подумаю%)
пробегать каждый бит в Y
если бит == 1, то result *= x;
вне зависимости от бита делать делать X = X * X
X * X можно считать алгоритмом карацубы (это если стоит задача совсем написать велосипед и не пользоваться библиотеками для длинной арифметики)
Здравствуйте, _software_engineer_, Вы писали:
___>пробегать каждый бит в Y ___>если бит == 1, то result *= x;
___>вне зависимости от бита делать делать X = X * X
Хм, я может чего-то пропустил, но где у вас защита переполнения в result? Основная проблема в ней.
Мафиозная диктатура это нестабильность. Если не мафиозная диктатура, то Конституция и демократия.
Здравствуйте, ZOI4, Вы писали:
ZOI>Здравствуйте, _software_engineer_, Вы писали:
___>>пробегать каждый бит в Y ___>>если бит == 1, то result *= x;
___>>вне зависимости от бита делать делать X = X * X
ZOI>Хм, я может чего-то пропустил, но где у вас защита переполнения в result? Основная проблема в ней.
Забыл уточнить — я предлагал это для длинной арифметики