Рассматривается уравнение
1=1/k1+1/k2+1/k3+...+1/kn ,
где k1,k2,k3,...,kn - натуральные числа.
Последовательно для n= 1, 2, 3, ... (постарайтесь продвинуться как можно дальше!) Вы должны найти 4 следующих варианта ответа на вопрос о количестве решений этого уравнения:
1) все знаменатели различны и идут в порядке возрастания,
2) все знаменатели различны, но могут идти в любом порядке,
3) среди знаменателей могут быть одинаковые, но они идут в порядке (нестрогого) возрастания,
4) среди знаменателей могут быть одинаковые и они могут идти в любом порядке.
Ваши ответы должны быть обоснованы. При малых n Вы должны перечислить все решения и доказать отсутствие других решений. Когда решений окажется слишком много, можно ограничиться описанием алгоритма их нахождения.
Наконец, почему эта задача - рейтинговая.
Случаи n=1 и n=2 банальны. Случай n=3 сводится к доступному школьникам перебору вариантов. Это тот минимум (для троечников), при котором работа может быть зачтена. Аналогично, случаи n=4 и n=5 соответствуют оценкам "хорошо" и "отлично". Если при n=4 ручной счёт ещё возможен, то для n=5 явно напрашивается программа.
Дальнейшее продвижение я оцениваю уже как учебно-исследовательскую работу. Казалось бы, написали программу и можно заменить в ней n=5 на 6 или больше. Однако на КАЖДОМ очередном шаге вылезает новая трудность.
Сначала ошибки округления приводят к потере нужных решений и появлению посторонних. Значит, вместо десятичных (двоичных) дробей нужно перейти к обыкновенным (отдельно хранить числитель и знаменатель, а действия выполнять над ними).
Легко понять, что числитель и знаменатель должны быть представлены в целочисленном (а не вещественном) формате, из-за чего быстро "срабатывает" ограничение на их величину. Следовательно, придётся перейти к записи целых чисел в текстовом формате и программированию процедур для арифметических действий с числами в такой записи. Ясно, что очень быстро придётся отказаться и от десятичной записи как крайне "расточительной": вместо 10 вариантов для цифры лучше использовать более двухсот разных символов выбранной кодовой страницы. Или хотя бы 100, чтобы сохранить скорость обратного перевода в десятичную запись.
Да, текстовый формат - тоже не панацея. Быстро исчерпается не только 256-символьный формат строки. Если перемножить числа, запись которых выражается в килобайтах, то произведение потянет уже на мегабайты. Как сократить дробь со столь длинными числителем и знаменателем? Как бороться с ростом знаменателей при сложении таких дробей?
Journal information