Поиск количества раз, когда выполняется оператор

Мне сказали выяснить количество раз, которое оператор foo работает в следующей программе. Мы предполагаем, что n - четное число.Поиск количества раз, когда выполняется оператор

j = 1; 
while(j <= n/2) 
{ 
    i = 1; 
    while(i <= j) 
    { 
    foo; 
    i++; 
    } 
    j++; 
}

Я понял, что лучший способ пойти по этому поводу - это начать с внутреннего цикла и работать по внешнему пути. Мы знаем, что i = 1 и внутри внутреннего цикла имеем i <= j. Это означает, что этот внутренний цикл работает j раз. (Здесь я начинаю запутываться). В внешнем цикле мы видим утверждение j <= n/2, так что это означает, что этот внешний цикл работает n/2 раз, правильно? чтобы подсчитать количество раз foo работает, было бы j раз n/2, не так ли? Итак, foo работает j * (n/2) раз? Это верно?

источник

2016-02-01 GenericUser01

Ну, 'j' установлен, поэтому ваш результат должен быть функцией только 'n'. –

Работайте с ним для различных значений n (начиная с 2) и посмотрите, можете ли вы определить шаблон. Подсказка: вы когда-нибудь играли в боулинг? –

Хорошо, я пытаюсь пройти через него, начиная с 2. Когда 'n = 2', то это означает, что оператор' j <= n/2' проверяет, является ли 'j <= 1' истинным, так как' j' инициализируется значением '1'. Затем мы переходим во внутренний цикл и видим, является ли 'i <= j'' '' '' '' '' '' '' '' '' '' '' '' '' '. Итак, 'foo' запускается один раз, а затем' i' увеличивается. Теперь, 'i = 2', и мы проверяем, есть ли' i <= j', который теперь является 'false', и мы выходим из этого цикла, а' j' увеличивается. Затем вернемся к вершине, чтобы увидеть, является ли 'j <= n/2', который теперь является« ложным », и цикл завершается. Поэтому, когда программа равна 2, она запускается один раз. – GenericUser01

Вы правы, что внешний цикл работает N/2 раз (j с шагом 1 до n/2). внутренний цикл работает j раз, поэтому количество раз, которое foo запускает изменения с каждым дополнительным значением j. Если посчитать пробеги, с каждой «строкой» является внешним Lopo перспективой, конечный результат выглядит как треугольник (или кегли, если центр выравнивание):

N=2 

j 
--- 
1 . = one run 

N=4 

j 
--- 
1 . 
2 .. = three runs 

N=6 

j 
--- 
1 . 
2 .. 
3 ... = 6 runs

Следующий шаг для вас, чтобы написать в зависимости от N.

источник

2016-02-01 23:13:41

Итак, если 'n = 8', то j будет равно« 1, 2, 3 и 4 », что означает, что' foo' будет запускаться '10' раз. Для 'n = 10',' foo' будет запускаться '15' раз и т. Д. Я думаю, что вижу шаблон. 'foo' будет запускаться, но много раз он запускался для PREVIOUS плюс плюс половина' n'. Так, например, 'n = 8'. Предыдущее количество прогонов для foo было тогда, когда 'n = 6', который был' 6 работает', поэтому '6 работает' + половина из 8, которая равна' 4', которая составляет '10'. Для 'n = 10', есть' 10' предыдущих прогонов, а половина текущего 'n' равна' 5', поэтому 'foo' выполняется 15 раз. Мне просто трудно писать это как функцию только 'n'. – GenericUser01

Поэтому я вижу, что каждый раз мы добавляем 'n/2'. то есть, когда 'n = 2' мы добавляем' 1', когда 'n = 4' добавим' 2', когда 'n = 6' добавим' 3' пробежки и т. д. – GenericUser01

Я полностью в тупике. Я смотрел на это часами, не в состоянии придумать что-то с точки зрения просто 'n'. Вы можете мне это объяснить? – GenericUser01

Как мы можем видеть ямайских приращения от 1 до п/2, в то время как для каждой итерации внутреннего цикла в то время как работает ямайских раз, приращение я от 1 до 1- J.

И для каждой итерации внутреннего, а foo пробегает 1 раз.

Для первой итерации первой итерации J = 1, foo работает 1 раз ..

Для второго J = 2, foo бежит в 2 раза ... При п/2-й итерации J = п/2, foo бежит п/2 раз ..

Так foo работает в общей сложности

1 + 2 + 3 + ... + N/2 раз
Это n/2 * ((n/2 +1))/2 = n/4 * (n/2 +1) = Θ (n)

источник

2016-02-02 10:34:10 windlessStorm

Поиск количества раз, когда выполняется оператор

ответ

Смежные вопросы