Здравствуйте, ononim, Вы писали:
L>>Мне кажется, что это либо вопрос на засыпку был, либо вопрос типа "угадай, из какой книжки я вычитал эту загадку и что именно я не понял". L>>Суть в том, что если сначала взять очень большое X и начать к нему прибавлять кучу очень малых Y, то сумма запросто может получиться равной X. Хотя если начать складывать с малых Y, то конечная сумма будет X + уже заметная Z. O>Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл?
С массивами — проблема — когда я хотел поговорить о них, мне говорили, что есть два числа для сравнения, и только.
Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы
Здравствуйте, landerhigh, Вы писали:
L>>>Но это само по себе по нынешним временам такой ахтунг, что я даже и не знаю, что задающий такой вопрос хотел услышатью _>>Да и проблемой рекурсивно использовать не-реентерабельную функцию имхо нельзя назвать, это просто ошибка.
L>Случается, что собеседователи ожидают, что ответ будет совпадать с вычитанным в учебнике.
Собеседователь вроде был адекватен, не тупил на моих ответах. Хотя, может он просто скипал незнакомое?
Здравствуйте, Marty, Вы писали:
M>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут
Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.
Здравствуйте, cserg, Вы писали:
M>>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут C>Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.
Зато место на стеке бесплатное. Не надо ничего в куче выделять
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
В такой формулировке вопрос странный. Точно также можно было бы спросить, какие проблемы могут быть при цикле while? Да какие угодно из-за кривости рук разработчика. Про рекурсию я бы ответил, что идеологически, алгоритм с использованием рекурсии должен быть глубиной O(log(n)). Т.е. все возможные алгоритмы devide & concure. И это правило не стоит нарушать. Например, считать факториал рекурсией — бред. Если правило не нарушено, то единственная проблема — иногда неудобно дебажить рекурсивные функции.
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Думаю, что этот вопрос нормальный только есть в компании надо будет заниматься графикой или подобным. Во всех остальных случаях вопрос непонятно зачем задавался. Я бы ответил, что просто чисел не бывает. В зависимости от реальной решаемой проблемы числа могут быть натуральными, целыми, рациональными, вещественными и тд. В зависимости от требуемой точности и особенностей работы с ними могут быть и разные представления чисел в системе. Например, в некоторых случаях, можно вообще хранить числа в виде отдельного числителя и отдельного знаменателя. Тогда нет никакой проблемы сравнить суммы двух наборов этих чисел.
Ты, мне кажется, излишне паришься. Как по мне, так ты собес прошёл неплохо, собеседующий просто хотел посмотреть как ты мыслишь. Имхо, мыслишь ты нормально. Есть, конечно, вариант, что собеседующий сам не знал ответы на свои вопросы, но я его не учитываю, предполагая что ты собеседовался в приличную компанию.
Здравствуйте, Marty, Вы писали:
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Проблемы если не выполняется условие выхода из рекурсии (вообще или очень долго) или получается слишком глубокий стек. Всякая нереентерабельность — это не про рекурсию, это другое (например, обработчик прерывания — там рекурсией и не пахнет).
Вообще, вопрос странный. Я б давал куски хорошего и плохого кода и просил сказать какой хороший и какой плохой, а перечислять какие бывают проблемы вообще — это уже какое то поле чудес с Якубовичем, угадывать надо.
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как? M>Я, если честно, только вскользь знаком с нюансами точной (с точностью до epsilon ) работы с плавающими числами. Сказал: нужно задать точность сравнения, эту epsilon, если delta = a — b < epsilon, то равны.
Если числа суммированы до тебя и тебе дают только a и b — то их и сравнивай через ">" Очень странный вопрос в такой формулировке. Меня обычно спрашивали как суммировать чтоб потерять по дороге по-меньше — типа сначала отсортировать по возрастанию, и суммировать от меньших к большим, а тут —
Здравствуйте, Marty, Вы писали:
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Здравствуйте, Marty, Вы писали:
M>>>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут C>>Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.
M>Зато место на стеке бесплатное. Не надо ничего в куче выделять
Можно пример кода с рекурсией, где за счёт этого будет экономия.
Здравствуйте, Marty, Вы писали:
O>>Гм, как вариант, можно отсортировать каждый массив по возрастанию, потом составить новый массив, равный разности (матричной) этих отсортированных массивов. Потом просуммировать этот разностный вектор и сравнить с нулем. Имеет смысл? M>С массивами — проблема — когда я хотел поговорить о них, мне говорили, что есть два числа для сравнения, и только. M>Откуда они взялись — просто суммирование двух массивов чисел, и нужно сравнить суммы
Интересная проблема, кстати. Вот два массива: [1, 1e50] и [5e49, 5e49] — явно сумма в первом больше. Но как это посчитать в общем случае в плавучке?..
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, ononim, Вы писали:
O>Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии"
По-моему, такого уже не бывает. Под стек просто резервируется сколько-то. Например, в ядре линукса под стек выделено 4К, куда уж меньше. Конечно, при программировании надо это учитывать, и не заводить на стеке больших массивов и структур.
Здравствуйте, Marty, Вы писали:
L>>Неделя? Если привык писать юнит-тесты, то достаточно знания, что из используемого представления вещественных чисел вытекают забавные вещи, чтобы очень быстро разобраться на примерах и подкрепить результат теорией. Ну или наоборот. M>А-ха-ха. Кто о чем, а ты о юнит тестах. А я — о сроках. Жизнь научила, что лучше срок поставить долгий, а потом перевыполнить и сделать быстрее, чем малый, а потом оправдываться о его несоблюдении
А меня жизнь научила не ставить сроки от балды, ни маленькие, ни большие
O>>Если ты на какой нить эмбеддед собеседовался то проблема может быть такая, что рекурсия может быть недоступной в принципе, изза того что компилятор не сможет автоматически просчитать необходимый размер памяти под стек и сконфигурять фирмарь соответствующим образом. хз правда подпадает ли этот вариант в понятие "проблемы при рекурсии" Pzz>По-моему, такого уже не бывает. Под стек просто резервируется сколько-то. Например, в ядре линукса под стек выделено 4К, куда уж меньше. Конечно, при программировании надо это учитывать, и не заводить на стеке больших массивов и структур.
В некоторых контроллерах оперативной памяти всего 8КБ. И сюда нужно засунуть глобальные переменные, стек и хип.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, alzt, Вы писали:
M>>Зато место на стеке бесплатное. Не надо ничего в куче выделять A>Можно пример кода с рекурсией, где за счёт этого будет экономия.
Обход дерева без рекурсии требует дополнительной памяти.
Здравствуйте, ononim, Вы писали:
O>В некоторых контроллерах оперативной памяти всего 8КБ. И сюда нужно засунуть глобальные переменные, стек и хип.
8K — это роскошь. В такой контроллер можно прям настоящую программу затолкать.
Мне тут приходилось программировать контроллер, в котором было только 128 байт. Причем когда мы договаривались об этой работе, мне сказали, что их там 256, а я сдуру поверил на слово. А когда вскрылась правда, было поздно что-то менять
Здравствуйте, Marty, Вы писали:
M> Здравствуйте!
M>Сходил тут на собеседование, неплохо пообщался, мне в целом понравилось. Но пару-тройку вопросов я похоже профакапил.
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой)
Кроме как проблемы переполнения стека еще типичная проблема быстродействия.
M>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.
Здравствуйте, Gradiens, Вы писали:
G>Здравствуйте, Marty, Вы писали:
G>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.
G>Но себеседование действительно странное.
А вот на это ни кто не обратил внимание, в задаче фигурируют просто числа, т.е. "сферические числа в вакууме".
Очень странный вопрос в такой формулировке. Меня обычно спрашивали как суммировать чтоб потерять по дороге по-меньше — типа сначала отсортировать по возрастанию, и суммировать от меньших к большим, а тут — 
