сколько раз будет выполняться функция?

Question

У меня есть этот кусок кода

for (i = 0; i < N ; i+=3){ 
    foo(); 
    if(i % 5 ==0) foo(); 
} 

и я, чтобы решить, сколько раз будет Foo() выполняется. У меня есть этот вариант

ceil(N/3)+floor(N/5) 
ceil(N/3)+ceil(N/5) 
floor((N+2)/3)+floor((N+14)/15) 
floor(N/3)+floor(N/5) 
floor(N/3)+ceilt(N/5) 

Каков правильный путь для решения правильного результата? Внешняя петля выполняет foo() вне условия N/3 раза, но как решить, сколько раз будет выполняться функция?

Answer 1

если цикл будет

for (i = 0; i < N ; i+=3){ 
    foo(); 
} 

тогда было бы выполнить приблизительно Н/3 раза (пол ((N + 2/3)), чтобы быть точным). Если цикл будет

for (i = 0; i < N ; i+=3){ 
    if(i % 5 ==0) foo(); 
} 

затем выполнить бы приблизительно N/15 раз (этаж ((N + 14)/15), чтобы быть точным), так как

• вы входите в петле только если i является кратным 3,
• , но foo выполняется только в том случае, если i является кратным 5;
• такой комбинированный; foo выполняется только в том случае, если i является кратным 3 и кратным 5; таким образом, только если он кратен 15.

Итак, некоторыми очень простыми выводами; правильный ответ - это сумма обоих.

floor((N+2)/3)+floor((N+14)/15) 

Answer 2

Просто, чтобы сделать его легче понять, мы можем разделить этот цикл в 2:

for (i = 0; i < N ; i += 3){ 
    foo(); 
} 

for (i = 0; i < N ; i += 15){ 
    foo(); 
} 

Для любого натурального N и K цикла (я = 0; я < N; i + = k) будет работать 1 + пол ((N - 1)/k) раз.

Таким образом, общее количество трасс будет: 1 + этаж ((N-1)/3) для первого и 1 + этаж ((N-1)/15) для второго цикла, который является :

2 + floor((N-1)/3) + floor((N-1)/15) 

Answer 3

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

Как уже отмечалось ранее, второй вызов функции foo() будет выполняться только тогда, когда i% 5 равен 0. Поскольку i наступает на 3, это будет выполняться только каждую 15-ю итерацию, поскольку 15 - это наименьшее число, делится на 3 и 5. Это должно позволить исключить некоторые из формул.