====== Глава 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> }}