Мозговой штурм

Разгадайте кроссворд

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

Использование числовых последовательностей

Пример 19.4.

Вывести на экран первые k четных чисел.

Алгоритм решения задачи.

1. Ввод числа k. (количество чисел)

2. Для получения четного числа запишем формулу an = 2n.

3. Так как количество чисел заранее известно, то для их поучения можно воспользоваться циклом for.

4. Текущее число будем хранить в переменной а. Значение a вычисляется по формуле и зависит от значения n — счетчика цикла. Переменная n будет изменяться от 1 (номер первого четного числа) до k (номер последнего числа).

5. Полученные числа будем выводить в цикле через пробел.

Упражнения

Пример 19.5.

Вывести на экран все элементы последовательности Фибоначчи меньше x (x вводится).

Алгоритм решения задачи.

1. Ввод числа x.

2. Вывод первых двух элементов.

3. Числа Фибоначчи, начиная с третьего, получают по формуле an=an-1+an-2 (a1=a2=1). Для вывода чисел понадобятся три переменные: значение а, которое нужно вывести, и два предыдущих значения — b и c.

После вывода значения a нужно «сдвинуть» значения переменных: c := b; b := a. Начальные значения: c := 1; b := 1; a := 2.

4. Так как количество чисел заранее неизвестно, то для их вычисления нужно использовать цикл while. Условие продолжения работы цикла: a < x.

5. В цикле выводим текущее значение a, «сдвигаем» значения переменных и получаем новое значение a.

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

Пример 19.6.

Катя и Петя решили организовать благотворительную лотерею. Для этого они случайным образом генерируют номер билета. Номера билетов принадлежат промежутку [1..100]. Выигрышным билетом будет тот, номер которого кратен 5. Определить, сколько будет выигрышных билетов среди n сгенерированных Катей и Петей.

Алгоритм решения задачи.

1. Ввод числа n.

2. До начала генерации количество выигрышных билетов равно нулю (k := 0).

3. Так как количество билетов заранее известно, то для получения их номеров можно воспользоваться циклом for.

4. Текущий номер билета будем хранить в переменной а. Номера билетов будем получать по формуле a = Random(1,100) и выводить на экран. Для каждого номера будем проверять, равен ли 0 остаток от деления числа на 5. И если равен, то увеличим на 1 значение переменной k.

5. Вывод результата.

Программа:

var n, k, a:integer;

begin

write('Количество билетов n =' );

read(n); k:= 0;

for var i:= 1 to n do begin

a:= random(1,100); write(a,'');

if a mod 5 = 0 then

k := k+1;

end;

writeln;

writeln('Выиграло ',k,' билета(-ов)');

end.

Тестирование.

Запустить программу и ввести значение n=20. Результат:

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

Нахождение суммы элементов числовой последовательности

Пример 19.7.

В лаборатории выводят полезные бактерии. Экспериментально было установлено, что количество бактерий (в млн) зависит от номера дня, в который проводится эксперимент, следующим образом:

Определите, сколько бактерий вывели за m дней.

Алгоритм решения задачи.

1. Ввод числа m.

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

3. Так как количество бактерий заранее известно, для вычисления суммы можно воспользоваться циклом for.

4. Количество бактерий в текущий день будем хранить в переменной а. Значение a зависит от значения n — счетчика дней. Переменная n изменяется от 1 до m.

5. Вывод результата S.

Программа:

var m : integer;

a, S: real;

begin

write('Количество дней m = ');

read(m); S := 0;

for var n := 1 to m do

begin

a := n*n*n/(sqrt(n*n*n)-n+1);

S := S+a;

end;

writeln('Всего бактерий = ',S,' млн');

end.

Тестирование.

Запустить программу и ввести значение m = 3. Результат:

Запустить программу и ввести значение m = 30. Результат:

Возведение числа в степень

Пример 19.8.

Возвести вещественное число a в целую степень n.

Алгоритм решения задачи.

1. Ввод чисел a, n.

2. Для возведения числа в целую неотрицательную степень нужно последовательно умножать на основание степени то значение, которое получили на предыдущем шаге. Это вытекает из равенства:

3. Если степень отрицательная, то результат можно получить из равенства:

Количество повторений цикла m можно определить как m = |n|.

4. Для вычисления произведения можно воспользоваться циклом for. Начальное значение степени равно 1.

5. В конце проверим, является ли значение n положительным или отрицательным. Если оно отрицательно, то нужно изменить значение переменной S.

6. Вывод результата S.

Программа:

var n, m: integer;

a, S: real;

begin

write('Основание a = '); read(a);

write('Показатель n = '); read(n);

S := 1; m := abs(n);

for var i:= 1 to m do

S := S*a;

if n<0 then S:= 1/S;

writeln('Степень = ',S);

end.

Тестирование программы.

Запустить программу и ввести значения a=5, n=3. Результат:

Запустить программу и ввести значения a=3, n=0. Результат:

Запустить программу и ввести значения a=5, n=–2. Результат:

Построение таблицы значений функции

Пример 19.9.

Вывести на экран таблицу значений функции

Количество значений вводится. Начальное значение x = –3, значения аргумента выводятся с шагом h = 0,5.

Алгоритм решения задачи.

1. Ввод числа k.

2. Для получения таблицы нужно в цикле вычислять и выводить значение аргумента и соответствующее ему значение функции:

начальное значение аргумента x = –3. Для получения очередного значения аргумента нужно к текущему значению прибавить шаг h;
значение функции вычисляется по формуле

полученные значения выводятся на экран. Для того чтобы значения выводились строго одно под другим, нужно использовать форматный вывод. Для этого задать количество позиций для вывода значения и определить количество цифр после запятой. Запись x:7:2 означает, что для вывода переменной используется 7 позиций, после запятой выводятся 2 цифры.

3. Поскольку количество точек известно, воспользуемся циклом for.

Программа:

var k:integer;

x,y,h: real;

begin

writeln('Количество значений');

readln(k); x := -3; h := 0.5;

writeln('------------');

writeln('| x | y |');

writeln('------------');

for var n := 1 to k do begin

y := (x+2)/(x*x+3);

writeln('|',x:7:2,'|',y:10:3,'|');

x := x+h;

end;

writeln('------------');

end.

Тестирование программы.

Запустить программу и ввести значение k = 5. Результат:

Результат при k = 4:

Выделение цифр из числа

Пример 19.10.

Дано натуральное число n. Вывести цифры числа по одной в строке (начиная с разряда единиц). Определить, сколько цифр в числе.

Алгоритм решения задачи.

Ввод исходных данных — число n.
Определение начального значения счетчика для количества цифр (k := 0).
Количество цифр числа равно количеству десятичных разрядов в числе. Для нахождения каждой цифры числа нужно:
- разделить число на 10;
- найти целую часть от деления и остаток (остаток и будет очередной цифрой) и увеличить счетчик количества цифр;
- вывести полученную цифру;
- поскольку количество цифр в числе заранее неизвестно, будем использовать цикл while. Пока целая часть от деления больше 0, в числе еще есть цифры и нужно перейти к выполнению пункта а), иначе все цифры найдены.
Вывод значения переменной k.

Программа:

var k,n,z: integer;

begin

write('Введите n = ');

read(n);

k := 0;

while n * 0 do begin

//Текущая цифра

z := n mod 10;

writeln(z);

//Уменьшение числа в 10 раз

n := n div 10;

//Подсчет кол-ва цифр

k := k + 1;

end;

writeln('в числе ', k, 'цифр(-а/-ы))');

end.

Тестирование.

Запустить программу и ввести значение n = 13579. Результат:

Запустить программу и ввести значение n = 1. Результат:

Наибольший общий делитель двух чисел

Алгоритм Евклида

Наибольшим общим делителем (НОД) для двух целых чисел называют наибольший из их общих делителей. Пример: для чисел 42 и 24 наибольший общий делитель равен 6.

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

Рассмотрим другой алгоритм, который называется алгоритм Евклида.

Из большего числа вычитаем меньшее.
Если получается 0, то числа равны друг другу и это значение является НОД.
Если результат вычитания не равен 0, то большее число заменяем на разность большего и меньшего.
Переходим к пункту 1.

Пример 19.12

Ира и Игорь коллекционируют значки. У Иры в коллекции a значков, а у Игоря — b. Поскольку значков много, ребята решили поделиться своими значками с друзьями. Какое наибольшее количество общих друзей может быть у Иры и Игоря, если каждый из них хочет разделить все свои значки между друзьями без остатка? Например, если a = 42 и b = 24, то значки можно разделить, если у Иры и Игоря 1, 2, 3 или 6 общих друзей. Наибольшее количество — 6.

Алгоритм решения задачи.

Ввод чисел a, b.
Поскольку значки нужно делить без остатка, то ответом на задачу может быть только общий делитель чисел a и b. Среди всех делителей нужно найти наибольший.
Для решения задачи напишем программу вычисления НОД(a, b) по алгоритму Евклида. Пока числа a и b не равны, выполняем следующее:
1. cравниваем два числа;
2. если a>b, заменяем a на разность a–b, иначе заменяем b на разность b–a.
Вывод результата. Вывести можно как значение a, так и b (поскольку они равны).

Программа:

var a,b:integer;

begin

write('Значки у Иры a = ');

read(a);

write('Значки у Игоря b = ');

read(b);

while a<>b do

if a>b then a := a - b

else b := b - a;

writeln('Всего друзей = ',a);

end.

Тестирование.

Запустить программу и ввести значения: а = 42, b = 24. Результат:

Пример 19.13*.

Написать программу вычисления НОД( x, y, z).

Алгоритм решения задачи.

Ввод чисел x, y, z.
Используем то, что НОД (x, y, z)= НОД (НОД (x, y), z). То есть сначала вычислим d = НОД (x, y), а затем f = НОД (d, z).
Для вычисления НОД двух чисел составим функцию NOD (a, b). Команды функции NOD рассмотрены в примере 19.12.
Вывод результата.

Программа:

var x,y,z,d,f:integer;

function NOD(a,b:integer):integer;

begin

while a<>b do

if a>b then a := a-b

else b := b-a;

NOD := a;

end;

begin

write('Введите x = '); read(x);

write('Введите y = '); read(y);

write('Введите z = '); read(z);

d := NOD(x,y);

f := NOD(d,z);

writeln('НОД = ',f);

end.

Тестирование.

Запустить программу и ввести значения: x = 26, y = 143, z = 65. Результат:

Запустить программу и ввести значения: x = 354, y = 847, z = 125. Результат:

Данный результат означает, что числа 354, 847 и 125 взаимно простые.

function NOD

Основная программа

Упражнения

Выполните задания для примера 19.4.

Вывести на экран первые k четных чисел.

Восстановите правильную последовательность строк кода программы. Проверьте работу программы запустив ниже представленный тест. Расставьте ниже записанные комментарии к программе, разместив их в соответствующие строки кода. 2+2 б

Код программы для исправления

begin

var k, a: integer;

a:= 2*n;

end.

end;

for var n := 1 to k do

write(a, ' ');

write('Количество k = '); read(k);

Запустить программу и ввести значение k=100. Результат:

Комментарии

// вывод полученного числа

// конец программы

// вычисление очередного числа

// конец цикла

// ввод количества чисел

// начало цикла с параметром

// описание переменных

2. Внесите в программу изменения так, чтобы числа выводились в обратном порядке — от большего к 2. +1б

3. Какие изменения нужно внести в программу, чтобы вывести все четные числа меньше введенного числа x? (Ответ запишите в виде комментария к конце кода программы) +2б

4. Внесите изменения в программу так, чтобы выводились числа, кратные 5. +1б

5. Внесите изменения в программу так, чтобы выводились числа, кратные введенному числу x. +2б

6. Измените программу так, чтобы можно было вывести все числа последовательности, заданной формулой 10 б

Упражнения

2. Выполните задания для примера 19.5.

Вывести на экран все элементы последовательности Фибоначчи меньше x (x вводится).

Восстановите правильную последовательность строк кода программы. Проверьте работу программы запустив ниже представленный тест. Расставьте ниже записанные комментарии к программе, разместив их в соответствующие строки кода. 2+2 б

Код программы для исправления

write('Граница x= ');

begin

c := 1; b := 1; a := 2;

var a, b, c, x, k: integer;

read(x);

write(c, ' ', b, ' ');

k := 2;

write('k = ',k);

write(a, ' '); k := k+1;

writeln;

c := b; b := a;

a := b + c;

while a < x do begin

end.

end;

Тестирование.

Запустить программу и ввести значение x = 100. Результат:

Результат для x = 1000.

Комментарии

// вывод полученного числа

// вывод первых значений последовательности

// конец программы

// вычисление очередного числа

// конец цикла

// начало цикла

// описание переменных

// ввод значение верхней границы последовательности

// определение значений последовательности

2. Запустите программу и протестируйте для разных значений x. Какое максимальное значение x можно ввести? (Ответ запишите в виде комментария к конце кода программы) +1б

3. Замените в программе тип integer на тип int64. Сколько чисел последовательности Фибоначчи можно найти теперь? (Ответ запишите в виде комментария к конце кода программы) +1б

4. Измените программу так, чтобы она выводила значение числа Фибоначчи по введенному номеру. +4б

3. Выполните задания для примера 19.6.

1. Восстановите правильную последовательность строк кода программы. Расставьте ниже записанные комментарии к программе, разместив их в соответствующие строки кода. 4б

Код программы:

begin

read(n); k:= 0;

if a mod 5 = 0 then

write('Количество билетов n =' );

for var i:= 1 to n do begin

writeln('Выиграло ',k,' билета(-ов)');

a:= random(1,100);

var n, k, a:integer;

end;

write(a,'');

k := k+1;

writeln;

end.

Комментарии

// вывод количества выигранных билетов

// ввод количества разыгрывающих билетов

// вывод номера очередного билета

// вычисление номера очередного билета

// конец программы

// конец цикла

// начало цикла

// проверка номера выигравшего

// описание переменных

// увеличение счетчика счастливых билетов

2. Запустите программу несколько раз для одного и того же значения (например, 20). Какое число получается в ответе чаще всего? Почему? (Ответ запишите в виде комментария к конце кода программы) +1б

3. Измените диапазон случайных чисел на [1, 1000] и проверьте, какое число получается в результате чаще других для тех же 20 элементов. (Ответ запишите в виде комментария к конце кода программы) +1б

4. Измените программу так, чтобы вычислялось количество чисел, кратных введенному числу x. +2б

5. Измените программу так, чтобы можно было посчитать количество чисел из промежутка [a; b], a и b вводятся. +2б

4. Выполните задание

Напишите программу, которая будет выводить на экран элементы последовательности трибоначчи — первые элементы последовательности: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ... . Каждый элемент, начиная с четвертого, равен сумме трех предыдущих: an = an-1 + an-2 + an-3. 6б

1. По заданному n вывести элемент последовательности. +2б

2. Для заданного x вывести элементы последовательности меньше x. +2б

5. Выполните задания для примера 19.7.

Определите, сколько бактерий вывели за m дней.

Код программы примера

begin

write('Количество дней m = ');

for var n := 1 to m do

S := S+a;

read(m);

var m : integer;

S := 0;

begin

end;

writeln('Всего бактерий = ',S,' млн');

a := n*n*n/(sqrt(n*n*n)-n+1);

end.

Комментарии

// ввод количества дней эксперимента

// вывод итогового количества бактерий

// конец программы

// конец цикла

// начало цикла

// вычисление количества бактерий за день

// вычислений общей суммы бактерий

// описание переменных

// увеличение счетчика счастливых билетов

// установка начального значения суммы

2. Замените в решении задачи цикл for на цикл while. +2б

3. Выполните программу для m = 2000. Почему в ответе сумма = NaN? (Ответ запишите в виде комментария к конце кода программы) +2

4. Внесите изменения в программу для получения результата? Найдите значение для m = 2000, m = 10000. +2

6. Выполните задание

Найдите сумму первых n элементов последовательности. Число n вводится. Элементы последовательности задаются формулой an =1/n3 6б

1. На сколько большим должно быть значение n, чтобы программа выдала ответ «сумма = Infinity»? Почему так произошло? +1б

2. Какие изменения нужно внести в программу для получения правильного результата? +1б

3. Замените в решении задачи цикл for на цикл while. Найдите сумму для n = 20 000, n = 1 000 000. +2б

var i,k,n,z: integer;

begin

write(ꞌВведите n = ꞌ); read(n);

write(ꞌВведите i = ꞌ); read(i);

k:=0;

while n > 0 do begin

z : = n mod 10; //Текущая цифра

k : = k + 1;

if k = i then writeln(ꞌВ разряде ꞌ, i, ꞌ стоит цифра ꞌ, z);

N : = n div 10; //Уменьшение числа в 10 раз

end;

if i > k then writeln(ꞌВ числе ꞌ, k, ꞌ цифр, в разряде ꞌ, i, ꞌ нет цифрꞌ)

else writeln(ꞌВ числе ꞌ, k, ꞌ цифрꞌ);

end.

Программа:

var k, a: integer;

begin

write('Количество k = '); read(k);

for var n := 1 to k do

begin

a:= 2*n; write(a, ' ');

end;

end.

Тестирование.

Запустить программу и ввести значения k=5. Результат:

Запустить программу и ввести значение k=100. Результат:

Программа:

var a, b, c, x, k: integer;

begin

write('Граница x= ');

read(x);

c := 1;

b := 1;

a := 2;

write(c, ' ', b, ' ');

k := 2;

while a < x do begin

write(a, ' ');

k := k+1;

c := b;

b := a;

a := b + c;

end;

writeln;

write('k = ',k);

end.

Тестирование.

Запустить программу и ввести значение x = 100. Результат:

Результат для x = 1000.

Google Sites

Report abuse

Мозговой штурм

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

Использование числовых последовательностей

Пример 19.4.

Пример 19.5.

Пример 19.6.

Нахождение суммы элементов числовой последовательности

Пример 19.7.

Возведение числа в степень

Пример 19.8.

Построение таблицы значений функции

Пример 19.9.

Выделение цифр из числа

Пример 19.10.

Наибольший общий делитель двух чисел

Алгоритм Евклида

Пример 19.12

Пример 19.13*.

Упражнения

Выполните задания для примера 19.4.

2. Выполните задания для примера 19.5.

3. Выполните задания для примера 19.6.

4. Выполните задание

5. Выполните задания для примера 19.7.

6. Выполните задание