\/d ГЛАВА III. ПРОГРАММИРОВАНИЕ РАЗВЕТВЛЯЮЩИХСЯ И ЦИКЛИЧЕСКИХ АЛГОРИТМОВ \/d- ... и если ничто уже не помогает - посмотри инструкцию для пользователя. Из завещания неизвестного программиста Линейные алгоритмы и соответствующие им программы редко встречаются в практике решения на компьютере реальных задач. Ведь неизменная последо- вательность действий, как правило, не может соответствовать изменяющимся обстоятельствам разнообразных жизненных или учебных ситуаций. Чаще всего порядок выполнения действий (ход алгоритмического процесса) зависит от оп- ределенных условий,поэтому возникает необходимость использовать операторы управления - оператор безусловной передачи управления, оператор условной передачи управления, оператор цикла. Изучение этих операторов позволит ответить на вопрос: может ли с т а - т и ч е с к и й объект - текст программы - быть построен таким образом, чтобы дать ясное представление о динамической ситуации - ее выполнении? III.1. ОПЕРАТОР БЕЗУСЛОВНОЙ ПЕРЕДАЧИ УПРАВЛЕНИЯ GOTO ...квалификация программистов является убы- вающей функцией от плотности предложений GOTO в создаваемых ими программах. Э.Дейкстра Выполнение операторов в программе осуществляется в порядке их естест- венного следования. Оператор GOTO ("to go to"-"перейти") позволяет нару- шить этот порядок. Приведем структуру оператора GOTO n , где: GOTO ("to go to"-"перейти") - служебное слово; n - любой существующий номер строки в программе; 0≤n≤65529 . Оператор GOTO передает управление программной строке с указанным номе- ром n . Если в программе нет строки с этим номером,то выдается сообщение "Undefined line number" ("Н о м е р с т р о к и н е о п р е д е л е н"). Управление передается заданной строке, даже если в ней нет выполняемо- го оператора; например, в строке может находиться оператор REM. Поскольку, однако, оператор REM не исполняется, лучше передавать управление следующе- му за ним исполняемому оператору. В этом случае программа будет выполнять- ся правильно и после удаления программной строки, содержащей комментарии. Выполнение оператора GOTO n в режиме прямого выполнения команд аналоги- чно выполнению команды RUN n , но в отличие от этой команды оператор GOTO n начинает выполнение программы с первого оператора указанной стро- ки, не присваивая начальных значений переменным и не меняя ранее присвоен- ных значений. С этой точки зрения оператор GOTO n в режиме прямого выпол- нения команд полезен при о т л а д к е и т е с т и р о в а н и и. В остальных случаях использовать его в этом режиме не рекомендуется, пос- кольку существует большая вероятность задать неправильный номер строки или непреднамеренно изменить значение переменной так, что фактически изме- нится порядок работы программы, что приведет к появлению многочисленных ошибок! Оператор GOTO - одна из наиболее интуитивно ясных и в то же время одна из наиболее опасных конструкций языков программирования. Оператором GOTO следует пользоваться как можно р е ж е, так как он делает программу труд- но читаемой для программиста - приходится особо следить за тем, в каком порядке выполняются строки программы. Отметим,что в школьный алгоритмичес- кий язык эта конструкция не включена вообще! П р и м е р ы: 1) 20 GOTO 20 'Зацикливание обеспечено! Стандартный при- ───────────── ем при работе с графикой. 2) NEW Ok 5'Пример плохой,трудно читаемой программы! 10 INPUT X 20 GOTO 40 30 PRINT X+Y:GOTO 60 40 INPUT Y 50 GOTO 30 60 END Нетрудно видеть, что приведенная программа эквивалентна программе, сос- тоящей из единственной программной строки: 10 INPUT X,Y:PRINT X+Y:END 3) NEW Ok 10 PRINT "2*2=4":GOTO 10 Эта программа никогда не закончит свою работу,т.к.после вывода текста "2*2=4" на экран оператор GOTO 10 возвращает к строке 10,которая опять вы- водит "2*2=4" и т.д. Пользователь,разумеется,может вмешаться и остановить такую "вечно" работающую программу(ее называют з а ц и к л и в ш е й с я) - для этого одновременно нажимают клавиши "CTRL" и "STOP" (напомним, что такое нажатие обозначается "CTRL"+"STOP"). В случае, если оператор записывается двумя служебными словами GO TO n, то он выполняется аналогично - этот формат сохранен для совместимости с другими языками программирования. Однако использовать "двухсловную" форму GOTO не рекомендуется, так как она требует большого объема памяти для хранения. Достигаемая экономия на первый взгляд несущественна, однако рано или поздно многие программисты попадают в ситуацию, когда "нескольких битов не хватает!" В статье Бема и Якопини [40] было показано, что любой алгоритм может быть описан на языке программировaния, использующем т о л ь к о т р и управляющие структуры: следование, цикл и ветвление. Возможность представ- ления любых алгоритмов с помощью вложенных друг в друга структур следова- ния, цикла и ветвления составляют основу метода структурного программиро- вания. В последующих разделах мы расскажем об операторах IF...THEN...ELSE и FOR...NEXT, которые являются простейшими эквивалентами управляющих конст- рукций Бема и Якопини. III.2. ОПЕРАТОР УСЛОВНОЙ ПЕРЕДАЧИ УПРАВЛЕНИЯ IF ЕСЛИ нельзя, но очень хочется, ТО можно! Евг.Сазонов, программовед и языколюб Сказочные герои, как известно, по дороге за тридевять земель в триде- сятое царство встречали на перекрестке камень с надписью - альтернативой. У программиста при написании программы возникает потребность запрограмми- ровать альтернативу,т.е. предусмотреть возможность выбора одного,либо дру- гого действия в зависимости от некоторого условия. Для программирования таких разветвляющихся участков алгоритма используется оператор условной передачи управления IF. Структура оператора : ┌───────────────────────────────────────────────────────────┐ │ IF условие THEN список операторов [ELSE список операторов]│ └───────────────────────────────────────────────────────────┘ Здесь: IF("если"), THEN("то"), ELSE("иначе") - служебные слова; у с л о в и е - арифметическое или логическое выражение; с п и с о к о п е р а т о р о в - несколько (или ни одного) опе- раторов MSX-BASIC, разделенных двоеточиями, или номер существующей про- граммной строки. Напомним, что квадратные скобки - обозначение, указывающее, что синтак- сическая конструкция внутри них не является обязательной! Кроме того,вместо служебного слова THEN может быть использовано служеб- ное слово GOTO, при этом за GOTO должен следовать номер существующей про- граммной строки. Более того, в случае, когда с п и с о к о п е р а т о - р о в состоит лишь из оператора GOTO n , служебное слово GOTO может опус- каться. Таким образом, если мы обозначим: n1 и n2 - номера программных строк, О1 и О2 - последовательности операторов MSX-BASIC (операторы внутри каждой последовательности разделяются символом ":"), то можно записать следующие формы оператора IF: IF условие THEN О1 IF условие ТHEN n1 IF условие GOTO n1 IF условие THEN O1 ELSE O2 IF условие THEN O1 ELSE n2 IF условие ТHEN n1 ELSE O2 IF условие ТHEN n1 ELSE n2 IF условие GOTO n1 ELSE O2 IF условие GOTO n1 ELSE n2 IF условие GOTO O1 ELSE O2 (обратите внимание!) Отметим,что в некоторых версиях BASIC (например, для ПЭВМ"ДВК-2М") ре- ализованы только "усеченные"конструкции оператора IF - без ветви "иначе" (т.е.без служебного слова ELSE): IF условие THEN n1 , IF условие THEN O1 . Теперь рассмотрим несколько примеров: 1) 300 DEFDBL A,B:IF A=B GOTO 700'Внимание!Может оказаться,что два чис ла,которые должны быть р а в н ы м и, все-таки н е м н о г о отл ичаются из-за ошибок округления! Переход на строку с номером 700 мо жет не осуществиться! Правильной будет следующая запись строки 300: 300 DEFDBL A,B:IF ABS(A-B)<=EPS GOTO 700 где EPS - допустимая "точность несовпадения" чисел A и B. Напомним, что основное различие между целыми и действительными (с фик- сированной или плавающей точкой) константами в том, что целые константы представлены в компьютере т о ч н о, а действительные - лишь п р и б л и- ж е н н о. Выполняя операции с действительными числами, мы о б я з а - т е л ь н о должны считаться с погрешностью округления, которая может очень сильно исказить результат! Взгляните: 10 INPUT А 10 INPUT A! 20 ? (A/3)^2*9 20 PRINT A!/3*3 run run ? 4 ? 1 15.999999999999 .99999999999999 Ok Ok 2) 10 INPUT A,A! 20 IF A!=A THEN PRINT "Верно!":END ELSE PRINT "Посмотрите комментар ий к предыдущему примеру!":END run ? 0.000001000002,0.000001000002 Посмотрите комментарий к предыдущему примеру! Ok 3) 10 IF AB THEN DIM C(4) ELSE DIM C(7) 30 C(6)=1:PRINT C(6) run run ? 1,3 ? 3,1 1 Subscript out of range in 30 Ok Ok Сообщение об ошибке "Subscript out of range"переводится как "В ы х о д за г р а н и ц ы м а с с и в а",то есть обращение к элементу массива со значением индекса,выходящим за пределы границ измерения массива. Таким образом, в некоторых случаях вместо использования "стирающего" оператора ERASE (см. раздел I.5) для переопределения размерности массива в программе можно применять указанный прием. 6) Ok ?11*(1/11) 1 Ok Однако естественно возникновение вопроса: почему компьютер выводит чис- ло 1 в качестве результата вычисления выражения 11*(1/11)? Объяснение этого факта следует искать в особенностях работы процедуры вывода, инициализируемой оператором PRINT,а именно: эта процедура самосто- ятельно выполняет определенные операции округления выводимых числовых дан- ных. Однако результаты подобных округлений, как видно из приведенных при- меров, труднопредсказуемы, что в свою очередь может приводить к непредви- денным последствиям. Замечание. Будьте осторожны при записи условий, ибо посмотрите: ───────── 10 IF Z%=&B11 THEN PRINT "1" ELSE PRINT "0" run Sintax error in 10 Исправить ошибку можно, заключив &В11 в круглые скобки! Напомним, что с е м а н т и к а (от греч."semantikos"-"обозначающий") - значения единиц языка, а с и н т а к с и с (от греч."syntaxis"-"постро- ение,порядок") - способы соединения слов(и их форм) в словосочетания,пред- ложения и текст. Опишем семантику конструкции IF...THEN...ELSE... .Вначале вычисляется значение условия. Если в качестве условия записано строковое выражение,то выдается сообщение об ошибке: "Type mismatch" ("Н е с о о т в е т с т в и е т и п о в"). Если условие истинно (TRUE), то управление передается фразе THEN; если условие ложно (FALSE) и есть фраза ELSE, то управление передается фразе ELSE; если условие ложно (FALSE) и нет фразы ELSE, то управление переда- ется первому оператору с л е д у ю щ е й программной строки (то есть ус- ловно можно считать,что фраза ELSE есть,но за ней стоит "пустой" оператор, не производящий никаких действий). Если непосредственно за THEN или ELSE указан номер программной строки и управление передается этой фразе, то фактически выполняется оператор GOTO Н о м е р с т р о к и В качестве примера рассмотрим программу, вычисляющую и показывающую на экране наибольший общий делитель (НОД) двух натуральных чисел M и N, вве- денных пользователем. Программа использует а л г о р и т м Е в к л и д а, который основывается на том, что НОД пары различных натуральных чисел сов- падает с НОД пары, полученной из предыдущей заменой большего числа раз- ностью большего и меньшего чисел. NEW Ok 20 DEFINT M,N:INPUT"Введите M,N";M,N 50 IF M>N THEN M=M-N 60 IF MN THEN GOTO 50 80 PRINT "НОД...";M:END run run run Введите M,N? 34,51 Введите M,N? 15,625 Введите M,N? 11,121 НОД... 17 НОД... 5 НОД... 11 Ok Оk Ok Проследим теперь за работой компьютера. При первом обращении к строке 50 переменная М имеет значение 34, а переменная N - значение 51. Условие M>N не соблюдено, поэтому следует переход к строке 60. Условие MN (M не равно N) то- же соблюдено, и поэтому строка 70 передает управление назад, строке 50. Теперь M имеет значение 34, а N - значение 17, и условие M>N соблюдено; поэтому переменной M присваивается значение 34-17=17. M=N=17.Условие стро- ки 60 не соблюдено, условие M<>N строки 70 тоже не соблюдено, и компьютер, наконец, выполняет строку 80,выводящую на экран дисплея текст "НОД... 17". В строке 80 работа программы заканчивается. Эта короткая программа позво- ляет найти НОД для любой пары натуральных чисел - выполнение серии строк 50, 60, 70 всегда будет повторено необходимое число раз. Об этом "заботят- ся" операторы IF...THEN ! В качестве еще одного примера приведем программу вычисления наименьше- го общего кратного (НОК) двух натуральных чисел. В алгоритме используем тот факт, что произведение НОК и НОД двух чисел равно произведению самих чисел (в программе - переменная К). NEW Ok 10 DEFINT M,N,K:INPUT"Введите M,N";M,N:K=M*N 20 IF M>N THEN M=M-N 30 IF N>M THEN N=N-M 40 IF M<>N THEN 20 50 PRINT "НОК...";K/M:END run run run Введите M,N? 4,6 Введите M,N? 12,45 Введите M,N? 888,117 НОК... 12 НОК... 180 НОК... 103896 Оk Ok Ok В а ж н о е з а м е ч а н и е : оператор IF должен полностью размеща- ться в одной программной строке (программная строка,вообще говоря,отлична от дисплейной строки!) и быть последним в ней. В этом случае будьте внима- тельны: программнaя строкa должна включать не более 255 символов (вместе с номером)! Однако не всегда удается "втиснуть"в одну программную строку последова- тельности операторов O1 и O2. В таких случаях помогает оператор GOTO, ко- торый передает управление на строку, с которой начинается нужный фрагмент программы (если необходимо вернуться к строке программы, следующей за ус- ловным оператором, то в конце фрагмента опять приходится ставить оператор GOTO). Такая конструкция весьма громоздка,поэтому предпочтительнее исполь- зовать подпрограммы (см. раздел IV.4). Любое арифметическое выражение может быть использовано в качестве у с- л о в и я; при этом следует помнить, что если результат его вычисления от- личен от нуля, то значением условия является TRUE, во всех остальных слу- чаях - FALSE . П р и м е р. IF X <> 0 THEN ... идентично записи ─────────── IF X THEN ... Отметим, что с п и с о к о п е р а т о р о в может содержать опера- тор IF...THEN...ELSE... (в этом случае говорят о в л о ж е н и и опера- торов IF друг в друга). Например, алгоритм нахождения большего из трех чисел A, B и C можно за- писать при помощи оператора: 10 IF A>B THEN IF A>C THEN Z=A ELSE Z=C ELSE IF B>C THEN Z=B ELSE Z=C 'Не правда ли, элегантно (!) и непонятно? Сравните: 10 BIG=X 20 IF Y>BIG THEN BIG=Y 30 IF Z>BIG THEN BIG=Z При вложении операторов IF возникают определенные логические трудности, связанные с проблемой "болтающегося ELSE". В самом деле, если написать опе- ратор вида: IF условие1 THEN IF условие2 THEN O1 ELSE O2 , то сразу же возникает вопрос: к какому IF (первому или второму)принадлежит фраза ELSE O2 (как говорят, ELSE "болтается"!)? Для устранения возможной двусмысленности учтите, что любой ELSE "связы- вается" с ближайшей п р е д ш е с т в у ю щ е й ему в программной строке конструкцией IF...THEN, которой еще не поставлен в соответствие ELSE (сра- вните с расстановкой скобок в алгебраическом выражении!). Поэтому можно сформулировать простое п р а в и л о: добавляйте нужное количество "пустых" ELSE, начиная с конца программной строки,для удовлетво- рения всех вхождений IF...THEN(сравните с правилом "вложенного IF"на языке программирования PL/1: каждая из вложенных конструкций IF...THEN должна иметь соответствующий ELSE, возможно "пустой"). Таким образом, конструкция IF условие1 THEN IF условие2 THEN O1 ELSE O2 понимается как IF условие1 THEN ( IF условие2 THEN O1 ELSE O2 ) Скобки поставлены т о л ь к о для наглядности. Упаси Вас бог употре- бить их в программе! Но если Вам все-таки хочется выделить в программе группу операторов,то можете применить для этой цели последовательность дво- еточий ::...: . Например: IF условие1 THEN:::IF условие2 THEN O1 ELSE O2::: . Смысл конструкции можно изменить, добавив "пустой" ELSE: IF условие1 THEN:::IF условие2 THEN O1 ELSE:::ELSE O2 . В какой-то мере последовательность двоеточий играет роль операторных скобок, присущих, например, языкам ALGOL, PL/1, Pascal, C ! П р и м е р ы: ───────────── 1) NEW Ok 10 INPUT X 20 IF X>1 THEN IF X<3 THEN PRINT "1≤X<3":END ELSE PRINT "X>3":END 30 PRINT "X≤1" run run run run ? 0 ? 1 ? 2.5 ? 4 X≤1 X≤1 1≤X<3 X>3 Ok Ok Ok Ok 2) NEW Ok 10 INPUT X 20 IF X>1 THEN IF X<3 THEN PRINT "1≤X<3":END ELSE ELSE PRINT "X≤1":END 30 PRINT "X≥3" run run run run ? 0 ? 1 ? 2.5 ? 4 x≤1 x≤1 1≤x<3 x≥3 Ok Ok Ok Ok 3) составить программу, определяющую, каким должен быть Ваш идеальный вес, по следующему алгоритму (формула Мэгони, уточненная К. Купером).Муж- чина берет свой рост в дюймах, умножает это число на 4 и вычитает 128.Жен- щине надо умножить свой рост в дюймах на 3.5 и затем вычесть 108. Эта фор- мула рассчитана на мужчину со средней шириной кости и женщину среднего те- лосложения. Но Вы можете заметить:"У меня широкая кость. Годится ли мне эта формула?" Да, но тогда прибавьте 10% к окончательному результату. Что- бы определить, насколько широка у Вас кость,используйте следующее правило. Измерьте окружность запястья доминирующей руки, т.е. руки, которой Вы пи- шите. Мужчина имеет широкую кость, если окружность его запястья больше 18 см, женщина - больше 16.5 см. Если размер окружности запястья меньше, то говорят о среднекостном или о тонкокостном типе сложения. Описанная выше формула предполагает измерение роста в футах и дюймах, а веса - в фунтах. Напомним, что 1 фут = 0.3048 м, 1 дюйм = 0.0254 м, 1 фунт = 0.4536 кг. NEW Ok 10 INPUT"Если Вы мужчина, то нажмите клавишу 'SHIFT'+'1',а если Вы жен щина, то нажмите клавишу 'клюшка'";X% 20 INPUT "Укажите Ваш рост в метрах";L 30 INPUT"Укажите обхват запястья сильнейшей руки в см";Y 35 PRINT"Ваш идеальный вес:" 40 IF X%=1 THEN IF Y>18 THEN PRINTUSING"###.###";(L/.0254*4-128)*.4536 *1.1;ELSE PRINTUSING "###.###"; (L/.0254*4-128)*.4536;ELSE IF Y>16.5 T HEN PRINTUSING "###.###";(L/.0254*3.5-108)*.4536*1.1;ELSE PRINTUSING " ###.###";(L/.0254*3.5-108)*.4536; 50 PRINT " кг":END run Если Вы мужчина, то нажмите клавишу 'SHIFT'+'1', а если Вы женщина, то нажмите клавишу 'клюшка'? 1 Укажите Ваш рост в метрах? 1.745 Укажите обхват запястья сильнейшей руки в см? 18.5 Ваш идеальный вес: 73.249 кг Ok 4) составить программу решения квадратного уравнения a·x² + b·x + c = 0 . NEW Ok 100 INPUT"Задайте a,b,c";A,B,C 110 DISC=B*B-4*A*C:W=1/2/A:Z=-B/2/A 120 IF ABS(DISC)<1.E-14 THEN PRINT"Двойной корень,x=";Z:GOTO 100'Услов ие ABS(DISC)<1.E-14 взято вместо условия DISC=0 с целью компенсации ош ибок округления. 130 IF DISC<0 THEN 160 140 PRINT "Корни";Z+SQR(DISC)*W; 150 PRINT "и";Z-SQR(DISC)*W:GOTO 100 160 PRINT "Мнимые корни:";Z;"+/-";SQR(-DISC)*W;"i":GOTO100 run Задайте a,b,c? 1,2,1 Двойной корень,x=-1 Задайте a,b,c? 1,1,1 Мнимые корни:-.5 +/- .8660254037844 i Задайте a,b,c? 1,-5,6 Корни 3 и 2 Задайте a,b,c? 0,1,1 Division by zero in 110 Ok Заметим, что указанная программа "не работает" в том случае, когда а=0. Поэтому добавим к программе строку: 105 IF A=0 THEN IF B=0 THEN IF C=0 THEN PRINT"x-любое":GOTO 100 ELSE P RINT"решений нет":GOTO 100 ELSE PRINT"корень равен";-C/B:GOTO 100 Это приведет к следующему результату: run Задайте a,b,c? 0,0,0 x-любое Задайте а,b,c? 0,1,1 корень равен-1 Задайте a,b,c? 0,0,1 решений нет и так далее... Целые числа сотворил господь бог, все остальное - дело рук человеческих. Л.Кронекер 5) написать программу, которая выводит на экран разложение введенного в компьютер натурального числа на простые сомножители, например, 24=2*2*2*3, 17=17 . Напомним о с н о в н у ю т е о р е м у а р и ф м е т и к и. Любое натуральное число n>2 может быть представлено в виде произведе- ния простых множителей; с точностью до порядка множителей такое представ- ление единственно. 10 PRINT "Введите натуральное N,N>1" 20 INPUT N:PRINT N;"=";:P=2 30 D=N/P 40 IF D=INT(D) THEN ?S$;P;:S$="*":N=D:GOTO 30 ELSE P=P+1 50 IF N>=P THEN 30 60 PRINT:END run run Введите натуральное N,N>1 Введите натуральное N,N>1 ? 111 ? 1111 111 = 3 * 37 1111 = 11 * 101 Ok Ok Далее легко получаются следующие результаты: 11111 = 41 * 271 111111 = 3 * 7 * 11 * 13 * 37 1111111 = 239 * 4649 11111111 = 11 * 73 * 101 * 137 ··· ··· 11111111111111 = 11 * 239 * 4649 * 909091 Объектом исследования в данной программе являются числа, записанные це- почкой единиц, р е п ь ю н и т ы (от английского "repeated unit"- повто- ренная единица) : 1,11,111, и т.д. Этот термин придумал в 1964 году амери- канец А. Бейлер. Первую же работу об этих удивительных числах написал дву- мя столетиями раньше Иоганн-III Бернулли в связи с исследованиями периоди- ческих десятичных дробей. В 1895 году француз Э.Люка в книге "Заниматель- ная математика" публикует проверенную им таблицу всех простых делителей репьюнитов до 18-го репьюнита включительно. В частности, 111111111111111 = 3*37*31*41*271*290*6161 1111111111111111 = 11*17*73*101*137*5882353 11111111111111111 = 2071723*5363222357 111111111111111111 = 3*7*11*13*19*37*52579*333667 . Сегодня таблица делителей репьюнитов достигла n=3000 (С. Ейтс, 1975), однако в ней еще достаточно много пробелов, и даже не все ясно в первой сотне репьюнитов. Практический интерес к репьюнитам существует в теории арифметических кодов,служащей основой помехоустойчивого кодирования в ком- пьютерной технике, и в проблеме простых чисел: их ищут сейчас в основном среди так называемых ч и с е л М е р с е н н а, имеющих вид 2ⁿ-1 , n=1,2,3,... . и последним достижением на этом пути стало число 132049 2 - 1 (1984 год). А ведь числа Мерсенна - это репьюниты в двоичной системе счисления! Про- верьте этот факт! Обязательно проведите аналогию между операторoм условной передачи уп- равления IF в языке программирования MSX-BASIC и командой ветвления если условие ──── │ то серия 1 │ ── │ иначе серия 2 │ ───── все ─── в школьном алгоритмическом языке! Кстати отметим, что аналог служебного слова все в MSX-BASIC не нужен ─── - признаком конца оператора IF является конец программной строки, в кото- рой он находится. В школьном алгоритмическом языке введена еще одна команда - команда п р о в е р к и к о н т р о л ь н о г о у с л о в и я утв у с л о в и е . ─── Если в процессе исполнения алгоритма условие нарушается, то компьютер прекращает исполнение алгоритма и сообщает, что возник отказ. Аналогом данной команды в MSX-BASIC может служить, например, конструк- ция IF...THEN...ELSE в следующем примере: NEW Ok 10 'Вычисление значения функции y=√(x-2) 20 INPUT"Введите X";X 30 IF X>=2 THEN PRINT SQR(X-2) ELSE PRINT 1/0 run run Введите X? 4 Введите X? 1.414213562373 Division by zero in 30 Ok Ok III.3. ОПЕРАТОР ON GOTO Общая форма записи оператора-переключателя (оператора выбора по целому значению) следующая: ON β GOTO N1,N2,...,Nk , где: ON ("на"), GOTO ("идти к") - служебные слова; β - арифметическое выражение, целая часть значения которого должна принадлежать отрезку [0,255]; N1,N2,...,Nk - номера программных строк; оператор ON GOTO воспри- нимает столько номеров строк в списке,сколько Вы сможете записать в одной логической строке (помните, что она ограничена 255 символами!). Выполнение оператора ON начинается с вычисления целой части значения арифметического выражения β, которое мы обозначим p. Далее, если p∈{1,2,...,k}, k - натуральное число, то управление перехо- дит к строке Np. Если p=0 или p>k, то выполняется оператор, следующий за ON. Если же p<0, то последует сообщение об ошибке "Illegal function call" ("Н е п р а в и л ь н ы й в ы з о в ф у н к ц и и"). П р и м е р ы: ───────────── 1) NEW Ok 10 INPUT X 20 ON X GOTO 200,300,400:? X:GOTO 10 200 PRINT X+200:END 300 PRINT X+300:END 400 PRINT X+400:END run run ? 0 ? 2 0 302 ? 3 Ok 403 run Ok ? 1 run 201 ? -1 Ok Illegal function call in 20 Ok Оператор ON GOTO удобен, когда выполнение одной или нескольких различ- ных ветвей алгоритма определяется значением переменной или выражения (так называемый выбор п о з н а ч е н и ю). Если эти ветви к о р о т к и е, то смело используйте оператор ON GOTO.Если же ветви имеют достаточно слож- ную логику и могут быть оформлены как п о д п р о г р а м м ы ,то для ре- ализации выбора по значению используйте оператор ON GOSUB (см. раздел IV.5). 2) NEW Ok 5 'Анализ символов, вводимых с клавиатуры 10 ON ASC(INPUT$(1))-26 GOTO 101,102,103 101 GOTO 10 102 PRINT "Нажата клавиша ──▶":END 103 PRINT "Нажата клавиша ◀──":END run ┌─────┐ Нажата клавиша ──▶ Нажмите клавишу │ ──▶ │ ! Ok └─────┘ run ┌─────┐ Нажата клавиша ◀── Нажмите клавишу │ ◀── │ ! Ok └─────┘ run ┌─────┐ Illegal function call in 10 Нажмите клавишу │ TAB │ ! Ok └─────┘ О строковой функции INPUT$() см. в разделе VII.1.1 . 3) Оператор ON A GOTO 110,110,110 позволяет совершить переход к программной строке 110, если значение пере- менной А находится в полуинтервале [1,4). 4) Пусть в программе требуется выполнить три различные операции в зави- симости от значения переменной K, которое может быть меньше, больше или равно нулю. Приведем фрагмент программы: 110 ON SGN(K)+1 GOTO 170,210 120 'Выполнение операции при K<0 · · · 170 'Выполнение операции при K=0 · · · 210 'Выполнение операции при K>0 · · · 5) Пусть в программе требуется совершить переход к различным строкам, если значение переменной A находится в следующих диапазонах: 0≤A< 800 - переход к строке 900; 800≤A<1600 - переход к строке 800; 1600≤A<2400 - переход к строке 700. Если же A≥2400 , то должен выполняться следующий оператор. В этом слу- чае программная строка с оператором ON будет иметь вид: 50 ON A/800+1 GOTO 900,800,700 Заметим, что оператор ON GOTO потенциально опасен, особенно для начи- нающих, так как его неаккуратное использование может привести к запутан- ной, трудной для понимания программе. В заключение проведем аналогию между оператором ON GOTO и командой в ы- б о р в сокращенном варианте выбор ───── │ при условие 1: серия 1 │ ─── │ при условие 2: серия 2 │ ─── │ ... │ при условие N: серия N │ ─── все ─── в школьном алгоритмическом языке. Говорят, что команда выбора реализует "выбор п о у с л о в и ю". Выбор по условию введен в школьный алгоритми- ческий язык из языка программирования Рапира. В большинстве языков высоко- го уровня (в том числе и в MSX-BASIC!) этой конструкции в чистом виде нет, но ее можно моделировать следующей последовательностью вложенных команд ветвления: если условие 1 ──── │ то серия 1 │ ── │ иначе если условие 2 │ ───── ──── │ │ то серия 2 │ │ ── │ │ иначе ... │ │ ───── │ │ если условие N │ │ ──── │ │ │ то серия N │ │ │ ── │ │ все │ │ ─── │ │ ... │ все │ ─── все ─── Зато в версии MSX-BASIC есть оператор ON GOTO - другая форма выбора (по з н а ч е н и ю выражения). Ясно, что, вообще говоря, механизмы работы выбора по условию и по зна- чению совпадают. Отличие лишь в форме условия: в выборе по условию оно мо- жет быть любым,а в выборе по значению условие определяется значением ариф- метического выражения. III.4. ПРОГРАММИРОВАНИЕ ЦИКЛОВ Три месяца каждую вторую среду он ходил смотреть фильм "Девушка моей мечты", но на связь с ним никто не вышел. В.Кожевников Понятие цикла является одним из основополагающих понятий информатики. Считается,что если бы в программах не было возможности организовывать цик- лы, то применять ЭВМ для решения многих задач не имело бы никакого смысла. Ц и к л - это многократное повторение одной и той же группы операторов, возможно, с новыми значениями переменных, входящих в эту группу. Типичный пример цикла мы видим в "Сказке о рыбаке и рыбке" А.С.Пушкина. Действия слабохарактерного старика повторялись ц и к л и ч е с к и : разговор с золотой рыбкой ──▶ путь от моря к старухе ──▶ получение нового приказания от старухи и снова ──▶ к морю, к золотой рыбке. Параметром цикла (в терминах языка BASIC) здесь выступает алчность ста- рухи, которая увеличивается при каждом новом прохождении циклического участка. Программы, содержащие циклы, называются ц и к л и ч е с к и м и. Цикл, не содержащий внутри себя других циклов,называется п р о с т ы м. В противном случае его называют к р а т н ы м или в л о ж е н н ы м. В школьном алгоритмическом языке для записи циклических алгоритмов при- меняются две конструкции: цикл "для" и цикл "пока". ─── ──── Рассмотрим, как на языке программирования MSX-BASIC программируется ц и к л "д л я". ───── Для этого существуют два специальных оператора: оператор начала цикла (оператор FOR),оператор конца цикла (оператор NEXT). Операторы FOR и NEXT, как правило(!), используются совместно. Оператор начала цикла (его называют еще з а г о л о в к о м цикла) имеет вид: FOR i = α TO β [ STEP γ ] . Здесь: FOR ("для"), TO ("до"), STEP ("шаг"), NEXT ("следующий") - служеб- ные слова; i - имя числовой переменной (без индекса!); α,β,γ - арифметические выражения. Вслед за оператором н а ч а л а цикла располагают операторы программы, которые должны выполняться циклически(эти операторы образуют т е л о цик- ла). За последним оператором тела цикла размещается оператор к о н ц а цикла, который имеет следующий синтаксис: NEXT [i] Обратите внимание на то, что переменная, указываемая после NEXT,должна быть той же переменной,которая упоминается в операторе начала цикла после служебного слова FOR (эту переменную называют п а р а м е т р о м цикла). Значения арифметических переменных α и β задают соответственно началь- ное и конечное значения параметру цикла. Значение арифметического выраже- ния γ - это ш а г ,на величину которого изменяется параметр цикла после каждого повторения тела цикла. Шаг может быть как положительным, так и от- рицательным. Если шаг цикла равен +1, указание STEP γ в операторе начала цикла мо- жет опускаться (говорят, что "по умолчанию шаг цикла равен 1"). Итак, в программе цикл "для" записывается следующим образом: ─── ┌───────────────────────────────────────-┐ │ FOR i = α TO β [ STEP γ ] │ │ т е л о ц и к л а │ │ NEXT i │ └───────────────────────────────────────-┘ Выполнение этого фрагмента программы происходит следующим образом: па- раметру цикла i присваивается его начальное значение (значение арифметиче- ского выражения α), и один раз выполняется тело цикла (т.е. группа опера- торов, размещенных между заголовком цикла и соответствующим оператором NEXT). Вслед за этим оператор NEXT изменяет значение параметра цикла i на величину шага (значение арифметического выражения γ) и проверяет, не выш- ло ли новое значение параметра цикла из рабочего интервала (если шаг поло- жителен,то не стало ли оно больше конечного значения параметра цикла (зна- чения арифметического выражения β); если шаг отрицателен - не стало ли ме- ньше конечного значения параметра цикла). Если этого не происходит, то осуществляется повторное выполнение тела цикла, в противном случае - в ы х о д из цикла, то есть переход к опера- тору, следующему за NEXT. Заметим, что при л ю б ы х значениях α,β,γ тело цикла будет выполне- но х о т я бы о д и н раз (в отличие от школьного алгоритмического языка и других языков программирования!)! П р и м е р: NEW ─────────── Ok 10 FOR A=1 TO 10 STEP-1 20 PRINT A 30 NEXT A run 1 Ok Эта программа выведет на экран только начальное значение параметра цик- ла A=1. При первой же встрече с оператором NEXT A будет обнаружено,что ко- нечное значение параметра цикла (A=10) уже "позади"! Еще раз обращаем Ваше внимание на то, что: проверка на окончание цикла производится п о с л е выполнения тела цикла; изменение параметра цикла происходит п е р е д проверкой на оконча- ние цикла. Таким образом, следующие фрагменты эквивалентны: ··· ··· 10 FOR K=1 TO 4 STEP 2 10 K=1 ··· тело цикла ··· 20 'Пустой оператор 100 NEXT K ··· тело цикла ··· ··· 100 K=K+2 110 IF K<=4 GOTO 20 ··· Отметим, что оператор цикла FOR...NEXT можно располагать на одной про- граммной строке. Это целесообразно делать, если тело цикла состоит из од- ного-двух операторов. Например: 10 FOR L=1 TO 10:PRINT L;L^3:NEXT L Выполнив эту строку, компьютер выведет на экран дисплея таблицу кубов чисел 1,2,3,...,10. Кстати, сравните конструкцию FOR...NEXT с циклом "для" в школьном ал- горитмическом языке: ─── для x от x до x шаг x ─── ── min ── max ─── шаг нц │ ── серия команд │ кц ── Напомним, что в том месте дисплейной строки,где надо обратить Ваше вни- мание на наличие символа пробел (" "), мы будем использовать в тексте сим- вол "·". В а ж н о е з а м е ч а н и е ! Значения переменных α,β,γ можно изменять операторами, находящимися в теле цикла! Следующие две программы идентичны: NEW NEW Ok Ok 10 A=7:B=9:H=1 5 A=7:B=9:H=1:A1=A:B1=B:H1=H 20 FOR I=A TO B STEP H 10 FOR I=A1 TO B1 STEP H1 30 A=4:B=5:H=2 20 A=4:B=5:H=2 40 PRINT A;B;H:NEXT 25 PRINT A;B;H:NEXT run run ·4··5··2 ·4··5··2 ·4··5··2 ·4··5··2 ·4··5··2 ·4··5··2 Ok Ok Таким образом, текущие значения переменных α,β,γ(в теле цикла) могут не совпадать с начальным, конечным значениями параметра цикла и значением шага соответственно! В то же время, з н а ч е н и я α, β и γ,указанные в заголовке цикла, "недоступны" для операторов тела цикла при условии, что в теле цикла нет обращения к заголовку цикла. NEW Ok 10 INPUT A,B,H 20 FOR I=A TO B STEP H:?"I=";I 30 A=A+2:IF A<6 GOTO 20 ELSE ?A 40 NEXT:?I run ? 2,3,1 I= 2 I= 4 6 5 Ok Следовательно, изменить начальное и конечное значения параметра цикла, а также значение шага можно только(!)с помощью обращения к заголовку цикла. Таким образом, операторы, находящиеся в теле цикла могут управлять чис- лом повторений цикла! Значение параметра цикла i также м о ж н о изменять операторами, на- ходящимися в теле цикла! По окончании работы цикла значение параметра цикла i равно первому его значению, для которого выполнилось неравенство sign([β]-i)·[γ]<0, (∗) где обозначено: 1) [β] и [γ] - значения арифметических выражений β и γ соответственно; 2) функция sign(x)("signum"-"знак") определяется формулой: 1, если x>0 sgn(x)= { 0, если x=0 -1, если x<0. Условие (∗) принято вместо условия ([β]-i)·[γ]<0 потому, что при малых ([β]-i) и [γ] произведение ([β]-i)·[γ] может дать "машинный нуль",хотя будет выполнено неравенство (∗)! Кстати,число повторений цикла "без фокусов" можно вычислить по формуле: K=INT(ABS(([β]-[α])/[γ]))+1 Отметим, что во многих других языках программирования (ALGOL, FORTRAN) по окончании цикла значение параметра i становится н е о п р е д е л е н- н ы м . В этом случае им можно "пользоваться" только после присвоения но- вого значения. П р и м е р ы: ───────────── 1) NEW 2) NEW Ok Ok 10 INPUT A,B,H 10 INPUT A,B,H 20 FOR I=A TO B STEP H 20 FOR I=A TO B STEP H 40 PRINT I;: I=I+1: ?I 30 H=H+1: I=I+H: PRINT H;I 50 NEXT 40 NEXT run run ? 1,3,1 ? 1,4,1 ·1··2 ·2··3 ·3··4 ·3··7 Ok Ok 3) NEW 4) NEW Ok Ok 10 INPUT A,B,H 10 INPUT A,B,H 20 FOR I=A TO B STEP H 20 FOR I=A TO B STEP H 30 NEXT I:PRINT I 30 I=I^2:NEXT: PRINT I run run ? 4,5,2 ? 5,1,1 6 26 Ok Ok Тело цикла по отношению к остальной части программы замкнуто, то есть н е л ь з я "входить" в него, минуя заголовок цикла. Возможен досрочный выход из цикла не через его окончание, а с использо- ванием операторов IF...THEN...ELSE... и GOTO (в этом случае говорят, что цикл выполняется "n+1/2" раз!). При этом значение параметра цикла о п р е- д е л е н о и равно тому значению, при котором произошел выход из цикла. П р и м е р. Найти индекс первого положительного элемента одномерного ─────────── числового массива А(N). NEW Ok 10 DEFINT N,I:INPUT "Введите N";N 20 DIM A(N) 'Описание массива А 30 FOR I=1 TO N:INPUT A(I):NEXT I 'Ввод массива A 40 FOR I=1 TO N 50 IF A(I)>0 THEN ?"Искомый индекс:";I:GOTO 60 ELSE NEXT I 60 PRINT"We are out of the loop!" 'Мы вышли из цикла! run Введите N? 4 ? -1 ? -3 ? 5 ? -4 Искомый индекс: 3 We are out of the loop! Ok Oтметим, что оператор GOTO 60 в 50 строке можно заменить на последова- тельность операторов: I=N:NEXT I (мы пользуемся тем, что параметр цикла I можно менять внутри цикла!), ко- торая обеспечит в случае A(I)>0 выход из цикла. Обратите внимание на то, что можно даже выйти из тела цикла в "окружающую" его часть программы, а затем вернуться снова в тело цикла, м и н у я заголовок! П р и м е р. NEW ─────────── Ok 10 FOR I=1 TO 5 20 IF I<=2 THEN GOTO 100 30 M=I^2: PRINT M 40 NEXT I:END 100 I=I+3:GOTO 30 'Возвращение в тело цикла! run 16 25 Ok Приведенный пример показывает, как, используя оператор GOTO,можно "рас- ширить" тело цикла, включив в него произвольные части программы. П р и м е р ы п р о с т ы х ц и к л о в 5% текста программы занимают 90% времени ее выполнения. Аксиома программирования 1) 10 FOR I=1 TO 1000:NEXT 'Задержка ≈ 2.35 секунды Применение оператора цикла с "пустым" телом позволяет получить эффект з а д е р ж к и по в р е м е н и. Запомните этот трюк! 2) Ok 10 'Признание в любви! 20 INPUT"Введите целое число N";N% 30 FOR I%=1 TO N% 40 PRINT"I love YOU!" 50 NEXT I% Думаем, что результат работы этой N-"любвиобильной" программы Вас пора- дует. Заметим, что программа идентична алгоритму с использованием команды повторения n раз в школьном алгоритмическом языке [13]: ─── нц число повторений раз ── серия команд ─── │ кц ── так как тело цикла не зависит от параметра цикла. 3) Ok 10 DEFINT N,I:INPUT "Введите N";N 20 DIM A(N) 'Массив А описан! 30 FOR I=0 TO N:INPUT A(I):NEXT I 40'Данный фрагмент позволяет осуществить ввод элементов одномерн ого массива А (в массиве N+1 элемент!) Приведем еще один способ решения указанной проблемы: Ok 10 DIM A(5) 'Массив A содержит 6 элементов! 20 DATA 1.,2.,3.,4.,5.,6. 30 FOR I=0 TO 5: READ A(I): NEXT I 4) и н и ц и а л и з а ц и я массива (присвоение начальных значений) целыми псевдослучайными числами, принадлежащими отрезку [A,B]: NEW Ok 10 DEFINT N,I,C: INPUT A,B,N: DIM C(N) 20 X=RND(-TIME) 'Начальная установка генератора псевдослучайных чисел 30 FOR I=1 TO N 40 C(I)=INT((B-A+1)*RND(1)+A):?C(I);NEXT I run ? -5,3,12 -1·-3··0·-1··0·-1·-3··3··2·-5··0··1 Ok З а м е ч а н и е. Как можно чаще применяйте указанный способ инициали- зации массива псевдослучайными числами при т е с т и р о в а н и и (про- цессе обнаружения ошибок) Ваших программ! 5) NEW Ok 10 'Табулирование функции y=exp(sin(x)) на [A,B] с шагом H. 100 INPUT A,B,H 110 FOR X=A TO B STEP H 120 ?USING"#.### #.###";X;EXP(SIN(X)) 130 NEXT run ? .0,1.,.2 0.000 1.000 0.600 1.759 0.200 1.220 0.800 2.049 0.400 1.476 1.000 2.320 Ok 6) составить программу табулирования функции y=sinx на отрезке [a,b], причем на первой половине отрезка - с шагом h, a на второй половине от- резка - с шагом h/2. Приведенные ниже программы эквивалентны и дают полное представление о работе оператора FOR...NEXT . a) NEW b) NEW Ok Ok 10 INPUT A,B,H:P=0 10 INPUT A,B,H:P=0'Р-флажок! 20 FOR X=A TO B STEP H 20 A1=A:B1=B:H1=H 30 IF X>=(A+B)/2ANDP=0 25 X=A1 THEN P=1:A=(A+B)/2:H=H 30 IF X>=(A+B)/2ANDP=0 THEN /2:GOTO 20 P=1:A=(A+B)/2:H=H/2:GOTO 20 35 PRINT X;SIN(X) 35 PRINT X;SIN(X) 40 NEXT X 40 X=X+H1:IF X<=B1 GOTO 30 run c) NEW ? 0,1,.1 Ok 0 0 10 INPUT A,B,H:P=0:X=A .1 .099833416646831 20 IF X>=(A+B)/2 THEN FOR X=(A .2 .19866933079507 +B)/2+H/2 TO B STEP H/2:P=1 EL ··· ··· SE FOR X=A TO (A+B)/2 STEP H .95 .81341550478941 30 PRINT X;SIN(X) 1 .84147098480792 40 NEXT:IF P=0 THEN GOTO 20 Ok 7) пусть требуется вычислить значение функции y=x² для x=0, 0.1, 0.2, ..., 1., кроме x=0.3. Предостережем от н е в е р н о г о (в принципе!) решения: 10 FOR X=0 TO 1 STEP 0.1 20 IF X><0.3 THEN ?X;X^2:NEXT X ELSE NEXT X Значение шага цикла (0.1) есть десятичная константа с фиксированной то- чкой. Поэтому, вследствие накопления погрешности округления, мало надежды (хотя она и есть!) на то, что на четвертом цикле значение X будет точно равно 0.3. Да и на одиннадцатом цикле значение X может оказаться "чуточку" большим (меньшим) единицы! Поэтому верное решение будет, например, таким: 10 FOR Y%=0 TO 10 20 IF Y%><3 THEN X=Y%/10:?X;X^2:NEXT X ELSE NEXT X 8) NEW Ok 5 'Вычисление значения многочлена A(0)+A(1)·x+A(2)·x²+···+A(n)· xⁿ в точке x=X0 по схеме Горнера 10 INPUT"Введите степень многочлена n=";N:INPUT "X0=";X 20 FOR I=0 TO N:PRINT"A("I")=";:INPUT A(I):NEXTI 36 C=A(N) 40 FOR I=N-1 TO 0 STEP -1:C=C*X+A(I):NEXTI:PRINT "c=";C 9) последовательность чисел Фибоначчи F(1), F(2),..., F(n),... определяется по следующим рекуррентным формулам: F(1)=1, F(2)=1, F(n+2)=F(n)+F(n+1), n=1,2,... . Напишите программу, вычисляющую F(N) по заданному N. NEW Ok 10 DEFINT N,I:INPUT N:A=1:B=1 20 IF N=1ORN=2 THEN C=1:? C:END 30 FOR I=1 TO N-2:C=A+B:A=B:B=C:NEXT 35 PRINT C:END run run run ? 5 ? 10 ? 100 5 55 3.5422484817927E+20 Ok Ok Ok Известно, что для членов последовательности Фибоначчи имеет место кра- сивая формула: 1┌ 1+√5 ⁿ 1+√5 ⁿ┐ F(n)= ──│(─────) ─ (─────) │ , n=1,2,... √5└ 2 2 ┘ Используем ее для написания второго варианта предыдущей программы: NEW Ok 10 FOR N=1 TO 63 20 A=FIX((((1+SQR(5))/2)^N-((1-SQR(5))/2)^N)/SQR(5)+0.5) 30 PRINT"n=";N;"A=";A 40 NEXT run n= 1 A= 1 ··· n= 63 A= 6557470319842 Ok Как уже говорилось, тело цикла может содержать второй цикл - в н у т- р е н н и й по отношению к первому, в н е ш н е м у циклу ("бумажные стаканчики"). Внутренний цикл должен целиком содержаться в теле внешнего цикла. Таким образом, оператор NEXT для внутреннего цикла должен стоять перед оператором NEXT внешнего цикла. Нарушение этого правила приводит к появлению на экране сообщения об ошибке: "NEXT without FOR in ..." ("О п е р а т о р NEXT б е з о п е р а т о р а FOR в с т р о к е ..."). П р и м е р. NEW ─────────── Ok 10 FOR I=1 TO 3: FOR J=2 TO 4 20 IF J>1 THEN NEXT I 30 NEXT J run NEXT without FOR in 30 Ok Тело внутреннего цикла в свою очередь может содержать еще один цикл, внутренний по отношению к нему и так далее. Интерпретатор MSX-BASICa уста- навливает максимальную "глубину" (число) вложений циклов, однако она на- столько велика, что превысить ее практически невозможно! Учтите, что каждый оператор FOR...NEXT занимает при работе 25 байтов с т е к а , причем стек освобождается только при завершении цикла, после последнего выполнения оператора NEXT! Тем не менее, если программа использует слишком много циклов одновре- менно, может возникнуть сообщение об ошибке: "Out of memory" ("В ы х о д з а п р е д е л ы п а м я т и"). Если требуется, чтобы несколько вложенных операторов FOR заканчива- лись в одном месте, можно использовать один оператор NEXT,содержащий спи- сок параметров циклов, разделенных запятыми: первое имя в списке соответ- ствует самому внутреннему, последнее - самому внешнему циклу. П р и м е р ы в л о ж е н н ы х ц и к л о в 1) Ok 2) Ok 10 FOR X=1 TO 100 10 'Инициализация диагональной 20 FOR Y=1 TO 10 (единичной) матрицы X(3,3) 30 ? "1000 раз" 20 FOR I=1 TO 3:FOR J=1 TO 3 40 NEXT Y 30 X(I,J)=INT(I/J)*INT(J/I) 50 ? "Tолько 100 раз" 40 NEXT J 60 NEXT X 50 NEXT I 3) 10 'Ввод двумерного массива MAS по столбцам 20 DIM MAS(30,20): FOR I=1 TO 20: FOR J=1 TO 30 30 INPUT MAS(J,I): PRINT MAS(J,I): NEXT J,I Оператор ? MAS(J,I) позволяет осуществить контроль вводимой информации. Вопрос к читателю:что необходимо изменить в приведенном фрагменте,если Вы пожелаете ввести массив MAS по строкам? 4) Ok 5'Проверка результатов логических операций NOT,AND,OR,XOR,EQV,IMP для операндов i,j∈{-1,0}. 10 FOR I=-1 TO 0: FOR J=-1 TO 0 20 PRINT I;J;NOT(I);IANDJ;IORJ;IXORJ;IEQVJ;IIMPJ 40 NEXT:NEXT run -1 -1 0 -1 -1 0 -1 -1 -1 0 0 0 -1 -1 0 0 0 -1 -1 0 -1 -1 0 -1 0 0 -1 0 0 0 -1 -1 Ok Сравните полученные результаты с таблицей, приведенной ранее в разделе I.7.2. 5) NEW Ok 5'"Удобный" вывод на экран двумерного массива. 10 FOR I=1 TO 3:FOR J=1 TO 4:READ A(I,J):NEXTJ,I 15 FOR I=1 TO 3:FOR J=1 TO 4 20 'Обратите внимание на символ ";" в строке 25! 25 PRINT A(I,J);:NEXT J:PRINT:NEXT I 30 DATA 1,2,3,4,3,4,5,6,0,4,5,3 run 1 2 3 4 3 4 5 6 0 4 5 3 Ok Операторы FOR и NEXT,как правило,должны идти в паре и быть согласованы друг с другом. Если оператор NEXT выполняется раньше оператора FOR с тем же параметром цикла, то при выполнении такого NEXT выдается сообщение об ошибке "NEXT without FOR" ("Н е т о п е р а т о р а FOR д л я д а н н о г о NEXT"). Oператор FOR...NEXT - единственный способ в MSX-BASIC для изменения ес- тественного порядка выполнения операторов без задания номеров программных строк, на которые нужно перейти. Весьма поучительно сопоставить конструкцию FOR...NEXT с конструкцией цикла "пока" в школьном алгоритмическом языке: ──── пока у с л о в и е ──── нц ── с е р и я к о м а н д │ кц ── Oтметим, что в некоторых версиях BASIC (например, для персональных ком- пьютеров фирмы IBM: IBM PC, IBM PC/XT, IBM PCjr) существует конструкция, почти дословно повторяющая цикл "пока"; ──── ее структура ([11], с.74): WHILE у с л о в и е т е л о ц и к л а WEND здесь WHILE("while"-"пока"), WEND("конец цикла WHILE") - служебные слова. Оператор цикла WHILE повторяет выполнение операторов тела цикла до тех пор, пока выполняется требуемое условие. Если условие не истинно или ста- новится не истинным, операторы тела цикла не выполняются ни разу, и управ- ление передается первому оператору, следующему за WEND. Обратите внимание на то, что если условие оказывается л о ж н ы м (не удовлетворяется при первой же проверке),то операторы тела цикла вообще не выполняются! Как правило, условие в операторе цикла WHILE...WEND должно когда-ни- будь стать ложным, иначе повторение будет бесконечным. Впрочем, если Ваша программа вошла в бесконечный цикл или каким-нибудь другим образом вышла из-под Вашего контроля, н е п а н и к у й т е ! В MSX-BASIC предусмот- рена возможность п р е р ы в а н и я программы - одновременным нажатием на две клавиши "CTRL"+"STOP". Метод решения хорош,если с самого начала мы можем предвидеть - и да- лее подтвердить это, - что, следуя этому методу, мы достигнем цели. Г.Лейбниц Истина всегда оказывается проще,чем можно было предположить. Р.Фейнман Попытаемся циклом FOR...NEXT(!) описать цикл "пока". Следующая весьма ──── нетривиальная конструкция позволяет это сделать: · · · 10 IF NOT у с л о в и е THEN 60'Если условие ложно,то в цикл не входим! 20 FOR I=1 TO 0 STEP 1 'Оригинальный заголовок цикла, не правда ли? 30 т е л о ц и к л а 40 I = у с л о в и е 'Потрясающе! Если условие ложно, то I=0, и цикл заканчивается; если условие истинно,то I=-1, и мы продолжим выполнение тела цикла. 50 NEXT I 60 . . . 'Продолжение программы. Если в операторе IF использовать указатель шага цикла STEP 0, то цикл будет бесконечным. И н о г д а(?) это бывает полезным! П р и м е р 1. Вычислить сумму вида: ───────────── k S = ∑ n Ok n=1 5 DEFINT K,N,I,S:INPUT K:S=0:N=1 20 IF N>K THEN 70 30 FOR I=1 TO 0 STEP 1 40 S=S+N: N=N+1 'Т е л о ц и к л а 50 I = N<=K 60 NEXT I 70 PRINT S;"Тестовый пример:";K*(K+1)/2 run ? 100 5050 Тестовый пример: 5050 Оk Ясно,что в приведенной программе можно применить оператор цикла FOR... NEXT, поэтому рассмотрим пример, где использование оператора цикла FOR... NEXT не помогает. П р и м е р 2. Пусть для данного положительного числа S требуется на- ───────────── йти наибольшее натуральное K, такое, что Ok S ≥ 1² + 2² + ··· + K² . 10 DEFINT I,J:INPUT S:J=0 20 IF S<=0 THEN PRINT"S неположительно!":END 30 FOR I=1 TO 0 STEP 1 40 J=J+1: S=S-J^2 50 I = S>=0 60 NEXT I 70 PRINT J-1:END run run ? 23 ? 300 3 9 Ok Ok Из сопоставления примеров 1 и 2 ясно, что цикл "для" используется,как ─── правило,когда количество исполнений цикла известно заранее. Если же число исполнений определить нельзя, если цикл должен быть прерван не по достиже- нии параметром цикла конечного значения,а по какому-то другому условию (в примере 2: S ≤ 1²+2²+···+k²), необходим цикл "пока". ──── Прежде чем решать задачу,подумай,что делать с ее решением. Р.Хемминг В науке часто недостаточно решить какую-нибудь задачу или группу задач. После этого нужно присмотреться к этим зада- чам и заново осмыслить, какие же вы задачи решили.Нередко, решая одну задачу,мы автоматически находим ответ и на дру- гой вопрос, о котором раньше вовсе не думали. Н.Винер П р и м е р 3. Составить программу нахождения суммы возрастающей ариф- ───────────── метической прогрессии. NEW Ok 5 DEFINT I:INPUT A1,AN,D'А1-первый член арифметической прогрессии;АN-п оследний ее член;D-знаменатель (D>0!) 7 IF D<0 OR A1>AN THEN ?"Прогрессия должна быть возрастающей! Повторит е ввод!":GOTO 5 10 S=0:N=A1 20 IF N>AN THEN GOTO 70 30 FOR I=1 TO 0 STEP 1 40 S=S+N: N=N+D 'Тело цикла 50 I = N<=AN 60 NEXT I 70 ? S;"Тестовый пример:";((AN-A1)/D+1)*(A1+D/2*(AN-A1)/D) run ? 1,20,1 210 Тестовый пример: 210 Оk run ? 20,2,1 Прогрессия должна быть возрастающей! Повторите ввод! ? ... Другой способ программирования на языке программирования MSX-BASIC цик- ла WHILE...WEND предполагает использование "о п а с н о г о" оператора GOTO: 10 GOTO 100 20 операторы т е л а ц и к л а 100 IF у с л о в и е THEN GOTO 20 Если количество операторов тела цикла невелико,то допустима следующая конструкция: 10 IF у с л о в и е THEN операторы т е л а ц и к л а: GOTO 10 ELSE продолжение программы ... Если же количество операторов цикла велико, то можно операторы тела цикла поместить в подпрограмму (см. раздел IV.4), вызываемую оператором GOSUB: 10 IF условие THEN GOSUB 1000: GOTO 10 ELSE продолжение программы ··· 1000 Т е л о ц и к л а ··· 1200 RETURN П р и м е р 4. Вычислить сумму S знакочередующегося числового ряда: ───────────── ∞ ∑ (-1)ⁿ/n² с точностью E . n=1 Приведем три варианта программы: a) NEW c) NEW Ok Ok 10 INPUT E 10 DEFINT I: INPUT E 20 S=0:N=1: A=-1 20 FOR I=1 TO SQR(1/E) 30 GOTO 50 30 S = S+(-1)^I/I/I 40 S=S+A:N=N+1:A=(-1)^N/N/N 40 NEXT I 50 IF ABS(A)>=E THEN GOTO 40 50 PRINT S 60 PRINT "Результат:";S 60 END run run ? .00001 ? .00001 Результат:-.82246204205923 -.82246204205923 Ok Ok b) NEW Ok 10 INPUT E 20 S=0:N=1:A=-1 30 IF ABS(A)>=E THEN S=S+A:N=N+1:A=(-1)^N/N/N:GOTO 30 ELSE PRINT "Р езультат:";S:PRINT"Контроль: ";-(4*ATN(1))^2/12:PRINT"Количество по вторений цикла:";N-1 'Напомним, что значение π совпадает с 4*ATN(1) run run ? .1 ? .01 Результат:-.86111111111111 Результат:-.82796217561099 Контроль: -.82246703342412 Контроль: -.82246703342412 Количество повторений цикла: 3 Количество повторений цикла: 10 Оk Ok run ? .001 Результат:-.82297055860543 Контроль: -.82246703342412 Количество повторений цикла: 31 Ок Для проверки работоспособности программы мы воспользовались т е с т о- в ы м примером на основе известного математического результата: ∞ ∑ (-1)ⁿ/n² = -π²/12 . n=1 Наконец, отметим, что в данном примере количество повторений цикла су- щественно зависит от значения переменной E (однако заранее количество по- вторений цикла нам неизвестно!). П р и м е р 5. Написать программу для вычисления ⁿ√A , используя ите- ───────────── рационную формулу Ньютона: X(0)=A; X(k+1)=X(k)+(A/X(k)^(n-1)-X(k))/n, k=1,2,... Вычисления продолжать до тех пор, пока │X(k+1)-X(k)│0 -задан- ное число (впрочем,возможен другой вариант "останова" вычислений по выпол- нению условия │X(K)^N-A│=E THEN GOTO 40 ELSE ? "Результат:";Y run ? 2,12,0.001 Результат: 3.4641016533502 Ok А теперь - проверка: Ok print SQR(12) 3.4641016151377 Ok ...Поверил Я алгеброй гармонию. А.Пушкин. Моцарт и Сальери Обратимся теперь к лирике. Вот стихотворение Л.Мартынова (речь в нем идет о девушке): "Кто геометрическое среднее между атомом и Солнцем? Ты, первое и последнее воплощение красоты. Не имеющая представления о строении вещества, слушающая в изумлении эти непонятные слова. Неспособная принять их к сведению,будучи ужасно молодой. Вот ведь,какова ты,нечто среднее между атомом и звездой." Проверим, прав ли поэт. Масса атома водорода Ма=1.67E-27 кг,масса Солн- ца Mс=1.99E+30 кг.Их произведение найдем в режиме непосредственного выпол- нения команд: print 1.67E-27*1.99E+30 3323.3 Ok Поэт утверждает, что масса девушки (в кг) равна квадратному корню из числа 3323.3 . А тогда, используя ранее написанную программу, получим: run ? 2,3323.3,.001 ▲ │ с точностью до грамма! Результат: 57.648070219218 Ок Результат вполне правдоподобен: вес девушки ≈ 58 кг. III.5. ПРИМЕРЫ Бросая в воду камешки, смотри на круги,ими образуемые: иначе твое занятие будет простой забавой. Козьма Прутков Если я и открыл некоторые новые истины в науках, то я могу утверждать, что все они либо являются прямыми следствиями пяти или шести главных задач, которые мне удалось решить, либо зависят от них;я рассматриваю их как такое же число сражений, в которых военное сча- стье было на моей стороне. Р.Декарт В заключение рассмотрим несколько, на наш взгляд, интересных примеров. Разумеется, некоторые из приведенных ниже программ не являются оптималь- ными по времени выполнения и по занимаемой памяти. Однако есть еще одна величина, которую надо принимать в расчет при оптимизации программы. Это - в р е м я программиста. Программа, требующая много времени на написа- ние и отладку,может оказаться очень дорогой, даже если она расходует мень- ше машинного времени и занимает меньше места в памяти, чем какая-то дру- гая, в целом эквивалентная ей программа. По этой причине распространена практика написания простых и понятных, но относительно медленных программ (для них имеется жаргонное выражение "quick and dirty programs" - "скорые, но грязные программы"). Если программу предлагается выполнить всего один-два раза, или если ее придется часто модифицировать, метод "скорых, но грязных программ" по- чти всегда дает наилучшие результаты! П р и м е р 1. Найти наибольший элемент в одномерном массиве A(N), не ───────────── пользуясь оператором IF (!). Ok 10 DEFINT I,J,N:INPUT N:DIM A(N):X=RND(-TIME):FOR I=1 TO N:A(I)=INT(40 *RND(1)):PRINT A(I);:NEXT:M=1:PRINT 20 FOR I=1 TO N-1:FOR J=I+1 TO N 30 Y=-((A(I)>A(J))*A(I))-(A(I)<=A(J))*A(J):M=-(Y>M)*Y-(Y<=M)*M:NEXT J: NEXT I:PRINT"Наибольший элемент:";M run ? 6 28 33 7 32 28 20 Наибольший элемент: 33 Ok П р и м е р 2. Написать программу, которая для введенной пользователем ───────────── суммы печатает способ выдачи этой суммы наименьшим чис- лом монет (имеются монеты 1,2,3,5,10,15 и 20 копеек). NEW Ok 20 DATA 20,15,10,5,3,2,1 30 PRINT "Введите сумму в копейках" 40 DEFINT S,I:INPUT S 50 IF S<>INT(S) OR S<1 THEN 20 ELSE PRINT"Разменяю-" 70 FOR I=1 TO 7:READ M:K=INT(S/M) 100 IF K>0 THEN PRINT K;"раз";M;"коп.":S=S-K*M ELSE S=S-K*M 120 NEXT I:END run run Введите сумму в копейках Введите сумму в копейках ? 105 ? 555 Разменяю- Разменяю- 5 раз 20 коп. 27 раз 20 коп. 1 раз 5 коп. 1 раз 15 коп. Оk Ok Каждая решенная мною задача становилась образцом, который служил впоследствии для решения других задач. Р.Декарт. Рассуждения о методе ...создается впечатление, что можно построить целый курс программирования, выбирая примеры только из за- дач сортировки. Н.Вирт П р и м е р 3. Напишите программу,располагающую массив слов на англий- ───────────── ском языке по алфавиту (выполняющую лексикографическое упорядочение) методом о б м е н н о й с о р т и р о в к и (методом "пу- зырька"). Ok 10 DEFINT N,I,J:INPUT "Количество слов";N 20 DIM A$(N) 30 FOR I=1 TO N:INPUT A$(I):NEXT 40 FOR I=1 TO N-1:FOR J=I+1 TO N 50 IF A$(I)<=A$(J) THEN 60 ELSE SWAP A$(I),A$(J) 60 NEXT:NEXT 70 FOR I=1 TO N:PRINT A$(I):NEXT run run Количество слов? 5 Количество слов? 5 ? Sedov ? Седов ? Filippov ? Филиппов ? Sokolova ? Соколова ? Shvetski ? Швецкий ? Sedova ? Седова Filippov Филиппов Sedov Седов Sedova Седова Shvetski Соколова Sokolova Швецкий Ok Ok Заметим,что коды ASCII букв русского алфавита не упорядочены в соответ- ствии с алфавитом (например, не соблюдено условие "ВОВА"<"ГЕНА"), так как в компьютере буква "В" следует за буквой "Г" - в соответствии с латински- ми буквами W и G, поэтому вышеприведенная программа не работает для слов, записанных русскими буквами! Следует отметить, что новый стандарт на отечественные персональные ком- пьютеры, принятый в конце 1986 года,кардинально решает проблему- в нем ко- ды русских букв возрастают в строгом соответствии с алфавитом (лексикогра- фически упорядочены), и сортировка строковых переменных ничем не отличает- ся от аналогичной процедуры над числовыми переменными. Но компьютеров с подобным кодированием русского алфавита,к сожалению, пока (1990 г.) очень мало! П р и м е р 4. ───────────── NEW Ok 10 'Сортировка с применением индекса. 11 'Вместо переупорядочения самих значений в процессе сортировки можно образовать вспомогательный массив индексов, в котором отмечаются прави льные места значений в массиве. 12 'Во время сортировки значения остаются на исходных местах,а изменяе тся лишь массив индексов. По окончании сортировки массив индексов испо льзуется для копирования сортируемых значений в новый массив или служи т справочником для работы с исходным массивом. 20 INPUT N:DIM A(N),I(N) 30 FOR M=1 TO N:INPUT A(M):NEXT M 40 FOR L=1 TO N:I(L)=L:NEXT 1000 'Фрагмент пузырьковой сортировки. 1040 FOR M=N TO 2 STEP -1 1050 FOR J=1 TO M-1 1052 I1=I(J):I2=I(J+1) 1060 IF A(I1)>=A(I2) THEN 1100 1070 I(J)=I2:I(J+1)=I1 1100 NEXT J 1110 NEXT M 1120 FOR L=1 TO N:I1=I(L):PRINT A(I1);:NEXT L run ? 4 ? 56 ? 34 ? 87 ? 6 87 56 34 6 Ok П р и м е р 5. В массиве X(1),X(2),...,X(N) каждый элемент равен 0,1 ───────────── или 2. Переставьте элементы массива так, чтобы сначала располагались все нули, затем все единицы, и, наконец, все двойки. Допол- нительного массива не вводить! 10 DEFINT N,I,J:INPUT N:DIM X(N):Z=RND(-TIME) 30 FOR I=1 TO N:X(I)=INT(3*RND(1)):?X(I);:NEXTI 40 FOR I=1 TO N-1:FOR J=I+1 TO N 50 IF X(I)A(I+1) THEN A(I)=A(I)-A(I+1) 50 IF A(I)A(I+1) THEN GOTO 40 70 NEXT 75 'Последний вычисленный НОД выводится на экран. 80 PRINT A(I) run run Введите N? 4 Введите N? 4 Для каких чисел ищется НОД? Для каких чисел ищется НОД? ? 125 ? 12 ? 25 ? 144 ? 625 ? 16 ? 1225 ? 20 25 4 Ok Ok П р и м е р 8. Даны 5 цифр: 0,1,2,3,4. Найти сумму всех трехзначных чи- ───────────── сел, кратных 3, которые можно записать с помощью этих цифр (цифры могут повторяться). NEW Ok 10 DEFINT I-K,S:FOR I=1 TO 4:FOR J=0 TO 4:FOR K=0 TO 4 20 IF (I+J+K)MOD3=0 THEN S=S+I*100+J*10+K 30 NEXT K,J,I:PRINT"Искомая сумма=";S run Искомая сумма= 8937 Ok П р и м е р 9. Найти количество тех трехзначных чисел, которые равны ───────────── сумме факториалов своих цифр (понятием п о д п р о - г р а м м ы не пользоваться!). NEW Ok 10 DEFINT I,J:FOR I=100 TO 999 15 'Ищем факториал старшей цифры! 20 P=1:FOR J=1 TO I\100:P=P*J:NEXT J 25 'Ищем факториал второй цифры! 30 Y=1:FOR J=1 TO (IMOD100)\10:Y=Y*J:NEXT J 40 Z=1:A=(IMOD100)MOD10 45 'Ищем факториал третьей цифры! 50 FOR J=1 TO A:Z=Z*J:NEXT J 60 IF P+Y+Z=I THEN K=K+1:PRINT "Искомые числа:";I 70 NEXT I:PRINT"Количество таких чисел:";K run Искомые числа: 145 Количество таких чисел: 1 Ok Верочка же, получив письмо (она его ждала раньше, еще в марте),не сразу,а как-то по- медлив,словно боясь чего-то,встала и,взяв со стола старинный костяной нож с инкрус- тацией(один перламутровый цветок давно вы- пал,чернело лишь гнездо на месте, куда он был вставлен), и вскрыла конверт неловкой рукой. И.Горелов П р и м е р 10. Найти наименьшее трехзначное число, кратное N, такое, ────────────── что его первая цифра 7 и все его цифры различны. Про- грамму уместить в одну программную строку! 5 DEFINTN,I:INPUTN:Y$="Нет":FORI=700TO799:IFI\100<>(IMOD100)\10THENIFI \100<>IMOD100MOD10THENIF(IMOD100)\10<>IMOD100MOD10THENIFIMODN=0THENY$= "Есть!":CLS:PRINTY$,I:ENDELSEIFI=798THENCLS:PRINTY$:ENDELSENEXTELSENEX TELSENEXTELSENEXT'Пример "абсолютно нечитабельной" программы! run run run run ? 5 ? 70 ? 18 ? 56 Есть! 705 Нет! Есть! 702 Есть! 728 Ok Ok Ok Ok П р и м е р 11. Задан одномерный массив A, элементы которого обозна- ────────────── чим A(1), A(2),..., А(N). Найдите длину самой длинной подпоследовательности подряд идущих элементов массива, равных 0. NEW Ok 10 DEFINT N,I,M,K:INPUT N:DIM A(N):X=RND(-TIME) 20 FOR I=1 TO N:A(I)=INT(2*RND(1)):PRINT A(I);:NEXT 40 FOR I=1 TO N 50 IF A(I)=0 THEN K=K+1:IF K>M THEN M=K:NEXT I ELSE NEXT I ELSE K=0:NE XT I 60 PRINT:PRINT"Максимальная длина:";M run ? 8 ·0··1··0··0··1··1··1··1 Максимальная длина:·2 Ok Программные строки 10-20 позволяют описать массив X и идентифицировать его псевдослучайными целыми числами (для контроля его элементы выводятся на экран в строке 20). Операторы в программных строках 40-60 подсчитывают максимальное количество подряд идущих нулей в массиве и выводят результат на экран. П р и м е р 12. Найдите наибольшую по длине неубывающую подпоследова- ────────────── тельность подряд идущих элементов в данной последова- тельности чисел (в одномерном массиве A(N)). NEW Ok 5 'Идентификация массива A(N) псевдослучайными целыми числами (програ ммные строки 10-20). 10 DEFINT N,I,J,K,M:INPUT N:K=1:DIM A(N):X=RND(-TIME) 20 FOR I=1 TO N:A(I)=INT(12*RND(1)):PRINT A(I);:NEXT 30 'Выделение неубывающей подпоследовательности, сравнение ее длины с длиной предыдущей выделенной подпоследовательности; наибольшая длина запоминается в переменную M (строки 40-70). 40 FOR I=1 TO N-1 50 IF A(I)<=A(I+1) THEN K=K+1:IF K>M THEN M=K:J=I+1:NEXT I ELSE NEXT I ELSE K=1:NEXT I 60 ?:?"Наибольшая длина:";M:PRINT"Подпоследовательность:"; 70 FOR I=J-M+1 TO J:PRINT A(I);:NEXT Ok run ? 8 ·0··9··2··10··1··6··3··5 Наибольшая длина·2 Подпоследовательность:·0··9 Ok П р и м е р 13. Определите, сколько различных элементов встречается в ────────────── одномерном массиве A(N) более чем по одному разу. NEW Ok 5 INPUT"Введите N";N:DIM A(N):X=RND(-TIME) 8 ? "Исходный массив:" 10 FOR I=1TO N:A(I)=INT(10*RND(1)):PRINT A(I);:NEXT 20 FOR I=1 TO N-1:FOR J=I+1 TO N 23 IF A(I)=A(I+1) THEN P=0:NEXT I ELSE IF P=0 THEN K=K+1:P=1:NEXT ELS E NEXT 'P-флажок! 50 PRINT:PRINT K;"элементов в массиве встречаются более одного раза" run Введите N? 13 Исходный массив: 0 4 7 6 7 5 6 1 2 0 5 2 3 5 элементов в массиве встречаются более одного раза Ok П р и м е р 14. Определить количество повторяющихся элементов в одно- ────────────── мерном массиве A(N). NEW Ok 5 INPUT N:DIM A(N) 6 X=RND(-TIME) 7 FOR I=1 TO N:A(I)=INT(10*RND(1)):PRINT A(I);:NEXT:PRINT 10 S=0 20 FOR I=1 TO N 30 P=0 40 FOR J=1 TO N 50 IF A(I)=A(J) THEN P=P+1 60 NEXT J 70 IF P>1 THEN S=S+1 80 NEXT I:PRINT S run run ? 10 ? 7 3 7 5 6 9 6 9 4 5 0 9 2 7 3 0 0 1 6 2 Ok Ok П р и м е р 15. Из заданного на плоскости множества точек выбрать три ────────────── такие, не лежащие на одной прямой, которые будут вер- шинами треугольника: а) наибольшей площади; b) наименьшего периметра. NEW Ok 20 DEFINT H,I-K,M:INPUT"Число точек";H:D=RND(-TIME):M=2*H 30 DIM A(M),B(M),C(M):IF H<3 THEN RUN 20 40 FOR I=1 TO M:A(I)=INT(190*RND(1)):B(I)=A(I):C(I)=A(I):NEXT:S=0:P=90 0 'Генерируем три одинаковых массива координат точек плоскости случайн ым образом. 50 FOR I=2 TO M STEP 2 60 FOR J=2 TO M STEP 2 70 FOR K=2 TO M STEP 2 80 U=SQR((A(I)-B(J))^2+(A(I-1)-B(J-1))^2):Q=SQR((A(I)-C(K))^2+(A(I-1)- C(K-1))^2):W=SQR((B(J)-C(K))^2+(B(J-1)-C(K-1))^2):G=U+Q+W 'Нашли перим етр треугольника. 90 V=SQR((G/2)*(G/2-U)*(G/2-Q)*(G/2-W)) 'Нашли его площадь. 100 IF V<1.E-10 THEN 130'Этим оператором гарантируем, что взяты три ра зличные точки, не лежащие на одной прямой. 110 IF G

S THEN S=V:A3=A(I):A4=A(I-1):B3=B(J):B4=B(J-1):C3=C(K):C4=C(K -1)'Ищем треугольник наибольшей площади и запоминаем координаты его ве ршин 130 NEXT K,J,I 140 PRINT"Вершины треугольника наиб.площади:(";A3;",";A4;"),(";B3;","; B4;"),(";C3;",";C4;");" 150 PRINT"Площадь треугольника:";S 160 PRINT"Вершины треугольника наим.периметра:(";A1;",";A2;"),(";B1;", ";B2;"),(";C1;",";C2;");" 170 PRINT"Периметр треугольника:";P 180 FOR I=1 TO 5000:NEXT 'Задержка по времени (≈13 секунд)! 185 'Графическая иллюстрация полученного результата. 190 SCREEN 2 200 FOR I=2 TO М STEP 2:PSET(A(I),A(I-1)),2:NEXT 210 LINE(A1,A2)-(B1,B2),1:LINE-(C1,C2),1:LINE-(A1,A2),1 220 LINE(A3,A4)-(B3,B4),2:LINE-(C3,C4),2:LINE-(A3,A4),2 230 GOTO 230'На экране изображены искомые треугольники! run Число точек? 5 Вершины треугольника наиб.площади:( 87 , 175 ),( 160 , 85),( 165 , 7 ); Площадь треугольника: 2622.0000000032 Вершины треугольника наим.периметра:( 142 , 57 ),( 165 , 7 ),( 161 , 2 4 ); Периметр треугольника: 110.57946634916 Далее следует графическая иллюстрация полученного решения. П р и м е р 16. Конечное множество из N точек в трехмерном пространст- ────────────── ве задано своими координатами: (X(N),Y(N),Z(N)), N=1,2,...,n. Составьте программу подсчета количества тех точек данного множества, которые принадлежат: а) шару x²+y²+z²≤25; c) пересечению шара и полупространства; b) полупространству x+y+z≤3; d) объединению шара и полупространства. NEW Ok 5 'Идентификация массивов X,Y,Z псевдослучайными целыми числами (прог раммные строки 10-30). 10 DEFINT N,I:INPUT "Количество точек";N 20 DIM X(N),Y(N),Z(N):U=RND(-TIME) 25 PRINT " X Y Z " 30 FOR I=1 TO N:X(I)=INT(11*RND(1)-5):Y(I)=INT(11*RND(1)-5):Z(I)=INT(1 1*RND(1)-5):PRINTX(I)Y(I)Z(I):NEXT 35 'Подсчет количества точек,лежащих в шаре (строки 40-60). 40 FOR I=1 TO N 50 IF(X(I)^2)+(Y(I)^2)+(Z(I)^2)<=25THENK=K+1:NEXTELSE NEXT 60 PRINT "Количество точек,лежащих в шаре:";K 65 'Подсчет количества точек, принадлежащих полупространству (строки 70-90). 70 FOR I=1 TO N 80 IF X(I)+Y(I)+Z(I)<=3 THEN C=C+1:NEXTI ELSE NEXTI 90 PRINT "Количество точек,принадлежащих полупространству:";C 95 'Подсчет количества точек,лежащих в шаре и одновременно в полупрост ранстве (строки 100-120). 100 FOR I=1 TO N 110 IF X(I)+Y(I)+Z(I)=<3 AND (X(I))^2+(Y(I))^2+(Z(I))^2<=25 THEN B=B+1 :NEXT ELSE NEXT 120 PRINT "Количество точек,принадлежащих пересечению шара и полупрост ранства:";B 125 'Подсчет количества точек,принадлежащих объединению шара и полупро странства (строки 130-140) 130 P=C-B+K 140 PRINT "Количество точек,принадлежащих объединению шара и полупрост ранства:";P run Количество точек? 5 X Y Z 0 -3 3 -4 -4 4 4 5 4 -5 5 1 -1 4 4 Количество точек,лежащих в шаре: 1 Количество точек,принадлежащих полупространству: 3 Количество точек,принадлежащих пересечению шара и полупространства: 1 Количество точек,принадлежащих объединению шара и полупространства: 3 Ok П р и м е р 17. В заданном двухмерном массиве A(N,M) найти минимальное ────────────── из чисел, встречающееся там более одного раза. NEW Ok 5 'Описание массива A(N,M) и заполнение его псевдослучайными целыми чи слами (строки 10-20). 10 DEFINT I,J,N,M,Y,K,L:INPUT N,M:DIM A(N,M):X=RND(-TIME) 20 FOR I=1 TO N:FOR J=1 TO M:A(I,J)=INT(10*RND(1)):PRINT A(I,J);:NEXT J:PRINT:NEXTI:IF N+M=2 THEN RUN10 30 'Идентификация дополнительного массива B (строки 40-50). 40 K=N*M:DIM B(K) 50 FORI=1TO N:FOR J=1 TO M:Y=M*(I-1)+J:B(Y)=A(I,J):NEXTJ,I 60 'Этот блок (строки 70-110) позволяет найти минимальное число элемен тов, встречающихся в массиве более одного раза. 70 FOR Y=1 TO K-1:FOR L=Y+1 TO K 80 IF B(Y)B(I+1) THEN U=U+1:NEXT I ELSE NEXT I 120 PRINT"Количество разл.элементов:";U run run ? 3,3 ? 3,4 ·9··6··9 ·1··5··3··5 ·3··9··4 ·8··9··7··5 ·2··1··8 ·0··4··4··9 Количество разл.элементов:·7 Количество разл.элементов:·8 Ok Ok П р и м е р 19. Проверьте, есть ли в двухмерном массиве C(M,N) отрица- ────────────── тельные элементы, если есть, найдите среди них тот, у которого сумма индексов будет наименьшей. NEW Ok 5 'Идентификация массива A(M,N) (строки 10-30). 10 DEFINT M,N,I,J,K:INPUT M,N:DIM A(M,N):K=N+M:X=RND(-TIME) 20 FOR I=1 TO M:FOR J=1 TO N 30 A(I,J)=INT(11*RND(1)-5):PRINT A(I,J);:NEXTJ:?:NEXT I 45 IF M=1 AND N=1 THEN IF A(1,1)<0 THEN ?"Искомый элемент:";A(1,1):END ELSE ?"Такого элемента нет!":END'Случай M=N=1 47 'Нахождение отрицательного элемента массива A, у которого сумма инд ексов минимальна (строки 50-70). 50 FOR I=1 TO M:FOR J=1 TO N 60 IF A(I,J)<0 THEN IF I+JC THEN C=B:B=0:NEXT K ELSE B=0:NEXT K 55 'Нахождение максимальной среди сумм элементов диагоналей, расположе нных ниже главной (строки 60-70). 60 FOR K=1 TO M-1:FOR I=1 TO M:FOR J=1 TO M 70 IF J=I-K THEN B=B+A(I,J):NEXT J:NEXTI ELSE NEXTJ:NEXTI:IF B>D THEN D=B:B=0:NEXT K ELSE B=0:NEXT K 80 IF C>D THEN PRINT C ELSE PRINT D 'Сравнение этих максимумов и выво д большего на экран дисплея. run run run ? 4 ? 3 ? 5 ·5··8··4··8 ·3··6··6 ·2··0··5··7··7 ·0··3··2··7 ·8··0··2 ·9··6··7··2··9 ·6··6··7··3 ·3··6··2 ·9··9··8··5··5 ·7··6··6··9 ·14 ·6··9··1··1··7 ·13 Ok ·7··3··9··8··3 Ok ·27 Ok П р и м е р 22. Вычислить сумму тех элементов двуxмерного целочислен- ────────────── ного массива A(M,N), в десятичной записи которых ис- пользуются только цифры 0,1,2,3. NEW Ok 10 DEFINT M,N,I,J,K,А:INPUT"Введите M и N";M,N 20 INPUT"Числовой отрезок[X,Y]";X,Y 30 Z=RND(-TIME):DIM B(M,N),A(M,N) 40 'Заполнение массива B(M,N) псевдослучайными целыми числами из отрез ка[X,Y](строки 50-70) 50 FOR I=1 TO M:FOR J=1 TO N:B(I,J)=INT((Y-X+1)*RND(1)+X):A(I,J)=B(I,J ):NEXT J,I 80 S=0:FOR I=1 TO M:FOR J=1 TO N 90 'Пока не просмотрим все цифры числа A(i,j),выполняем цикл "пока"(ст роки 100-160) 100 IF A(I,J)=0 THEN 180 ELSE FOR K=1 TO 0 STEP 1 120 B=ABS(A(I,J))-INT(ABS(A(I,J))/10)*10 'Выделяем последнюю цифру чис ла A(i,j) 130 IF B>=4 THEN 180 ELSE A(I,J)=(ABS(A(I,J))-B)/10 150 K=A(I,J) 'проверка условия: если A(i,j)=0,то из цикла "пока" выход им 160 NEXT K 170 IF A(I,J)=0THEN S=S+B(I,J)'Ищем сумму нужных элементов 180 NEXT J,I:FOR I=1 TO M:FOR J=1 TO N 210 PRINT B(I,J);:NEXT J:PRINT:NEXT I:?"Искомая сумма:";S run Введите M и N? 4,6 Числовой отрезок[X,Y]? 1,9 9 4 9 3 5 6 3 1 6 4 3 3 1 9 2 3 9 1 3 8 4 8 9 2 Искомая сумма: 25 Ok П р и м е р 23. Подсчитайте количество элементов двухмерного массива ────────────── A(M,N) натуральных чисел, которые являются составными. NEW Ok 10 DEFINT M,N,I,J,A,K:INPUT"Введите M и N";M,N:X=RND(-TIME):DIM A(M,N) :IF M<1 OR N<1 THEN RUN 10 30 FOR I=1 TO M:FOR J=1 TO N 40 A(I,J)=INT(30*RND(1)+1):IF A(I,J)=2 THEN PRINTUSING"\ \";STR$(A(I, J))+"*";:NEXT:PRINT:NEXT 50 K=0:FOR K=2 TO A(I,J)-1 60 IF A(I,J)/K<>FIX(A(I,J)/K) THEN NEXT K:PRINTUSING"\ \";STR$(A(I,J) )+"*";:NEXT J:PRINT:NEXT I ELSE Y=Y+1:PRINT USING"\ \";STR$(A(I,J))+ " ";:NEXT J:PRINT:NEXT I 70 PRINT"Звездочками отмечены простые числа;составных чисел в Вашем ма ссиве";Y run Введите M и N? 3,5 ·27··20··25··0···2* ·26··17*·23*·2*··23* ·20··12··22··9···21 Звездочками отмечены простые числа;составных чисел в Вашем массиве·10 Ok В этой программе во время идентификации массива A(M,N) случайными чис- лами сразу же производится проверка каждого элемента массива: является ли он простым? Если "да",то на экран этот элемент выводится со "звездочкой" ("*") позади. Если "нет", то - без нее. Затем подсчитывается количество составных чисел и результат выводится на экран. П р и м е р 24. Х а р а к т е р и с т и к о й столбца целочисленной ────────────── матрицы назовем сумму модулей ее отрицательных четных элементов. Переставляя столбцы заданной матрицы, расположить их в соответ- ствии с ростом характеристик. NEW Ok 10 DEFINT M,N,I,J,W,K,B,D:INPUT"Укажите M,N";M,N 15 IF M<2 OR N<2 THEN PRINT "Слишком малое количество столбцов (строк) !":RUN 10 20 INPUT"Числовой отрезок[X,Y]";X,Y 30 Z=RND(-TIME):DIM A[M,N],Q[M,N],L[N],F[N] 40 'Заполняем массив A[M,N] случайными целыми числами из отрезка [X,Y] и копируем его в массив Q[M,N](строки 50-70) 50 FOR I=1 TO M:FOR J=1 TO N 60 A[I,J]=INT((Y-X+1)*RND(1)+X):Q[I,J]=A[I,J] 70 NEXT J,I 80 'Находим характеристики столбцов(строки 90-110) 90 FOR J=1 TO N:FOR I=1 TO M 100 IF A[I,J]<0 AND ABS(A[I,J])MOD2=0 THEN L[J]=L[J]+ABS(A[I,J]) 110 F[J]=L[J]:NEXT I,J 120 'Упорядочиваем столбцы по возрастанию характеристик(строки 130-180) 130 FOR W=1 TO N-1 'Удивительный цикл! 140 FOR B=1 TO N-1:FOR K=B+1 TO N 150 IF L[B]<=L[K] THEN 180 ELSE SWAP L[B],L[K] 170 FOR D=1 TO M:SWAP A[D,B],A[D,K]:NEXT D 180 NEXT K,B,W 190 'Вывод результатов 200 FOR I=1 TO M 210 FOR J=1 TO N:PRINT USING"####";Q[I,J];:NEXTJ:? SPC(4) 220 FOR J=1 TO N:PRINT USING"####";A[I,J];:NEXT J:PRINT 230 NEXT I 240 FOR H=0 TO 30:PRINT "-";:NEXT H:PRINT 250 'А теперь заполняем строки характеристик! 260 FOR J=1 TO N:PRINT USING"####";F[J];:NEXT:? SPC(4) 270 FOR J=1 TO N:PRINT USING"####";L[J];:NEXT run Укажите M,N? 4,3 Числовой отрезок[X,Y]? -40,10 -17 -18 -6 -6 -17 -18 -23 -16 1 1 -23 -16 1 -38 7 7 1 -38 -12 -5 -1 -1 -12 -5 ------------------------------ 12 72 6 6 12 72 ◀──── строки характеристик Ok Подумайте, каким был бы результат тестового примера, если бы в програм- ме отсутствовал цикл с параметром W (строки 130-180). П р и м е р 25. Вычисление определенного интеграла от функции,заданной ────────────── на отрезке [-1,1], по квадратурной формуле Гаусса. NEW Ok 10 DEFINT N,I:DEF FNF(Z)=Z*SIN(Z) 20 INPUT"Порядок интегрирования=";N:DIM X[N],H[N] 40 IF N=2 THEN RESTORE 160 50 IF N=3 THEN RESTORE 170 60 IF N=4 THEN RESTORE 180 70 IF N=5 THEN RESTORE 190 80 FOR I=1 TO N:READ X[I]:NEXT 90 IF N=2 THEN RESTORE 200 100 IF N=3 THEN RESTORE 210 110 IF N=4 THEN RESTORE 220 120 IF N=5 THEN RESTORE 230 130 FOR I=1 TO N:READ H[I]:NEXT:J=0 140 FOR I=1 TO N:J=J+FNF(X[I])*H[I] 150 NEXT:PRINT "Интеграл=";J:END 155 'Коэффициенты метода Гаусса. 160 DATA-.57735026919, .57735026919 170 DATA-.774596669241,0 , .774596669241 180 DATA-.861136311594,-.339981043585,.339981043585,.861136311594 190 DATA-.906179845939,-.538469310106,0,.538469310106,.906179845939 200 DATA 1,1 210 DATA .55555555555556,.88888888888889,.55555555555556 220 DATA .347854845137,.652145154863,.652145154863,.347854845137 230 DATA .236926885056,.478628670499,.56888888888889,.478628670499,.23 6926885056 run run Порядок интегрирования=? 2 Порядок интегрирования=? 4 Интеграл= .6302420371144 Интеграл= .6023395913427 Ok Ok