Федотов Валерий Павлович (matholimp) wrote,
Федотов Валерий Павлович
matholimp

Category:

Египетские разложения единицы (рейтинговая задача для программёров)

Ещё раз я хочу предложить склонным к математике френдам занимательный сюжет по мотивам моих лекций в ИТМО. На этот раз не гуманитарный факультет, а естественно-научный.

Рассматривается уравнение
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-символьный формат строки. Если перемножить числа, запись которых выражается в килобайтах, то произведение потянет уже на мегабайты. Как сократить дробь со столь длинными числителем и знаменателем? Как бороться с ростом знаменателей при сложении таких дробей?
Subscribe

promo matholimp november 26, 17:30 55
Buy for 10 tokens
Дистанционное обучение внезапно оказалось в тренде. Поэтому пишут о нём сейчас все, кому не лень, вплоть до вездесущего Онищенко. В итоге громкое большинство минимум в 99% составляют публикации несведущих профанов. А 9 из 10 написанных педагогами статей о дистанционном обучении явно свидетельствуют…
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 10 comments