Как посчитать количество итераций

Python, как подсчитать кол-во итераций в цикле for

Изучаю сортировку пузырьком для списков. Подскажите, как посчитать количество итераций в цикле for:

Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.3.11.43304

Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.

Как поcчитать количество итераций в цикле?

Мне интересно сколько итераций выполнится во внешнем и внутреннем цикле.

• Вопрос задан более трёх лет назад
• 5492 просмотра

• Facebook
• Вконтакте
• Twitter

Определяете целочисленную переменную перед внешним циклом, делаете ей ++ во внутреннем:

Если надо суммарное количество итераций обоих циклов — тогда и во внешнем тоже ++.

16. Оператор цикла for

Цикл for являются управляющей конструкцией, позволяя в зависимости от определенных условий выполнять некоторое действие множество раз, рассмотрим на решении задачи для вывода квадратов чисел от 0 до 4:

1. Инициализация счетчика, 2. условие выхода, 3. изменение переменной цикла

Loop_2

Без использования среды программирования, сколько итераций цикла в данной программе?

Решаем прибегая формуле max-min+1: 25 — -25 + 1 = 51

Loop_3

Без использования среды программирования, определите, сколько раз и как сработает следующая программа?

От 5 до 19 включительно пятнадцать чисел, следовательно цикл имеет 15 итераций и 15 раз выведет в консоль фразу «Hello World!», каждый раз на новой строке.

Loop_4

Без использования среды программирования, сопоставьте циклы, которые выполняют одинаковое количество итераций:

Loop_5

Напишите программу, которая выводит «Hello World!» 99 раз, каждый раз на новой строке.

Организуем цикл for с инициализацией переменной цикла i целого типа равной 0, с условием выхода когда переменная i будет равна 99, и каждую итерацию цикла будем инкрементировать переменную i на единицу.

Или можем инкрементировать в теле цикла, а блок изменения в заголовке цикла оставить пустым:

Или вообще не использовать целый тип для счетчика, а пофантазировать, и взять тип double:

Loop_6

Напишите программу, которая выводит только четные числа от 2 до 200.

Разберем задачу, в котором надо вывести четные числа от 1 до 200. Воспользуемся циклом for, в котором переменная цикла будет принимать все значения от 1 до 100. Каждое такое значение будем проверять на четность и выводить на консоль.

Или можно решить эту задачу при помощи изменения переменной цикла. В прошлом решении, мы увеличивали переменную цикла на 1 и тем самым перебирали все числа. Но мы можем перебирать не все числа, а каждое второе. То есть начнем с четного — двойки и будем прибавлять к переменной цикла по два.

Loop_7

Напишите программу, которая выводит все четные числа на заданном отрезке.

Обратим внимание на пример использования, где во вторых входных данных введен диапазон не от малого к большому, а большого к малому. После получения числовых границ, назначим стартовое и финишное значения путем сравнения или использования метода Max и Min. В теле цикла для вывода чисел будем использовать сравнение на остаток от деления на 2.

Или без условия, где получим начальное значение уже в четном состоянии, и переменную цикла будем увеличивать на 2.

Loop_8

По данному натуральному числу x, выведите все его делители.

Используем цикл for, для прохождения по числовому диапазону от 1 до квадратного корня введенного числа, в теле цикла проверяем на делимость без остатка введенного числа на переменную цикла. Переменную циклу инрементируем с каждой итерацией.

Loop_9

Выведите обратную последовательность нечетных чисел на отрезке от a до b, где неизвестно какая переменная больше.

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

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

Loop_10

По данному числу n найдите те числа, где сумма цифр квадрата числа больше n. Гарантируется, что n меньше 1000.

Организуем цикл for с начальным значением равным единице, с условием выхода кода переменная цикла будет больше n, в теле цикла находим квадратное значение переменной цикла, раскладываем число на разряды, которые суммируем. В условии проверяем на отношение суммы чисел квадрата числа к n.

Loop_11

Найти сумму введенных пользователем десяти чисел.

В цикле, который выполняется 10 раз, будем вводить число и суммировать в переменную(сумматор). Главное учесть, что переменную суммы нужно объявить перед циклом.

Цикл начинается с 19 и уменьшается на единицу по будет больше одного, следовательно программа находит сумму чисел от 2 до 19.

Loop_13

Без использования среды программирования, проанализируйте предложенный код и выберите какую задачу он решает.

Находит количество четных чисел от 1 до n не кратных 5.

Loop_14

Выведите количество натуральных делителей целого числа x, исключая 1 и само число.

Организуем цикл, где начальное значение переменной цикла будет два, а условие выхода — когда перемененная цикла будет больше или равно введенному пользователем числа.

Или пишем сокращенный код:

Loop_15

Пользователь ввел n чисел. Найти сумму и количество отрицательных четных чисел.

Решение не сложное, при этом необходимо заранее объявить счетчики для суммы и для количества. В теле цикла использовать составное условия для поиска необходимых значений.

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

Организуем цикл for, где нужно выполнить n итераций. В теле предлагаем пользователю ввести число, и если это число оканчивается на ноль, то увеличиваем счетчик количества искомых чисел.

Или сократим, избавимся от лишней переменной:

Loop_18

По данным n числам, определить наличие нуля среди них.

Организуем цикл for с n повторениями. В теле цикла приглашаем пользователя ввести любое число, проверяем число на ноль, где при истинной ситуации увеличиваем счетчик количества нулей на единицу. После цикла, узнаем, если счетчик больше ноля выводим, что есть ноль, иначе что ноля нет. Когда узнаем как прерывать цикл, то сможем написать более лаконичный и быстрый в исполнении код.

Loop_19

Вывести факториал числа n, где гарантируется, что n не больше 10.

Вспомним, что такое факториал: факториалом целого числа n называется произведение всех целых чисел от 1 до n. Обозначается как n! и равняется: n! = 1*2*3*n, где например факториал пяти будет равен 5!=1*2*3*4*5=120. Следовательно, организуем цикл for от 1 до n, и каждое новое значение будем умножать на значение переменной, изначально равной единице, так как это будет произведение и если один из множителей будет равен нулю, то и произведение будет равно нулю. В задание ограничено значение для n, поэтому проверим корректен ли ввод.

Или можем сократить, очистив тело цикла от инструкций:

Рассмотрим ограничение в условии задачи, где указано то, что n будет не больше 10. В нашем случае происходит умножение, где на начальном этапе множители маленькие, соответственно произведение получается не большое, но если вычислить факториал 12 то получиться большое число = 479 001 600, и если его еще умножить на 13, чтобы получить факториал 13 — произойдет переполнение для максимального значения в типе int, где int.MaxValue = 2.147.483.647. Следовательно, значение 13! будет не корректно. Для того чтобы такая ошибка не возникла, то используем для вычислений произведений тип long, но опять же корректный результат будет если значение произведения не будет превышать огромного числа 9.223.372.036.854.775.807, соответственно 20! посчитается корректно, но 21! уже будет с переполнением.

Далее, в следующей теме мы разберемся в проблеме больших чисел с помощью объекта BigInteger. А пока, будем решать задачи с малыми множителями.

Loop_20

По данному числу n!=0, найдите произведение четных чисел от 1 до n, или от n до 1, если n < 0.

Получаем число от пользователя и анализируем его. Если ввели положительное число, то стартовое значение для цикла будет равно единице, а конечное n. Если же ввели отрицательное число, то стартовое значение для цикла будет равно n, а конечное будет равно -2 — самому первому четному отрицательному значению, так как если мы будем ставить в конечное значение цикла единицу, то при прохождении от отрицательных чисел к положительным будет множитель 0, и следовательно произведение будет тоже равно нулю.

Loop_21

Написать программу для нахождения a в степени n, введенных построчно с клавиатуры. Не использовать методы класса Math.

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

Loop_22

По данным двум целым числа a и b, вычислите произведение чисел на отрезке от a до b. Не гарантируется, что a обязательно меньше b. Сделать форматированный вывод.

В условии указано, что нет гарантии того, что пользователь введет сначала меньшее число, а потом большее. Поэтому мы должны определить начальное значение и конечное значение для цикла for, а потом вычислять произведение чисел. И обязательно будем использовать форматированный вывод.

Решать задачу будет исходя требованиям в примере использования, где будет выводиться ответ, не только произведение чисел оканчивающихся на 7, но и при одном числе с семеркой на конце, и вообще если таких чисел нет. Поэтому, сначала определим, если ли вообще на введенном отрезке числа оканчивающиеся на семь. Если количество чисел больше одного, то будем опять будем просматривать числовой отрезок, и с каждым найденным числом добавлять форматированный вывод. Если же количество чисел, на первом этапе, было всего одно, то выведем, что только найдено одно число. Иначе, если на первом этапе нужных чисел не найдено, то выведем в консоль сообщение о не найденных числах.

Для корректного значения используем тип long для хранения значения произведения. На проверку программе задаем малые числа.

Алгоритмы и структуры данных

Если ты вообще не понимаешь ничего в программировании и хочешь с чего-то начать, но не знаешь с чего именно, то информация, которую ты здесь получишь, станет хорошим «entry point» в мир разработки.

Если ты учишься и мечтаешь стать хорошим программистом, то материал который будет освещен — именно для тебя.

Если ты уже хороший программист и хочешь стать еще и лучшим, то темы, которые будут раскрыты, тебе пригодятся.

Если ты уже senior-помидор, гуру программирования и познал «дзен», то бери свой кофе, садись поудобнее и проверь, не заржавел ли еще и помнишь ли азы.

Если ты готовишься к собеседованию в топ компанию — этот материал поможет тебе в подготовке.

Если ты хочешь зарабатывать больше — твоя прибыль вырастет, потому что работодатели ценят людей с такими знаниями.

Если ты хочешь решать действительно тяжелые и интересные задачи, где надежность и производительность являются ключевыми — написанное именно для тебя.

Данную статью можно использовать как для обучения, так и в качестве пособия, к которому возвращаешься, чтобы подсмотреть в случае, если забыл или сомневаешься, какую структуру данных выбрать или если знаешь точно, какую, но не помнишь, как именно ее эффективно применить.

Также, это хорошая практика языка программирования С++, потому что я буду использовать его в своих примерах. Кто думает, что это тяжелый язык, увидит — не такой страшный монстр, как его рисуют. Но сразу скажу: я не буду подробно останавливаться на тонкостях С++ (шпаргалка по C++). Нужно понимать, что различные подходы, алгоритмы и структуры данных не зависят от языка.

Поэтому ты можешь делать все то же самое, но использовать комфортный язык программирования вместо предложенного.

Для чего и что это вообще

Ты сейчас скажешь что-то типа: «В наши дни очень мощные машины, которые «вытянут» все, и я не должен заморачиваться с этими алгоритмами.»

Не все машины мощные, например: телевизоры, игровые консоли, медицинские устройства и так далее. Они очень ограничены и для них критически важно создавать производительные программы. Сверхмощными являются компьютеры или смартфоны, но вместе с мощным железом появляются такие же мощные запросы, которые нужно решать — большее количество пользователей, данных, новый функционал, который было невозможно реализовать раньше.

Нам бы не помогли самые новые и мощные машины, если продукты, которыми мы пользуемся, не оптимизировались самым эффективным способом. Вспомни, сколько раз после обновления какой-то программы она начинала «подтупливать», а через несколько дней после еще одного обновления все снова работает безупречно. Программисты нашли проблемное место и заменили медленный код на более эффективный. Поэтому даже самую мощную машину можно перегрузить неэффективным алгоритмом.

Приведу пример из личного опыта: внезапно в производительной системе перестал работать один очень важный функционал, который был реализован много лет назад (более 10) и который используется заказчиками компании по всему миру каждый день. До этого времени все работало, как швейцарские часы, и никто в эту часть кода с тех пор не заглядывал. Компания начала терять огромные деньги каждую минуту, а самое страшное — репутацию и клиентов. «Backup» не помог.

Конечно, это вызвало панику у руководства и меня попросили разобраться как можно быстрее и устранить проблему. После анализа я нашел проблемное место: реализация, которую много лет назад создал программист, была неэффективной; она работала правильно, но медленно. На маленьких объемах данных это было вообще незаметно. С годами данные увеличивались, логика отрабатывала все медленнее, но никто не замечал, потому что когда ты запускаешь что-то каждый день, то не видишь разницы. В конце концов, апогей наступил и логика уже была не в состоянии освоить тот объем данных — все остановилось.

Я переделал проблемную часть и после изменений все заработало снова, более того, пользователи отметили, что функционал стал намного «user friendly» (с точки зрения отклика на их действия) и они теперь могут быстрее работать.

Важно отметить: у пользователей были сверхсовременные и мощные машины — ноутбуки, планшеты, смартфоны. Со стороны компании так же — крутейшая база данных, сверхмощные серверы. Но все это никак не помогло, потому что логика обработки была неэффективна. Проблему можно было предотвратить с самого начала, 10+ лет назад, написав эффективный код, который бы одинаково быстро работал, как тогда на старых, так и сейчас на современных машинах.

Программист не мыслил алгоритмически и не думал о последствиях. Предположу, что даже не догадывался, что делает что-то не так, и не знал, есть ли вариант сделать существенно лучше.

Будем считать, разобрались для чего это, а теперь переходим к вопросу «Что это?».

Структура данных — это способ организации данных. В зависимости от того, какими данными мы хотим манипулировать и что с ними делать, — должны выбрать ту или иную структуру данных, которая идеально подходит для нашего случая.

Например, у меня есть несколько учебников, которые каждый день нужно носить с собой. Это мои данные. Также имею дома, скажем: рюкзак, чемодан для путешествий на колесиках и деревянный ящик. Это мои структуры данных. 100% не выберу деревянный ящик, потому что он тяжелый и большой. Буду тратить много усилий, к тому же стану значительно медленнее. Мне такой вариант не подходит. Далее, есть дорожный чемодан, он уже выглядит не так страшно, но все равно, ради нескольких учебников не буду каждый день ездить с ним. Это не удобно и, опять же, тратится лишнее время и силы, чтобы справиться с ним. И вот, наконец, рюкзак, который подходит идеально и решает мою проблему эффективно. С ним я становлюсь мобильный, не трачу лишнее время и силы, обе руки свободны.

Зная данные и условия — выбираю рюкзак. Но нужно помнить — это не значит, что я не могу достичь той же цели с ящиком или чемоданом. Конечно могу, вопрос лишь в том, чего это мне будет стоить.

Как же все изменится, если мои данные — не пара учебников, а, скажем, одежда для зимнего отдыха, и мне не нужно носить ее с собой каждый день. Только перевезти вещи от дома до отеля и обратно. Рюкзак не подходит, потому что маловат, и не все нужные вещи поместятся, а о ящике вообще молчу. Конечно, буду рад дорожному чемодану. А вот если мне нужно где-то в подвале хранить строительный инструмент, который очень редко достаю, то деревянный ящик пригодится. Это практично, и с ним ничего не случится через десятки лет, его невозможно испортить инструментами — чего не скажешь о рюкзаке или чемодане.

Какой вывод можно сделать из этого — не бывает ненужных структур данных, просто каждая из них подходит под конкретные цели.

Поэтому очень важно для программиста знать их все и, понимая условия задачи, выбрать правильную. Чтобы не быть похожим на того, кто каждый день носит учебники в чемодане или едет в путешествие с вещами в деревянном ящике =)

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

Именно поэтому крайне необходимо иметь возможность оценить эффективность алгоритма по сравнению с другими, чтобы точно определить, какой лучше. Эта оценка называется — Сложность алгоритма. Об этом и пойдет речь в следующем разделе.

Сложность алгоритма и Big O

Это очень важная тема, поэтому посвящу много времени этому разделу. Многие путаются в понимании этих понятий, но я попробую объяснить просто и на примерах. В конце раздела проверим знания и потренируемся.

Сложность алгоритмов — это оценка работы алгоритма. Используется для сравнения с другими, которые приводят к одному и тому же результату. В программировании важны два ключевых фактора сравнения — время и память.

В обоих случаях сложность зависит от входных данных: список из 10 клиентов отработает быстрее и займет меньше памяти, чем аналогичный из 100 000. Причем точное время никого не интересует: это зависит от языка программирования, типа данных, процессора и многого другого. Важна только сложность при стремлении размера входных данных к бесконечности (асимптотическая сложность) — то есть, как будет расти расход ресурсов (времени и памяти) с увеличением входных данных.

Следить за ростом и в сравнении расхода ресурсов поможет понятие «Big O» (О-нотация, как ее называют). О пришла в IT-мир из математики, но я на этом сейчас не буду останавливаться. Для нас достаточно сказать, что Big O — это описание верхнего возможного предела. Сейчас на примере объясню, что это значит.

Сначала поговорим о времени (Time Complexity, или просто TC)

Например, есть int массив, который имеет N элементов. Алгоритм печати всех значений массива будет иметь сложность алгоритма O(N), потому что нужно проверить каждый элемент массива. Количество элементов массива = количество итераций в цикле. Если 10 элементов, то 10 итераций — если 100 000, то 100 000.

В этом примере, мы точно знаем, что сложность не изменится и всегда будет O(N), потому что невозможно проверить все элементы массива сделав меньше итераций. Чего нельзя сказать о следующем примере:

Имеем тот же массив, но нам нужно печатать до тех пор, пока мы не встретим целевое значение, которое передано параметром.

goal (целевое значение) может находиться где угодно — первый элемент массива, последний, где-то посередине, или вообще не находиться в массиве (тогда напечатаются все числа).

Но мы четко можем сказать, что сложность алгоритма не превысит O(N), хотя меньше — вполне возможно.

Вот этот максимально возможный предел и есть Big O. Это очень похоже на отношение «меньше или равно» (<=). Если у меня есть 100 гривен в кошельке, то я могу потратить меньше или ровно 100, но никак не больше.

Переходим к памяти (Space Complexity, или просто SC)

Каждый хороший программист должен заботиться об объеме затраченной памяти или пространства. Пространственная сложность является параллельным понятием временной сложности. То есть, с одной стороны существует верхний предел времени — TC, а с другой верхний предел пространства — SC. Нужно думать об обеих сложностях одновременно.

Бывают задачи/проекты, где нужно пренебречь одним показателем ради другого. Собственный пример: проект по миграции очень большого количества данных. Заказчик сразу отметил, что ему не важно, сколько времени будет отрабатывать логика. Главное, чтобы все было перенесено корректно. Как руководитель и исполнитель проекта я детально проанализировал требования и условия, и принял решение пренебречь временем ради памяти, так как потенциально память могла бы стать проблемным местом. Таким образом функционал был максимально эффективно адаптирован под SC, запускался порционально в фоновом режиме ночью.

Таких примеров может быть очень много, но возьмем за правило, что всегда нужно заботиться о TC & SC одинаково, и пытаться максимально оптимизировать, если нет никаких дополнительных обстоятельств.

Посмотрим на первый пример — O(N) TC. Что мы можем сказать о SC? Тратится ли дополнительное пространство? Нет, потому что логика «бегает» по входному массиву. Поэтому можно сказать так: данный алгоритм имеет O(1) SC. О(1) используется для описания константной сложности алгоритма.

Сейчас будет то, что очень часто вижу в реальных алгоритмах:

Создается новый массив, такого же размера, как и входной, и копируются все данные. На результат этот «move» никак не повлияет.

Что теперь с Big O:

TC — O(N), как и раньше, потому что алгоритму нет разницы, каким именно массивом «ходить». Поскольку размер массива не изменился — количество итераций остается таким же.

SC — стало O(N), а было О(1) (не учитываю входной массив, потому что мы никак на это повлиять не можем). Создана копия входного массива и для нее выделен такой же объем памяти. То есть, мы сделали хуже, тратя дополнительный ресурс, и алгоритм теперь менее эффективен. Была ли какая-то необходимость в выделении дополнительного пространства? Нет.

Очень часто каждый программист пишет что-то подобное, не задумываясь, как это влияет на расход ресурсов. «Работает — вот и хорошо, значит, я молодец и все правильно сделал! Юхуууууу». Но важно тщательно планировать логику и проверять код после написания, по возможности, избавляясь от лишнего.

Далее поговорим о том, какие Big O бывают, какая между ними разница и как их сравнивать.

О(1) — Константная сложность (Constant)

Алгоритм имеет О(1) сложность — когда известно, сколько точно раз что-то произойдет, или сколько памяти будет выделено, независимо от изменения входных данных. То есть, алгоритм всегда будет использовать одинаковое количество ресурсов. Это наилучшая возможная сложность, к которой нужно стремиться.