Брой точки, които дава задачата: 5 + 3 (елегантни решения).

Краен срок: 14-и май 2008г., 19:00 часа.

Формуляр за изпращане.

Предистория

Множеството на рационалните числа е изброимо, т.е., може да се създаде биекция между него и естествените числа. За да се докаже това е достатъчно да се създаде биекция между естествените и положителните рационални числа. Това става по следния метод:

Създавате двумерна таблица, като нареждате естествените числа (до безкрайност) веднъж по абцисата и веднъж по ординатата (вж. фигурата). След това заставате в клетка (1, 1) и я номерирате 1. После повтаряте:

1. Стъпка надолу.
2. Диагонал горе-дясно.
3. Повтаряте горното, докато не стигнете първия ред.
4. Стъпка надясно.
5. Диагонал долу-ляво.
6. Повтаряте горното, докато не стигнете до първата колонка.

При всяко влизане в нова клетка проверявате дали вече сте срещнали рационалното число ред/колона. Ако не — давате му следващия номер. Ето и как изглежда на картинка:

Диаграмата е от Wikipedia.

Да се напише…

• …безкраен итератор enumerate_rationals(), който да връща наредени двойки от цели числа, представляващи (числител, знаменател) на рационалните числа в описания по-горе ред. Т.е., първите няколко двойки трябва да са (1, 1), (2, 1), (1, 2), (1, 3), (3, 1), (4, 1), (3, 2), (2, 3), (1, 4), (1, 5), (5, 1) и т.н.
• …итератор primed(iterator). Тук iterator (краен или безкраен) връща двойки от цели числа. primed оставя само тези, които се състоят единствено от прости числа и първото е по-малко от второто. Ако изпълните primed(enumerate_rationals()), първите няколко двойки ще бъдат (2, 3), (2, 5), (3, 5) и т.н..

Подсказки

Чувствайте се свободни да ползвате решението си на пета задача, ако смятате че ще ви е от полза. Направете го като копирате класа за рационални числа в решението, а не като импортирате модул.

Може да ползвате възможностите на модула itertools.

Елегантни решения

Ако смятате, че сте се справили по красив начин, моля заявете го във форума. Ако сме съгласни, дори ще ви дадем бонус точки.

Примерен тест

Връзка: p6-sample.py

Теста може да изпълните като свалите p6-sample.py, заедно с него в една директория запазите своето решение, именувано p6.py и изпълните p6-sample.py. Крайната ви цел е да получите OK някъде из резултата.

Тестът не гарантира, че сте си решили задачата на 100%, но поне ще ви гарантира, че не сте допуснали глупава грешка, която да ви коства всички точки.