Программа "аналога" подопытного числа

[Знаменок]

Программа "аналога" подопытного числа

Ограничение по времени: 1 секунда
Ограничение по памяти: 64 Мб
Максим работает в лаборатории чисел. Ученые этой лаборатории проводят важный опыт над числами. Дано число в десятичной системе счисления. Его переводят в двоичную и записывают на листок как последовательность единиц и нулей. Затем над этой последовательностью производят циклический сдвиг - каждую цифру перемещают на одну вправо, а последнюю на первое место. С новой последовательностью проводят ту же операцию, и всё это продолжается до тех пор пока не получается исходная последовательность. Все последовательности на листке снова преобразуют в числа и переводят в десятичную систему. Все эти числа называют "аналогами" подопытного числа. Среди них находят максимальное и называют его "старшим аналогом". "старший аналог" числа может соответствовать самому числу. (например для числа 12 аналогами будут являться числа 9,3, 5, 12, максимальное из них - 12). Максим пишет программу, которая по числу определяет его старшего аналога. можете ли вы ему помочь?
ФОрмат входных данных
На вход программе подаётся натуральное число N(1<=N<=2 в 15 степени) (<= - меньше либо равно) - подопытное число
Формат выходных данных:
Выведите старший аналог числа

 

[Mr.Програмист]

Сразу видно что это програма с олимпиады, так издеваться можно только над участниками
:tehnari_ru_117: не знаю как решить :tehnari_ru_117:

 

[AlexZir]

2^15=32768
Таким образом, на вход подается положительное целое число из промежутка [1;32768].
Зная допустимый диапазон значений для целочисленных типов, можем определить переменную N типа Integer.
Для перевода из десятичной в двоичную систему счисления воспользуемся способом последовательного деления N на основание 2. Думаю, написать алгоритм для реализации этого не составит большого труда.
Для реализации сдвига можно пойти двумя путями:
1) битовый сдвиг - достаточно сложно;
2) преобразование двоичного числа в строку, обработка вырезкой символов и обратное преобразование из строки в число.
Затем вам нужно будет каждое полученное двоичное значение перевести в десятичное и записать в результирующий массив. После достижения значения, совпадающего с исходным, вам нужно будет произвести поиск максимального значения элемента в массиве и вывести его как аналог.

 

[Vladimir_S]

Мне кажется, всё гораздо проще (во всяком случае, ежели речь о Паскале). Впрочем, не просто кажется, а написал я программку, решающую эту задачку, и заняла она у меня всего-то 20 строк, включая раздел описания переменных.
Алгоритм:
Всё-таки воспользоваться командой SHR - ничего в ней особо сложного нет. Труднее организовать перенос последнего бита на первое место. Тут так: нужно определить номер старшего двоичного разряда исходного числа - я это делаю через TRUNC(Ln(N)/Ln(2)), затем запомнить число, равное двум в степени этот самый номер, и в зависимости от значения остатка от деления исходного числа на 2 прибавлять или не прибавлять запомненное число к "сдвинутому".
Как-нибудь потом выложу решение. Если не будет возражений.

 

[Vladimir_S]

Ну, поскольку возражений вроде не последовало, да к тому же и тема старая, думаю, греха не будет, если я выложу свой вариант решения - вдруг кого-то заинтересует?

Var
 Order:Byte;
 N,M,P,Upper,Max:Word;
BEGIN
 Write('N= ');
 ReadLn(N);
 Order:=TRUNC(Ln(N)/Ln(2));
 Upper:=ROUND(Exp(Order*Ln(2)));
 Max:=N;
 P:=N;
 Repeat
  M:=P SHR 1;
  If (P mod 2)=1 then M:=M+Upper;
  If M>Max then Max:=M;
  P:=M;
 Until M=N;
 WriteLn(Max);
 ReadLn;
END.

И всего-то!

 

[AlexZir]

Учитывая, что олимпиада рассчитана на учеников 10-11 классов, вряд ли они смогут понять данный алгоритм, они логарифмы в достаточном объеме не изучают, не говоря уже про экспоненту

 

[Vladimir_S]

Учитывая, что олимпиада рассчитана на учеников 10-11 классов, вряд ли они смогут понять данный алгоритм, они логарифмы в достаточном объеме не изучают, не говоря уже про экспоненту

Ну можно циклами, да мне лень. Это момент вовсе непринципиальный.
Кстати, насчет логарифмов. Как бы объяснить школьникам и студентам, что если нужно сосчитать a в степени b, то это действительно Exp(Ln(a)*b), но если а=е, то это просто Exp(b), и множить на Ln(2.71) не нужно, поскольку Ln(2.71) есть единица тождественная? Помню, с одной барышней на эту тему рубился - безнадёга, у Шрека тоже недавно попалось...

 

[AlexZir]

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

У меня был случай. Есть разные формы записи логарифма в зависимости от основания: Ln, Lg, Log. Мне пришлось потратить час, чтобы объяснить разницу между ними одинадцатиклассникам.

 

[Vladimir_S]

Ладно, вот решение без логарифмов. Нарисовал в порядке преодоления собственной лени:

Var
 N,M,P,Upper,Max:Word;
BEGIN
 Write('N= ');
 ReadLn(N);
 Upper:=1;
 Repeat
  Upper:=Upper*2;
 Until Upper>N;
 Upper:=Upper div 2;
 Max:=N;
 P:=N;
 Repeat
  M:=P SHR 1;
  If (P mod 2)=1 then M:=M+Upper;
  If M>Max then Max:=M;
  P:=M;
 Until M=N;
 WriteLn(Max);
 ReadLn;
END.

 

[Vladimir_S]

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

Прискорбно. С математикой так IMHO нельзя. Уж по крайней мере элементарные функции-то нужно не просто знать, но и понимать.

 

[Vladimir_S]

Еще один (надеюсь, заключительный) аккорд по задаче. Путем невероятного умственного напряжения мне удалось прийти к ошеломительному выводу, что сдвиг вправо на одну позицию в двоичной записи числа есть ни что иное, как целочисленное деление того же числа в десятичной записи на 2. А потому даже надобности в команде SHR и вовсе нету. Итак:

Var
 N,M,P,Upper,Max:Word;
BEGIN
 Write('N= ');
 ReadLn(N);
 Upper:=1;
 Repeat
  Upper:=Upper*2;
 Until Upper>N;
 Upper:=Upper div 2;
 Max:=N;
 P:=N;
 Repeat
  M:=P div 2;
  If (P mod 2)=1 then M:=M+Upper;
  If M>Max then Max:=M;
  P:=M;
 Until M=N;
 WriteLn(Max);
 ReadLn;
END.

Вот. Какие-то паршивые сутки - и школьная задачка по Паскалю напрочь решена. Триумф, однако...:tehnari_ru_864: