2001-gre-vs-practice.pdf/Q67 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
== Вопрос: Q67-e5724f == | == Вопрос: Q67-e5724f == | ||
| Строка 42: | Строка 40: | ||
{{cstest-source|2001-gre-vs-practice.pdf|45|67}} | {{cstest-source|2001-gre-vs-practice.pdf|45|67}} | ||
| − | Заметим, что каждый вызов функции f влечет за собой (за исключением случаев, когда аргумент < 1) вызов самой функции f и функции g, которая в свою очередь также вызывает функцию f и функцию g. Получается, что каждый вызов любой из этих функций создает еще по 2 вызова функции f. Получаем следующую цепочку количества вызовов функции f на каждом шаге: 1 -> 2 -> 4 -> 8 | + | Заметим, что каждый вызов функции f влечет за собой (за исключением случаев, когда аргумент < 1) вызов самой функции f и функции g, которая в свою очередь также вызывает функцию f и функцию g. Получается, что каждый вызов любой из этих функций создает еще по 2 вызова функции f. Получаем следующую цепочку количества вызовов функции f на каждом шаге: 1 -> 2 -> 4 -> 8 … |
| − | Данная | + | Данная цепочка — ни что иное как экспонента <m>2^x</m>, следовательно верный ответ — экспонента. |
| − | + | ||
| − | + | ||
| − | {{ | + | {{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 … Данная цепочка — ни что иное как экспонента , следовательно верный ответ — экспонента.