Форум » Обработка числовых последовательностей » Задача 27-26 » Ответить

Задача 27-26

Олег Шумков: Добрый день! В задаче 26 необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел в шестнадцатеричной системе счисления оканчивалась на F и при этом была минимально возможной. В моей программе на Паскале ответы для файла B сходятся, а вот для файла А нет. Не понятно почему. Обратился к авторскому решению на Python и тоже ничего не понял. Поэтому я вставил в авторскую программу печать пары входных чисел, их разности и окончания этой разности в шестнадцатеричной системе счисления. Вот что получилось: 749 245 504 8 756 979 223 15 174 345 171 11 565 915 350 14 168 381 213 5 594 478 116 4 895 738 157 13 910 372 538 10 43 458 415 15 297 193 104 8 434 905 471 7 751 498 253 13 103 722 619 11 238 374 136 8 549 487 62 14 26 631 605 13 325 741 416 0 133 695 562 2 160 177 17 1 109 253 144 0 6245 5 [144, 17, 178, 195, 116, 133, 166, 183, 104, 121, 250, 171, 188, 157, 62, 79] 6495 0x195f Последние две строки напечатаны авторской программой, где и указан ответ. 6245+250=6495 Из распечатанных мной выше разностей видно, что числа 250 там нет. Где автор его взял? Распечатаны все входные числа и все их разности. Разность 538 даёт окончание на F, но не минимальную сумму. Похоже, что минимум даст 6245+213+116+17=6591

Ответов - 4

Поляков: Олег Шумков пишет: Из распечатанных мной выше разностей видно, что числа 250 там нет. Вы не учитываете, что оптимальное решение может быть получено заменой в нескольких строках. В начале файла ege27.doc разбирается похожая задача.

Олег Шумков: Поляков пишет: Вы не учитываете, что оптимальное решение может быть получено заменой в нескольких строках. Разве не учитываю? Мой ответ получен из суммы трёх разностей, оканчивающихся в шестнадцатеричной системе на 5, 4 и 1. 5+4+1=10, что и нужно добавить к 5 чтоб получить 15 т.е. F. 213+116+17=346 и наконец 6245+346=6591 Ответ: 6591 А вот откуда взялось число 250 вы мне можете объяснить?

Поляков: Олег Шумков пишет: А вот откуда взялось число 250 вы мне можете объяснить? 250 = 171 + 62 + 17.


Олег Шумков: Поляков пишет: 250 = 171 + 62 + 17. Вот теперь понятно! Спасибо большое! 11+14+1+5=31, так же как и 47, 63 и т.д. оканчивается на F в шестнадцатеричной системе. Это не так привычно и наглядно, как в десятичной: 9, 19, 29 и т.д.



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