2001-gre-vs-practice.pdf/Q67 — различия между версиями
Материал из DISCOPAL
| Строка 3: | Строка 3: | ||
== Вопрос: 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|}} | |
| − | + | ||
| − | + | ||
| − | + | {{checkme|[[Участник:Tiniakov.ad|Tiniakov.ad]] 20:17, 20 декабря 2024 (UTC)}} | |
| − | + | ||
| − | {{ | + | |
[[Категория:Надо не забыть выбрать тему]] | [[Категория:Надо не забыть выбрать тему]] | ||
Версия 20:17, 20 декабря 2024
Задача зарезервирована: Tiniakov.ad 15:01, 20 декабря 2024 (UTC)
Вопрос: 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 ...
Данная цепочка - ни что иное как экспонента , следовательно верный ответ - экспонента.
Решено: Tiniakov.ad 20:17, 20 декабря 2024 (UTC)