Назовём такой метод - контролируемый перебор.
program zadacha3_8c;
for k:=1 to 4 do
for t:=2 to 9 do
if k<>t then
for o:=0 to 9 do
if (k<>o) and (t<>o) then
kto:=k*100+t*10+o;
kot:=k*100+o*10+t;
tok:=t*100+o*10+k;
if kto+kot=tok then writeln(kto,"+",kot,"=",tok);
Такой алгоритм даже при 8-10 вложенных циклах работает очень быстро.
Вопросы для повторения :
1. Может ли во вложенных циклах использоваться одна и та же переменная, например i?
2. Можно ли вкладывать друг в друга различные циклы: FOR в WHILE или REPEAT в FOR?
Задания для самостоятельной работы :
1. Старинная задача. Сколько можно купить быков, коров и телят, если бык стоит 10 рублей, корова – 5 рублей, телёнок – полтинник (0,5 рубля), при условии, что на 100 рублей надо купить 100 голов скота.
2. Задано натуральное n. Для всех чисел от 1 до n найти:
a) количество делителей; b) сумму чётных делителей.
3. Найти все решения следующих числовых ребусов:
a) БАБКА+ДЕДКА+РЕПКА=СКАЗКА (4 решения)
b) КОРОВА+ТРАВА+ДОЯРКА=МОЛОКО (2 решения)
c) АЛЁНКА+ИВАН+КОЗЛИК=СКАЗКА (1 решение)
d) ВЕТКА+ВЕТКА+СТВОЛ=ДЕРЕВО (3 решения)
e) ВОРОТА+ТРАВА=ФУТБОЛ (3 решения)
Изучаем “Циклы”
М4_Блок № 3
Тема урока :
Вложенные циклы.
Цель занятия :
1. Закрепить знания по использованию различных типов циклов;
2. Получить навыки решения алгоритмов с вложенными циклами.
СШ №1 г. Лида
Для решения задачи достаточно часто требуется использовать несколько вложенных друг в друга циклических конструкций. Такие конструкции называют вложенными циклами.
Рассмотрим несколько примеров:
Дано натуральное число S . Требуется написать программу для нахождения всех прямоугольников, площадь которых равна S и стороны выражены натуральными числами.
program zadacha3_6;
var s, a, b:longint;
writeln("Введите s"); readln(s);
for a:=1 to s do
for b:=1 to s do
if a*b=s then writeln ("стороны ",a," и ",b);
Данную задачу можно было решить, используя только один цикл. Подумайте, как это сделать.
Даны натуральные числа n , m . Получить все натуральные числа, меньшие n , сумма квадратов цифр которых равна m .
program zadacha3_7;
var n, m, i, a, sum, cif:longint;
writeln("введите n и m");readln(n, m);
for i:=1 to n do
sum:=sum+sqr(cif);
if sum=m then write(i," ");
Найти все решения заданного числового ребуса. Каждой букве соответствует некоторая цифра. Причём одинаковым буквам соответствуют одинаковые цифры, разным буквам - разные цифры.
Поскольку здесь всего три буквы, то для решения достаточно написать три вложенных цикла, и перебрать все варианты сложения трёхзначных чисел.
program zadacha3_8a;
var k, t, o, kto, kot, tok:longint;
for k:=0 to 9 do
for t:=0 to 9 do
for o:=0 to 9 do
kto:=k*100+t*10+o;
kot:=k*100+o*10+t;
tok:=t*100+o*10+k;
if (k<>t) and (k<>o) and (t<>o) and (kto+kot=tok) then
writeln(kto,"+",kot,"=",tok);
В данном алгоритме тело цикла выполнялось 10∙10∙10=1000 раз. (будем говорить сложность алгоритма =1000)
Если же для решения более сложных ребусов потребуется написать 8-10 вложенных циклов, то такой полный перебор будет работать достаточно долго.
Можно немного упростить данный алгоритм, если увидеть что 1≤k≤4, t≥2.
for k:=1 to 4 do
for t:=2 to 9 do
for o:=0 to 9 do
Теперь сложность алгоритма 4∙8∙10=320. Простое косметическое исправление дало увеличение скорости в 3 раза.
Но и данный алгоритм не является оптимальным. Посмотрите, при k =2 и t =2 программа переберёт все 10 вариантов o . В таких случаях когда k =t цикл по o вообще необходимо не выполнять.
Кто из нас не знаком с ребусами? Эти занимательные шифровки знакомы всем от мала до велика. В ребусах слова зашифрованы с помощью последовательности картинок и разных символов, в том числе букв и цифр. Слово "ребус" переводится с латинского как "при помощи вещей". Зародился ребус во Франции в XV веке, а первый печатный сборник ребусов, изданный в этой стране в 1582 году, был составлен Этьеном Табуро. За время, прошедшее с тех пор, техника составления ребусных задач обогатилась множеством разнообразных приёмов. Чтобы разгадать ребус, важно не только знать, что нарисовано, но и учесть расположение рисунков и символов друг относительно друга, и это достигается практикой. Есть некоторые негласные правила, по которым составляют ребусы, и разгадывать их легче тоже по тем же правилам, а правила такие:
Общие правила разгадывания ребусов
Слово или предложение в ребусе делится на части, которые изображают в виде рисунка или символа. Читают ребус всегда слева направо, реже сверху вниз. Пробелы и знаки препинания не читают. То, что в ребусе нарисовано на картинках, читается в именительном падеже, обычно в единственном числе, но бывают исключения. Если нарисовано несколько предметов, стрелкой указывают, какую именно часть всего изображения используют в этом ребусе. Если загадывается не одно слово, а предложение (пословица, крылатая фраза, загадка), то в нём помимо существительных есть глаголы и другие части речи. Обычно это оговаривается в задании (например: “Отгадай загадку”). Ребус должен всегда иметь решение, причём одно. Неоднозначность ответа должна оговариваться в условиях ребуса. Например: “Найди два решения этого ребуса». Количество используемых в одном ребусе приёмов и их сочетаний не ограничивается.
Как разгадывать ребусы из картинок
Называют последовательно все предметы слева направо в именительном падеже единственном числе.
Ответ: след опыт = следопыт
Ответ: вол окно = волокно
Ответ: око лица = околица
Если предмет нарисован в перевёрнутом виде, название его надо читать справа налево. Например, нарисован «кот», читать нужно «ток», нарисован «нос», читать нужно «сон». Иногда направления чтения показывают стрелкой.
Ответ: сон
Часто предмет, нарисованный в ребусе, можно назвать по-разному, например «луг» и «поле», «нога» и «лапа», «дерево» и «дуб» или «береза», «нота» и «ми», в таких случаях подбирать нужно подходящее слово, такое, чтобы ребус имел решение. Это одна из самых главных трудностей в разгадывании ребусов.
Ответ: дуб рава = дубрава
Как разгадывать ребусы с запятыми
Иногда название изображенного предмета не может быть использовано целиком и необходимо отбросить одну или несколько букв в начале или в конце слова. Тогда используется запятая. Если запятая стоит слева от рисунка, от его названия отбрасывают первую букву, если справа - последнюю. Сколько запятых стоит, столько букв отбрасывают.
Ответ: хо мяч к = хомяк
Например, нарисованы 3 запятые и «кормушка», надо прочесть только «мушка»; нарисован «парус» и 2 запятые, надо прочесть только «пар».
Ответ: у зонт р = узор
Ответ: ли са то пор ги = сапоги
Как разгадывать ребусы с буквами
Такие буквосочетания как перед, над, на, под, за, при, у, в, как правило, в ребусах рисунком не изображаются, но выявляются из соответствующего положения букв и рисунков. Буквы и буквосочетания с, к, из, от, по, и не показываются, а показываются отношения букв или предметов, или направление.
Если два предмета или две буквы, или буквы и цифры нарисованы одна в другой, то их названия читаются с прибавлением предлога «в». Например: «в-о-да», или «в-о-семь», или «не-в-а». Возможно различное прочтение, например, вместо "восемь" можно прочесть "семь-в-о", а вместо "вода" - "да-в-о". Но таких слов не бывает, поэтому такие слова не являются решением ребуса.
Ответы: в-о-да, в-о-семь, в-о-лк, в-о-ро-н, в-о-рот-а
Если один предмет или символ нарисован под другим, то расшифровываем с прибавлением «на», «над» или «под», нужно выбрать предлог по смыслу. Пример: «фо-на-ри», «под-у-шка», «над-е-жда».
Ответы: фо-на-ри, под-у-шка, над-е-жда
Если за какой-нибудь буквой или предметом находится другая буква или предмет, то читать нужно с прибавлением «за». Например: «Ка-за-нь», «за-я-ц».
Ответ: за-я-ц
Если одна буква лежит у другой или прислонена к ней, то читают с прибавлением «у» или «к». Например: «Л-у-к», «д-у-б», «о-к-о».
Ответы: лук, дуб
Если буква или слог состоит из другой буквы или слога, то читают с прибавлением «из». Например: «из-б-а», «б-из-он», «вн-из-у», «ф-из-ик».
Ответы: изба, бизон
Если по всей букве написана другая буква или слог, читают с прибавлением «по». Например: «по-р-т», «по-л-е», «по-я-с». Также «по» может использоваться, когда одна буква с ножками бежит по другой букве, цифре или предмету.
Ответ: Польша
Ответы: пояс, поле
Если нарисован предмет, а около него написана, а потом зачеркнута буква, то это значит, что букву эту надо выбросить из слова. Если же над зачеркнутой буквой стоит другая, то это значит, что нужно ею заменить зачеркнутую. Иногда в этом случае между буквами ставится знак равенства.
Ответ: лаз
Ответ: ма лина з Монт = лимон
Как разгадывать ребусы с цифрами
Если над рисунком стоят цифры, это подсказка, в каком порядке нужно читать буквы из названия предмета. Например, 4, 2, 3, 1 означает, что сначала читается четвертая буква названия, потом - вторая, за ней - третья и первая.
Ответ: бриг
Цифры могут быть перечеркнуты, значит нужно отбросить соответствующую этому порядку букву из слова.
Ответ: конек ак ЛУа бо мба = Колумб
Довольно редко в ребусах используется действие буквы - бежит, летит, лежит, в таких случаях к названию этой буквы надо добавить соответствующий глагол в третьем лице настоящего времени, например «у-бежит».
Как разгадывать ребусы с нотами
Часто в ребусах отдельные слоги, соответствующие названиям нот - «до», «ре», «ми», «фа»... изображают соответствующими нотами. Иногда используется обобщающее слово «нота».
Ноты, использующиеся при составлении ребусов
Ответы: фасоль, минус