МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ
Четверг, 17.01.2019, 16:53
ГлавнаяРегистрацияВход Приветствую Вас Гость | RSS

Меню сайта

Категории раздела
Линейный алгоритм [2]
Условный оператор if [3]
Оператор выбора [1]
Операторы цикла [2]
Целочисленное деление div и mod [2]
Генератор случайных чисел [1]
Практика [5]
Это интересно [2]
ЗАДАНИЕ 3 [1]

Наш опрос
Какой язык программирования Вы изучаете
Всего ответов: 954

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

Форма входа


Главная » Файлы » ВИДЫ АЛГОРИТМОВ » Это интересно

Сверхнечетное число?
[ Скачать с сервера (0.4 Kb) ] 01.01.2013, 22:03

Кому нужны сверхнечетные числа?

или поиск четности на линии, как надежный способ защиты от помех

Сверхнечетное число

задача Ярославской олимпиады http://projects.edu.yar.ru/program/12/

Назовем натуральное число сверхнечетным, если оно состоит только из нечетных цифр. Требуется для заданного значения 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.


 


Категория: Это интересно | Добавил: i_elf
Просмотров: 597 | Загрузок: 101 | Комментарии: 1 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *:
Поиск

Друзья сайта
  • Творческий учитель
  • Сайт ООАКМР
  • Школьный сайт
  • Информатика учебник
  • МОИ

  • Copyright MyCorp © 2019 Сделать бесплатный сайт с uCoz