Форум » Циклы и ветвления » Задача 20 №119 » Ответить

Задача 20 №119

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

Ответов - 10

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

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

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


Тузова: Задачи 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.

polyakovss: Просто другой способ решения. Этот способ предлагался мною здесь на форуме ещё в 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. Вывод Метод может быть рекомендован для решения подобных задач в системах счисления с четным основанием.

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

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

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

Поляков: 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 – когда число чётное, если последняя цифра в семеричной системе – нечётная

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



полная версия страницы