П р и м е р 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 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 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 "Р езультат:";S:PRINT"Контроль: ";-(4*ATN(1))^2/12:PRINT"Количество по вторений цикла:";N-1 'Напомним, что значение π совпадает с 4*ATN(1) run run ? .1 ? .01 Результат:-.86111111111111 Результат:-.81796217561099 Контроль: -.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 и все его цифры различны. Про- грамму уместить в одну программную строку! 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 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; b) полупространству x+y+z≤3; c) пересечению шара и полупространства; 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+J