IV.4.1. П р и м е р ы П р и м е р 1. Написать программу, вычисления числа сочетаний из m ───────────── по n по формуле: n m! С = ──────── , (m≥n). m n!(m-n)! Целесообразно разработать подпрограмму вычисления факториала и затем трижды (почему?) обратиться к ней из основной программы. Итак, NEW Ok 40 INPUT "Введите значения m,n";M,N:GOTO 100 ───┐ 50 'Подпрограмма вычисления факториала F! │ 60 F=1:FOR J=1 TO K:F=F*J:NEXTJ │ 90 RETURN 'Конец подпрограммы! │ 100 K=M:GOSUB 60:M1=F ◀──────────────────────┘ 110 K=N:GOSUB 60:N1=F 120 K=M-N:GOSUB 60:R1=F 130 CMN=M1/N1/R1 140 ? "Число сочетаний из М=";M;"по N=";N;"равно";CMN:END run Введите значения m,n? 6,3 Число сочетаний из M= 6 по N= 3 равно 20 Ok Заметим, что оператор GOSUB может оказаться полезным в качестве коман- ды прямого режима. Если Ваша программа состоит из подпрограмм, которые Вы хотите проверить, то, используя команду GOSUB в прямом режиме,можно войти в любую подпрограмму. После выполнения оператора RETURN система MSX-BASIC снова вернется в режим прямого выполнения команд. В примере 1, например, можно проверить работоспособность подпрограммы следующим образом (находясь в прямом режиме!): F=1:k=4:GOSUB 60 Ok print F 24 Ok Ибо это недостойно совершенства человеческого, подобно рабам тратить часы на вычисления. Г.В.Лейбниц П р и м е р 2. Составить программу, которая позволяет методом половин- ───────────── ного деления (дихотомии) на отрезке [A,B] с точностью E определить какой-либо (!) вещественный корень уравнения F(x)=0, где F(x) непрерывна на [A,B] и на концах отрезка принимает значения разных знаков (F(A)·F(B)<0). Пусть, например, x x F(x)=cos e - sin π , A=1, B=3, E=0.00001. NEW Ok 10 INPUT A,B,E 20 X=A:GOSUB 200:F1=Y 30 X=(A+B)/2 40 GOSUB 200:F2=Y:IF Y=0 THEN 90 50 IFSGN(F1)*SGN(F2)>0 THEN 70 60 B=X:GOTO 80 70 A=X:F1=F2 80 IF B-A>E THEN 30 90 PRINTUSING "Корень####.##### точность##^^^^";X,E 100 END 200 Y=COS(EXP(X))-SIN(EXP(X*LOG(3.14159))) 210 RETURN run ? 1,3,.00001 Корень···1.27163·точность·1Е-05 Оk П р и м е р 3. Если у Вас есть знакомый художник, попросите его разде- ───────────── лить произвольный отрезок на две неравные части. Возмож- но он сделает это в золотом отношении, если его чувство меры воспитано на классических образцах. Такое чувство меры целесообразно "внушить" компьютеру, которому часто приходится отыскивать единственную точку минимума некоторой функции y=f(x) на отрезке [a,b]. Основа алгоритма - последовательное приближение к мини- муму до достижения заданной точности E. NEW Ok 10 'Поиск минимума функции y=f(x) на отрезке [a,b] методом золотого се- чения 20 DEFFN Y(X)=-X^2+5: 'Вид функции 30 INPUT"A,B,точность";A,B,E 40 GOSUB 110:GOSUB120 50 IF ABS(B-A)Y2 THEN 70 65 B=X2:X2=X1:Y2=Y1:GOSUB 110:GOTO 80 70 A=X1:X1=X2:Y1=Y2:GOSUB120 '──▶ 80 GOTO 50 90 X=(A+B)/2:PRINT"Y мин=";FNY(X);"при x=";X 100 END 110 X1=.618*A+.382*B:Y1=FNY(X1):RETURN '──▶ 120 X2=.382*A+.618*B:Y2=FNY(X2):RETURN '──▶ run A,B,точность? -1,4 ?? 0.00001 Y мин=-10.999971821564 при x= 3.999996477694 Ok П р и м е р 4. Вычислить π ───────────── 1 ⎧ ┌ sin(10·x)┐6 -·│ │──────────│ dx π ⎭ └ sin(x) ┘ 0 по формуле парабол (формуле Симпсона). Внимание! Интеграл несобственный! NEW Ok 20 INPUT "Нижний предел";А 30 INPUT "Верхний предел";B 40 INPUT "Количество точек";M 70 S=0:H=(B-A)/M 80 S1=0:FOR X=A+H/2 TO B-H/2 STEP H 90 GOSUB 180:S1=S1+Y:NEXT:S1=S1*4 100 S2=0:FOR X=A+H TO B-H STEP H 110 GOSUB 180:S2=S2+Y:NEXT:S2=S2*2 120 X=A:GOSUB 180:S=S+Y 130 X=B:GOSUB 180:S=S+Y 140 S=(S+S1+S2)*H/6 160 PRINT"Интеграл = ";S:END 180 Y=(SIN(10*X)/SIN(X))^6/(4*ATN(1)):RETURN ──▶ run run Нижний предел? 0.00000001 Нижний предел? 0.00000001 Верхний предел? 3.14159265 Верхний предел? 3.14159265 Количество точек? 250 Количество точек? 500 Интеграл = 55251.99567425 Интеграл = 55251.995674258 Ok Ok П р и м е р 5. Написать программу, осуществляющую лексикографическое ───────────── упорядочение (расположение в алфавитном порядке) масси- ва фамилий на русском языке (после фамилий можно указывать инициалы,напри- мер: Бобров А.В.). NEW Ok 10 DATA " ",".","А","Б","В","Г","Д","Е","Ж","З","И","Й","К","Л","М","Н ","О","П","Р","С","Т","У","Ф","Х","Ц","Ч","Ш","Щ","Ы","Ь","Э","Ю","Я" 15 DATA " ",".","-","а","б","в","г","д","е","ж","з","и","й","к","л","м ","н","о","п","р","с","т","у","ф","х","ц","ч","ш","щ","ы","ь","э","ю", "я" 20 INPUT"Введите количество фамилий";S:DIM C$(S) 30 FOR I=1TOS:INPUT"Введите очередную фамилию";C$(I):NEXTI 40 GOSUB 190 50 DIM N(L1,S) 56 FOR I=1 TO S:RESTORE 10:FOR J=1 TO 33:READB$ 57 IF B$=MID$(C$(I),1,1) THEN N(1,I)=J 58 NEXTJ 70 FOR K=2 TO LEN(C$(I))-4 71 IF MID$(C$(I),K-1,1)="-"THEN RESTORE 10 ELSE RESTORE 15 80 FOR J=1 TO 34 90 READ B$:IF B$=MID$(C$(I),K,1) THEN N(K,I)=J 100 NEXT J,K 101 FOR K=LEN(C$(I))-3 TO L1:RESTORE 10 103 FOR J=1 TO 33 105 READ B$:IF B$=MID$(C$(I),K,1) THEN N(K,I)=J 107 NEXT J,K 108 NEXT I 110 FOR K=1 TO L1 120 FOR I=1 TO S-1:FORJ=I+1 TO S 130 IF MID$(C$(I),1,K)=MID$(C$(J),1,K) THEN GOTO 140 ELSE IF(N(K,I)>N( K,J))AND(MID$(C$(I),1,K-1)=MID$(C$(J),1,K-1)) THEN SWAP C$(I),C$(J):FO R L=1 TO L1:SWAP N(L,I),N(L,J):NEXT L 140 NEXT J,I,K 150 CLS 'Очистим экран дисплея! 160 PRINT SPC(10);"Итоговый список" 170 FOR I=1 TO S:PRINT SPC(10);STR$(I);". ";C$(I):NEXTI 180 END 190 L1=0:FOR P=1 TO S:IF LEN(C$(P))>L1THEN L1=LEN(C$(P)) 200 NEXT:RETURN run Введите количество фамилий? 4 Итоговый список Введите очередную фамилию? Ухин И.Н. 1. Лим А. Введите очередную фамилию? Ми-Ка М.У. 2. Ми-Ка М.У. Введите очередную фамилию? Ми-Ша А.А. 3. Ми-Ша А.А. Введите очередную фамилию? Лим А. 4. Ухин И.Н. Ok П р и м е р 6. Абсолютно простым числом назовем натуральное число, об- ───────────── ладающее следующим свойством: при любой перестановке цифр данного числа образуется также простое число. Найдите все абсолютно простые числа, принадлежащие [C,E]. NEW Ok 1 CLS 'Вначале очистим экран! 2 INPUT"Введите два натуральных числа через запятую,причем второе числ о должно быть больше первого (эти числа задают диапазон,в котором ищут ся абсолютно простые числа)";C,E 3 PRINT"Вы хотите узнать всю правду об абсолютно простых числах, лежащ их на отрезке[";C;",";E;"] ? Пожалуйста..." 4 FOR A=C TO E:IF A<10AND(A=1ORA=2ORA=3ORA=5ORA=7)THEN PRINTA;:NEXTA E LSE IF A<10AND(A=4ORA=6ORA=8ORA=9)THEN NEXTA ELSE A$=MID$(STR$(A),2) 5 N=LEN(A$):DIM A(N) 10 FOR L=1TO N:A(L)=VAL(MID$(A$,L,1)):NEXT L:GOSUB 200 20 I=N 30 GOTO 110 40 GOSUB 300:J=N-1 50 IF A(J)>=A(J+1)ANDJ>0 THEN J=J-1:GOTO 50 60 I=J 70 IF I>0 THEN J=N:GOTO 80 ELSE GOTO 110 80 IF A(I)>=A(J) THEN J=J-1:GOTO 80 90 SWAP A(I),A(J):P1=I+1:P2=N 100 IF P10 THEN GOTO 40 120 ERASEA:IF JJ<>1 THEN PRINT A;:NEXT AELSE JJ=0:NEXTA 125 PRINT:PRINT"Надеюсь, Вы остались довольны?!" 130 END 190 'Подпрограмма,производящая сортировку массива A(N),состоящего из ц ифр числа А. 200 FOR M=1 TO N-1:FOR S=M+1 TO N 210 IFA(M)<=A(S)THEN NEXT:NEXTELSESWAP A(M),A(S):NEXT:NEXT 220 RETURN 290 'Подпрограмма,позволяющая определить,является ли число V,составлен ное из цифр числа A, простым. 300 V=0:FOR P=1TON:V=V+A(P)*10^(N-P):NEXT 310 FOR Q=2 TO INT(SQR(V)) 320 IF VMODQ=0 THEN JJ=1:RETURN ELSE NEXT Q:RETURN run Введите два натуральных числа через запятую, причем второе число должн о быть больше первого (эти числа задают диапазон, в котором ищутся абс олютно простые числа)? 1,100 Вы хотите узнать всю правду об абсолютно простых числах,лежащих на отр езке[ 1 , 100 ] ? Пожалуйста... ·1··2··3··5··7··11··13··17··31··37··71··73··79··97 Надеюсь, Вы остались довольны? Ok П р и м е р 7. ───────────── 10'**************************************************** 30'* Программа LONGMULT * 50'* позволяет найти точное значение произведения * 70'* не более чем 210-значных чисел * 81'* Мах. время работы - 1.5 мин. * 83'**************************************************** 90 CLEAR 1000:DIMA(30),C(31,61),D(62),D$(62),B(30),S(62):CC=10000000! 92 DEFFND$(X)=RIGHT$("0000000"+RIGHT$(STR$(X),LEN(STR$(X))-1),7):CLS 100 PRINT"Введите 1-й множитель":PRINT"a=";:GOSUB 150 110 FOR I=1TO N:A(I)=S(1):NEXT:NA=N 120 ?:PRINT"Введите 2-й множитель":PRINT"b=";:GOSUB 150 130 FOR I=1 TO N:B(I)=S(I):NEXT:NB=N:GOSUB 190 135 IF D(1)=0 THEN S=2 ELSE S=1 140 PRINT:PRINT"a*b=";:FOR I=S TO NA+NB:PRINT FND$(D(I));:NEXT 145 PRINT :PRINT:END 150 VV$="" 160 S$=INKEY$:IF S$=""THEN160 ELSE IF S$=CHR$(13) THEN PRINT:GOTO170 E LSE IF ASC (S$)<48 OR ASC(S$)>57 THEN160 ELSE PRINT S$;:VV$=VV$+S$:GOT O160 170 N=LEN(VV$):IFNMOD7=0THEN180 ELSE VV$="0"+VV$: GOTO170 180 N=N/7:FOR I=1 TO N:S(I)=VAL(MID$(VV$,1+(I-1)*7,7)):NEXT:RETURN 190 '∗∗∗ Собственно длинное умножение ∗∗∗ 200 FOR I=NB TO 1 STEP-1:S=0 210 FOR J=NA TO 0 STEP-1 220 C(I,J+I)=S+B(I)*A(J)-INT((S+B(I)*A(J))/CC)*CC:S=INT((S+B(I)*A(J))/ CC):NEXT:NEXT 230 S=0:FORJ=NA+NBTO1 STEP-1:FORI=1TONB:D(J)=D(J)+C(I,J):NEXT:D(J)=D(J )+S:S=INT((D(J)+S)/CC):D(J)=D(J)-INT(D(J)/CC)*CC:NEXT:RETURN run Введите 1-й множитель a=11111111111111111111111111111111111111111111111111111 Введите 2-й множитель b=10000000000000000000000000000000000000000000000000001 a*b= 11111111111111111111111111111111111 11111111111111111211111111111111111 11111111111111111111111111111111111 Ok У попа была собака, он ее любил. Она съела кусок мяса - он ее убил! Убил и закопал, и надпись написал: "У попа была собака, он ее любил. Она съела кусок мяса - ..." Из русского народного фольклора Допустимо использование рекурсивных подпрограмм. Р е к у р с и е й называется обращение подпрограммы (функции) к самой себе непосредственно или посредством других подпрограмм. Такие программы (функции) называются р е к у р с и в н ы м и. Само слово "рекурсия" озна- чает "возвращение" (лат. "recursio"). В программировании различают два типа рекурсии - рекурсивное определе- ние или п р я м у ю рекурсию и рекурсивное использование или к о с - в е н н у ю рекурсию. Рекурсивное использование - это способ описания процесса через подпро- цессы, идентичные основному процессу, а рекурсивное определение - способ описания процесса через самого себя. Рекурсия получается в программах, реализующих алгоритмы, которые содер- жат р е к у р р е н т н ы е формулы, то есть формулы,в которых значение функции от некоторого аргумента X выражается через значение этой же функ- ции, но от другого аргумента Y,который в каком-то смысле "предшествует" X. Рекуррентной является, например,формула вычисления факториала: F(k)= { 1 , если k=1 , { F(k-1)·k, если k>1 . П р и м е р 1. Составим программу вычисления факториала натурального ───────────── числа К, содержащую рекурсивную подпрограмму. NEW Ok 10 INPUT K:F=1:GOSUB 100 '──▶ 30 PRINT F:END 90 'Внимание! Рекурсивная подпрограмма! 100 IF K>1 THEN F=F*K:K=K-1:GOSUB 100 '──▶ 110 RETURN '──▶ run run run run ? 4 ? 6 ? 48 ? 49 24 720 1.2413915592536E+61 Overflow in 100 Ok Ok Ok Ok Конечно, любая рекурсивная подпрограмма может быть написана как цикли- ческая программа. Например,последнюю программу можно переписать следующим образом: 10 INPUT K:F=1 20 IF K>1 THEN F=F*K:K=K-1:GOTO 20 30 PRINT F:END Но многим программистам больше нравится использование рекурсивных под- программ, несмотря на то, что коварство рекурсии проявляется в том,что бы- вает довольно трудно заметить дефект программы или алгоритма,а в цикличес- ком процессе все на виду! П р и м е р 2. Пользуясь рекуррентной формулой ───────────── 0 m n-m+1 m-1 C = 1 ; C = ────── · C ,(∗) n n m n ─── вычислить число сочетаний из n по m при m,n=1,k, k≥1, m≤n. Приведем два варианта программы. a) 10 INPUT K 20 FOR N=0 TO K:C=1:FOR M=1 TO N:IF M>N THEN NEXTN ELSE C=(N-M+1)/M *C:PRINT N;M;FIX(C+.5):NEXT:NEXT run ? 3 ·1··1··1 ·2··2··1 ·3··2··3 ·2··1··2 ·3··1··3 ·3··3··1 b) NEW Ok Ok 5 'Программа находит число сочетаний из N по M по формуле (∗) с при менением рекурсивной подпрограммы. 10 INPUT N,M:C=N:GOSUB100:PRINT FIX(C+.5):END 100 IF M>1THEN C=C*(N-M+1)/M:M=M-1:GOSUB100:RETURN ELSE RETURN run run run далее... Ok ? 232,231 ? 233,232 ? 4080,4079 print m 232 0 ◀── ?! Out of memory in 100 2 Ok Ok Ok Ok П р и м е р 3 [6]. ───────────── NEW Ok 100 INPUT "Строка для сжатия:";FS$ 109 'Удаление пробелов из FS$. 110 S$=FS$:RMV$=" ":GOSUB 200 130 PRINT S$:END 140 '∗∗∗∗ Рекурсивная подпрограмма сжатия строк. ∗∗∗∗ 150 'В RMV$ - удаляемые символы 160 'В S$ - исходная строка и результат 200 IF INSTR(1,S$,RMV$)<>0 THEN S$=LEFT$(S$,INSTR(1,S$,RMV$)-1)+RIGHT $(S$,LEN(S$)-INSTR(1,S$,RMV$)):GOSUB 200 210 RETURN Сравните: NEW Ok 10 INPUT"Строка для сжатия:";A$ 20 FOR I=1 TO LEN(A$):C$=MID$(A$,I,1) 30 IF C$<>" " THEN B$=B$+C$ 40 NEXT:PRINT B$ Существует ограничение на число обращений подпрограммы к себе самой. Оно зависит от нескольких факторов,в частности от количества других вло- женных одна в другую подпрограмм, выполняемых в этот же момент времени, и от размеров рабочего стека. Отметим, что понятие рекурсии охватывает также и весьма интересную си- туацию, при которой первая подпрограмма вызывает вторую, а та в свою оче- редь вызывает первую! IV.5. ОПЕРАТОР ON GOSUB Кроме оператора перехода на подпрограмму в MSX-BASIC есть оператор вы- бора подпрограмм (оператор-"переключатель"). Его общий вид: ON β GOSUB n1,n2,...nk где: ON("на"),GOSUB("to GO to SUBroutine"-"идти к подпрограмме") - служеб- ные слова; β - арифметическое выражение; n1,n2,...,nk - номера начальных строк подпрограмм. Выполнение оператора ON...GOSUB начинается с вычисления целой части значения арифметического выражения β, которую мы обозначим p. Далее, если p ∈ {1,2,...,k}, где k - целое положительное число, то уп- равление переходит к строке np . Если p=0 или p>k, то выполняется оператор, следующий за ON.После выпол- нения соответствующей подпрограммы управление передается оператору, распо- ложенному за ON GOSUB . Если p<0, то компьютер выдает сообщение об ошибке: "Illegal function call". П р и м е р 1. ───────────── NEW Ok 20 INPUT "Ваш выбор (1-3)";CH 27 ON CH GOSUB 31,32,33:END 31 PRINT "1":RETURN'Попадаем сюда, если CH=1 32 PRINT "2"'RETURN'Попадаем сюда, если CH=2 33 PRINT "3"'RETURN'Попадаем сюда, если CH=3 run Ваш выбор (1-3)? 2 2 Ok П р и м е р 2. ───────────── NEW Ok 10 PRINT "Draw,Print,Change,Quit:";:I$=INPUT$(1) 20 ON INSTR(2," DdPpCcQq",I$)/2 GOSUB 100,200,300,400 30 PRINT:GOTO 10 100 PRINT "D":RETURN '──▶ 200 PRINT "P":RETURN '──▶ 300 PRINT "C":RETURN '──▶ 400 PRINT "Q":RETURN '──▶ run Draw,Print,Change,Quit:█ Draw,Print,Change,Quit: ◀── нажата клавиша "а" Draw,Print,Change,Quit:Q ◀── нажата клавиша "q" Draw,Print,Change,Quit:P ◀── нажата клавиша "p" ··· Обратите внимание на примеры из раздела III.3.! В ы в о д ы [8]. При применении подпрограмм BASIC придерживайтесь сле- ─────────────── дующих правил: 1. Четко обозначайте начало и конец каждой подпрограммы. Если это воз- можно, выделяте их путем отступа операторов вправо. 2. Никогда не пользуйтесь оператором GOTO для входа в подпрограмму и для выхода из нее. Каждую подпрограмму надо рассматривать как независимый логически завершенный м о д у л ь . 3. Имейте под рукой список глобальных входных переменных и выходных ре- зультатов каждой подпрограммы. Лучше всего оформить его комментариями к программе с помощью операторов REM . 4. Обязательно убедитесь, что в подпрограмме не изменяются значения та- ких внешних переменных, как счетчики циклов. Если это возможно, в каждой подпрограмме вводите свой принцип именования внутренних переменных. 5. В отличии от функций, подпрограммы не появляются в программе до то- го, как ими будут пользоваться, поэтому полезно группировать подпрограммы вместе после оператора END, указанного в конце основной программы. Д о п о л н е н и е 1 [77]. Программа позволяет умножить два числа, ────────────────────────── причем каждое из них может иметь "л ю - б о е" количество цифр при следующих ограничениях: в произведении должно содержаться не более 765 цифр и длина каждого из чисел должна быть ограни- чена возможной длиной строки. В заключение отметим, что приведенная программа работает неправильно либо когда одно из введенных чисел меньше 10, либо когда их произведение меньше 1000. Безусловно имеет смысл сделать программу "защищенной" в этом отношении! 5 CLEAR 1000 10 DIM A(255),B(255),C(255) 20 T=1000:Z$="000" 30 PRINT"Точное произведение целых чисел" 40 INPUT"Введите первое число: ";A$ 50 LA=LEN(A$):NA=INT((LA-1)/3) 60 FOR I=0 TO NA-1 70 A(I)=VAL(MID$(A$,LA-2-3*I,3)) 80 NEXT I 90 A(NA)=VAL(LEFT$(A$,LA-3*NA)) 100 INPUT"Введите второе число: ";B$ 110 LB=LEN(B$):NB=INT((LB-1)/3) 120 FOR I=0 TO NB-1 130 B(I)=VAL(MID$(B$,LB-2-3*I,3)) 140 NEXT I 150 B(NB)=VAL(LEFT$(B$,LB-3*NB)) 160 NC=NA+NB+1 170 FOR I=0 TO NC:C(I)=0:NEXT I 180 FOR I=0 TO NA 190 FOR J=0 TO NB 200 K=I+J:X=A(I)*B(J)+C(K) 210 Y=INT(X/T):C(K)=X-T*Y 220 IF Y>0 THEN K=K+1:X=Y+C(K):GOTO 210 230 NEXT J 240 NEXT I 250 PRINT "Произведение = "; 260 IF C(NC)=0 THEN NC=NC-1 270 PRINT C(NC) 280 FOR I=NC-1 TO 0 STEP -1 290 PRINT",";RIGHT$(Z$+STR$(C(I)),3); 300 NEXT I 320 END run Точное произведение целых чисел Введите первое число: 12345678 Введите второе число: 987654321 Произведение = 12 ,193,262,222,374,638 Оk print 12345678*987654321 1.2193262222375E+16 Ok run Точное произведение целых чисел Введите первое число: 11111111111111111111 Введите второе число: 6666666666666666666666666666666666666666 Произведение = 74 , 74, 74, 74, 74, 74, 73,333,333,333,33 3,333,333,325,925,925,925,925,925,926 Ok print 11111111111111111111*6666666666666666666666666666666666666666 7.4074074074074E+58 Ok Д о п о л н е н и е 2[90]. Нахождение факториалов "огромных" чисел. ────────────────────────── 10 DIM A(100):PRINT"Введите число N":INPUT N:A(1)=1:J=1 60 FOR I=2 TO N 80 P=0 90 FOR K=1 TO J 100 C=A(K)*I+P:P=INT(C/10):A(K)=C-P*10 130 NEXT K 140 IF P=0 GOTO 200 150 J=J+1 160 IF J>100 THEN PRINT"Не хватает места в массиве":STOP 170 A(J)=P-INT(P/10)*10:P=INT(P/10) 190 GOTO 140 200 NEXT I 210 PRINT STR$(N);"!="; 220 FOR K=J TO 1 STEP -1:PRINT RIGHT$(STR$(A(K)),1);:NEXT K run Введите число N ? 23 23!=25852016738884976640000 Ok run Введите число N ? 50 50!=30414093201713378043612608166064768844377641568960512000000000000 Ok