Вопрос с интервью

Все, что вы хотели знать о программизме, но боялись спросить.
Аватара пользователя
nemiga
Маньяк
Сообщения: 2425
Зарегистрирован: 02 сен 2006, 19:05
Откуда: Minsk -> Seoul -> Ottawa

Вопрос с интервью

Сообщение nemiga »

Дана программа (псевдокод):

Код: Выделить всё

integer N; N -- целое. Разрядность велика, но конечна

input N; юзер вводит начальное число с клавиатуры

1000; Метка -- начало цикла

if Even(N)=true then N:=N/2 else N:=3*N+1; Если N четное, то разделить его пополам, иначе утроить и прибавить 1

print N; вывод нового значения N

goto 1000; возврат в начало цикла на метку 1000
Вопрос: Каким условиям должно удовлетворять входное число N, чтобы при выполнении этой программы не произошло переполнение?

Я ответа не знаю :-(

.
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Хе хе

Сообщение aissp »

Как кодер программисту

n=-1;
Я даже больше скажу переполнится на первом же шаге
Аватара пользователя
nemiga
Маньяк
Сообщения: 2425
Зарегистрирован: 02 сен 2006, 19:05
Откуда: Minsk -> Seoul -> Ottawa

Re: Хе хе

Сообщение nemiga »

aissp писал(а):Как кодер программисту
n=-1;
А еще?

Как найти метод обнаружения таких чисел?

.
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Сообщение aissp »

А вот как программист, я еще думаю :)
Аватара пользователя
Otto
Пользователь
Сообщения: 91
Зарегистрирован: 08 июл 2006, 23:09
Откуда: Vancouver

Re: Хе хе

Сообщение Otto »

aissp писал(а):n=-1
А где здесь переполнение?
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Сообщение aissp »

unisgned char n = -1;

unsigned char q = n*3+1....
Аватара пользователя
nemiga
Маньяк
Сообщения: 2425
Зарегистрирован: 02 сен 2006, 19:05
Откуда: Minsk -> Seoul -> Ottawa

А причем тут unsigned?

Сообщение nemiga »

aissp писал(а):unisgned char n = -1;
unsigned char q = n*3+1....
А причем тут unsigned?

.
Аватара пользователя
Otto
Пользователь
Сообщения: 91
Зарегистрирован: 08 июл 2006, 23:09
Откуда: Vancouver

Re: А причем тут unsigned?

Сообщение Otto »

nemiga писал(а):А причем тут unsigned?
Вот и я о том же, в условии сказано - целое число, т.е. N может быть и отрицательным.
Аватара пользователя
nemiga
Маньяк
Сообщения: 2425
Зарегистрирован: 02 сен 2006, 19:05
Откуда: Minsk -> Seoul -> Ottawa

Re: А причем тут unsigned?

Сообщение nemiga »

Otto писал(а):
nemiga писал(а):А причем тут unsigned?
Вот и я о том же, в условии сказано - целое число, т.е. N может быть и отрицательным.
Тут мне подсказывают из другой конфы: Оказывается некоторые всерьез думают, что отрицательные числа не могут быть четными или нечетными :lol:

.
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Сообщение aissp »

OK разжуем
unsigned char q = -1;
unsigned char s = q>>2;
char p = s;
char result = s*3+1;

Вместо типа поставьте люьой другой требуемый в задаче
s=63 p=63 result != 190

если ето не переполнение то я не знаю что это такое. Или по другому, у мальчика Васи было 63 рубля (он добился етих рублей махинациями с числами скажем на бирже) после етого мальчик вася пошел в банк Хопер инвест, где ему сказали что всего за месяц утроят его капитал и даже положут ему сверху рупль. Мальчик Вася расчитывает получить 190 руплев, однако в конце месяца к нему приходят братки с паяльничком и требуют 66 руплев долга, которые он задолжал Хопру инвест. Мальчик Вася плаятит ети деньги, потом находит программиста сидорова и вставляет ему кипятильник в рот. Может ето и не прполнение, но программисту сидорову с паяльником от етого не легчее
Аватара пользователя
Otto
Пользователь
Сообщения: 91
Зарегистрирован: 08 июл 2006, 23:09
Откуда: Vancouver

Сообщение Otto »

У тебя разрядность - байт и переполнение из-за знака. Это совсем другая задачка.

Исходная задачка гораздо интереснее.
У кого еще какие мысли есть?
Аватара пользователя
nemiga
Маньяк
Сообщения: 2425
Зарегистрирован: 02 сен 2006, 19:05
Откуда: Minsk -> Seoul -> Ottawa

Сообщение nemiga »

Otto писал(а):У тебя разрядность - байт и переполнение из-за знака. Это совсем другая задачка.

Исходная задачка гораздо интереснее.
У кого еще какие мысли есть?
Все правильно, разрядность предполагается очень большая.

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

.
Аватара пользователя
aissp
Маньяк
Сообщения: 2710
Зарегистрирован: 07 ноя 2005, 09:51

Сообщение aissp »

Вообще про байт там не слова - вместо байта можно использовать

MonsterVasjaBigDigit тип. Опять же если не заметил, я написал что отвеячаю как кодер. Мне надо было добитьсе перполнения, я его добился. Если надо что то другое, то и задачу надо ставить другую. Например так, существует ли последовательность чисел, правила генерации которой описаны в посте немиги и предел которой при n стремяцемся к бесконечности тоже стремиться к ней. Но согласись ето совсем другая задача. Скажу больше, если тебя попросили написать программу а ты начал ее с проектирование операционной системы - то ето минус для программиста как мне кажется.

Ок ок отвечаю точно на условие задачи.

Вопрос: Каким условиям должно удовлетворять входное число N, чтобы при выполнении этой программы не произошло переполнение?


Ответ: число должно быть степенью двойки.
Аватара пользователя
ajkj3em
Маньяк
Сообщения: 2063
Зарегистрирован: 12 ноя 2006, 06:53

Re: Вопрос с интервью

Сообщение ajkj3em »

nemiga писал(а):

Код: Выделить всё

if Even(N)=true then N:=N/2 else N:=3*N+1;
это вопрос на общее образование. это так называемые числа-градины
(hailstone numbers). http://mathworld.wolfram.com/CollatzProblem.html

IIRC среди начальных условий есть т.н. резонаторы, но формула для
них не известна. так что ответ на оригинальный вопрос -

Аватара пользователя
Otto
Пользователь
Сообщения: 91
Зарегистрирован: 08 июл 2006, 23:09
Откуда: Vancouver

Re: Вопрос с интервью

Сообщение Otto »

ajkj2em писал(а):это вопрос на общее образование. это так называемые числа-градины
(hailstone numbers). http://mathworld.wolfram.com/CollatzProblem.html
Спасибо! Интересная инфа. В общем, пока ХЗ :D
Ответить