2004-gre-cs-practice-book.pdf/Q67 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q67-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q67-4c9f66 == | == Вопрос: Q67-4c9f66 == | ||
| − | < | + | Для каждого неотрицательного целого числа ''n'' пусть <m>R_n</m> — максимально возможное число областей, на которые плоскость может быть разделена ''n'' прямыми линиями. |
| − | + | ||
| − | + | Например, <m>R_0 = 1</m> и <m>R_1 = 2</m> | |
| − | + | ||
| + | Тогда <m>R_n</m> имеет порядок | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>\Theta(n)</m> |
| − | ( | + | * <m>\Theta(n \log n)</m> |
| + | * Правильный ответ: <m>\Theta(n^2)</m> | ||
| + | * <m>\Theta(2^n)</m> | ||
| + | * <m>\Theta(n!)</m> | ||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|43|67}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Каждая новая прямая ''n'' пересекает предыдущие ''n-1'' прямую, порождая ''n'' новых областей. | |
| − | + | ||
| − | + | ||
| + | [[File:Q67_2024-12-16_12-22-58_image0.png|640px]] | ||
| − | + | Тут явно надо будет решить рекурентное уравнение. | |
| − | + | ||
| − | + | ||
| − | + | <m> | |
| + | R(n) = R(n-1) + n | ||
| + | </m> | ||
| + | → <m>\frac{3 n \left(n - 1\right)}{2} + 7</m> | ||
| + | |||
| + | <code-python> | ||
| + | from sympy import * | ||
| + | T = Function('T') | ||
| + | n = symbols('n', integer=True, positive=True) | ||
| + | recurrence = T(n+1) - T(n) - 3*n | ||
| + | rsolve(recurrence, T(n), {T(1):7}) | ||
| + | # print(latex(rsolve(recurrence, T(n), {T(1):7}))) | ||
| + | </code-python> | ||
{{question-ok|}} | {{question-ok|}} | ||
| + | |||
| + | {{checkme|[[Участник:StasFomin|StasFomin]] 09:26, 16 декабря 2024 (UTC)}} | ||
Версия 09:26, 16 декабря 2024
Вопрос: Q67-4c9f66
Для каждого неотрицательного целого числа n пусть — максимально возможное число областей, на которые плоскость может быть разделена n прямыми линиями.
Например, и
Тогда имеет порядок
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 67 на 43 странице книги «2004-gre-cs-practice-book.pdf»
Каждая новая прямая n пересекает предыдущие n-1 прямую, порождая n новых областей.
Тут явно надо будет решить рекурентное уравнение.
→
from sympy import * T = Function('T') n = symbols('n', integer=True, positive=True) recurrence = T(n+1) - T(n) - 3*n rsolve(recurrence, T(n), {T(1):7}) # print(latex(rsolve(recurrence, T(n), {T(1):7})))
Решено: StasFomin 09:26, 16 декабря 2024 (UTC)