Кому нужны сверхнечетные числа?или поиск четности на линии, как надежный способ защиты от помех
Сверхнечетное число
Назовем натуральное число сверхнечетным, если оно состоит только из нечетных
цифр. Требуется для заданного значения n найти n-е по счету
сверхнечетное число.
Вход: файл input.txt, содержащий только натуральное число n.
Ограничения: 1 ≤ n ≤ 1000000.
Выход: файл output.txt, содержащий одно натуральное число – n-е
по счету сверхнечетное число.
Пример:
|
input.txt
|
output.txt
|
|
13
|
35
|
Начинаю решение!
Попробуем для начала найти все нечетные числа по
порядку
Var i, k,
n: longint;
begin
cls;
readln(n);
while
i<> n do
begin
inc(k);
if k mod 2
<> 0 then i:=i+1;
writeln('k=',
k,' ', 'n=', i);
end;
end.
Получилось, но в задаче просят найти не просто нечетные числа! Начинаю вставлять цикл, чтобы он мог разные числа проверять
есть ли в них четные числа и ничего не получается :-(
Может быть нужно идти наоборот, по n восстанавливать число? Пробую делить n на 5 с остатком несколько раз.
допустим,
n=9
делим n на 5 с остатком. Остаток равен 4. так что последняя
цифра 7
далее 5/5 = 1 - вот наша цифра десятков
итого для n=9 ответ 17
Если n=13, то делим на 5 с остатком.
остаток равен 3, так что последняя цифра это 5
теперь 10 делим на 5, получаем ровно 2. Так что следующая цифра - это 3
n=10 - делится без остатка на 5, получается остаток = 0, и
результат 2
так что число будет 31
берем число, пусть это число n
делим n с остатком на 5
если остаток равен 0, то пишем 1. если 1, то 3. если 2, то
5. если 3 - то 7, если 4 - то 9
если n>5; например, n=6, то делаем следующее.
делим n/5 с остатком. остаток равен 1 - значит, последняя цифра числа равна 1
Результат от деления тоже равен 1 - так что получаем число 11
если n=7, делим. остаток равен 2, так что последняя цифра
равна 3.
результат от деления по-прежнему 1.
фактически, нужно перевести число из 10й системы счисления в
пятеричную
при этом заменить 01234 на набор 13579.
если n>5; например, n=6, то делаем следующее.
делим n/5 с остатком. остаток равен 1 - значит, последняя цифра числа равна 1
Результат от деления тоже равен 1 - так что получаем число 11
если n=7, делим. остаток равен 2, так что последняя цифра
равна 3.
результат от деления по-прежнему 1 Идея алгоритма
итак, полное решение нашей задачки.
1. Переведем n в пятеричную систему счисления, сохранив результат в строку
2. Теперь заменяем цифры в числе справа налево. То есть если получили 12430, то
сначала заменяем 0
Делаем это таким образом:
Резервируем переменную "заём", принимаем её равной 0
а) текущая цифра=текущая цифра - заём
б) пусть заём = 0
в) Если текущая цифра равна 4, то пишем 7
Если текущая цифра равна 3, то пишем 5
Если текущая цифра равна 2, то пишем 3
Если текущая цифра равна 1, то пишем 1
Если текущая цифра равна 0, то пишем 9, и заём = 1
продолжаем, пока строка не кончится.
не надо массива
находит rem=n%5 и n=|n/5|, пока n не станет меньше или
равным 5
каждая цифра остатка будет давать тебе цифры результата,
справа налево, и самая левая цифра у тебя получится из окончательного значения
n
она не работает, у нее есть косяк, если число нацело делится
на 5
если в какой-то момент остаток равен 0, то нужно на выходе
писать 9, а от n отнимать 1
алгоритм
пусть buf - это строка, strcat(buf, "1" ) -дозапись числа 1 в строку
buf
функции такие
тогда
1) rem=n%5
n=n/5
if rem=1 то strcat(buf,"1")
if rem=2 -> strcat (buf, "3")
if rem=3 -> strcat (buf, "5")
if rem=4 -> strcat (buf, "7")
if rem=0 -> ( strcat (but, "9") и n=n-1)
2) повторять, пока n не станет равен 0
потом нужно числа из буфера в обратном порядке вывести
если должно получиться число 357, то на экране ты увидишь
753.)) вот и всё, осталось записать алгоритм на Паскаль.
Когда мы что-то делаем, то часто задаем себе вопрос, ЗАЧЕМ? Вот и сейчас, решаю задачу и думаю, кому и как пришла идея подсчета нечетных чисел, перевод в пятеричную систему счисления.
Оказывается поиск четности на линии является надежным способом защиты линии от помех.
Например, реализация протокола обмена с защитой.
Устанавливается, что кодовые сигналы могут быть только
нечетные. Если приходит четный сигнал - значит, помехи на линии. Это довольно надежный способ защиты от помех
Конечно, нужно передаваемые данные закодировать и
затем обратно раскодировать. Окончательный вариант задачи:
Var i, k, n, rem,rez, sum, ost: longint;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
readln(n);
k:=0;
begin
while n > 0 do
begin
rem:= n mod 5;
if rem=1 then k:= 1;
if rem=2 then k:= 3;
if rem=3 then k:= 5;
if rem=4 then k:= 7;
if rem=0 then k:= 9; n:= n -1;
n:= n div 5;
rez:= rez*10 +k;
end;
end;
while rez > 0 do
begin
ost:= rez mod 10;
sum:=sum*10 + ost;
rez:=rez div 10;
end;
writeln (sum);
close(input);
close(output);
end.
| 
