Отправлено: 16.05.18 18:34. Заголовок: Задача 20 №119

Здравствуйте! У меня минимальное трехзначное число получилось 174 (в пятиричной 1144), а не 605 (4410). Где моя ошибка?

 Отправлено: 16.05.18 21:42. Заголовок: grsf пишет: Где моя..

grsf пишет:

цитата:

Где моя ошибка?

В том, что вы не проверили работу программы. А потом нужно начать думать, почему вы ошиблись в рассуждениях.

 Отправлено: 17.05.18 18:31. Заголовок: Добрый день! Ну в лю..

Добрый день! Ну в любом случае минимальное число не может начинаться с 4410. Похоже, что в условии ошибка, и это задача поиска максимального числа при заданных условиях.

 Отправлено: 18.05.18 23:45. Заголовок: grsf пишет: Ну в люб..

grsf пишет:

цитата:

Ну в любом случае минимальное число не может начинаться с 4410. Похоже, что в условии ошибка, и это задача поиска максимального числа при заданных условиях.

Там довольно сложная ситуация с четностью. Все зависит от количества четных и нечетных цифр в пятеричной записи числа и от их расстановки.

 Отправлено: 21.05.18 11:25. Заголовок: Задание типа 20 -- №№ 115-119

Задачи 118-119, действительно, поначалу ставят в тупик.
Я попробовала построить способ, в котором формируются "обратные цепочки" прохождения цикла. Но не уверена, что он будут всегда хорошо работать, так как там есть элемент подбора.
Способ описан ниже с использованием конкретных примеров.

Интересно, есть ли более универсальный подход.. Это вопрос :)

"Обратные цепочки"

Задание 115 (ищем наименьшее число).
В цикл (while x > 0 do ...) мы входим 4 раза - два раза с нечётным числом, два раза - с чётным.
Нечётные числа при делении на 8 дают остаток 1, чётные - 4 и 6.
Строим цепочку чисел, с которыми мы входим в цикл, в обратном порядке, стараясь каждый раз подбирать минимальное число, но так, чтобы выполнялось условие задачи.
Такой цепочкой будет:
1 -> 9 -> 76 -> 614

В прямом порядке: 614 (чётное, остаток от деления на 8 = 6) -> 76 ( чётное, остаток от деления на 8 = 4 ) -> 9 (нечётное, остаток от деления на 8 = 1 ) -> 1 (нечётное, остаток от деления на 8 = 1 )

Ответ: 614

Задание 116 (ищем наибольшее число).
Так как в этом задании определяется и выводится сумма остатков от деления на 6, то при подсчёте выполненных циклов нужно учитывать, что для чётного числа остаток от деления на 6 может быть равен 0 и этот остаток не влияет на сумму. Таким образом, остатки для чётных чисел могут равняться 2, 4 и 0, для нечётных - два остатка, равные 1.
Таким образом, с учётом данных о количестве остатков цикл может выполняться 5 и более раз. Но так как поиск наибольшего числа ограничен трёхзначными числами, то цикл может выполняться не более 5 раз.
Посмотрим, что происходит с наибольшим 3-значным числом при прохождении цикла без учёта условий, которые накладываются на остатки от деления на 6.

999 -> 166 -> 27 -> 4

Мы видим, что максимальное число выполнения цикла равно 4.

Пробуем пройти обратную цепочку вхождения в цикл, на каждом шаге выбирая максимально возможное число:

4 -> 26 -> 157 ->943

Ответ: 943.

Задание 118 (наибольшее число)
В этом задании, проверив самое большое 3-значное число, мы видим, что цикл может выполняться 5 раз (без учёта условия задачи, которому должны удовлетворять остатки от деления на 5):

999 -> 199 -> 39 -> 7 -> 1

Остатки от деления на 5 для чётных чисел могут равняться 0, 1 (например, 6 mod 5 = 1), 2, 3 (например, 8 mod 5). Также, в цикл мы дважды входим с нечётным числом.

Пробуем строить обратную цепочку с учётом этих условий и с учётом того, что мы ищем наибольшее число.

1 -> 7 -> 38 -> 192 -> 960

Ответ: 960.

Задание 119 (наименьшее число)

Здесь мы видим, что предложенный подход имеет особенности.
У нас не получается построить цепочку, начиная с 1, как это было, например, в задании 115.
Проанализировав проблему, можно увидеть следующую закономерность.
Так как сумма остатков от деления на 5 равна 8, то единственная возможность - 4 + 4. Остаток, равный 0, мы не рассматриваем, чтобы не удлинять цепочку.
Таким образом, в нашей цепочке должно быть 2 нечётных числа и два чётных, оканчивающихся на 4.
Легко проверить, что для чётных чисел x >= 10 операция x div 5 даёт чётное число (для x = 10k+m, m<5, x div 5 = 2k).
Так как мы входим в цикл только два раза с чётным числом, то единственно возможный фрагмент цепочки с чётными числами:
... 24 -> 4

Имея это окончание цепочки, проходим её, как и раньше, в обратном порядке, стремясь минимизировать каждый шаг:
4 -> 24 -> 121 -> 605

Ответ: 605.

 Отправлено: 21.05.18 23:10. Заголовок: Просто другой способ

Просто другой способ решения.

Этот способ предлагался мною здесь на форуме ещё в 2016 году ссылка


1. Система счисления с четным основанием (2, 4, 6, 8, 10, ...).

Если число четное, то и последняя цифра этого числа четная. И наоборот: если последняя цифра числа четная, то и само число четное.

Задачи решаются очень просто.

Например, N115:

Сумма цифр, каждая из которых является нечетным числом, в восьмеричном представлении числа равна 2, а произведение цифр, каждая из которых является четным числом, в восьмеричном представлении числа равно 24.
Наименьшее натуральное восьмеричное число, удовлетворяющее этим условиям, очевидно, равно 1146. Десятичное значение этого числа - 614.

N116:

Сумма цифр, каждая из которых является нечетным числом, в шестиричном представлении числа равна 2,
a cумма цифр, каждая из которых является четным числом, в шестиричном представлении числа равна 6
(единичку просто так в начале прибавили к сумме и к числу она не имеет никакого отношения, поэтому ее нужно вычесть: 7-1=6).

Наибольшее натуральное шестиричное число, удовлетворяющее этим условиям, очевидно, равно 4211.
Десятичное значение этого числа - 943.


N114:

Наибольшее трёхзначное натуральное число в десятичной системе счисления 999 в восьмеричной системе равно 1747.

Сумма цифр, каждая из которых является нечетным числом, в восьмеричном представлении числа равна 2,
а произведение цифр, каждая из которых является четным числом, в восьмеричном представлении числа равно 8.

Наибольшее натуральное восьмеричное число, удовлетворяющее этим условиям, очевидно, равно 1421. Десятичное значение этого числа - 785.

N113:

Количество цифр в восьмеричном числе равно 3, а сумма цифр, каждая из которых является нечетным числом, в восьмеричном представлении числа равна 14.

Наибольшее натуральное восьмеричное число, удовлетворяющее этим условиям, очевидно, равно 776. Десятичное значение этого числа - 510.

N111:

Количество четных цифр в записи числа в системе счисления с основанием 4 равна 2, а сумма нечетных цифр равна 7.

Наименьшее натуральное число в системе счисления с основанием 4, удовлетворяющее этим условиям равно 10033. Десятичное значение этого числа - 271.

N109:

Количество четных цифр в записи числа в системе счисления с основанием 6 равна 2, а сумма нечетных цифр равна 6.

Наименьшее натуральное число в системе счисления с основанием 6, удовлетворяющее этим условиям равно 1005. Десятичное значение этого числа - 221.


2. Система счисления с нечетным основанием (3, 5, 7, 9, ...).

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

Задачи решаются, но не так просто, как в предыдущем случае.

N118:

Наибольшее трёхзначное натуральное число в десятичной системе счисления 999 в системе с основанием 5 равно 12444.

Количество нечетных сумм всех цифр числа при его "усечении" с конца при записи числа в системе счисления с основанием 5 равно 2, а сумма последних цифр, входящих в четные суммы, равна 5 (единичку просто так в начале прибавили к сумме и к числу она не имеет никакого отношения. Поэтому 6-1=5).

2 нечетные суммы в системе с основанем 5 уже нашли: 12xxx. Это 1 и 1+2=3.

Больше нечентых сумм быть не должно. Поэтому следующая цифра не может быть 4 (1+2+4=7). А вот 3 может: 123xx. Следующая цифра не должна создавать нечетную сумму цифр. 1+2+3=6, одну цифру из четной суммы цифр уже нашли. Это 3. Следующая цифра, очевидно, равна 2, т.к. создает четную сумму цифр (1+2+3+2=8), 5=3+2, и в данных условиях цифра 2 самая большая. Получили 1232x. Следующая цифра должна создавать четную сумму цифр и не изменять сумму цифр, равную 5. Это 0. Получили в системе счисления с основанием 5 число 12320.
Десятичное значение этого числа - 960.

Простым это решение не назовёшь. Нужно быть очень внимательным.

N119:

Наибольшее трёхзначное натуральное число в десятичной системе счисления 999 в системе с основанием 5 равно 12444, а наименьшее трёхзначное натуральное число (100) равно 400.

Количество нечетных сумм всех цифр числа при его "усечении" с конца при записи числа в системе счисления с основанием 5 равно 2, а сумма последних цифр, входящих в четные суммы всех цифр числа, равна 8 (единичку просто так в начале прибавили к сумме и к числу она не имеет никакого отношения. Поэтому 9-1=8).

Чтобы получить наименьшее число, нужно сделать его как можно короче. Поэтому очевидно, что две цифры должны быть равны 4 и 4 и входить в четные суммы цифр. А еще должны быть маленькие цифры 0 или 1, которые входили бы в нечетные суммы цифр.

Получается 4410.
Десятичное значение этого числа - 605.

1044 не подойдет, т.к. четных сумм цифр здесь нет совсем. 4401 тоже не подойдет, т.к. нечетных сумм всех цифр числа при его "усечении" с конца будет 1, а не 2.

3. Вывод

Метод может быть рекомендован для решения подобных задач в системах счисления с четным основанием.

 Отправлено: 22.05.18 14:02. Заголовок: polyakovss пишет: М..

polyakovss пишет:

цитата:

Метод может быть рекомендован для решения подобных задач в системах счисления с четным основанием.

Спасибо!
С чётным основанием всё ясно. Хотелось найти универсальный способ для чётных и нечётных оснований. То. что Вы предложили, интересно. Спасибо.

 Отправлено: 24.05.18 10:16. Заголовок: Вот еще один подход ..

Вот еще один подход к анализу таких задач с нечётным основание системы счисления (разобранная новая задача Р-10).

 Отправлено: 23.11.18 13:55. Заголовок: Здравствуйте, в Р-10..

Здравствуйте, в Р-10 все понятно до пункта 12. Почему не подойдут маски 101 и 111, которые также дадут одно четную и 2 нечетных числа?

 Отправлено: 23.11.18 14:17. Заголовок: itcvetkova12 пишет: ..

itcvetkova12 пишет:

цитата:

в Р-10 все понятно до пункта 12. Почему не подойдут маски 101 и 111, которые также дадут одно четную и 2 нечетных числа?

Спасибо за вопрос. Добавил в файл ege20.doc объяснение. Продублирую здесь:
12) при добавлении в конец семеричной записи числа новой нечётной цифры (1 в маске) чётность меняется, а при добавлении чётной (0 в маске) – нет
13) поэтому исходное число с маской, например, 010, в ходе работы алгоритма как раз даст два нечётных числа (с масками 010 и 01) и одно чётное (с маской 0)
14) конечное значение b = 5 (нечётное) и начальное значение равно 1, для этого к 1 нужно добавить чётную цифру (4) в тот момент, когда всё число – чётное
15) маски 101 и 111, которые также при отсечении дают два нечётных и одно чётное число, не подходят, потому что не выполняется условие 14 – когда число чётное, если последняя цифра в семеричной системе – нечётная

 Отправлено: 18.01.19 05:56. Заголовок: Предлагаемый алгорит..

Предлагаемый алгоритм дает числа в обратном порядке при переводе из СС с другим основанием в десятичную по схеме Горнера. Т.е. встает вопрос сколько четных и нечетных числ в ряду чисел при переводе по схеме Горнера и здесь порядок не важен рассмотрим число слева направо. С четным основанием проще.
Рассмотрим нечетное основание СС. Приписывая очередную четную цифру, четность образованного нового числа в последовательности не меняется. Добавление нечетной цифры меняет четность числа. В числе должны появиться две 4 (четные цифры) и лучше их брать подряд. Если 4 приписать нечетному числу, то четверка будет "потеряна" и "засчитана" в нечетность - не выгодно. Четверки должны идти после четного числа или первыми (первое число в ряду Горнера можно считать 0). Минимальная нечетная цифра - 1. Если 1 ставить на первое место, то перед 4 потребуется еще одна 1, которая изменит четность ряда и еще одна, чтобы набрать нужное количество нечетных. Получится в этом случае длинный ряд цифр числа. Выгодно начать с двух 4, затем перейти на нечетность, приписывая единицу - 441 в пятеричной СС. В этом случае ряд будет иметь два четных числа и одно нечетное. Второе нечетное число ряда получим приписывая минимальную четную цифру - 0.