2001-gre-vs-practice.pdf/Q67 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
== Вопрос: Q67-e5724f == | == Вопрос: Q67-e5724f == | ||
| − | + | Дан следующий фрагмент кода на C | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | <code-c> | |
| − | + | int f(int x) | |
| + | { | ||
| + | if (x < 1) | ||
| + | { | ||
| + | return 1; | ||
| + | } else | ||
| + | { | ||
| + | return f(x - 1) + g(x); | ||
| + | } | ||
| + | } | ||
| − | + | int g(int x) | |
| − | + | { | |
| + | if (x < 2) | ||
| + | { | ||
| + | return 1; | ||
| + | } else | ||
| + | { | ||
| + | return f(x - 1) + g(x / 2); | ||
| + | } | ||
| + | } | ||
| + | </code-c> | ||
| − | + | Какая функция лучше описывает скорость роста количества вызовов функции f(x)? | |
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| + | * Логарифмическая | ||
| + | * Линейная | ||
| + | * Квадратичная | ||
| + | * Кубическая | ||
| + | * Правильный ответ: экспонента | ||
=== Объяснение === | === Объяснение === | ||
| − | + | {{cstest-source|2001-gre-vs-practice.pdf|45|67}} | |
| − | {{cstest-source|2001-gre-vs-practice.pdf| | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | Заметим, что каждый вызов функции f влечет за собой (за исключением случаев, когда аргумент < 1) вызов самой функции f и функции g, которая в свою очередь также вызывает функцию f и функцию g. Получается, что каждый вызов любой из этих функций создает еще по 2 вызова функции f. Получаем следующую цепочку количества вызовов функции f на каждом шаге: 1 -> 2 -> 4 -> 8 … |
| + | Данная цепочка — ни что иное как экспонента <m>2^x</m>, следовательно верный ответ — экспонента. | ||
| − | {{question-ok|}} | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 12:23, 21 декабря 2024 (UTC)}} |
| − | [[Категория: | + | [[Категория:Понимание кода]] |
Текущая версия на 12:23, 21 декабря 2024
Вопрос: Q67-e5724f
Дан следующий фрагмент кода на C
int f(int x) { if (x < 1) { return 1; } else { return f(x - 1) + g(x); } } int g(int x) { if (x < 2) { return 1; } else { return f(x - 1) + g(x / 2); } }
Какая функция лучше описывает скорость роста количества вызовов функции f(x)?
Ответы
- Логарифмическая
- Линейная
- Квадратичная
- Кубическая
- Правильный ответ: экспонента
Объяснение
Исходники — вопрос 67 на 45 странице книги «2001-gre-vs-practice.pdf»
Заметим, что каждый вызов функции f влечет за собой (за исключением случаев, когда аргумент < 1) вызов самой функции f и функции g, которая в свою очередь также вызывает функцию f и функцию g. Получается, что каждый вызов любой из этих функций создает еще по 2 вызова функции f. Получаем следующую цепочку количества вызовов функции f на каждом шаге: 1 -> 2 -> 4 -> 8 … Данная цепочка — ни что иное как экспонента , следовательно верный ответ — экспонента.