рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Смешанные алгоритмы

Смешанные алгоритмы - раздел Программирование, ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ Для Решения Задач Часто Бывает Необходимо Организовать Перебор Нескольких Зна...

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

 
 

 

 


Примеры:

Пример 1. Требуется получить таблицу умножения каждого натурального числа от 1 до 9 на 2, 3, 4, …, 9 (таблица Пифагора):

 

 

 

Program Tablica ; Var x, y : byte ; Begin For x:=1 to 9 do {1-й сомножитель} Begin For y:=1 to 9 do {2-й сомножитель} Write (x*y:3);{вывод x*y } Writeln {переход на новую строку} End ; End.

Пример 2. Требуется найти количество двузначных чисел, которые делятся на сумму своих цифр.

Будем рассматривать искомые числа в виде совокупности цифр и, перебирая их различные возможные значения, формировать число х=10а+b и сумму цифр S = a + b. Пусть K – количество искомых чисел.


 

 
 

 

Program Liki; Var a, b, x, S : Byte; K : Integer; Begin K := 0; {a - старшая цифра, b - младшая цифра} For a:=1 to 9 do For b:=0 to 9 do Begin x := 10*a+b; {x - двузначное число} S :=a+b; {S - сумма цифр числа} If x mod S =0 then Begin {если число x делится на сумму цифр, считаем его} K := K+1; {и выводим на экран} Write (x, ' ') End End ; {перевод курсора на новую строку} Writeln ; {вывод общего количества чисел} Writeln ('Всего чисел: ', K) End .  

* Пример 3. Хозяйство должно разлить весь собранный березовый сок в банки емкостью 3 л, 5 л, 10 л. Требуется определить, можно ли это сделать и сколько банок каждого вида понадобится (считать, что количество банок неограниченно). Получить вариант разлива с наименьшим количеством использованных банок.

Дано: L (л) – объем собранного сока

Найти: a, b, c – количество банок соответственно емкостью 3 л, 5 л, 10 л.

Связь:

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

При: L – целое число

Метод:

1. Для получения варианта разлива в десятилитровые банки будем перебирать значения переменной z от минимально возможного (0) до максимального ([L/10]). Останется не разлитым Р=L-10z (л) сока, которые будем пытаться разлить в банки емкостью 5 л; для этого будем перебирать значения переменной y от 0 до [Р/5]. Для разлива в трехлитровые банки останется х=Р-5y (л) сока. Пусть t = х/3. Если t – целое число, одно из решений задачи получено; его можно вывести на экран компьютера. Факт получения решения будем фиксировать логической переменной Yes, которой присвоим значение True. По значению Yes при завершении работы программы будем судить, требуется ли вывести сообщение «Разлив невозможен».

2. Для получения наилучшего варианта разлива будем сравнивать общее количество использованных банок K=t+y+z со значением некоторой переменной min. Эту переменную будем использовать для хранения наименьшего значения суммы: min= K, если справедливо неравенство: K < min. Одновременно запомним в переменных a, b, c соответствующие значения t, y, z. Первоначально будем полагать значение min равным достаточно большому целому числу (MaxInt).


 

Программа Разлив Описание L,y,b,c,z,P,min,K,a,x:Целый Х3 : Вещественный Yes: Логический Конец_описания Ввод(L, 'Всего сока=') Yes:=Ложь min:=32000 Повторять_Для z От 0 До Целая_часть(L/10) P:=L-10*z Повторять_Для y От 0 До Целая_часть(P/5) x:=P-5*y x3:=x/3 Если х3=Целая_часть(x3) То Yes:=Истина Вывод(Целая_часть(x3), ', ' , y, ', ' ,z) Новая_строка K:=Целая_часть(x3)+y+z Если K<min То Min:=K a:=Целая_часть(x3) b:=y c:=z Конец_Если Конец_Если Завершить Завершить Если Yes=Ложь То Вывод ('Разлив невозможен') Иначе Вывод (a, ', ',b, ', ',c) Конец_Если Конец_Программы Program Rasliv ; Var L, y, z, P, min, K, t, a, b, c, x : Integer ; x3: Real ; Yes: Boolean ; Begin Write ('Всего сока='); Readln (L); Yes:=False; min:=MaxInt; For z:=0 To L div 10 do Begin P:=L -10*z ; For y:=0 To P div 5 do Begin x:=P-5*y; x3:=x/3 ; t:=Trunc(x3); If x3=t Then Begin Yes:=True; Writeln(t, ',',y,',',z); K:=t+y+z; If K<min Then Begin min:=K; a:=t; b:=y; c:=z End End End End; Writeln; If Yes=False Then Writeln ('невозможно') Else Writeln (a,',',b,',',c) End .    
* Пример 4. Расшифровать ребус: ГОД * 4 = ВЕК, где каждая буква соответствует некоторой цифре (разные буквы – разным цифрам). Смоделируем алгоритм умножения столбиком, начиная умножение с младшего разряда (справа налево). Так как Д ≠ К, то Д не равно нулю. Пусть Pr =Д*4, тогда К – остаток от деления Pr на 10, р1 – перенос в следующий разряд (разряд десятков). В следующем разряде О ≠ Д, О ≠ К, Pr1=О*4+р1; Е – остаток от деления Pr1 на 10, Е – цифра, не равная другим, уже использованным в алгоритме: Е ≠ О, Е ≠ Д, Е ≠ К; р2 – перенос в следующий разряд (разряд сотен), Цифра, соответствующая букве Г, может быть равна 1 или 2, так как слово ВЕК состоит из трех букв; Г ≠ О, Г ≠ Д, Г ≠ Е, Г ≠ К. В=Г*4+р2. Следует проверить справедливость выполнения условий: В < 10, В – цифра, не равная использованным ранее цифрам. В программе переменным Г, О, Д, В, Е, К соответствуют переменные g, o, d, v, e, k. Program SHIFR; Var d, o, g, v, e, k, Pr, Pr1, p1, p2 : Byte; Begin For d:=1 To 9 do Begin Pr:=d*4; k:= Pr mod 10; p1:=Pr div 10; For o:=0 To 9 do If (o<>d) and (o<>k) Then Begin Pr1:=o*4+p1; e:=pr1 mod 10; If (e<>o) and (e<>d) and (e<>k) Then Begin p2:=pr1 div 10; For g:=1 To 2 do If (g<>o) and (g<>d) and (g<>k) and (g<>e) Then Begin v:=g*4+p2; if (v<10) and (v<>o) and (v<>d) and (v<>k) and (v<>e) Then Writeln (g,o,d,'*4=',v,e,k) End End End End End.
Пример 5. Методом Монте-Карло вычислить значение числа π. Напомним, что модель и ее реализация на ИнтАле изучалась Вами в 10-м классе. Здесь приведем реализацию модели на языке программирования Паскаль. Сущность метода заключается в случайном размещении точек в квадрате с вписанной окружностью единичного радиуса. Для подсчета количества испытаний (генерируемых точек) в алгоритме используется переменная i, для которой известны начальное значение (1), конечное значение (n) и величина шага (1). Значит, в Паскале уместно использование цикла с параметром. Program PI_; Var n, i, k: LongInt; SF, a, x, y : Real; Begin Randomize; Write ('всего точек='); Readln (n); a:=2; k:=0; For i:=1 to n do Begin x:=2*Random-1; y:=2*Random-1; if x*x+y*y<=1 then k:=k+1 End; SF:=a*a*k/n; Writeln ('Число ПИ=', SF) End.
* Пример 6. («Умножить на 3 и сложить с 1»). Задано некоторое натуральное число. Подвергнем его следующему испытанию: если это число четное, разделим его на 2, если нечетное – умножим на 3 и прибавим 1. С полученным числом проделаем аналогичные действия. Например, для числа 7 получается последовательность чисел: 7, 22, 11, 34, 17, 52, 26, … Замечено, что какое бы натуральное число ни было введено, через некоторое количество шагов будет получено число 1; затем наблюдается циклическое повторение некоторых чисел. Определите число шагов, требуемых для получения первой единицы в такой последовательности чисел. Один шаг – это одно действие над числом: деление на 2, или умножение на 3 и прибавление 1. Program Experiment ; Var n, k : LongInt ; Begin Write ('n=') ; Readln (n) ; k := 0 ; While n<>1 do Begin If n mod 2 =0 then n := n div 2 else n := n*3 + 1 ; Write (', ', n) ; k := k +1 ; End ; Writeln ; Writeln ('K=', k) ; End .
В данном случае количество повторений цикла заранее не известно. Кроме того, цикл может не выполняться ни разу (если n=1), поэтому из известных нам циклических конструкций выбрана именно структура цикл While. Проведите испытание программы, присмотритесь к получаемым последовательностям при различных значениях n: возможно, Вам удастся получить формулу зависимости k от n.
       

1. Какие управляющие конструкции используются в Паскале?

2. Что такое «условный оператор» и как он применяется?

3. Какие операторы цикла Вы знаете?

4. Когда и как применяется оператор цикла for? while?

* 1. Определите, что будет выведено на экран компьютера после выполнения последовательности операторов:

Readln (k); For n:=1 to k do Begin

For m:=1 to k do if n>=m then Write ('1') else Write ('2'); Writeln End;

* 2. Определите, какое значение следует ввести при запуске программы, фрагмент которой записан ниже, чтобы при выводе было напечатано число 2:

Readln (n); k:=0; for i:=n to 5 do if i>0 then k:=k-1 else k:=k+1; Writeln (k);

* 3. Сколько раз выполняются внешний и внутренний циклы в следующих фрагментах:

1) x:=0; While x<=7 do While x=0 do x:=x+1; 2) x:=0; While x<=10 do While x<=17 do x:=x+1; 3) x:=0; While x<=17 do While x<=10 do x:=x+1;

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

2. Решите задачу В (п. 11.3) о покупке тетрадей и ручек в предположении, что их стоимости заранее не известны и вводятся с клавиатуры; можно покупать и ручки и тетради одновременно. Получите вариант покупки с наибольшим количеством приобретенных товаров.

3. Напишите программы решения следующих задач:

1) вычислить произведение всех цифр (кроме 0) заданного натурального числа;

2) проверить, является ли четной первая цифра заданного натурального числа;

3) подсчитать количество четных цифр заданного натурального числа;

* 4) подсчитать, сколько в записи заданного натурального числа содержится нулей, четных и нечетных цифр отдельно;

* 5) Расшифровать ребусы:

а) БИТ х 8 = БАЙТ б) ЗНОЙ х 3 = ЛЕТО в) ТРИ х 6 = ДЫРА

г) ВАНЯ х 4 = ИВАНЫ д) ГРАЧ х 4 = СТАЯ е) ЛЮДИ х 4 = ТОЛПА

ж) ШЛАК х 3 = БЛОК з) ТРУД х 5 = УСПЕХ и) ОГОНЬ х 8 = ПОЖАР

к) ЛУНА х 4 = НОЧИ л) ДУБ х 7 = РОЩА м) ИГРАЛ х 6 = УСТАЛ

н) ЛОБ + ТРИ = САМ о) ДО х РЕ + МИ = НОТЫ

* 6) Определить числа, являющиеся длинами сторон прямоугольного треугольника и зашифрованные в виде слов: а) КУ, КА, РЕ; б) ОН, НО, НА; в) СОН, ОНИ, НИЗ (здесь одинаковым буквам соответствуют одинаковые цифры);

7) найти наибольшее значение функции y=sinx+cos2x на отрезке [0; 1];

8) числа a, b, c называют пифагоровыми, если a2+ b2= c2. Составьте программу вывода на экран всех пифагоровых троек из числового промежутка [1; 100] (тройки 3, 4, 5 и 5, 3, 4 считаются одинаковыми; нужно вывести только одну из них);

9) требуется подсчитать количество натуральных пятизначных чисел, делящихся на 23 и на свою последнюю цифру.

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

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

Продумайте и реализуйте в программе стратегию выигрыша.

6. Напишите программу игры «Угадай число»: компьютер случайным образом загадывает число в некотором диапазоне (например, от 1 до 100) и предлагает угадать его. Задача пользователя: за возможно меньшее количество попыток угадать это число.

* 7. Напишите программу «Загадка жрецов бога РА». Известна глубина воды в некотором колодце цилиндрической формы. В него опущены две тростинки так, как изображено на рисунке. Длины тростинок известны. Требуется помочь кандидату на замещение вакантной должности жреца определить диаметр колодца.

* 8. Реализуйте на языке программирования Паскаль модель замкнутой биосистемы, известной Вам из 10 класса.

* 9. Реализуйте алгоритм экологической модели, осуществляя контроль исходных данных в соответствии с алгоритмом п. 9.3.

* 10. Напишите программу для контроля усвоения устного счета пользователем. Программа должна запросить два числа (слагаемых), вывести их на экран, предложить ввести сумму этих чисел; проверить, правильна ли эта сумма, и вывести на экран компьютера соответствующее сообщение («Правильно», «Неправильно»). Таким образом предложить для решения 10 примеров. Затем вывести количество правильных и неправильных ответов.

* 11. Напишите программу решения задачи о размещении железнодорожного вокзала (§ 11, 10 класс).

– Конец работы –

Эта тема принадлежит разделу:

ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

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

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Смешанные алгоритмы

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Алгоритмическая структура ВЕТВЛЕНИЕ
В языке Паскаль выделяются два класса операторов: простые и управляющие (структурные). Простой оператор не содержит в своей записи других операторов, а его выполнение не связано с анализом некоторы

Логические величины и выражения
Довольно часто на поставленный вопрос Вы получаете ответ «да» или «нет». Величины, которые могут принимать одно из двух значений «истина» (TRUE) или «ложь» (FALSE), называют логическими. Им соответ

Алгоритмическая структура ПОВТОРЕНИЕ
В системе программирования ИнтАл Вы познакомились с командами повторения, которые мы выделим в такие алгоритмические структуры: 20.1. ПОКА – цикл с предусловием (WHILE)

Графические построения
При построении графических изображений Вы использовали только одну из известных Вам алгоритмических структур (СЛЕДОВАНИЕ). Освоение других структур позволяет использовать их для получения сложных г

Программирование движущихся объектов
Выделим два подхода к решению задач моделирования движений средствами языка программирования: 1. «Нарисуй – сотри – и нарисуй в новом месте». Этот способ реализовать легко: нужно организов

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги