Будет ли эта программа завершаться для каждого целого числа?

312
prakhar londhe

В Частичном тесте для подготовки к GATE возник вопрос:

f(n): if n is even: f(n) = n/2 else f(n) = f(f(n-1)) 

Я ответил: «Это прекратится для всех целых чисел», потому что даже для отрицательных целых чисел это прекратится как ошибка переполнения стека .

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

Изменить: была небольшая проблема в коде ..

Какой ответ правильный и почему?

-2
подсказка: каково ваше определение даже? Для меня `-2` даже слишком Máté Juhász 6 лет назад 0
Не указано .. Но имеет ли это значение? prakhar londhe 6 лет назад 0
`если n четное: f (n) = n / 2` означает, что программа останавливается на четное n Máté Juhász 6 лет назад 0
Единственные два варианта были, если он заканчивается для всех целых чисел или заканчивается только для некоторых целых чисел. prakhar londhe 6 лет назад 0
может кто-нибудь, пожалуйста, объясните понижающий голос prakhar londhe 6 лет назад 0
Вероятно, это потому, что вы задали не по теме вопрос (здесь программирование не по теме), а также в нем отсутствуют детали. Máté Juhász 6 лет назад 1
Это не подходит для супер пользователя. Я думаю, это должно продолжаться [cs.se], потому что это теоретический вопрос. Daniel B 6 лет назад 2
Ой извините .. Как я могу перенести этот вопрос туда? prakhar londhe 6 лет назад 0
[* Как переместить свой вопрос на другой сайт Stack Exchange? *] (Https://meta.stackexchange.com/q/85017/355310) Отметьте вопрос для внимания модератора, но сначала убедитесь, что он подходит для целевой аудитории. сайт. Kamil Maciorowski 6 лет назад 0

1 ответ на вопрос

3
Jeff Zeitlin

Этот псевдокод в том виде, в котором он был задан изначально , завершится для всех целых чисел. Если дано нечетное целое число, оно вычтет одно из него и вернется к измененному значению; для четных целых он делится на 2, но не рекурсивно . Поскольку функция возвращается с четным числом в качестве параметра при первоначальном вводе нечетного числа, она будет повторяться не более одного раза, а затем возвращаться.

(Примечание: код, который изначально был указан на момент публикации, был f (x) = f (x-1) для нечетного x.)

В новой редакции оно будет прекращено для всех неотрицательных целых чисел. Тем не менее, он не завершится для всех отрицательных целых чисел; в частности, f(-1)это нескончаемый вызов.

Можете ли вы описать, используя пример? Я не могу понять, как это закончится для отрицательных целых чисел .. prakhar londhe 6 лет назад 0
Извините, вопрос не был правильным, я изменил его .. prakhar londhe 6 лет назад 0

Похожие вопросы