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

Знаменок · 05.10.2010, 15:28

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

Mr.Програмист · 26.01.2011, 13:03

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

не знаю как решить

AlexZir · 26.01.2011, 18:44

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

Vladimir_S · 27.01.2011, 10:59

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

Vladimir_S · 27.01.2011, 20:27

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

Код:

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 · 27.01.2011, 20:55

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

Vladimir_S · 27.01.2011, 21:16

Цитата:

Сообщение от AlexZir

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

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

AlexZir · 27.01.2011, 21:24

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

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

Vladimir_S · 27.01.2011, 21:30

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

Код:

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 · 27.01.2011, 21:33

Цитата:

Сообщение от AlexZir

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

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

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

26.01.2011, 18:44	#3 (permalink)
AlexZir support Регистрация: 19.08.2007 Адрес: Зея Сообщений: 15,797 Записей в дневнике: 71 Сказал(а) спасибо: 166 Поблагодарили 203 раз(а) в 86 сообщениях Репутация: 75760	2^15=32768 Таким образом, на вход подается положительное целое число из промежутка [1;32768]. Зная допустимый диапазон значений для целочисленных типов, можем определить переменную N типа Integer. Для перевода из десятичной в двоичную систему счисления воспользуемся способом последовательного деления N на основание 2. Думаю, написать алгоритм для реализации этого не составит большого труда. Для реализации сдвига можно пойти двумя путями: 1) битовый сдвиг - достаточно сложно; 2) преобразование двоичного числа в строку, обработка вырезкой символов и обратное преобразование из строки в число. Затем вам нужно будет каждое полученное двоичное значение перевести в десятичное и записать в результирующий массив. После достижения значения, совпадающего с исходным, вам нужно будет произвести поиск максимального значения элемента в массиве и вывести его как аналог. __________________ Убить всех человеков!

27.01.2011, 20:27	#5 (permalink)
Vladimir_S Специалист Регистрация: 27.08.2008 Адрес: Санкт-Петербург Сообщений: 27,807 Сказал(а) спасибо: 340 Поблагодарили 583 раз(а) в 208 сообщениях Репутация: 113184	Ну, поскольку возражений вроде не последовало, да к тому же и тема старая, думаю, греха не будет, если я выложу свой вариант решения - вдруг кого-то заинтересует? Код: 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. И всего-то!

27.01.2011, 20:55	#6 (permalink)
AlexZir support Регистрация: 19.08.2007 Адрес: Зея Сообщений: 15,797 Записей в дневнике: 71 Сказал(а) спасибо: 166 Поблагодарили 203 раз(а) в 86 сообщениях Репутация: 75760	Учитывая, что олимпиада рассчитана на учеников 10-11 классов, вряд ли они смогут понять данный алгоритм, они логарифмы в достаточном объеме не изучают, не говоря уже про экспоненту __________________ Убить всех человеков!

27.01.2011, 21:24	#8 (permalink)
AlexZir support Регистрация: 19.08.2007 Адрес: Зея Сообщений: 15,797 Записей в дневнике: 71 Сказал(а) спасибо: 166 Поблагодарили 203 раз(а) в 86 сообщениях Репутация: 75760	Это бесполезно, если этого нет в школьной программе - значит, они не изучали, следовательно, основы нет, а информация без фундаментальной основы - ничто, просто очередная формула, позволяющая что-то вычислить. У меня был случай. Есть разные формы записи логарифма в зависимости от основания: Ln, Lg, Log. Мне пришлось потратить час, чтобы объяснить разницу между ними одинадцатиклассникам. __________________ Убить всех человеков!

26.01.2011, 13:03	#2 (permalink)
Mr.Програмист Banned Регистрация: 25.01.2011 Сообщений: 27 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Сразу видно что это програма с олимпиады, так издеваться можно только над участниками не знаю как решить

27.01.2011, 10:59	#4 (permalink)
Vladimir_S Специалист Регистрация: 27.08.2008 Адрес: Санкт-Петербург Сообщений: 27,807 Сказал(а) спасибо: 340 Поблагодарили 583 раз(а) в 208 сообщениях Репутация: 113184	Мне кажется, всё гораздо проще (во всяком случае, ежели речь о Паскале). Впрочем, не просто кажется, а написал я программку, решающую эту задачку, и заняла она у меня всего-то 20 строк, включая раздел описания переменных. Алгоритм: Всё-таки воспользоваться командой SHR - ничего в ней особо сложного нет. Труднее организовать перенос последнего бита на первое место. Тут так: нужно определить номер старшего двоичного разряда исходного числа - я это делаю через TRUNC(Ln(N)/Ln(2)), затем запомнить число, равное двум в степени этот самый номер, и в зависимости от значения остатка от деления исходного числа на 2 прибавлять или не прибавлять запомненное число к "сдвинутому". Как-нибудь потом выложу решение. Если не будет возражений.

Ads
Яндекс Member Регистрация: 31.10.2006 Сообщений: 40200 Записей в дневнике: 0 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 55070

27.01.2011, 21:30	#9 (permalink)
Vladimir_S Специалист Регистрация: 27.08.2008 Адрес: Санкт-Петербург Сообщений: 27,807 Сказал(а) спасибо: 340 Поблагодарили 583 раз(а) в 208 сообщениях Репутация: 113184	Ладно, вот решение без логарифмов. Нарисовал в порядке преодоления собственной лени: Код: 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.