Расшифровка назначения функции в C с двумя для вложенных циклов, одним входом int и возвращением int - PullRequest
Новая
       21

Расшифровка назначения функции в C с двумя для вложенных циклов, одним входом int и возвращением int

0 голосов
/ 07 января 2019

Друг из другого колледжа пришел ко мне с этим испытанием. Я был не в состоянии помочь ему, и стал довольно обеспокоенным, поскольку я не могу понять цель функции, которую он должен был расшифровать. Кто-нибудь видел что-нибудь подобное?

Я пытался визуализировать данные, но не мог сделать какие-либо значимые выводы из графика: (синий - возвращаемое значение 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;
}

Это похоже на случайный код, но я действительно видел рабочий лист, где он появляется. Любые входные данные приветствуются.

Спасибо

1 Ответ

0 голосов
/ 07 января 2019

Приращение, добавляемое к переменной результата на каждой итерации внутреннего цикла, зависит только от параметра функции n , который функция не изменяет. Таким образом, результатом является произведение приращения (n/2) на общее количество итераций внутреннего цикла (предположим, что оно не переполняется).

Так сколько же итераций цикла? Рассмотрим сначала внешний цикл. Если нижняя граница i равна 0, тогда включающая верхняя граница n даст n+1 итераций. Но мы пропускаем первые n/2 итераций (0 ... (n/2)-1), так что это n+1-(n/2). Все деления здесь являются целыми делениями, и с целочисленным делением это верно для всех m , что m = ( m / 2) + (( м + 1) / 2). Мы можем использовать это, чтобы переписать число итераций внешнего цикла как ((n+1)/2) + 1 или (n+3)/2 (все еще используя целочисленное деление).

Теперь рассмотрим внутренний цикл. Индексная переменная j начинается с 2 и удваивается на каждой итерации, пока не превысит n. Это дает число итераций, равное полу логарифма base-2 n. Таким образом, общее количество итераций составляет 

(n+3)/2 * floor(log2(n))

(предположим, что мы можем предположить точный результат, когда n является степенью 2). Суммарный результат равен 

((n+3)/2) * (n/2) * floor(log2(n))

, где деления по-прежнему являются целочисленными делениями и выполняются до умножения. Это объясняет, почему производная функции шипит на аргументы степени 2: количество итераций внешнего цикла увеличивается на единицу в каждой из этих точек.

У нас нет контекста, из которого можно угадать назначение функции, и я не узнаю ее как широко известную функцию, но мы можем немного поговорить о ее свойствах. Например,

  • растет асимптотически быстрее, чем n 2 , и асимптотически медленнее, чем n 3 . На самом деле
  • он имеет форму, напоминающую те, которые имеют тенденцию появляться в вычислительных асимптотических границах, поэтому, возможно, это оценка или оценка памяти или времени, которые потребуются некоторым вычислениям. Кроме того,
  • оно строго увеличивается для n > 0. Это может быть не сразу понятно из-за использования целочисленного деления, но обратите внимание, что n и n + 3 имеют противоположную четность, поэтому всякий раз, когда n увеличивается на единицу, точно один из n / 2 и ( n + 3) / 2 увеличивается на единицу, в то время как другой не изменяется (и логарифмический термин не уменьшается).
  • , как уже обсуждалось, имеет внезапные скачки в степени 2. Это можно рассматривать с точки зрения количества итераций внешнего цикла или, альтернативно, с точки зрения участия функции floor() в одиночном -выравнивание формы.
  • Полиномиальная часть функции связана с уравнением для суммы целых чисел от 1 до n .
  • Логарифмическая часть функции связана с количеством значащих бит в двоичном представлении n .
...