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

Подобно хорошему произведению искусства, хорошую программу мы видим сразу. И, подобно произведению искусства, часто трудно определить, что делает программу хорошей.
Пол Пивоварски, 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 не будет опубликован. Обязательные поля помечены *

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