Информатика: алгоритмический аспект

Подобно хорошему произведению искусства,
хорошую программу мы видим сразу. И,
подобно произведению искусства, часто
трудно определить, что делает программу
хорошей.
Пол Пивоварски, IBM.

Хорошая программа — это эффективная
программа.
Авторы.

Чтобы полностью решить задачу по информатике требуется три ве-
щи: компьютер, программа и алгоритм. Компьютер нужен для запуска на
нем программы, которая является записью алгоритма на языке програм-
мирования. Ни компьютер,  ни программа, ни алгоритм по отдельности,
как мы видим, не является единственно необходимым для решения зада-
чи. Однако мы можем выделить две наиболее важные части:  алгоритм и
программную его реализацию, при которой необходимо решать следующие
вопросы:

1) какая  информация необходима  для  обеспечения максимальной
эффективности выполнения программы;

2) какая  структура данных является наилучшей для записи,  по-
иска и изменения этой информации;

3) какие алгоритмы больше всего подходят для обработки  данных
такой структуры.

Правильное решение  этих вопросов позволяет значительно эффек-
тивнее реализовать алгоритм и намного уменьшить время решения зада-
чи. Но решать задачу надо, естественно, с составления алгоритма.

Алгоритм — одно из основных понятий информатики.  Само  по  себе
понятие  алгоритма  существует  не одну сотню лет.  Алгоритмом были
названы правила выполнения  арифметических  операций  в  десятичной
системе  счисления.  Эти  правила  были  сформулированы  в  IX веке
персидским математиком Абу-Джабаром ибн Муса ал-Хорезми и попали  в
Западную Европу в латинском переводе. С течением времени алгоритма-
ми стали называть правила выполнения каких-либо действий. Каждый из
вас  умеет  пользоваться телефоном-автоматом,  но не каждый задумы-
вался над тем,  что эти правила являются алгоритмом. В качестве ал-
горитма  можно также рассматривать приготовления любимого всеми ла-
комками мороженого. В то же время алгоритмом является известный ал-
горитм  нахождения  наибольшего общего делителя (алгоритм Евклида),
сформулированный задолго до появления самого понятия «алгоритм». Но
именно с появлением информатики и персональных компьютеров это сло-
во приобрело особый смысл.  Понятие алгоритма включает в  себя  все
многообразие действий: от простых операций до  сложных математичес-
ких методов.

Алгоритм определяется  как точное и понятное предписание о том,
какие действия и в каком порядке необходимо выполнить  для  решения
поставленной задачи.  Алгоритм должен обладать следующими свойства-
ми:

1) Дискретность. Это свойство подразумевает, что результат дол-
жен быть достигнут за конечное число шагов, причем каждый следующий
шаг  может  быть выполнен только при условии завершения предыдущего
шага;

2) Определенность.  Это значит, что любое предписание алгоритма
должно восприниматься однозначно. Другими словами, различные испол-
нители  на одних и тех же входных данных должны получить один и тот
же результат;

3) Массовость.  Как правило, алгоритм должен обеспечивать реше-
ние не одной конкретной задачи,  а целого класса задач данного типа
(т.е. при различных значениях входных данных);

4) Результативность.  Это свойство подразумевает, что с помощью
алгоритма  должен  быть  достигнут конкретный результат при решении
поставленной задачи;

Существуют различные способы записи алгоритмов. Наиболее распро-
страненными являются:

1) словесный способ;

2) графический способ (блок-схема);

3) учебный алгоритмический язык;

4) язык программирования.

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

Проиллюстрируем важность  эффективности  алгоритма  на примере
следующей задачи:

Написать программу определения количества шестизначных «счаст-
ливых» трамвайных билетов,  у которых сумма первых трех цифр совпа-
дает с суммой трех последних.

Опять же, как и в предыдущей статье, все приведенные фрагменты
программ написаны на языке Паскаль.

Метод 1.  Самое простое — это перебрать все возможные комбина-
ции шести цифр и подсчитать число «счастливых» билетов.

Count:=0;             { количество «счастливых» билетов }
for a1:=0 to 9 do
for a2:=0 to 9 do
for a3:=0 to 9 do
for a4:=0 to 9 do
for a5:=0 to 9 do
for a6:=0 to 9 do
if a1+a2+a3=a4+a5+a6  { «счастливый»? }
then Count:=Count+1;

Под сложностью алгоритма будем понимать количество  выполнений
тела  наиболее  глубоко  вложенного цикла.  Условие if во вложенных
циклах будет проверяться 10^6  раз,  поэтому  будем  говорить,  что
сложность этого алгоритма 10^6.

Метод 2.  Обратим внимание на то,  что в  «счастливом»  билете
последняя цифра a6 однозначно определяется первыми пятью:

a6=(a1+a2+a3)-(a4+a5).

Если 0<=a6<=9,  то билет «счастливый», иначе — нет. Таким об-
разом, мы можем убрать шестой вложенный цикл:

Count:=0;
for a1:=0 to 9 do
for a2:=0 to 9 do
for a3:=0 to 9 do
for a4:=0 to 9 do
for a5:=0 to 9 do
begin
a6:=(a1+a2+a3)-(a4+a5);
if (a6>=0) and (a6<=9)
then Count:=Count+1;
end;

Сложность алгоритма 10^5.  Используя элементарное соображение,
мы уменьшили сложность алгоритма и, вообще говоря, время выполнения
программы в 10 раз!

Метод 3.  Если  комбинаций  a1 a2 a3 первых трех цифр с суммой
T=a1+a2+a3 насчитывается C[T], то всего «счастливых» билетов с сум-
мой половины T=a1+a2+a3=a4+a5+a6 будет C[T]^2.  Действительно, каж-
дое «счастливое» шестиразрядное число может быть получено  склейкой
двух произвольных  трехразрядных  чисел  с  одинаковой суммой цифр.
Всего существует 28 всевозможных значений сумм T —  от  0=0+0+0  до
27=9+9+9.  Подсчитаем C[i], i=0, …, 28, затем найдем интересующее
нас количество «счастливых» билетов C[0]^2 + C[1]^2 + … + C[27]^2.

Заметим, что  «счастливых»  билетов  с  суммой  T столько же,
сколько и с суммой 27-T.  Действительно, если билет a1 a2 a3 a4 a5
a6  с  суммой  T  —  «счастливый»,  то таковым же является и билет
(999999 —  a1 a2 a3 a4 a5 a6) с суммой 27-T.  Поэтому число билетов
можно вычислять и по формуле 2(C[0]^2+ … +C[13]^2), т.е. рассмат-
ривать только суммы T от 0 до 13.

var C:array[0..13] of longint; { массив С из 14 элементов — по
. . .                          числу рассматриваемых сумм  }
Count:=0;
for T:=0 to 13 do C[T]:=0;
for a1:=0 to 9 do    { перебираем все }
for a2:=0 to 9 do  { возможные a1 a2 a3 }
for a3:=0 to 9 do
begin
T:=a1+a2+a3;
C[T]:=C[T]+1   { нашли еще один билет }
end;             { с суммой T }
for T:=0 to 13 do    { считаем число билетов }
Count:=Count+C[T]*C[T];
Count:=Count*2;      { удваиваем сумму }

Сложность этого алгоритма 10^3.

Метод 4. В методе 3 мы перебирали комбинации цифр и искали ко-
личество комбинаций с суммами C[T].  Сейчас мы пойдем от суммы T, и
по ней будем определять,  какое количество комбинаций a1 a2  a3  ее
имеет. Итак T=a1+a2+a3.

Минимальное значение,  которое  может  принимать  a1,  —  это
max{0,T-18}.  Член T-18 появляется из следующих соображений: пусть
a2=a3=9, тогда a1=T-18, но a1 не может быть меньше 0. Максимальное
значение a1=min{9,T} (так как a2 и a3 неотрицательны,  то a1<=T  и
одновременно a1<=9).

Для цифры a2 аналогично получаем, что она лежит в пределах от

max{0,T-a1-9} до min{9,T-a1}.

Цифра a3 по T, a1 и a2 определяется однозначно.

Получаем, что  комбинаций a1 a2 a3 с суммой T и с первой циф-
рой  a1  столько  же,  сколько  возможных  цифр   a2,   а   именно
min{9,T-a1}-max{0,T-a1-9}+1.
Как и в методе 3 мы можем рассматривать диапазон сумм T от 0 до 13.

Count:=0;
for T:=0 to 13 do
begin
CT:=0;
for a1:=max(0,T-18) to min(9,T) do
CT:=CT+min(9,T-a1)-max(0,T-a1-9)+1;
Count:=Count+CT*CT
end;
Count:=Count*2;

Сложность этого  алгоритма  (т.е.  количество  выполнений
операций присваивания внутри двух вложенных циклов) есть 95.

В общей формулировке рассмотренная задача выглядит так:

Написать программу  определения количества 2N -значных «счаст-
ливых» билетов, у которых сумма первых N цифр равна сумме последних
N цифр; N -произвольное натуральное число.

Эта задача опять же имеет очевидное решение, которое состоит в
генерации всех  2N-разрядных  чисел  и  проверке  их  на  требуемое
свойство.  Однако общее количество таких чисел равно 10^(2N) и поэ-
тому при N>3 практически очень трудно получить  результат  на  ЭВМ.
Следовательно необходимо разработать алгоритм, не требующий генера-
ции чисел.

Определим через S(k,i) количество k-разрядных чисел, сумма цифр
которых равна i. Например, S(2,3)=4, так как существует 4 двуразряд-
ных числа (03,  12, 21, 30), сумма цифр которых равна 3. Легко заме-
тить,  что S(1,i)=1 при i<10 и S(1,i)=0 при i>9. Предположим теперь,
что  мы  сумели вычислить значения величин S(N,i) для всех i от 0 до
9N,  т.е.  мы знаем,  сколько существует N-разрядных чисел с  суммой
цифр, равной 0,1,…,9N ( 9N — максимальная сумма цифр в N-разрядном
числе).  Тогда нетрудно убедиться, что общее количество «счастливых»
2N-разрядных чисел равно

P=S(N,0)^2+S(N,1)^2+…+S(N,9N)^2.

Действительно, рассуждая как и в методе 3, каждое «счастливое»
2N-разрядное число может быть получено склейкой  двух  произвольных
N-разрядных чисел с одинаковой суммой цифр.

Таким образом,  необходимо уметь  вычислять  значения  величин
S(k,i)  для  всех k<=N,i<=9k.  Определим способ вычисления S(k+1,i)
через значения величин S(k,j), j<=i. Понятно, что любое k+1-разряд-
ное число может быть получено из k-разрядного добавлением еще одно-
го разряда (цифры). Следовательно

S(k+1,i) = S(k,i-ц1)+S(k,i-ц2)+…,

где ц1,ц2,… — возможные добавленные цифры. Ясно, что это 0,1,…,m
где m=min(9,i). Следовательно,

S(k+1,i) = S(k,i-0)+S(k,i-1)+…+ S(k,i-m).

Упражнение. Определите сложность приведенного алгоритма.

Для того, чтобы Вы могли попробовать свои силы в самостоятель-
ном решении задач, мы представляем наш

Задачник.

Используя последний из приведенных  выше  методов  попытайтесь
решить задачи И1 и И2 (И — это сокращение от «Информатика»).

И1. Найти сумму квадратов всех положительных целых чисел,  за-
пись которых в десятичной системе счисления состоит ровно из k  от-
личных от нуля цифр.

И2. Найти количество  n-значных  чисел  в  десятичной  системе
счисления,  у каждого из которых сумма цифр равна k. При этом в ка-
честве n-значного числа мы допускаем и числа, начинающиеся с одного
или нескольких нулей.  Например, 000102 рассматривается как шестиз-
начное число, сумма цифр которого равна 3.

И еще 2 задачи,  которые,  как мы надеемся,  Вы найдете  инте-
ресными:

И3. В программистском фольклоре есть предание,  что при приеме
в одну из ведущих компьютерных фирм претенденту предлагалась решить
следующую задачу:

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

24, 81, 63, 26, 41, …

Продолжить ее. Найти правило формирования последующих членов.

И4. Во время поездки на поезде девочка заменила в названии по-
езда  каждую  букву ее номером в русском алфавите и получила запись
из единиц и двоек «211221-21221». Определить откуда и куда идет по-
езд.

И.А.Волков, В.М.Котов, Т.Г.Котова

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

методические материалы по информатике