====== Глава III ====== |{{..author_files:003.msx|}}|{{..author_files:003.txt|}}|[[..003|]]| @@ -1,14 +1,11 @@ -c1E +\/d ГЛАВА III. ПРОГРАММИРОВАНИЕ РАЗВЕТВЛЯЮЩИХСЯ И ЦИКЛИЧЕСКИХ АЛГОРИТМОВ - - +\/d- ... и если ничто уже не помогает - посмотри инструкцию для пользователя. Из завещания неизвестного программиста - - Линейные алгоритмы и соответствующие им программы редко встречаются в практике решения на компьютере реальных задач. Ведь неизменная последо- вательность действий, как правило, не может соответствовать изменяющимся @@ -21,20 +18,15 @@ т и ч е с к и й объект - текст программы - быть построен таким образом, чтобы дать ясное представление о динамической ситуации - ее выполнении? - - III.1. ОПЕРАТОР БЕЗУСЛОВНОЙ ПЕРЕДАЧИ УПРАВЛЕНИЯ GOTO - - ...квалификация программистов является убывающей функцией от - плотности предложений GOTO в создаваемых ими программах. + ...квалификация программистов является убы- + вающей функцией от плотности предложений + GOTO в создаваемых ими программах. Э.Дейкстра - - Выполнение операторов в программе осуществляется в порядке их естест- венного следования. Оператор GOTO ("to go to"-"перейти") позволяет нару- -шить этот порядок. - Оператор безусловной передачи управления имеет следующую структуру: +шить этот порядок. Приведем структуру оператора GOTO n , где: GOTO ("to go to"-"перейти") - служебное слово; n - любой существующий номер строки в программе; 0≤n≤65529 . @@ -64,10 +56,8 @@ но читаемой для программиста - приходится особо следить за тем, в каком порядке выполняются строки программы. Отметим,что в школьный алгоритмичес- кий язык эта конструкция не включена вообще! - П р и м е р ы: 1) 20 GOTO 20 'Зацикливание обеспечено! Стандартный при- ───────────── ем при работе с графикой. - 2) NEW Ok 5'Пример плохой,трудно читаемой программы! @@ -77,15 +67,12 @@ 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" и т.д. Пользователь,разумеется,может вмешаться и остановить @@ -95,7 +82,7 @@ В случае, если оператор записывается двумя служебными словами GO TO n, то он выполняется аналогично - этот формат сохранен для совместимости с другими языками программирования. - Однако, использовать "двухсловную" форму GOTO не рекомендуется,так как + Однако использовать "двухсловную" форму GOTO не рекомендуется, так как она требует большого объема памяти для хранения. Достигаемая экономия на первый взгляд несущественна, однако рано или поздно многие программисты попадают в ситуацию, когда "нескольких битов не хватает!" @@ -109,15 +96,10 @@ FOR...NEXT, которые являются простейшими эквивалентами управляющих конст- рукций Бема и Якопини. - - III.2. ОПЕРАТОР УСЛОВНОЙ ПЕРЕДАЧИ УПРАВЛЕНИЯ IF - ЕСЛИ нельзя, но очень хочется, ТО можно! Евг.Сазонов, программовед и языколюб - - Сказочные герои, как известно, по дороге за тридевять земель в триде- сятое царство встречали на перекрестке камень с надписью - альтернативой. У программиста при написании программы возникает потребность запрограмми- @@ -160,9 +142,7 @@ ализованы только "усеченные"конструкции оператора IF - без ветви "иначе" (т.е.без служебного слова ELSE): IF условие THEN n1 , IF условие THEN O1 . - Теперь рассмотрим несколько примеров: - 1) 300 DEFDBL A,B:IF A=B GOTO 700'Внимание!Может оказаться,что два чис ла,которые должны быть р а в н ы м и, все-таки н е м н о г о отл ичаются из-за ошибок округления! Переход на строку с номером 700 мо @@ -182,7 +162,6 @@ ? 4 ? 1 15.999999999999 .99999999999999 Ok Ok - 2) 10 INPUT A,A! 20 IF A!=A THEN PRINT "Верно!":END ELSE PRINT "Посмотрите комментар ий к предыдущему примеру!":END @@ -190,23 +169,18 @@ ? 0.000001000002,0.000001000002 Посмотрите комментарий к предыдущему примеру! Ok - 3) 10 IF AN не соблюдено, поэтому следует переход к строке 60. Условие MN (M не равно N) то- -же соблюдено и поэтому строка 70 передает управление назад, строке 50. +же соблюдено, и поэтому строка 70 передает управление назад, строке 50. Теперь M имеет значение 34, а N - значение 17, и условие M>N соблюдено; поэтому переменной M присваивается значение 34-17=17. M=N=17.Условие стро- ки 60 не соблюдено, условие M<>N строки 70 тоже не соблюдено, и компьютер, @@ -298,7 +266,6 @@ го общего кратного (НОК) двух натуральных чисел. В алгоритме используем тот факт, что произведение НОК и НОД двух чисел равно произведению самих чисел (в программе - переменная К). - NEW Ok 10 DEFINT M,N,K:INPUT"Введите M,N";M,N:K=M*N @@ -327,7 +294,6 @@ л о в и я; при этом следует помнить, что если результат его вычисления от- личен от нуля, то значением условия является TRUE, во всех остальных слу- чаях - FALSE . - П р и м е р. IF X <> 0 THEN ... идентично записи ─────────── IF X THEN ... Отметим, что с п и с о к о п е р а т о р о в может содержать опера- @@ -336,14 +302,14 @@ Например, алгоритм нахождения большего из трех чисел 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 условие1 THEN IF условие2 THEN O1 ELSE O2 , то сразу же возникает вопрос: к какому IF (первому или второму)принадлежит фраза ELSE O2 (как говорят, ELSE "болтается"!)? Для устранения возможной двусмысленности учтите, что любой ELSE "связы- @@ -382,7 +348,6 @@ ? 0 ? 1 ? 2.5 ? 4 X≤1 X≤1 1≤X<3 X>3 Ok Ok Ok Ok - 2) NEW Ok 10 INPUT X @@ -393,7 +358,6 @@ ? 0 ? 1 ? 2.5 ? 4 x≤1 x≤1 1≤x<3 x≥3 Ok Ok Ok Ok - 3) составить программу, определяющую, каким должен быть Ваш идеальный вес, по следующему алгоритму (формула Мэгони, уточненная К. Купером).Муж- чина берет свой рост в дюймах, умножает это число на 4 и вычитает 128.Жен- @@ -429,7 +393,6 @@ Ваш идеальный вес: 73.249 кг Ok - 4) составить программу решения квадратного уравнения a·x² + b·x + c = 0 . NEW @@ -467,12 +430,9 @@ решений нет и так далее... - Целые числа сотворил господь бог, все остальное - дело рук человеческих. Л.Кронекер - - 5) написать программу, которая выводит на экран разложение введенного в компьютер натурального числа на простые сомножители, например, 24=2*2*2*3, 17=17 . @@ -491,7 +451,7 @@ ? 111 ? 1111 111 = 3 * 37 1111 = 11 * 101 Ok Ok - Далее, легко получаются следующие результаты: + Далее легко получаются следующие результаты: 11111 = 41 * 271 111111 = 3 * 7 * 11 * 13 * 37 1111111 = 239 * 4649 @@ -499,8 +459,8 @@ ··· ··· 11111111111111 = 11 * 239 * 4649 * 909091 Объектом исследования в данной программе являются числа, записанные це- -почкой единиц, р е п ь ю н и т ы (от английского "repeated unit"-"повто- -ренная единица"): 1,11,111, и т.д. Этот термин придумал в 1964 году амери- +почкой единиц, р е п ь ю н и т ы (от английского "repeated unit"- повто- +ренная единица) : 1,11,111, и т.д. Этот термин придумал в 1964 году амери- канец А. Бейлер. Первую же работу об этих удивительных числах написал дву- мя столетиями раньше Иоганн-III Бернулли в связи с исследованиями периоди- ческих десятичных дробей. В 1895 году француз Э.Люка в книге "Заниматель- @@ -540,13 +500,12 @@ рой он находится. В школьном алгоритмическом языке введена еще одна команда - команда п р о в е р к и к о н т р о л ь н о г о у с л о в и я - утв у с л о в и е + утв у с л о в и е . ─── Если в процессе исполнения алгоритма условие нарушается, то компьютер прекращает исполнение алгоритма и сообщает, что возник отказ. Аналогом данной команды в MSX-BASIC может служить, например, конструк- ция IF...THEN...ELSE в следующем примере: - NEW Ok 10 'Вычисление значения функции y=√(x-2) @@ -559,14 +518,13 @@ III.3. ОПЕРАТОР ON GOTO - Общая форма записи оператора-переключателя (оператора выбора по целому значению) следующая: - ON β GOTO N1,N2,...,Nk + ON β GOTO N1,N2,...,Nk , где: ON ("на"), GOTO ("идти к") - служебные слова; β - арифметическое выражение, целая часть значения которого должна принадлежать отрезку [0,255]; - 3) N1,N2,...,Nk - номера программных строк; оператор ON GOTO воспри- + N1,N2,...,Nk - номера программных строк; оператор ON GOTO воспри- нимает столько номеров строк в списке,сколько Вы сможете записать в одной логической строке (помните, что она ограничена 255 символами!). Выполнение оператора ON начинается с вычисления целой части значения @@ -577,7 +535,6 @@ Если же p<0, то последует сообщение об ошибке "Illegal function call" ("Н е п р а в и л ь н ы й в ы з о в ф у н к ц и и"). - П р и м е р ы: ───────────── 1) NEW @@ -597,7 +554,6 @@ ? -1 Ok Illegal function call in 20 Ok - Оператор ON GOTO удобен, когда выполнение одной или нескольких различ- ных ветвей алгоритма определяется значением переменной или выражения (так называемый выбор п о з н а ч е н и ю). Если эти ветви к о р о т к и е, @@ -700,16 +656,12 @@ жет быть любым,а в выборе по значению условие определяется значением ариф- метического выражения. - - III.4. ПРОГРАММИРОВАНИЕ ЦИКЛОВ - - Три месяца каждую вторую среду он ходил смотреть фильм - "Девушка моей мечты", но на связь с ним никто не вышел. + Три месяца каждую вторую среду он ходил + смотреть фильм "Девушка моей мечты", но + на связь с ним никто не вышел. В.Кожевников - - Понятие цикла является одним из основополагающих понятий информатики. Считается,что если бы в программах не было возможности организовывать цик- лы, то применять ЭВМ для решения многих задач не имело бы никакого смысла. @@ -721,8 +673,7 @@ приказания от старухи и снова ──▶ к морю, к золотой рыбке. Параметром цикла (в терминах языка BASIC) здесь выступает алчность ста- рухи, которая увеличивается при каждом новом прохождении циклического -участка. - Программы, содержащие циклы, называются ц и к л и ч е с к и м и . +участка. Программы, содержащие циклы, называются ц и к л и ч е с к и м и. Цикл, не содержащий внутри себя других циклов,называется п р о с т ы м. В противном случае его называют к р а т н ы м или в л о ж е н н ы м. В школьном алгоритмическом языке для записи циклических алгоритмов при- @@ -736,10 +687,9 @@ оператор начала цикла (оператор FOR),оператор конца цикла (оператор NEXT). Операторы FOR и NEXT, как правило(!), используются совместно. Оператор начала цикла (его называют еще з а г о л о в к о м цикла) -имеет вид: FOR i = α TO β [ STEP γ ] +имеет вид: FOR i = α TO β [ STEP γ ] . Здесь: FOR ("для"), TO ("до"), STEP ("шаг"), NEXT ("следующий") - служеб- -ные слова; - i - имя числовой переменной (без индекса!); +ные слова; i - имя числовой переменной (без индекса!); α,β,γ - арифметические выражения. Вслед за оператором н а ч а л а цикла располагают операторы программы, которые должны выполняться циклически(эти операторы образуют т е л о цик- @@ -779,7 +729,6 @@ Заметим, что при л ю б ы х значениях α,β,γ тело цикла будет выполне- но х о т я бы о д и н раз (в отличие от школьного алгоритмического языка и других языков программирования!)! - П р и м е р: NEW ─────────── Ok 10 FOR A=1 TO 10 STEP-1 @@ -788,7 +737,6 @@ run 1 Ok - Эта программа выведет на экран только начальное значение параметра цик- ла A=1. При первой же встрече с оператором NEXT A будет обнаружено,что ко- нечное значение параметра цикла (A=10) уже "позади"! @@ -805,6 +753,7 @@ ··· 100 K=K+2 110 IF K<=4 GOTO 20 ··· + Отметим, что оператор цикла FOR...NEXT можно располагать на одной про- граммной строке. Это целесообразно делать, если тело цикла состоит из од- ного-двух операторов. Например: @@ -825,26 +774,23 @@ В а ж н о е з а м е ч а н и е ! Значения переменных α,β,γ можно изменять операторами, находящимися в теле цикла! Следующие две программы идентичны: - 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 ? A;B;H:NEXT 25 ? A;B;H:NEXT + 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 @@ -858,7 +804,6 @@ 6 5 Ok - Следовательно, изменить начальное и конечное значения параметра цикла, а также значение шага можно только(!)с помощью обращения к заголовку цикла. Таким образом, операторы, находящиеся в теле цикла могут управлять чис- @@ -883,38 +828,34 @@ по окончании цикла значение параметра 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 ?I;:I=I+1:?I 30 H=H+1:I=I+H:?H;I + 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:?I + 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 @@ -934,42 +875,34 @@ Искомый индекс: 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:?M + 30 M=I^2: PRINT M 40 NEXT I:END 100 I=I+3:GOTO 30 'Возвращение в тело цикла! run 16 25 Ok - Приведенный пример показывает, как, используя оператор GOTO,можно "рас- ширить" тело цикла, включив в него произвольные части программы. - - П р и м е р ы п р о с т ы х ц и к л о в - - 5% текста программы занимают 90% времени ее выполнения. + 5% текста программы занимают 90% + времени ее выполнения. Аксиома программирования - - 1) 10 FOR I=1 TO 1000:NEXT 'Задержка ≈ 2.35 секунды Применение оператора цикла с "пустым" телом позволяет получить эффект з а д е р ж к и по в р е м е н и. Запомните этот трюк! - 2) Ok 10 'Признание в любви! 20 INPUT"Введите целое число N";N% @@ -984,7 +917,6 @@ │ кц ── так как тело цикла не зависит от параметра цикла. - 3) Ok 10 DEFINT N,I:INPUT "Введите N";N 20 DIM A(N) 'Массив А описан! @@ -996,13 +928,12 @@ 10 DIM A(5) 'Массив A содержит 6 элементов! 20 DATA 1.,2.,3.,4.,5.,6. 30 FOR I=0 TO 5:READ A(I):NEXTI - 4) и н и ц и а л и з а ц и я массива (присвоение начальных значений) целыми псевдослучайными числами, принадлежащими отрезку [A,B]: NEW Ok 10 DEFINT N,I,C:INPUT A,B,N:DIM C(N) - 20 X=RND(-TIME) 'начальная установка генератора псевдослучайных + 20 X=RND(-TIME) 'Начальная установка генератора псевдослучайных чисел 30 FOR I=1 TO N 40 C(I)=INT((B-A+1)*RND(1)+A):?C(I);NEXTI @@ -1012,8 +943,7 @@ Ok З а м е ч а н и е. Как можно чаще применяйте указанный способ инициали- зации массива псевдослучайными числами при т е с т и р о в а н и и (про- -цессе обнаружении ошибок) Ваших программ! - +цессе обнаружения ошибок) Ваших программ! 5) NEW Ok 10 'Табулирование функции y=exp(sin(x)) на [A,B] с шагом H. @@ -1027,10 +957,9 @@ 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. +причем на первой половине отрезка - с шагом h, a на второй половине от- +резка - с шагом h/2. Приведенные ниже программы эквивалентны и дают полное представление о работе оператора FOR...NEXT . a) NEW b) NEW @@ -1046,12 +975,11 @@ ? 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 + .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. Предостережем от н е в е р н о г о (в принципе!) решения: @@ -1065,7 +993,6 @@ Поэтому верное решение будет, например, таким: 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)· @@ -1074,7 +1001,6 @@ 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),... определяется по следующим рекуррентным формулам: @@ -1106,7 +1032,6 @@ ··· n= 63 A= 6557470319842 Ok - Как уже говорилось, тело цикла может содержать второй цикл - в н у т- р е н н и й по отношению к первому, в н е ш н е м у циклу ("бумажные стаканчики"). Внутренний цикл должен целиком содержаться в теле внешнего @@ -1115,7 +1040,6 @@ появлению на экране сообщения об ошибке: "NEXT without FOR in ..." ("О п е р а т о р NEXT б е з о п е р а т о р а FOR в с т р о к е ..."). - П р и м е р. NEW ─────────── Ok 10 FOR I=1 TO 3:FOR J=2 TO 4 @@ -1124,7 +1048,6 @@ run NEXT without FOR in 30 Ok - Тело внутреннего цикла в свою очередь может содержать еще один цикл, внутренний по отношению к нему и так далее. Интерпретатор MSX-BASICa уста- навливает максимальную "глубину" (число) вложений циклов, однако она на- @@ -1132,7 +1055,7 @@ Учтите, что каждый оператор FOR...NEXT занимает при работе 25 байтов с т е к а , причем стек освобождается только при завершении цикла, после последнего выполнения оператора NEXT! - Тем не менее, если программа использует слишком много цикловодновре- + Тем не менее, если программа использует слишком много циклов одновре- менно, может возникнуть сообщение об ошибке: "Out of memory" ("В ы х о д з а п р е д е л ы п а м я т и"). @@ -1141,24 +1064,22 @@ сок параметров циклов, разделенных запятыми: первое имя в списке соответ- ствует самому внутреннему, последнее - самому внешнему циклу. - П р и м е р ы в л о ж е н н ы х ц и к л о в + П р и м е р ы в л о ж е н н ы х ц и к л о в 1) Ok 2) Ok - 10 FOR X=1 TO 100 10 'Инициализация диагональ - 20 FOR Y=1 TO 10 ной (единичной) матрицы X(3,3) + 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):? MAS(J,I):NEXT J,I + 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}. @@ -1173,7 +1094,6 @@ Ok Сравните полученные результаты с таблицей, приведенной ранее в разделе I.7.2. - 5) NEW Ok 5'"Удобный" вывод на экран двумерного массива. @@ -1187,7 +1107,6 @@ 3 4 5 6 0 4 5 3 Ok - Операторы FOR и NEXT,как правило,должны идти в паре и быть согласованы друг с другом. Если оператор NEXT выполняется раньше оператора FOR с тем же параметром цикла, то при выполнении такого NEXT выдается сообщение об @@ -1205,8 +1124,8 @@ │ кц ── Oтметим, что в некоторых версиях BASIC (например, для персональных ком- -фирмы IBM: IBM PC, IBM PC/XT, IBM PCjr) существует конструкция, почти до- -словно повторяющая цикл "пока"; +пьютеров фирмы IBM: IBM PC, IBM PC/XT, IBM PCjr) существует конструкция, +почти дословно повторяющая цикл "пока"; ──── ее структура ([11], с.74): WHILE у с л о в и е @@ -1226,10 +1145,9 @@ из-под Вашего контроля, н е п а н и к у й т е ! В MSX-BASIC предусмот- рена возможность п р е р ы в а н и я программы - одновременным нажатием на две клавиши "CTRL"+"STOP". - - Метод решения хорош, если с самого начала мы можем предвидеть - и далее - подтвердить это, - что, следуя этому методу, мы достигнем цели. - Г.В.Лейбниц + Метод решения хорош,если с самого начала мы можем предвидеть - и да- + лее подтвердить это, - что, следуя этому методу, мы достигнем цели. + Г.Лейбниц Истина всегда оказывается проще,чем можно было предположить. Р.Фейнман Попытаемся циклом FOR...NEXT(!) описать цикл "пока". Следующая весьма @@ -1246,7 +1164,6 @@ 60 . . . 'Продолжение программы. Если в операторе IF использовать указатель шага цикла STEP 0, то цикл будет бесконечным. И н о г д а(?) это бывает полезным! - П р и м е р 1. Вычислить сумму вида: ───────────── k S = ∑ n @@ -1262,11 +1179,9 @@ ? 100 5050 Тестовый пример: 5050 Оk - Ясно,что в приведенной программе можно применить оператор цикла FOR... NEXT, поэтому рассмотрим пример, где использование оператора цикла FOR... NEXT не помогает. - П р и м е р 2. Пусть для данного положительного числа S требуется на- ───────────── йти наибольшее натуральное K, такое, что Ok S ≥ 1² + 2² + ··· + K² . @@ -1281,16 +1196,14 @@ ? 23 ? 300 3 9 Ok Ok - Из сопоставления примеров 1 и 2 ясно, что цикл "для" используется,как ─── правило,когда количество исполнений цикла известно заранее. Если же число исполнений определить нельзя, если цикл должен быть прерван не по достиже- -нию параметром цикла конечного значения,а по какому-то другому условию (в +нии параметром цикла конечного значения,а по какому-то другому условию (в примере 2: S ≤ 1²+2²+···+k²), необходим цикл "пока". ──── - Прежде чем решать задачу,подумай,что делать с ее решением. Р.Хемминг В науке часто недостаточно решить какую-нибудь задачу или @@ -1299,8 +1212,6 @@ решая одну задачу,мы автоматически находим ответ и на дру- гой вопрос, о котором раньше вовсе не думали. Н.Винер - - П р и м е р 3. Составить программу нахождения суммы возрастающей ариф- ───────────── метической прогрессии. NEW @@ -1324,7 +1235,6 @@ ? 20,2,1 Прогрессия должна быть возрастающей! Повторите ввод! ? ... - Другой способ программирования на языке программирования MSX-BASIC цик- ла WHILE...WEND предполагает использование "о п а с н о г о" оператора GOTO: 10 GOTO 100 @@ -1343,35 +1253,35 @@ · · · 1200 RETURN FIXME + + П р и м е р 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)^N/N^2 20 FOR I=1 TO SQR(1/E) - 30 GOTO 50 30 S=S+(-1)^I/I^2 - 40 S=S+A:N=N+1:A=(-1)^N/N^2 40 NEXT I + 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 - - c) NEW + b) NEW Ok 10 INPUT E - 20 S=0:N=1:A=(-1)^N/N^2 - 30 IF ABS(A)>=E THEN S=S+A:N=N+1:A=(-1)^N/N^2:GOTO 30 ELSE PRINT "Р + 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 Результат:-.81796217561099 + Результат:-.86111111111111 Результат:-.82796217561099 Контроль: -.82246703342412 Контроль: -.82246703342412 Количество повторений цикла: 3 Количество повторений цикла: 10 Оk Ok @@ -1381,16 +1291,14 @@ Контроль: -.82246703342412 Количество повторений цикла: 31 Ок - Для проверки работоспособности программы мы воспользовались т е с т о- -в ы м примером на основе известного математическего результата: +в ы м примером на основе известного математического результата: ∞ ∑ (-1)ⁿ/n² = -π²/12 . n=1 Наконец, отметим, что в данном примере количество повторений цикла су- -щественно зависит от значения переменной E (однако, заранее количество по- +щественно зависит от значения переменной E (однако заранее количество по- вторений цикла нам неизвестно!). - П р и м е р 5. Написать программу для вычисления ⁿ√A , используя ите- ───────────── рационную формулу Ньютона: X(0)=A; X(k+1)=X(k)+(A/X(k)^(n-1)-X(k))/n, k=1,2,... @@ -1412,13 +1320,9 @@ print SQR(12) 3.4641016151377 Ok - - ...Поверил Я алгеброй гармонию. - А.С.Пушкин. Моцарт и Сальери - - + А.Пушкин. Моцарт и Сальери Обратимся теперь к лирике. Вот стихотворение Л.Мартынова (речь в нем идет о девушке): "Кто геометрическое среднее между атомом и Солнцем? @@ -1427,7 +1331,6 @@ слушающая в изумлении эти непонятные слова. Неспособная принять их к сведению,будучи ужасно молодой. Вот ведь,какова ты,нечто среднее между атомом и звездой." - Проверим, прав ли поэт. Масса атома водорода Ма=1.67E-27 кг,масса Солн- ца Mс=1.99E+30 кг.Их произведение найдем в режиме непосредственного выпол- нения команд: print 1.67E-27*1.99E+30 @@ -1444,11 +1347,8 @@ Ок Результат вполне правдоподобен: вес девушки ≈ 58 кг. - - III.5. ПРИМЕРЫ - Бросая в воду камешки, смотри на круги,ими образуемые: иначе твое занятие будет простой забавой. Козьма Прутков @@ -1458,12 +1358,10 @@ удалось решить, либо зависят от них;я рассматриваю их как такое же число сражений, в которых военное сча- стье было на моей стороне. - Рене Декарт - - + Р.Декарт В заключение рассмотрим несколько, на наш взгляд, интересных примеров. Разумеется, некоторые из приведенных ниже программ не являются оптималь- -ными по времени выполнения и по занимаемой памяти. Однако, есть еще одна +ными по времени выполнения и по занимаемой памяти. Однако есть еще одна величина, которую надо принимать в расчет при оптимизации программы. Это - в р е м я программиста. Программа, требующая много времени на написа- ние и отладку,может оказаться очень дорогой, даже если она расходует мень- @@ -1475,7 +1373,6 @@ Если программу предлагается выполнить всего один-два раза, или если ее придется часто модифицировать, метод "скорых, но грязных программ" по- чти всегда дает наилучшие результаты! - П р и м е р 1. Найти наибольший элемент в одномерном массиве A(N), не ───────────── пользуясь оператором IF (!). Ok @@ -1489,7 +1386,6 @@ 28 33 7 32 28 20 Наибольший элемент: 33 Ok - П р и м е р 2. Написать программу, которая для введенной пользователем ───────────── суммы печатает способ выдачи этой суммы наименьшим чис- лом монет (имеются монеты 1,2,3,5,10,15 и 20 копеек). @@ -1510,16 +1406,14 @@ 1 раз 5 коп. 1 раз 15 коп. Оk Ok - Каждая решенная мною задача становилась образцом, который служил впоследствии для решения других задач. - Рене Декарт. Рассуждения о методе + Р.Декарт. Рассуждения о методе ...создается впечатление, что можно построить целый курс программирования, выбирая примеры только из за- дач сортировки. Н.Вирт - П р и м е р 3. Напишите программу,располагающую массив слов на англий- ───────────── ском языке по алфавиту (выполняющую лексикографическое упорядочение) методом о б м е н н о й с о р т и р о в к и (методом "пу- @@ -1558,7 +1452,6 @@ ся от аналогичной процедуры над числовыми переменными. Но компьютеров с подобным кодированием русского алфавита,к сожалению, пока (1990 г.) очень мало! - П р и м е р 4. ───────────── NEW @@ -1568,7 +1461,7 @@ образовать вспомогательный массив индексов, в котором отмечаются прави льные места значений в массиве. 12 'Во время сортировки значения остаются на исходных местах,а изменяе - тся лишь массив индексов. По окончанию сортировки массив индексов испо + тся лишь массив индексов. По окончании сортировки массив индексов испо льзуется для копирования сортируемых значений в новый массив или служи т справочником для работы с исходным массивом. 20 INPUT N:DIM A(N),I(N) @@ -1591,7 +1484,6 @@ ? 6 87 56 34 6 Ok - П р и м е р 5. В массиве X(1),X(2),...,X(N) каждый элемент равен 0,1 ───────────── или 2. Переставьте элементы массива так, чтобы сначала располагались все нули, затем все единицы, и, наконец, все двойки. Допол- @@ -1611,7 +1503,6 @@ Операторы в программных строках 40-60 упорядочивают элементы по возраста- нию (если предыдущий элемент больше последующего,то они меняются местами). Операторы 70-й строки выводят на экран дисплея упорядоченный массив X. - П р и м е р 6. Дан одномерный массив X(1),X(2),...,X(N). Все его эле- ───────────── менты не равные нулю, переписать в начало массива, со- храняя порядок, а нулевые элементы записать в конец массива. Новый массив @@ -1634,7 +1525,6 @@ Идея алгоритма проста! Надо менять местами элемент, равный нулю, и сле- дующий за ним элемент. Подумайте, с какой целью в программе используется цикл с параметром цикла J? - П р и м е р 7. Найти наибольший общий делитель (НОД) одномерного мас- ───────────── сива натуральных чисел A(N). NEW @@ -1661,7 +1551,6 @@ ? 1225 ? 20 25 4 Ok Ok - П р и м е р 8. Даны 5 цифр: 0,1,2,3,4. Найти сумму всех трехзначных чи- ───────────── сел, кратных 3, которые можно записать с помощью этих цифр (цифры могут повторяться). @@ -1673,7 +1562,6 @@ run Искомая сумма= 8937 Ok - П р и м е р 9. Найти количество тех трехзначных чисел, которые равны ───────────── сумме факториалов своих цифр (понятием п о д п р о - г р а м м ы не пользоваться!). @@ -1693,21 +1581,17 @@ Искомые числа: 145 Количество таких чисел: 1 Ok - - - Верочка же, получив письмо (она его ждала раньше, еще в марте), - не сразу,а как-то помедлив,словно боясь чего-то, встала и, взяв - со стола старинный костяной нож с инкрустацией (один перламутро- - вый цветок давно выпал,чернело лишь гнездо на месте,куда он был - вставлен), и вскрыла конверт неловкой рукой. - И.Н.Горелов - - + Верочка же, получив письмо (она его ждала + раньше, еще в марте),не сразу,а как-то по- + медлив,словно боясь чего-то,встала и,взяв + со стола старинный костяной нож с инкрус- + тацией(один перламутровый цветок давно вы- + пал,чернело лишь гнездо на месте, куда он + был вставлен), и вскрыла конверт неловкой + рукой. И.Горелов П р и м е р 10. Найти наименьшее трехзначное число, кратное N, такое, ────────────── что его первая цифра 7 и все его цифры различны. Про- грамму уместить в одну программную строку! - NEW - Ok 5 DEFINTN,I:INPUTN:Y$="Нет":FORI=700TO799:IFI\100<>(IMOD100)\10THENIFI \100<>IMOD100MOD10THENIF(IMOD100)\10<>IMOD100MOD10THENIFIMODN=0THENY$= "Есть!":CLS:PRINTY$,I:ENDELSEIFI=798THENCLS:PRINTY$:ENDELSENEXTELSENEX @@ -1716,7 +1600,6 @@ ? 5 ? 70 ? 18 ? 56 Есть! 705 Нет! Есть! 702 Есть! 728 Ok Ok Ok Ok - П р и м е р 11. Задан одномерный массив A, элементы которого обозна- ────────────── чим A(1), A(2),..., А(N). Найдите длину самой длинной подпоследовательности подряд идущих элементов массива, равных 0. @@ -1738,7 +1621,6 @@ на экран в строке 20). Операторы в программных строках 40-60 подсчитывают максимальное количество подряд идущих нулей в массиве и выводят результат на экран. - П р и м е р 12. Найдите наибольшую по длине неубывающую подпоследова- ────────────── тельность подряд идущих элементов в данной последова- тельности чисел (в одномерном массиве A(N)). @@ -1765,7 +1647,8 @@ Ok П р и м е р 13. Определите, сколько различных элементов встречается в - ────────────── одномерном массиве A(N) более, чем по одному разу. + ────────────── одномерном массиве A(N) более чем по одному разу. + NEW Ok 5 INPUT"Введите N";N:DIM A(N):X=RND(-TIME) @@ -1787,6 +1670,7 @@ П р и м е р 14. Определить количество повторяющихся элементов в одно- ────────────── мерном массиве A(N). + NEW Ok 5 INPUT N:DIM A(N) @@ -1805,12 +1689,9 @@ 3 7 5 6 9 6 9 4 5 0 9 2 7 3 0 0 1 6 2 Ok Ok - П р и м е р 15. Из заданного на плоскости множества точек выбрать три ────────────── такие, не лежащие на одной прямой, которые будут вер- -шинами треугольника: - а) наибольшей площади; - b) наименьшего периметра. +шинами треугольника: а) наибольшей площади; b) наименьшего периметра. NEW Ok 20 DEFINT H,I-K,M:INPUT"Число точек";H:D=RND(-TIME):M=2*H @@ -1840,7 +1721,7 @@ 160 PRINT"Вершины треугольника наим.периметра:(";A1;",";A2;"),(";B1;", ";B2;"),(";C1;",";C2;");" 170 PRINT"Периметр треугольника:";P - 180 FOR I=1 TO 5000:NEXT 'Задержка по времени (≈13 сек)! + 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 @@ -1855,16 +1736,12 @@ 4 ); Периметр треугольника: 110.57946634916 Далее следует графическая иллюстрация полученного решения. - П р и м е р 16. Конечное множество из N точек в трехмерном пространст- ────────────── ве задано своими координатами: (X(N),Y(N),Z(N)), N=1,2,...,n. Составьте программу подсчета количества тех точек данного множества, которые принадлежат: - а) шару x²+y²+z²≤25; - b) полупространству x+y+z≤3; - c) пересечению шара и полупространства; - d) объединению шара и полупространства. - + а) шару x²+y²+z²≤25; c) пересечению шара и полупространства; + b) полупространству x+y+z≤3; d) объединению шара и полупространства. NEW Ok 5 'Идентификация массивов X,Y,Z псевдослучайными целыми числами (прог @@ -1908,7 +1785,6 @@ Количество точек,принадлежащих пересечению шара и полупространства: 1 Количество точек,принадлежащих объединению шара и полупространства: 3 Ok - П р и м е р 17. В заданном двухмерном массиве A(N,M) найти минимальное ────────────── из чисел, встречающееся там более одного раза. NEW @@ -1936,7 +1812,6 @@ ·9··3··9··3 Ок Минимальное число: 0 Ok - П р и м е р 18. Определите, сколько различных элементов в данном двух- ────────────── мерном массиве А(N,M)? NEW @@ -1966,7 +1841,6 @@ ·2··1··8 ·0··4··4··9 Количество разл.элементов:·7 Количество разл.элементов:·8 Ok Ok - П р и м е р 19. Проверьте, есть ли в двухмерном массиве C(M,N) отрица- ────────────── тельные элементы, если есть, найдите среди них тот, у которого сумма индексов будет наименьшей. @@ -1990,7 +1864,6 @@ -5··5·-4··3·-5 ·1··3··4 Искомый отрицат.элемент:-5 Искомый отрицат.элемент:-2 Ok Ok - П р и м е р 20. Операция сглаживания матрицы дает новую матрицу того ────────────── же размера, каждый элемент которой получается как сред- нее арифметическое имеющихся соседей соответствующего элемента исходной @@ -2067,7 +1940,6 @@ ·13 Ok ·7··3··9··8··3 Ok ·27 Ok - П р и м е р 22. Вычислить сумму тех элементов двуxмерного целочислен- ────────────── ного массива A(M,N), в десятичной записи которых ис- пользуются только цифры 0,1,2,3. @@ -2102,7 +1974,6 @@ 3 8 4 8 9 2 Искомая сумма: 25 Ok - П р и м е р 23. Подсчитайте количество элементов двухмерного массива ────────────── A(M,N) натуральных чисел, которые являются составными. NEW @@ -2130,7 +2001,6 @@ он простым? Если "да",то на экран этот элемент выводится со "звездочкой" ("*") позади. Если "нет", то - без нее. Затем подсчитывается количество составных чисел и результат выводится на экран. - П р и м е р 24. Х а р а к т е р и с т и к о й столбца целочисленной ────────────── матрицы назовем сумму модулей ее отрицательных четных элементов. Переставляя столбцы заданной матрицы, расположить их в соответ- @@ -2178,7 +2048,6 @@ Ok Подумайте, каким был бы результат тестового примера, если бы в програм- ме отсутствовал цикл с параметром W (строки 130-180). - П р и м е р 25. Вычисление определенного интеграла от функции,заданной ────────────── на отрезке [-1,1], по квадратурной формуле Гаусса. NEW {{tag> }}