Расшифровка назначения функции в C с двумя для вложенных циклов, одним вводом int и возвратом int
Ко мне подошел друг из другого колледжа с этим вызовом. Я не смог ему помочь и очень обеспокоился, так как не мог понять цель функции, которую он должен был расшифровать. Кто-нибудь видел что-нибудь подобное?
Я пробовал визуализировать данные, но не смог сделать никаких значимых выводов из графика:
(синий - это возвращаемое значение mistery, оранжевый - разница между последним и текущим возвращением. Для удобства чтения шкала логарифмическая.)
int mistery(int n){
int i, j, res=0;
for(i = n / 2; i <= n; i++){
for(j = 2; j <= n; j *= 2){
res += n / 2;
}
}
return res;
}
Это похоже на случайный код, но я действительно видел лист, где это появляется. Любой вклад приветствуется.
Спасибо
в нынешнем виде этот код просто вычисляет значение n / 2 * floor (log n) * floor (n / 2), логарифм равен основанию 2.
@YakovDan, я не думаю, что вы правильно поняли формулу (например, внешний цикл for не является ни n/2, ни floor(n/2)), но да, это достаточно близко и для меня тоже не имеет смысла.
@SergGr Я перепроверил. Это.
@SergGr, конечно, правильное значение floor (n / 2) +1.
В этом случае он просто вычисляет функцию. ничего особенного в этом нет.
Это действительно имеет смысл, поскольку петли не взаимодействуют друг с другом!
Верно. это в основном n / 2 плюс n / 2 плюс n / 2 ...., повторяется k раз. k кажется (floor (n / 2) +1) * floor (log n), но я предлагаю вам дважды проверить это.
@SergGr, На мой взгляд, в английском предложении n/2 интерпретируется в математическом смысле, а не как оператор языка программирования c. В любом случае, когда вы пишете пол (n / 2), вы получаете одно и то же числовое значение в любой интерпретации по вашему выбору - C или математике.
Ответы 1
Приращение, добавляемое к переменной результата на каждой итерации внутреннего цикла, зависит только от параметра функции п, который функция не изменяет. Таким образом, результатом является произведение приращения (n/2) на общее количество итераций внутреннего цикла (при условии, что не происходит переполнения).
Итак, сколько существует итераций цикла? Рассмотрим сначала внешний цикл. Если бы нижняя граница i была равна 0, то включающая верхняя граница n дала бы итерации n+1. Но мы пропускаем первые итерации n/2 (0 ... (n/2)-1), так что это n+1-(n/2). Все деления здесь являются делениями целое число, и с целочисленным делением для всех ((n+1)/2) + 1 или (n+3)/2 (все еще используя целочисленное деление).
Теперь рассмотрим внутренний цикл. Переменная индекса j начинается с 2 и удваивается на каждой итерации, пока не превысит значение n. Это дает количество итераций, равное нижнему пределу логарифма по основанию 2 n. Таким образом, общее количество итераций составляет
(n+3)/2 * floor(log2(n))
(предположим, что мы можем предположить точный результат, когда n является степенью двойки). Комбинированный результат, таким образом, будет
((n+3)/2) * (n/2) * floor(log2(n))
где деления по-прежнему являются целочисленными делениями и выполняются до умножения. Это объясняет, почему производная функции резко возрастает при мощности двух аргументов: количество итераций внешнего цикла увеличивается на единицу в каждой из этих точек.
У нас нет контекста, из которого можно было бы догадаться о назначении функции, и я не считаю ее хорошо известной функцией, но мы можем немного поговорить о ее свойствах. Например,
- он растет асимптотически быстрее, чем п2, и асимптотически медленнее, чем п3. По факту,
- он имеет форму, напоминающую те, которые имеют тенденцию появляться в вычислительных асимптотических границах, поэтому, возможно, это оценка или граница памяти или времени, которые потребуются для некоторых вычислений. Также,
- он строго увеличивается для п> 0. Это может быть не сразу понятно из-за задействования целочисленного деления, но обратите внимание, что п и п + 3 имеют противоположную четность, поэтому всякий раз, когда п увеличивается на единицу, ровно одно из п / 2 и ( п + 3) / 2 увеличивается на одно, а другое не изменяется (и логарифмический член не убывает).
- как уже обсуждалось, он имеет внезапные скачки при степени 2. Это можно рассматривать с точки зрения количества итераций внешнего цикла или, альтернативно, с точки зрения участия функции
floor()в форме одного уравнения. - Полиномиальная часть функции связана с уравнением для суммы целых чисел от 1 до п.
- Логарифмическая часть функции связана с количеством значащих битов в двоичном представлении п.
Вы уверены, что это правильный код? Внешний цикл не взаимодействует ни с чем внутри, поэтому его можно заменить умножением. Кроме того,
n / 2является константой вres += n/2, и ее также можно вынести за одно умножение. Эти 2 факта предполагают, что где-то есть ошибка.