Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2017-09-30 | 1388 |
5.00
из
|
Заказать работу |
|
|
Проследим все этапы технологии решения задачи на компьютере на примере конкретной задачи.
1. Постановка задачи. Дано N кубиков, на которых написаны разные буквы. Сколько различных N -буквенных слов можно составить из этих кубиков (слова не обязательно должны иметь смысл)?
Искомую целочисленную величину обозначим буквой F. Тогда постановка задачи выглядит так:
Дано: N.
Найти: F.
2. Математическая формализация. Получим расчетную формулу. Сначала рассмотрим несколько конкретных примеров. Имеются два кубика с буквами «И» и «К». Ясно, что из них можно составить два слова:
ИК КИ.
Добавим к ним третью букву, «С». Теперь число разных слов будет в три раза больше предыдущего, т. е. равно 6:
ИКС КИС ИСК КСИ СКИ СИК.
Если добавить четвертую букву, например «А», то число слов возрастет в четыре раза и станет равным 24:
КИСА КИАС КСИА КСАИ КАИС КАСИ ИКСА ИКАС ИСКА
ИСАК ИАКС ИАСК СКИА СКАИ СИКА СИАК САКИ САИК
АКИС АКСИ АИКС АИСК АСКИ АСИК.
Попробуйте записать все варианты слов из пяти букв: И, К, С, А, У. Сделать это непросто.
Ясно лишь, что количество таких слов будет в пять раз больше 24, т. е. равно 120. Из шести букв можно составить 720 различных слов. С ростом числа букв число слов быстро растет. Например, для 10 букв получается 3 628 800 слов.
Подобные задачи решает раздел математики, который называется комбинаторикой.
Количество различных комбинаций из N предметов, получаемых изменением их порядка, называется числом перестановок. Это число выражается функцией от N, которая называется факториалом и записывается так:
N!
Читается: «эн факториал». Для любого натурального N значение N!вычисляется как произведение последовательности натуральных чисел от 1 до N. Например:
|
1!= 1;
2! = 1·2 = 2;
3! = 1·2·3 = 6;
4!= 1·2·3·4 = 24;
5! = 1·2·3·4·5 = 120
И т. д.
Теперь вернемся к формулировке задачи. Если N обозначает количество букв, aF — количество слов из этих букв, то расчетная формула такова:
F = N! = 1·2·...· N.
3. Построение алгоритма. Поскольку алгоритм должен быть независимым от данного значения N, то его нельзя сделать линейным. Дело в том, что для разных N надо выполнить разное число умножений. В таком случае с изменением N линейная программа должна была бы менять длину.
Алгоритм решения данной задачи будет циклическим. С циклическими алгоритмами вы уже познакомились, работая с графическим исполнителем.
Рассмотрим блок-схему на рис. 2.7 и алгоритм на АЯ.
Здесь применена знакомая вам алгоритмическая структура «цикл с предусловием». Выполняется она так: пока истинно условие цикла, повторяется выполнение тела цикла.
Тело цикла составляют две команды присваивания, заключенные между служебными словами нц и кц. Условие цикла — это отношение R<=N (R меньше или равно N).
В данном алгоритме переменная R выполняет роль множителя, значение которого меняется от 1 до N через единицу. Произведение накапливается в переменной F, начальное значение которой равно 1. Цикл заканчивается, когда R становится равным N + 1. Это значение в произведение уже не попадет.
Для проверки правильности алгоритма построим трассировочную таблицу (для случая N = 3):
Шаг | Операция | N | F | R | Условие |
ввод N | - | - | |||
F:=l | - | ||||
Д:=1 | |||||
R<=N | 1<=3, да | ||||
F:=F*R | |||||
R:=R+ 1 | |||||
R<=N | 2<=3, да | ||||
F:=F*R | |||||
R:=R+1 | |||||
R<=N | 3<=3, да | ||||
F:=F*R | |||||
R:=R+1 | |||||
R<=N | 4<=3, нет | ||||
вывод F | |||||
конец |
Из этой таблицы хорошо видно, как менялись значения переменных. Новое значение, присвоенное переменной, стирает ее старое значение (в данной таблице не повторяется запись значения переменной, если оно не изменяется; в таком виде таблица менее загромождена числами). Последнее значение F равно 6. Оно выводится в качестве результата. Очевидно, что результат верный: 3! = 6.
|
4. Составление программы. Чтобы составить программу решения нашей задачи, нужно научиться программировать циклы на Паскале. Основной циклической структурой является цикл с предусловием (цикл-пока). С помощью этой структуры можно построить любой циклический алгоритм. Оператор цикла с предусловием в Паскале имеет следующий формат:
while <выражение> do <оператор>
Служебное слово while означает «пока», do — «делать», «выполнять».
Оператор, стоящий после слова do, называется телом цикла. Тело цикла может быть простым или составным оператором, т. е. последовательностью операторов между служебными словами begin и end.
А теперь запрограммируем на Паскале алгоритм решения нашей задачи (добавив к нему организацию диалога).
Program Words;
var F, N, R: integer;
Begin
write('Введите число букв');
readln(N);
F: =1;
R:=l;
while R<=N do
Begin
F:=F*R;
R:=R+1
end;
write('Из ',N,' букв можно составить ', F,' слов')
End.
Снова бросается в глаза схожесть алгоритма на АЯ и программы на Паскале. Обратите внимание на то, что в Паскале нет специальных служебных слов для обозначения конца цикла (так же как и конца ветвления). Во всех случаях, где это необходимо, используются слова begin и end.
|
|
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!