Очень многие алгоритмы, выполнение которых поручается компьютеру, по своей природе являются циклическими. И это не случайно, потому что человек обычно поручает машине рутинную работу, где нужно много считать, и счет производится по некоторым одинаковым правилам.
Определение. Цикл – это последовательность операторов, которая может выполняться более одного раза.
Определение. Циклический алгоритм – это алгоритм, содержащий один или несколько циклов.
Возьмем для примера задачу: найти сумму некоторого количества чисел, задаваемых пользователем.
Исходными данными в этом случае являются переменная N — количество чисел и сами эти числа. Значение очередного числа обозначим переменной Х. Результатом работы алгоритма станет сумма этих чисел, которую обозначим переменной S.
Допустимые значения переменной N должны удовлетворять условию n>0, так как количество слагаемых не может быть числом отрицательным.
Как же мы должны решать эту задачу? Сначала нужно запросить, сколько чисел нужно будет сложить и считать это число в переменную N. Затем нужно так организовать операторы, чтобы программа запрашивала очередное число и каждый раз складывала его с предыдущими; и повторяла эту группу операторов N раз.
Автозаполнение ячеек в Excel
На предыдущих занятиях при изучении оператора безусловного перехода мы знакомились с решением подобных задач. Но в языке Паскаль существуют более удобные конструкции для организации циклов:
• цикл с предусловием;
• цикл с постусловием;
• цикл со счетчиком.
Познакомимся с первым из них – оператором цикла с предусловием while.
Циклы с предусловием используются тогда, когда выполнение цикла связано с некоторым логическим условием. Оператор цикла с предусловием имеет две части: условие выполнения цикла и тело цикла.
При выполнении оператора while определенная группа операторов выполняется до тех пор, пока определенное в операторе while булево условие истинно. Если условие сразу ложно, то оператор не выполнится ни разу.
Общая форма записи следующая
На русском языке это звучит примерно так:
пока выполняется это условие делай
Вполне понятно, что операторные скобки ставят, чтобы отделить от остальной программы ту группу операторов, которую нужно повторить в цикле. Если в цикле нужно выполнить только один оператор, то операторные скобки не ставят.
При использовании цикла с предусловием надо помнить следующее:
1) значение условия выполнения цикла должно быть определено до начала цикла;
2) если значение условия истинно, то выполняется тело цикла, после чего повторяется проверка условия. Если условие ложно, то происходит выход из цикла;
3) хотя бы один из операторов, входящих в тело цикла, должен влиять на значение условия выполнения цикла, иначе цикл будет повторяться бесконечное число раз.
Вернемся к нашей задаче вычисления суммы чисел. При вычислении суммы используем следующий прием: вначале, когда еще не задано ни одно слагаемое, сумму полагают равной нулю (S:=0), а затем, получая очередное слагаемое, прибавляют его к сумме (S:=S+x) (см. программу ниже).
Функция ЕСЛИ в Excel с несколькими условиями (IF) и функция из Excel 2016 ЕСЛИМН (IFS)
Очень важное значение в операторе цикла имеет так называемая переменная цикла. В нашей программе она называется i. С ее помощью мы обращаемся к пользователю за очередным числом (write (‘Введите ‘,i,’-ое число ’)) и считаем количество уже введенных чисел (i:=i+1), чтобы не запросить лишнее. Одновременно переменная цикла участвует в булевом выражении (i<=N).
Рассмотрите внимательно программу, решающую нашу задачу.
write (‘Сколько чисел для сложения? ‘);
write (‘Введите ‘,i,’-е число ’);
write (‘Сумма введенных чисел равна ‘,s:5:2);
Хотелось бы, чтобы Вы смогли представить работу этой программы. Давайте попробуем вместе.
Пусть нам требуется сложить следующие числа: 5, 7, -4, 0, 8, 20. Посчитаем, сколько их всего – шесть. Это число мы введем, когда программа задаст вопрос: Сколько чисел для сложения?
Теперь наша программа запросит ввести 1-ое число, т. к. на первом шаге переменная i равна 1. Мы введем число 5. Программа считает его в переменную х. Теперь число 5 сложим с числом 0 и результат присвоим переменной S (оператор S:=S+x). В этот момент S становится равной 5. Чтобы перейти к следующему числу, увеличим значение переменной i на 1 (оператор i:=i+1). Выполнение операторов тела цикла закончено. Теперь программа переходит опять к анализу условия вхождения в цикл (i<=N). Переменная цикла i=2, переменная N=6, поэтому значение логического условия 2<=6 равно True. Значит снова выполняется тело цикла:
write (‘Введите ‘,i,’-ое число ’);
Итак, мы сложили два числа и переходим опять к проверке условия. Ответим на вопрос: 3
write (‘Введите ‘,i,’-ое число ’);
Аналогично, мы сложим и остальные числа. Но когда же операторы цикла выполнятся последний раз и остановится работа цикла? Когда сложим последнее число. Проверим это.
write (‘Введите ‘,i,’-ое число ’);
В этом примере известно заранее количество повторений — N раз. Но чаще всего этот вид цикла используется тогда, когда количество повторений заранее не известно и зависит от выполнения какого-либо условия. Рассмотрим еще один пример.
Отвлечемся от цифр и вспомним окружающую жизнь. Сколько циклических алгоритмов можно увидеть вокруг, если внимательно посмотреть на события: чередование времен года, посещения магазинов, школы или секции, получение за контрольные оценок и др. Попробуем записать их.
Например, рассмотрите следующие циклические алгоритмы
а) Пока не сдал выпускные экзамены делай
б) Пока есть желание, возможность и здоровье делай
посещай занятия спортом
Задание. Выберите самостоятельно сказку из предложенных (или придумайте другой циклический алгоритм из жизни или произведений известных авторов) и напишите программы, с помощью которых можно в шутливой форме проверить знания первоклассников.
а) “Репка”. “Дед тянет-потянет, вытянуть не может. Позвал бабку. Бабка за дедку , дедка за репку, тянут потянут, вытянуть не могут. Позвала бабка внучку. И вытянули репку”.
б) “Курочка ряба”. “Снесла курочка яичко. Дед бил, бил, не разбил. Баба била, била, не разбила. Мышка бежала, хвостиком задела, яичко упало и разбилось”.
в) “Колобок”. “. Катится колобок по лесу. От зайца ушел, от медведя ушел, от волка ушел. Встретил лису, она его и съела”.
г) “Волк и лиса”. “. Сидит волк у проруби, хвост в воду опустил и приговаривает: “Ловись, ловись, рыбка, большая и маленькая”. Пришла за водой баба. Прогнала волка.
д) “Горшочек каши”. “. Варит горшок кашу, варит. Каша из дома на улицу потекла. Не знает мать девочки, что надо горшочку сказать. Пришла девочка, сказала: “Горшочек, не вари”. Перестал горшок кашу варить”.
Цикл с предусловием.
Продолжим изучение цикла с предусловием на примере решения следующей задачи.
Задача. Найти сумму чисел в непустой последовательности.
Рассмотрим алгоритм решения. Пусть нам дана такая последовательность чисел:
3, -4, 0, 5, 19, -20, 6, 2
Для работы нам нужно организовать обращение к каждому элементу последовательности. Нетрудно догадаться, что это будет происходить через порядковый номер каждого члена последовательности. Пронумеруем эти числа:
1 2 3 4 5 6 7 8
3, -4, 0, 5, 19, -20, 6, 2
Получилось, что всего у нас чисел восемь, на первом месте стоит число 3, на втором — число (-4), на третьем — число 0 и т.д. Тогда переменная цикла i будет пробегать числа от 1 до 8, становясь на каждом шаге больше на 1 и запрашивая каждый раз очередное число. Поэтому общая схема цикла будет выглядеть так:
write (‘Введите ‘,i,’-ое число’);
Здесь N — количество чисел последовательности (в нашем случае 8), х — член последовательности, i — порядковый номер очередного члена последовательности. Просмотрим, как будет работать этот цикл.
write (‘Введите ‘,i,’-ое число’);
Источник: studopedia.net
1. Изменить программу для нахождения суммы двух чисел.
2. Изменить программу для нахождения суммы четырех чисел.
3. Найти значение выражения: (a + (d — 12)*3) * (c — 5*k), где значения переменных a, d, c и k вводятся с клавиатуры.
4. Выведите на экран свою фамилию, имя и отчество, в следующей строке — дату рождения.
Сохранение программы
Для того, чтобы сохранить программу, необходимо:
выйти в главное меню и выбрать режим File;
нажать и из появившегося окна выбрать режим Save as. после нажатия клавиши появится окно, в котором наберите имя файла. Например, а:prim1_1.pas; здесь а: — это название диска, на котором будем сохранять файл, prim1_1 — имя файла (оно может содержать не более 8 символов), pas — расширение, сообщающее о том, что файл содержит программу, написанную на языке Паскаль.
Примечание. Существует список символов, которые нельзя употреблять в именах файлов:
* = + []|;. <>/?. А также не следует использовать в именах файлов символ пробела и буквы русского алфавита.
После того, как имя файла набрано, нажмите клавишу .
Примечание. Следует отметить, что для быстрого сохранения файла можно воспользоваться командами Save или Save all меню File.
Выход из системы программирования Паскаль
Для того, чтобы закончить работу, необходимо:
выйти в главное меню и выбрать режим File;
нажать и из появившегося окна выбрать режим Quit -, после чего нажать либо , либо комбинацию -.
После выполнения всех заданий оформить отчет и сдать его преподавателю.
Источник: studfile.net
Подбор слагаемых для нужной суммы
Не очень частый, но и не экзотический случай. На моих тренингах такой вопрос задавали не один и не два раза 🙂 Суть в том, что мы имеем конечный набор каких-то чисел, из которых надо выбрать те, что дадут в сумме заданное значение. В реальной жизни эта задача может выглядеть по-разному.
- Например, мы выгрузили из интернет-банка все платежи, которые поступили на наш счет за последний месяц. Один из клиентов разбивает сумму своего платежа на несколько отдельных счетов и платит частями. Мы знаем общую сумму оплаты и количество счетов, но не знаем их сумм. Надо подобрать те суммы в истории платежей, которые дадут в общем заданное значение.
- У нас есть несколько рулонов стали (линолеума, бумаги. ), из которых надо подобрать под заказ те, что дадут заданную длину.
- Блэкджек или в народе «очко». Надо набрать карты суммарной стоимостью максимально близкой к 21 баллу, но не превысить этот порог.
В некоторых случаях может быть известна разрешенная погрешность допуска. Она может быть как нулевой (в случае подбора счетов), так и ненулевой (в случае подбора рулонов), или ограниченной снизу или сверху (в случае блэкджека).
Давайте рассмотрим несколько способов решения такой задачи в Excel.
Способ 1. Надстройка Поиск решения (Solver)
Эта надстройка входит в стандартный набор пакета Microsoft Office вместе с Excel и предназначена, в общем случае, для решения линейных и нелинейных задач оптимизации при наличии списка ограничений. Чтобы ее подключить, необходимо:
- в Excel 2007 и новее зайти Файл — Параметры Excel — Надстройки — Перейти (File — Excel Options — Add-ins — Go)
- в Excel 2003 и старше — открыть меню Сервис — Надстройки (Tools — Add-ins)
и установить соответствующий флажок. Тогда на вкладке или в меню Данные (Data) появится нужная нам команда.
Чтобы использовать надстройку Поиск решения для нашей задачи необходимо будет слегка модернизировать наш пример, добавив к списку подбираемых сумм несколько вспомогательных ячеек и формул:
- Диапазон A1:A20 содержит наши числа, из которых мы будем выбирать нужные, чтобы «вписаться» в заданную сумму.
- Диапазон В1:B20 будет своего рода набором переключателей, т.е. будет содержать нули или единички, показывая, отбираем мы данное число в выборку или нет.
- В ячейке E2 стоит обычная автосумма всех единичек по столбцу B, подсчитывающая кол-во выбранных чисел.
- В ячейке E3 с помощью функции СУММПРОИЗВ (SUMPRODUCT) считается сумма попарных произведений ячеек из столбцов А и B (то есть A1*B1+A2*B2+A3*B3+. ). Фактически, здесь подсчитывается сумма чисел из столбца А, отобранных единичками из столбца В.
- В розовую ячейку E4 пользователь вводит желаемую сумму для подбора.
- В ячейке E5 вычисляется абсолютное по модулю значение погрешности подбора с целью ее будущей минимизации.
- Все желтых ячейках Е8:E17 хотелось бы получить список отобранных чисел, т.е. тех чисел из столбца А, напротив которых в столбце В есть единички. Для этого необходимо выделить сразу все (!) желтые ячейки и в них ввести вот такую формулу массива:
=ЕСЛИОШИБКА(ИНДЕКС($A$1:$A$20;НАИМЕНЬШИЙ(ЕСЛИ(B1:B20=1;СТРОКА(B1:B20);»»);СТРОКА()-СТРОКА($E$8)+1));»»)
=IFERROR(INDEX($A$1:$A$20;SMALL(IF(B1:B20=1;ROW(B1:B20);»»);ROW()-ROW($E$8)+1));»»)
После ввода формулы ее необходимо ввести не как обычную формулу, а как формулу массива, т.е. нажать не Enter, а Ctrl+Shift+Enter. Похожая формула используется в примере о ВПР, выдающей сразу все найденные значения (а не только первое).
Теперь перейдем на вкладку (или в меню) Данные и запустим инструмент Поиск решения (Data — Solver):
В открывшемся окне необходимо:
- Задать как целевую функцию (Target Cell) — ячейку вычисления погрешности подбора E5. Чуть ниже выбрать опцию — Минимум, т.к. мы хотим подобрать числа под заданную сумму с минимальной (а лучше даже нулевой) погрешностью.
- В качестве изменяемых ячеек переменных (Changing cells) задать диапазон столбца переключателей B1:B20.
- С помощью кнопки Добавить (Add) создать дополнительное условие на то, что ячейки диапазона B1:B20 должны быть бинарными (т.е. содержать только 0 или 1):
С помощью той же кнопки, при необходимости, создать ограничение на количество чисел в выборке. Например, если мы знаем, что сумма была разбита на 5 счетов, то:
После ввода всех параметров и ограничений запускаем процесс подбора кнопкой Найти решение (Solve). Процесс подбора занимает от нескольких секунд до нескольких минут (в тяжелых случаях) и заканчивается появлением следующего окна:
Теперь можно либо оставить найденное решение подбора (Сохранить найденное решение), либо откатиться к прежним значениям (Восстановить исходные значения).
Необходимо отметить, что для такого класса задач существует не одно, а целое множество решений, особенно, если не приравнивать жестко погрешность к нулю. Поэтому запуск Поиска решения с разными начальными данными (т.е. разными комбинациями 0 и 1 в столбце В) может приводить к разным наборам чисел в выборках в пределах заданных ограничений. Так что имеет смысл прогнать эту процедуру несколько раз, произвольно изменяя переключатели в столбце В.
Найденные комбинации можно сохранять виде сценариев (кнопка Сохранить сценарий), чтобы вернуться к нем позднее с помощью команды Данные — Анализ «что-если» — Диспетчер сценариев (Data — What-If Analysis — Scenario Manager):
И весьма удобно будет вывести все найденные решения, сохраненные в виде сценариев, в одной сравнительной таблице с помощью кнопки Отчет (Summary):
Способ 2. Макрос подбора
В этом способе всю работу делает макрос, который тупо перебирает случайные комбинации чисел, пока не наткнется на нужную сумму в пределах разрешенной погрешности. Добавлять столбец с нулями и единичками и формулы в этом случае не нужно.
Для использования макроса нажмите сочетание Alt+F11, в открывшемся окне редактора Visual Basic вставьте новый модуль через меню Insert — Module и скопируйте туда этот код:
Sub Combinator() Dim Data() As Variant, Selected() As Variant Dim goal As Double, sel_count As Integer, prec As Double Const LIMIT = 1000000 prec = Range(«D5»).Value sel_count = Range(«D2»).Value goal = Range(«D4»).Value Set OutRange = Range(«D8») Set InputRange = Range(«A1», Range(«A1»).End(xlDown)) input_count = InputRange.Cells.Count Data = InputRange.Value ReDim Selected(1 To sel_count) As Variant NewTry: For j = 1 To sel_count Start: RandomIndex = Int(Rnd * input_count + 1) RandomValue = Data(RandomIndex, 1) ‘начиная со второго элемента дополнительно проверяем, чтобы такой уже не был выбран If j > 1 Then For k = 1 To j — 1 If Selected(k) = RandomValue Then GoTo Start Next k End If Selected(j) = RandomValue Next j If Abs(WorksheetFunction.Sum(Selected) — goal) LIMIT Then MsgBox «Достигнут лимит попыток. Решение не найдено.» Exit Sub Else GoTo NewTry End If End If End Sub
Аналогично первому способу, запуская макрос несколько раз, можно получать разные наборы подходящих чисел.
P.S. Сейчас набегут энтузиасты с мехмата МГУ с криками «Тупой перебор — это неэстетично!» Да, я в курсе, что прямой перебор вариантов — это не самый оптимальный способ поиска. Да, существует много умных алгоритмов поиска решения таких задач, которые сокращают время поиска и находят нужную комбинацию заметно быстрее. Могу даже рассказать про парочку. Но мне на данном этапе существующей скорости «тупого перебора» вполне достаточно — обработка массива из 1000 ячеек идет меньше секунды. Готов подождать 🙂
Ссылки по теме
- Оптимизация бизнес-модели с помощью надстройки Поиск решения (Solver)
- Что такое макросы, куда и как вставлять код макросов на VBA
Источник: www.planetaexcel.ru